Le voyageur de commerce (applet Java)

Voici un problème d’optimisation classique : un voyageur de commerce doit passer dans chaque ville d’une contrée, et ce une seule fois. Comment faire pour que le trajet soit le plus court possible ? Une méthode d’énumération exhaustive est exclue : s’il y a N villes, pour la seconde étape de son périple notre voyageur a N-1 possibilités, pour la troisième N-2, etc. Le nombre de combinaisons est donc (N-1) ! . Pour seulement 40 villes, cela fait à peu près 2E46 solutions à tester. En supposant que l’on dispose d’un ordinateur permettant de tester un milliard de solutions par seconde, cela nous prendrait plus de 1E19 fois l’âge de l’univers pour tester toutes les solutions ! Alors qu’un Algorithme Génétique trouvera une très bonne solution en testant seulement quelques milliers de solutions. Ce simple exemple illustre bien la puissance du concept d’évolution naturelle.

L’applet Java ci-dessous illustrant ce problème a été réalisée par deux étudiants de l’EUDIL, alors en 2ème année IMA : Raphaël RAIMBAULT et Laurent DUVAL. A vous de jouer avec ! Grâce à un internaute généreux (J.-P. Neuser), cette applet fonctionne désormais avec Netscape et Internet Explorer.

Cliquez ici pour accéder à l’applet

Mode d’emploi succinct :
 Paramètres de l’algorithme génétique :

• Le nombre d’individus est le nombre de le voyageur qui "recherchent" le plus court chemin.
• Le taux de reproduction est le nombre de nouveaux individus pour 100 dans l’ancienne génération créés par croisement des meilleurs individus.
• La probabilité de mutation d’un individu : nombre compris entre 0 et 1. Il reflète la probabilité d’un individu au sein de la population de pouvoir muter (0 = pas de mutation d’individu).
• La probabilité de mutation d’un gène :nombre compris entre 0 et 1. Il reflète la probabilité d’un gène au sein d’un individu de pouvoir muter (0 = pas de mutation de gène).

 Valeurs liées au résultat affiché :

• Valeur d’adaptation maximum, est la valeur d’adaptation du meilleur individu de la population. La Valeur d’adaptation n’est .ici, pas très représentative
• Distance correspondante, est la distance parcourue par le meilleur voyageur de la population. C’est surtout cette valeur que l’on regarde évoluer.
• Numéro de génération, est le nombre de générations déjà calculées. Lorsque la méthode déterministe est sélectionnée, ce nombre est un équivalent par rapport au nombre d’individus testés.
• Nombre d’individus testés, est le nombre d’individus qui ont été évalués depuis le début du calcul.
• La courbe d’évolution n’est utilisée que par l’algorithme génétique. Elle présente l’évolution sur les générations de la valeur d’adaptation du meilleur individu (en rouge) et de la moyenne des valeurs d’adaptation de la population (en bleu). Ceci permet de se faire une idée sur la rapidité de la convergence de l’algorithme, de la diversité de la population
• Choix de la méthode de calcul, cela permet de résoudre un problème donné par algorithme génétique ou par calcule de toutes les solutions possibles.
• Le meilleur parcours courant est une représentation du placement géographique des villes et du parcours effectué par le meilleur voyageur.

Chapitre suivant