Comparaison de deux algorithmes d’optimisation

Abstract

Les métaheuristiques constituent une classe de méthodes approchées adaptables à un grand nombre de problèmes d’optimisation combinatoire. Mais, si l’on a pu constater leur grande efficacité sur de nombreuses classes de problèmes, il existe en revanche très peu de résultats permettant de comprendre la raison de cette efficacité, et aucune méthode particulière ne peut garantir qu’une métaheuristique sera plus efficace qu’une autre sur n’importe quel problème. Concrètement, certaines métaheuristiques présentent l’avantage d’être simples à mettre en œuvre, comme nous l’avons vu avec le recuit simulé ; d’autres sont plutôt bien adaptées à la résolution de certaines classes de problème, très contraints, comme le système de colonies de fourmis. Dans ce projet nous avons définie quelque algorithme de métaheuristiques et test deux algorithme sur fonction de test et comparai ces algorithme pour trouve le optimisation minimum. La qualité des solutions trouvées par les métaheuristiques dépend de leur paramétrage (il faut éviter que les algorithmes ne convergent trop rapidement vers un optimum local), et de l’équilibre à trouver entre un balayage de tout l’espace des solutions (diversification) et une exploration locale poussée (l’intensification). Le choix d’une bonne représentation, d’un bon voisinage, sont également, nous l’avons dit, des facteurs influençant grandement l’efficacité de la méthode choisie, quelle qu’elle soit. Depuis une dizaine d’années, l’hybridation des métaheuristiques est devenue un enjeu important, à tel point que toutes les différentes métaheuristiques que nous avons examinées, recuit simulé, Tabou, algorithmes génétiques, sont maintenant perçues comme des points de départ au développement de nouveaux algorithmes d’optimisation. Les différentes caractéristiques de ces métaheuristiques (mémoires, listes de candidats, populations d’agents, transformations de la fonction objectif, etc.) sont recomposées entre elles pour former de nouvelles méthodes. [DaGo09]