 |
Vie Artificielle
Où la biologie rencontre l'informatique Illustré avec Java |
|
||
 |
Jean-Philippe Rennard
Vuibert, 2002, 432 p. ISBN 2-7117-8694-3 |
|
||
Algorithme génétique : le voyageur de commerce
Le plugin Java étant désormais obsolète vous pouvez :
Téléchargez les sources commentées : pvcag_src.zip (202 ko).
On rappelle au préalable que le problème du voyageur de commerce consiste à trouver le plus court chemin entre un nombre donné de villes. En général le circuit est bouclé ; départ et arrivée sont donc confondus. La complexité du problème croît comme la factorielle du nombre de villes. Si l'on considère des permutations simples, il existe 3 628 000 permutations de 10 villes. Pour 100 villes, on passe à 10 puissance 158. La complexité du problème croît de manière plus que polynomiale (problème dit NP). Cette applet montre ainsi la capacité d'un algorithme génétique à se déplacer au sein d'un immense espace de recherche.
Vérifiez la capacité de l'algorithme à trouver une solution, mais constatez également les difficultés qu'il éprouve à sortir d'un optimum local. Examinez le processus de convergence génétique (grâce à l'écart type), voyez comment y pallier. Etudiez les conséquences d'un taux de mutation trop élevé. D'une manière générale, testez les différents paramètres comme l'opérateur de sélection, le type de crossover ou la taille de la population.
Les algorithmes génétiques sont très présents sur Internet. On peut citer :
Enfin, on trouvera de nombreux liens ici : http://www.rennard.org/alife/french/liens.html#ag
|
|
 |
Le livre est disponible ici :
 |
 |
 |
 |
 |
 |
Pour les droits de traduction en anglais, vous pouvez
consulter :
Sample Chapters and TOC are available in english. For rights
availability please see :
http://www.frontmatter.com/artificial_more.html
Dernière mise à jour : 6 May, 2006