Les algorithmes génétique

[caroulline]

bonjour
je veux savoir quelque exemple sur l'application de l'algorithme génétique au problème de voyageur de commerce .
j'ai trouver cet exemple
http://perso.ens-lyon.fr/aurelien.pardon/archive/bio_memo.pdf
mais j'ai pas bien compris.
Merci

[fatal_error]

salut,

ce poly sert à rien. Il fait que definir des fonctions, mais ne présente pas comment résoudre le problème.
voilàa comment ca marche.
on se donne n villes avec des coordonnées (x,y). C'est notre map. On connait toutes les distances entre chaque ville.
La fonction d'évaluation, c'est simplement la longueur du circuit.
(ex : si t'as le chemin 1234, la distance, c'est d(1,2)+d(2,3)+d(3,4) et eventuellement d(4,1), ca dépend de la définition du probleme certains disent que le voyageur boucle, d'autres non).

au niveau gen comment ca se passe.
tu prends n circuits (que tu génères, donc tu peux les construire, ou au pif).
ensuite tu fais une sélection dessus.

donc tu regardes wiki, t'as plusieurs selections possibles. Bon, on est des bofs, on fait le plus intuitif.
On classe tous nos circuits en fonction de leur fitness (résultat de la fonction d'évaluation).
En tete de liste, on a le circuit le plus court. En fin de liste, le plus long.
On choisit par exemple les 5 premiers meilleurs.

On fait un crossover. donc on prend deux circuits des cinq meilleurs et on va les croiser. Donc mettons qu'on a
1234
et
2134
un crossover, serait de dire je prends la premiere moitié du premier circuit, et je complète la seconde avec les elem du second. Dans ce cas là, on prend 12, et on complète avec 34 soit 1234.
ce nouveau candidat (circuit), on va le mettre a la place des plus mauvais mettons. donc le plus mauvais on le vire et on met ce nouveau circuit à la place.

Une fois qu'on a "reproduit" nos meilleurs et eliminé nos merdiques, on peut faire muter la population. Donc ici, ca revient à interchanger deux villes avec une faibles proba.
ex : 1234 on run sur chaque indice (1, 2? 3 et 4). Si le random est supérieur à 0.1, par exemple, alors on dit : toi tu mutes. et du coup, on swap l'indice qui doit muter avec un autre indice du circuit.

Ok, une fois qu'on a fait ca, ben on itère. longtemps.
...
très longtemps.

et on trouve une solution merdique.
mais voilà l'idée. Après tu peux être smart et faire des sélections plus fines, optimiser ton cross over (celui que jtai présenté c'est faut le dire, de la merde).