Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficiles (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 global d'une fonction), par échantillonnage d’une fonction objectif. Elles se comportent comme des algorithmes de recherche, tentant d’apprendre les caractéristiques d’un problème afin d’en trouver une approximation de la meilleure solution (d'une manière proche des algorithmes d'approximation).
Il existe un grand nombre 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.
Généralités Terminologie
On parle de méta-, du grec , « après » en composition., (), heuristique, du grec , « 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 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 où les algorithmes peuvent regrouper plusieurs heuristiques. On rencontre cette définition 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 (cas du recuit simulé), en biologie 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 est de résoudre un problème d’optimisation donné : elle cherche un objet mathématique (une permutation, un vecteur, 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 de contraintes.
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 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 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 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
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, 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é 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 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).
Les métaheuristiques sont des algorithmes « anytime », capables de proposer une solution (même mauvaise) à chaque itération.
Organisation générale
D’une manière générale, les métaheuristiques s’articulent autour de plusieurs notions : Voisinage ; Diversification/exploration ; Intensification/exploitation ; Mémoire et apprentissage.
Voisinage
Le voisinage d'une solution est un sous-ensemble 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.
La notion de voisinage est sans doute le principe général le plus utilisé pour la conception 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éV. Angel, La rugosité des paysages : une théorie pour la difficulté des problèmes d’optimisation combinatoire relativement aux métaheuristiques, thèse de doctorat de l’université de Paris-Sud, Orsay, 1998.. 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
La diversification (ou exploration, 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é. Lintensification (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 étroite. 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 diversification sont prépondérantes dans la conception des métaheuristiques, qui doivent atteindre un équilibre délicat entre ces deux dynamiques de recherche. 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.
Classification
Parcours et population
Les métaheuristiques les plus classiques sont celles fondées sur la notion de parcours. Dans cette optique, l’algorithme fait évoluer une seule solution sur l’espace de recherche à chaque itération. La notion de voisinage est alors primordiale.
Les plus connues dans cette classe sont le recuit simulé, la recherche avec tabous, la recherche à voisinage variable, la méthode GRASP ou encore les méthode de bruitage. Ces méthodes peuvent être comparées avec la méthode classique du hill-climbing
Dans cette classification, l’autre approche utilise la notion de population. La métaheuristique manipule un ensemble de solutions en parallèle, à chaque itération.
On peut citer les algorithmes génétiques, l’optimisation par essaims particulaires, les algorithmes de colonies de fourmis.
La frontière est parfois floue entre ces deux classes. On peut ainsi considérer qu’un recuit simulé où la température baisse par paliers, a une structure à population. En effet, dans ce cas on manipule un ensemble de points à chaque palier, il s’agit simplement d’une méthode d’échantillonnage particulière.
Emploi de mémoire
Les métaheuristiques utilisent l’historique de leur recherche pour guider l’optimisation aux itérations suivantes.
Dans le cas le plus simple, elles se limitent à considérer l’état de la recherche à une itération donnée pour déterminer la prochaine itération : il s’agit alors d’un processus de décision markovien, et on parlera de méthode sans mémoire. C’est le cas de la plupart des méthodes de recherche locale.
Beaucoup de métaheuristiques utilisent une mémoire plus évoluée, que ce soit à court terme (solutions visitées récemment, par exemple) ou à long terme (mémorisation d’un ensemble de paramètres synthétiques décrivant la recherche).
Fonction objectif statique ou dynamique
La plupart des métaheuristiques utilisent la fonction objectif en l’état, et font évoluer leur comportement de recherche de l’optimum. Cependant, certains algorithmes, comme la recherche locale guidée, modifient la représentation du problème, en incorporant l’information collectée durant la recherche, directement au sein de la fonction objectif.
Il est donc possible de classer les métaheuristiques selon qu’elles utilisent une fonction objectif statique (qui demeure inchangée tout au long de l’optimisation) ou dynamique (quand la fonction objectif est modifiée au cours de la recherche).
Nombre de structures de voisinage
La plupart des métaheuristiques utilisées dans le cadre des problèmes d’optimisation combinatoire utilisent une seule structure de voisinage. Cependant, des méthodes comme la recherche à voisinage variable permettent de changer de structure en cours de recherche.
Implicite, explicite, directe
En considérant les métaheuristiques comme des méthodes itératives utilisant un échantillonnage de la fonction objectif comme base d’apprentissage (définition plus particulièrement adaptée aux métaheuristiques à populations) apparaît le problème du choix de l’échantillonnageJ. Dréo, J.-P. Aumasson, W. Tfaili, P. Siarry, Adaptive Learning Search, a new tool to help comprehending metaheuristics, to appear in the International Journal on Artificial Intelligence Tools..