Métaheuristique - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l'ingénierie ou de l'intelligence artificielle) pour lesquels on ne connaît pas de méthode classique plus efficace.

Les métaheuristiques sont généralement des algorithmes stochastiques itératifs, qui progressent vers un optimum global, c'est-à-dire l'extremum (L'expression « élément extremum » signifie « élément maximum » ou « élément minimum ».) global d'une fonction, par échantillonnage (L'échantillonnage est la sélection d'une partie dans un tout. Il s'agit d'une notion importante en métrologie : lorsqu'on ne peut pas saisir un événement dans son...) d’une fonction objectif. Elles se comportent comme des algorithmes de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche scientifique...), tentant d’apprendre les caractéristiques d’un problème afin d’en trouver une approximation (Une approximation est une représentation grossière c'est-à-dire manquant de précision et d'exactitude, de quelque chose, mais encore assez significative pour être utile. Bien qu'une...) de la meilleure solution (d'une manière proche des algorithmes d'approximation).

Il existe un grand nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de métaheuristiques différentes, allant de la simple recherche locale à des algorithmes complexes de recherche globale. Ces méthodes utilisent cependant un haut niveau d’abstraction, leur permettant d’être adaptées à une large gamme de problèmes différents.

Les métaheuristiques (M) sont souvent des algorithmes utilisant un échantillonnage probabiliste. Elles tentent de trouver l’optimum global (G) d’un problème d’optimisation difficile (avec des discontinuités — D —, par exemple), sans être piégé par les optima locaux (L).

Généralités

Terminologies

On parle de méta, du grec « au-delà » (comprendre ici « à un plus haut niveau »), heuristique, du grec ευρισκειν / heuriskein, qui signifie « trouver ». En effet, ces algorithmes se veulent des méthodes génériques pouvant optimiser une large gamme de problèmes différents, sans nécessiter de changements profonds dans l’algorithme employé.

Une terminologie légèrement différente (En mathématiques, la différente est définie en théorie algébrique des nombres pour mesurer l'éventuel défaut de dualité...) considère que les méta-heuristiques sont une forme d’algorithmes d’optimisation stochastique, hybridés avec une recherche locale. Le terme méta est donc pris au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du ralentissement du...) où les algorithmes peuvent regrouper plusieurs heuristiques. On rencontre cette définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) essentiellement dans la littérature concernant les algorithmes évolutionnaires, où elle est utilisée pour désigner une spécialisation. Dans le cadre de la première terminologie, un algorithme évolutionnaire hybridé avec une recherche locale sera plutôt désigné sous le terme d’algorithme mémétique.

Les métaheuristiques sont souvent inspirées par des systèmes naturels, qu’ils soient pris en physique (La physique (du grec φυσις, la nature) est étymologiquement la « science de la nature ». Dans un sens général et ancien, la...) (cas du recuit simulé), en biologie (La biologie, appelée couramment la « bio », est la science du vivant. Prise au sens large de science du vivant, elle recouvre une partie des sciences naturelles et de l'histoire naturelle...) de l’évolution (cas des algorithmes génétiques) ou encore en éthologie (cas des algorithmes de colonies de fourmis ou de l’optimisation par essaims particulaires).

Nomenclature

Le but d’une métaheuristique (Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines...) est de résoudre un problème d’optimisation donné : elle cherche un objet (De manière générale, le mot objet (du latin objectum, 1361) désigne une entité définie dans un espace à trois dimensions, qui a une fonction précise, et qui peut être désigné par une étiquette verbale. Il est défini par les...) mathématique (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les...) (une permutation (En mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à un changement de l'ordre...), un vecteur (En mathématiques, un vecteur est un élément d'un espace vectoriel, ce qui permet d'effectuer des opérations d'addition et de multiplication par un scalaire. Un n-uplet peut constituer un exemple de...), etc.) minimisant (ou maximisant) une fonction objectif, qui décrit la qualité d’une solution au problème.

L’ensemble des solutions possibles forme l’espace de recherche. L’espace de recherche est au minimum borné, mais peut être également limité par un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) de contraintes.

Exemple de front de Pareto dans un problème nécessitant la minimisation de deux objectifs (f1 et f2). Les points A et B sont « non dominés » alors que le point (Graphie) C n’est optimum pour aucun des objectifs.

Les métaheuristiques manipulent une ou plusieurs solutions, à la recherche de l’optimum, la meilleure solution au problème. Les itérations successives doivent permettre de passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques Brisson (1723-1806) en 1760.) d’une solution de mauvaise qualité à la solution optimale. L’algorithme s’arrête après avoir atteint un critère d’arrêt, consistant généralement en l’atteinte du temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) d’exécution imparti ou en une précision demandée.

Une solution ou un ensemble de solutions est parfois appelé un état, que la métaheuristique fait évoluer via des transitions ou des mouvements. Si une nouvelle solution est construite à partir d’une solution existante, elle est sa voisine. Le choix du voisinage et de la structure de donnée (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) le représentant peut être crucial.

Lorsqu’une solution est associée à une seule valeur, on parle de problème mono-objectif, lorsqu’elle est associée à plusieurs valeurs, de problème multi-objectifs (ou multi-critères). Dans ce dernier cas, on recherche un ensemble de solutions non dominées (le « front de Pareto »), solutions parmi lesquelles on ne peut décider si une solution est meilleure qu’une autre, aucune n’étant systématiquement inférieure aux autres sur tous les objectifs.

