Pathfinding et algorithmes génétiques

Par Franck Deroche et Frédéric Devilliers

Sommaire

Critère de sélection

Les individus chemins sont évalués sur le seul critère du nombre de déplacements qu'ils utilisent pour joindre les points de départ et d'arrivée, c'est-à-dire la longueur du chemin. Si jamais ils n'arrivent pas à l'arrivée une fois tout leur programme exécuté ( ie au bout de nbGenes déplacements ), on pénalise le programme en lui rajoutant la distance qui sépare le point final du chemin de l'arrivée théorique.

Méthode de sélection

A chaque génération, on ne conserve que quelques individus ; plus précisement sur une population de n individus, racine de n éléments seront conservés, les autres condamnés. Les individus sélectionnés se reproduiront.

Méthode de reproduction

Il a été choisi d'étudier une méthode de reproduction sexuée dans le cadre d'individus hermaphrodites. Tout d'abord, les points de rencontre des deux chemins sont déterminés.

On définit de plus la reproduction d'un individu avec lui-même, le fils étant alors identique au père. Cela permet de conserver de façon sûre les meilleurs parents dans la génération suivante.

Mutations

Pour simuler la présence de mutations, juste après la reproduction, l'individu généré subit aléatoirement des mutations. Chaque gène possede une probabilité de 1% de muter, et chacune des mutations modifie le gène concerné en lui additionnant un nombre aléatoire, puis en prenant le résultat de la congruence modulo 4.


Principes