ciel

Le voyageur de commerce

Recherche d'une solution recuit simulé

Un voyageur de commerce doit visiter un ensemble {1,...,d} de villes et revenir chez lui en minimisant la distance parcourue.

Mode d'emploi

Cliquez sur la carte pour positionner les villes, ou bien ouvrez une carte aléatoire ou régulière avec le nombre de villes souhaité et complétez-la ensuite en cliquant. Cliquer sur une ville existante l'efface.
Sélectionnez ensuite une loi de température, le nombre d'itérations à effectuer, et la fréquence d'affichage, puis validez.
Notez qu'il est possible de changer la fréquence d'affichage en cours d'exécution.

Le recuit simulé

Le recuit simulé est un algorithme d'optimisation qui permet de calculer les minima globaux d'une fonction définie sur un ensemble fini.
Le recuit est une technique utilisée en métallurgie qui consiste à faire fondre plusieurs fois un métal puis à le laisser lentement refroidir pour en améliorer les qualités mécaniques.

L'algorithme du recuit simulé est inspiré de cette technique :
- On se donne une suite décroissante de températures {Tn} qui tend vers 0.
- On choisit un chemin X0 au hasard.
- À l'étape n+1, on choisit un chemin y voisin de Xn au sens où on a échangé 2 villes (et on a changé le sens du voyage entre elles).
- On tire ensuite un nombre U au hasard dans [0,1[.
- On accepte la sélection y si U < exp[1/Tn (Longueur(Xn) - Longueur(y))], et dans ce cas Xn+1 = y, sinon on la refuse, et Xn+1 = Xn.

Cet algorithme converge.

Rôle de la température

Le choix du schéma de décroisance est crucial dans cet algorithme car une décroissance trop rapide peut piéger X dans le voisinage d'un minimum local.
Pour vous en convaincre, saisissez une petite carte d'une dizaine de villes, et demandez le calcul immédiat avec 100 000 itérations (la suite est alors stationnaire). Répétez l'opération plusieurs fois avec chaque température, et relevez le résultat. N3 a les plus mauvais résultats, car diminue trop vite. Log N a les meilleurs résultats, mais il lui faut davantage de temps pour converger.


Conforme au standard HTML 4.01 Feuille de style CSS valide Page non-fumeur(c) JM27-08-2002 Me laisser un message Page d'accueil