Cours des Méthodes de Résolution Exactes Métaheuristiques

Les métaheuristiques sont des méthodes générales d'exploration de l'espace des solutions réalisables, qui peuvent être décrites indépendamment du problème. Les métaheuristiques peuvent parfois donner de très bons résultats ou constituer la seule arme pour attaquer un problème; il est donc nécessaire de les connaître lorsqu'on fait de la recherche opérationnelle. De plus, il est facile de contrôler leur temps d'exécution. Cela dit, leur implémentation dépend d'un certain nombre de paramètres dont les valeurs nécessitent beaucoup d'expérimentations. De plus, ces algorithmes n'ont généralement pas de garantie sur la qualité de la solution trouvée.

Face aux défis posés par les heuristiques dans l'obtention de solutions réalisables de haute qualité pour des problèmes d'optimisation difficiles, les métaheuristiques ont émergé en tant qu'alternatives puissantes. Ces algorithmes sont plus complets et complexes que les heuristiques simples, et ils sont souvent capables de générer des solutions de très haute qualité pour des problèmes provenant des domaines de la recherche opérationnelle ou de l'ingénierie pour lesquels des méthodes efficaces sont inconnues, ou lorsque la résolution du problème nécessite un temps de calcul élevé ou une grande capacité de stockage en mémoire.

Le rapport entre le temps d'exécution et la qualité des solutions trouvées par les métaheuristiques reste généralement très favorable par rapport à d'autres approches de résolution dans la plupart des cas.

La plupart des métaheuristiques utilisent des processus itératifs et aléatoires pour collecter des informations, explorer l'espace de recherche et traiter des problèmes tels que l'explosion combinatoire. Une métaheuristique peut être adaptée à différents types de problèmes, tandis qu'une heuristique est spécifique à un problème donné. De nombreuses métaheuristiques s'inspirent de systèmes naturels dans divers domaines, notamment la biologie (algorithmes évolutionnaires et génétiques), la physique (recuit simulé) et l'éthologie (algorithmes de colonies de fourmis).

La conception de métaheuristiques implique de faciliter le choix d'une méthode appropriée et le réglage des paramètres pour les adapter à un problème spécifique.

Les métaheuristiques peuvent être classées de différentes manières, notamment en fonction de leur utilisation d'une population de solutions ou de la manipulation d'une seule solution à la fois. Les méthodes qui visent à améliorer itérativement une solution sont appelées méthodes de recherche locale ou méthodes de trajectoire. Elles construisent une trajectoire dans l'espace des solutions en cherchant à se rapprocher des solutions optimales. Les exemples les plus connus de ces méthodes incluent la recherche tabou et le recuit simulé. D'autres méthodes, telles que les algorithmes génétiques, l'optimisation par essaim de particules et les algorithmes de colonies de fourmis, travaillent avec une population de solutions.

Le recuit simulé (SA) a été introduit par Kirkpatrick et al. en 1983 et par Cerný en 1985 en tant que méthode de recherche locale visant à éviter les minima locaux. Cette métaheuristique s'inspire d'une technique longtemps utilisée par les métallurgistes, consistant à alterner les cycles de réchauffage (ou de recuit) et de refroidissement lent des métaux pour obtenir un alliage sans défaut. Le recuit simulé repose sur les travaux réalisés par Metropolis et al. en 1953, qui ont permis de décrire l'évolution d'un système en thermodynamique.

Le principe du recuit simulé consiste à parcourir de manière itérative l'espace des solutions. On commence par une solution initiale notée s0, générée de manière aléatoire, à laquelle est associée une énergie initiale E0, ainsi qu'une température initiale T0 généralement élevée. À chaque itération de l'algorithme, une modification élémentaire est apportée à la solution, ce qui entraîne une variation d'énergie ΔE. Si cette variation est négative (c'est-à-dire que la nouvelle solution améliore la fonction objectif et réduit l'énergie du système), la modification est acceptée. Si la nouvelle solution est moins favorable que la précédente, elle est tout de même acceptée avec une probabilité P calculée selon la distribution de Boltzmann suivante :