Dans certains cas, le but recherché est explicitement de trouver un ensemble d’optimums « satisfaisants ». L’algorithme doit alors trouver l’ensemble des solutions de bonne qualité, sans nécessairement se limiter au seul optimum : on parle de méthodes multimodales.

Concepts généraux

Comportement d’une métaheuristique. Le graphique représente les distributions des valeurs des optimums trouvés (sur un grand nombre d’exécutions) : l’algorithme passe d’une population de solution très dispersée (A) à une population plus centrée sur l’optimum trouvé (B).

Les métaheuristiques ne nécessitent pas de connaissances particulières sur le problème optimisé pour fonctionner, le fait de pouvoir associer une (ou plusieurs) valeurs à une solution est la seule information nécessaire.

En pratique, elles ne devraient être utilisées que sur des problèmes ne pouvant être optimisés par des méthodes mathématiques. Utilisées en lieu et place d’heuristiques spécialisées, elles montrent généralement de moins bonnes performances.

Les métaheuristiques sont souvent employées en optimisation combinatoire (L’optimisation combinatoire est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la...), mais on en rencontre également pour des problèmes continus ou mixtes (problèmes à variables discrètes et continues).

Certaines métaheuristiques sont théoriquement « convergentes » sous certaines conditions. Il est alors garanti que l’optimum global sera trouvé en un temps fini, la probabilité (La probabilité (du latin probabilitas) est une évaluation du caractère probable d'un évènement. En mathématiques, l'étude des probabilités est un sujet de grande importance donnant lieu à de...) de ce faire augmentant asymptotiquement avec le temps. Cette garantie revient à considérer que l’algorithme se comporte au pire comme une recherche aléatoire pure (la probabilité de tenter toutes les solutions tendant vers 1). Cependant, les conditions nécessaires sont rarement vérifiées dans le cadre d’applications réelles. En pratique, la principale condition de convergence (Le terme de convergence est utilisé dans de nombreux domaines :) est de considérer que l’algorithme est ergodique (qu’il peut atteindre n’importe quelle solution à chaque mouvement), mais on se satisfait souvent d’une quasi-ergodicité (si la métaheuristique peut atteindre n’importe quelle solution en un nombre fini de mouvements).

Organisation (Une organisation est) générale

Les trois phases d’une métaheuristique itérative. Les points rouges représentent l’échantillonnage de la fonction objectif (ici à une dimension).

D’une manière générale, les métaheuristiques s’articulent autour (Autour est le nom que la nomenclature aviaire en langue française (mise à jour) donne à 31 espèces d'oiseaux qui, soit appartiennent au genre Accipiter, soit...) de plusieurs notions :

  • Voisinage ;
  • Diversification/exploration ;
  • Intensification/exploitation ;
  • Mémoire (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.) et apprentissage (L’apprentissage est l'acquisition de savoir-faire, c'est-à-dire le processus d’acquisition de pratiques, de connaissances, compétences, d'attitudes ou de valeurs culturelles, par l'observation,...).

Voisinage

Le voisinage d'une solution est un sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi...) de solutions qu'il est possible d'atteindre par une série de transformations données. Par extension on désigne parfois par le terme « voisinage » l'ensemble des transformations considérées.

Un voisinage simple pour le problème du voyageur de commerce sera, par exemple, l'ensemble des solutions qu'il est possible de construire en permutant deux villes dans une solution donnée (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un...).

La notion de voisinage est sans doute le principe général le plus utilisé pour la conceptions d’heuristiques. Pour les problèmes combinatoires, le voisinage a un impact important sur le comportement des métaheuristiques, alors que pour des problèmes continus, la notion même de voisinage est plus difficile à cerner.

Bien qu’il n’existe que très peu de résultats théoriques sur l’adéquation entre un voisinage et un problème discret donné, il peut être possible d’en calculer des indicateurs empiriques, comme la rugosité. Les techniques les plus classiques concernant la définition d’un voisinage tournent autour des notions de permutations, de chaînes d’éjections et d’optimisations partielles.

Intensification, diversification, apprentissage

Les notions d’intensification et de diversifications sont liées à l’utilisation de la fonction objectif et aux processus aléatoires. Combinés avec la notion de mémoire, elles permettent de positionner les différents aspects des métaheuristiques entre eux.

La diversification (ou exploration (L'exploration est le fait de chercher avec l'intention de découvrir quelque chose d'inconnu.), synonyme utilisé presque indifféremment dans la littérature des algorithmes évolutionnaires) désigne les processus visant à récolter de l’information sur le problème optimisé. L'intensification (ou exploitation) vise à utiliser l’information déjà récoltée pour définir et parcourir les zones intéressantes de l’espace de recherche. La mémoire est le support de l’apprentissage, qui permet à l’algorithme de ne tenir compte que des zones où l’optimum global est susceptible de se trouver, évitant ainsi les optima locaux.

Les métaheuristiques progressent de façon itérative, en alternant des phases d’intensification, de diversification et d’apprentissage, ou en mélant ces notions de façon plus étroites. L’état de départ est souvent choisi aléatoirement, l’algorithme se déroulant ensuite jusqu’à ce qu’un critère d’arrêt soit atteint.

Les notions d’intensification et de diversifications sont prépondérantes dans la conception des métaheuristiques, qui doivent atteindre un équilibre délicat entre ces deux dynamiques de recherches. Les deux notions ne sont donc pas contradictoires, mais complémentaires, et il existe de nombreuses stratégies mélant à la fois l’un et l’autre des aspects.

Page générée en 0.011 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique