En ce moment, je m'intéressent aux algos mémétiques qui combinent l'approche évolutionnaire avec une recherche locale (hill-climbing). Parait que ca marche bien pour le TSP : http://neo.lcc.uma.es/EAWebSite/SKELETON/MEMETIC/SUIZCTSP.PS.gz(...) (je l'ai pas encore lu). Pour d'autres ref sur les memetics algos : http://neo.lcc.uma.es/EAWebSite/web/Memetic.html(...)
Les algos mémétiques simulent une "évolution culturelle" (avec des opérateurs lamarckiens) au lieu de la classique "évolution naturelle" des algos génétiques.
[^] # Re: liens ?
Posté par Olivier Grisel (site web personnel) . En réponse à la dépêche WIFIledefrance organise un "noderunner" géant en Île de France. Évalué à 4.
http://neo.lcc.uma.es/EAWebSite/SKELETON/MEMETIC/SUIZCTSP.PS.gz(...) (je l'ai pas encore lu). Pour d'autres ref sur les memetics algos :
http://neo.lcc.uma.es/EAWebSite/web/Memetic.html(...)
Les algos mémétiques simulent une "évolution culturelle" (avec des opérateurs lamarckiens) au lieu de la classique "évolution naturelle" des algos génétiques.
Sinon pour en revenir au TSP, l'article de wikipedia présentent différents algos (exactes ou heuristiques) : http://en.wikipedia.org/wiki/Traveling_salesman_problem(...)
Sinon, la page référence concernant la résolution du TSP :
http://www.tsp.gatech.edu/(...)
avec notamment une biblio intéressante :
http://www.tsp.gatech.edu/tspbiblio.html(...)
et une bibliothèque de benckmarks :
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/(...)