Le problème du voyageur de commerce : le défi des 250 villes

Résultats de Alexandre Aupetit

C'est depuis 1995 que je m'intéresse au problème du voyageur de commerce, par le biais des algorithmes génétiques. Je n'y passais que quelques heures de temps en temps, mais j'ai vite été pris au jeu : quelques modifications des paramètres de l'algorithme génétique ou quelques ligne de code en plus pouvaient avoir un effet surprenant sur l'efficacité de l'algorithme... Je ne pense pas exagérer en disant que la version 0.32 de mon algo (avril 2002) est 1000 fois plus puissante que la version de 1997... Il y a tellement de façons d'aborder le problème ou de trouver des optimisations que cela stimule la créativité. Encore maintenant, j'ai pas mal d'idées d'améliorations.

J'ai d'abord commencé par un programme très simple en Pascal, dans le but d'étudier les algorithmes génétiques. En 1997, je le porte en C dans le cadre d'une formation que j'ai donnée sur ce language. Il est alors capable de trouver le chemin idéal pour 25 villes (voir les sources en C et le tutoriel sur les algos génétiques). Mais il n'y a pas de représentation graphique du résultat ce qui est un peu frustrant. C'est pourquoi j'en fait une version en Delphi (dont j'ai perdu puis reconstitué les sources, qui sont donc disponibles maintenant sous licence libre GPL). Cela me donne envie de tester avec un nombre de villes plus grand. Les résultats ne sont pas très probants... Surtout que l'affichage ralentit le calcul.

Je décide alors de séparer le calcul et l'interface, et de le réécrire en C++, qui a l'avantage d'être portable, car entre temps je suis passé à Linux !

Modifier la description

Configuration matérielle et logicielle

Athlon 1.3 GHz

Fréquence du processeur : 1333 MHz
Système d'exploitation : Linux Mandrake 9.0 kernel 2.4.19

Logiciel

tspgen 0.32

Langage : C++ (gcc 3.2)
Description rapide de l'algorithme : Algo génétique + optimisations

Algorithme :

Mon idée initiale était d'utiliser les algorithmes génétiques. Mais sans utiliser d'informations heuristiques (c'est à dire qui dépendent du problème, par exemple connaître les villes les plus proches), les performances ne sont pas exceptionnelles. Heureusement - et c'est là le grand avantage de l'algorithme génétique - son efficacité reste constante même si on l'associe à d'autres méthodes ! Autrement dit, quand une méthode heuristique arrive à sa limite, l'algo génétique pourra trouver mieux, grâce à sa capacité de combiner deux bonnes solutions pour en faire une meilleure.