Métaheuristique - Définition

Variantes

Liste de métaheuristiques

Les métaheuristiques les plus connues sont :

• Les algorithmes évolutionnistes, parmi lesquels :
  • les stratégies d’évolution,
  • les algorithmes génétiques,
  • les algorithmes à évolution différentielle,
  • les algorithmes à estimation de distribution,
  • les systèmes immunitaires artificiels,
  • la recomposition de chemin (Path relinking en anglais)
  • Shuffled Complex Evolution (Duan et al. 1992)
• le recuit simulé,
• les algorithmes de colonies de fourmis,
• Les algorithmes d’optimisation par essaims particulaires,
• la recherche avec tabous,
• la méthode GRASP.

Il existe un très grand nombre d’autres métaheuristiques, plus ou moins connues :

• l’algorithme du kangourou,
• la méthode de Fletcher et Powell,
• la méthode du bruitage,
• la tunnelisation stochastique,
• l’escalade de collines à recommencements aléatoires,
• la méthode de l'entropie croisée,
• etc.

La recherche dans le domaine étant très active, il est impossible de produire une liste exhaustive des différentes métaheuristiques d’optimisation. La littérature spécialisée montre un grand nombre de variantes et d’hybridations entre méthodes, particulièrement dans le cas des algorithmes évolutionnaires.

Historique

• 1952 : premiers travaux sur l’utilisation de méthodes stochastiques pour l’optimisation.
• 1954 : Barricelli effectue les premières simulations du processus d’évolution et les utilise sur des problèmes d’optimisation généraux.
• 1965 : Rechenberg conçoit le premier algorithme utilisant des stratégies d’évolution.
• 1966 : Fogel, Owens et Walsh proposent la programmation évolutionnaire.
• 1970 : Hastings propose l’algorithme de Metropolis-Hastings, permettant d’échantillonner n’importe-quelle distribution de probabilité.
• 1970 : John Horton Conway conçoit le jeu de la vie, l’automate cellulaire le plus connu à ce jour.
• 1975 : travaillant sur les automates cellulaires, Holland propose les premiers algorithmes génétiques.
• 1980 : Smith utilise la programmation génétique.
• 1983 : s’appuyant sur les travaux d’Hastings, Kirkpatrick, Gelatt et Vecchi conçoivent le recuit simulé.
• 1985 : indépendamment de ceux-ci, Černý propose le même algorithme.
• 1986 : La première mention du terme méta-heuristique est faite par Fred Glover, lors de la conception de la recherche tabou :

« La recherche avec tabou peut être vue comme une "méta-heuristique", superposée à une autre heuristique. L'approche vise à éviter les optimums locaux par une stratégie d'interdiction (ou, plus généralement, de pénalisation) de certains mouvements. »

• 1986 : Farmer, Packard et Perelson travaillent sur les systèmes immunitaire artificiels.
• 1988 : la première conférence sur les algorithmes génétiques est organisée à l’université de l’Illinois à Urbana-Champaign.
• 1988 : des travaux sur le comportement collectif des fourmis trouvent une application en intelligence artificielle.
• 1988 : Koza dépose son premier brevet sur la programmation génétique.
• 1989 : Goldberg publie un des livres les plus connus sur les algorithmes génétiques.
• 1989 : Evolver, le premier logiciel d’optimisation par algorithmes génétiques est publié par la société Axcelis.
• 1989 : le terme algorithme mémétique apparait.
• 1991 : Les algorithmes de colonie de fourmis sont proposées par Marco Dorigo, dans sa thèse de doctorat.
• 1993 : le terme « Evolutionary Computation » (calcul évolutionnaire en français) se répand, avec la parution de la revue éponyme, publiée par le Massachusetts Institute of Technology.
• 1995 : Feo et Resende proposent la méthode GRASP (pour Greedy randomized adaptive search procedure, « procédure de recherche gloutonne aléatoire adaptative » en français).
• 1995 : Kennedy et Eberhart conçoivent l’optimisation par essaims particulaires.
• 1996 : Mühlenbein et Paaß proposent les algorithmes à estimation de distribution.
• 1997 : Storn et Price proposent un algorithme à évolution différentielle.
• 1997 : Rubinstein conçoit la méthode de l’entropie croisée.
• 1999 : Boettcher propose l’optimisation extrêmale.
• 2000 : premiers algorithmes génétiques interactifs.

Extensions

Exemple de problème d’optimisation continue, dynamique et bruité.

Les métaheuristiques, de par leur nature flexible, se prêtent particulièrement à des extensions. On peut ainsi trouver des adaptations pour des problèmes plus complexe que l’optimisation mono-objectif :

• problèmes multi-objectifs (plusieurs objectifs contradictoires doivent être optimisés de concert),
• optimisation multi-modale (plusieurs optimums doivent être trouvés),
• optimisation en environnement incertain (un bruit est présent sur la valeur renvoyée par la fonction objectif, ou sur le passage des paramètres à celle-ci),
• hybridations entre métaheuristiques,
• hybridations avec des méthodes exactes,
• problèmes dynamiques (la fonction objectif change durant le temps de l’optimisation),
• gestion de contraintes fortement non-linéaires,
• combinaison des problèmes précédents,
• etc.