Cette page reprend le mini-site réalisé en 1^ère année à Centrale Nantes dans le cadre du cours d'Organisation des systèmes informatiques et visant à présenter les algorithmes génétiques et leur application possible au pathfinding, dans un cas particulièrement simple. Le site est consultable à l'adresse http://defr.org/genetique/

Un article de l'ECNiouzes de Juin 2005 semble vouloir remettre en cause la théorie de l'évolution de Darwin, arguant de la forte improbabilité de voir apparaître par hasard des fonctions évoluées chez les êtres vivants. Cependant, le calcul de probabilité utilisé est fauss, puisqu'il présume que l'ensemble des mutations doivent se produire simultanément, sur un unique individu.

L'informatique actuelle permettant, par le biais d'algorithmes génétiques, de simuler aisément, en les accelérant, les différents processus intervenant dans la théorie, nous avons décidé d'écrire un programme ludique dans lequel une population de chemins se reproduiraient, et où l'on pourrait observer le résultat du passage du temps sur les générations successives.

Le pathfinding, ou dans la langue de Molière la recherche de chemins est un domaine en plein essor, utilisé par des industries très différentes. Entre autres, on trouve des applications très serieuses en robotique, où l'on cherche un chemin dans l'espace articulaire ( c'est-à-dire l'espace dans lequel les axes représentent les différents degrés de libertés du robot ) pour passer d'une configuration à l'autre, mais aussi une utilisation massive dans l'industrie du jeu video, où il est particulierement utilisé dans le déplacement des différentes unités dans les jeux de stratégie.

C'est un domaine où la recherche est encore active puisque si la résolution systématique est possible dans les cas où la dimension de l'espace de travail est faible (2 ou 3), elle devient nettement plus complexe lorsque l'on s'attaque à des espaces de dimension 6 (cas de la majorité des robots industriels).

• L'article Pathfinding de Wikipedia

La théorie de Darwin est basée sur les idées de mutations et de sélection naturelle. Pour simplifier, dans une espèce, un certain nombre d'individus naissent avec des mutations qui les différencient légerement des autres individus et leur procurent éventuellement un avantage. La sélection naturelle élimine, au bout d'un certain nombre de générations, les individus n'ayant pas acquis un avantage donné. Cette théorie repose entre autres sur deux phénomènes importants ayant lieu lors de la reproduction : la sélection et les mutations.

Dans le cadre de la reproduction sexuée, il y a une sélection du partenaire. Ainsi, on constate chez de nombreuses espèces animales qu'au début de la saison des amours, les mâles s'affrontent, et seul le mâle dominant pourra s'accoupler et transmettre ses gènes aux générations futures.

Cela constitue une des parties de la sélection naturelle.

Lors de la création des gamètes, il peut exister des différences entre l'ADN du parent et le fragment d'ADN que contiennent les gamètes. On peut ainsi constater l'apparition chez les enfants de caractéristiques totalement absentes des parents.

Le rôle du hasard est ici préponderant, puisque seule la probabilité d'un gène à muter peut-être déterminée, sans que l'on puisse dire avec certitude s'il mutera avant d'avoir sous les yeux le résultat final, et on ne peut jamais prédire ce qui résultera de la mutation si jamais elle a lieu.

Dans le cadre de notre projet d'implémentation d'algorithmes génétiques de pathfinding, nous avons été amenés à choisir une modélisation de nos chemins, à laquelle nous pourrions appliquer ces principes généraux. Pour cela, nous avons décidé de modeliser un chemin par la structure :

typedef struct {
		int genes[nbGenes];
		int longueur;
} t_Indiv;

Plus précisement, chacun des gènes du tableau contient un entier, compris entre 0 et 3, qui indique un déplacement de l'individu. Le tableau dans son intégralité constitue donc la suite des déplacements qu'effectuera l'individu en partant du point de départ, et en espérant atteindre le point d'arrivée.

L'entier longueur chiffre quand à lui la performance de l'individu, c'est à dire le nombre de déplacements qu'il doit effectuer pour rejoindre l'arrivée. En conséquence, tous les gènes au delà de cette longueur seront ignorés.

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.

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 seront autorisés à se reproduire.

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.

• Si les deux chemins ne se rencontrent pas, le fils généré sera identique au père.
• Sinon, on recherche le point de rencontre qui optimise le trajet : chemin identique à celui du père du départ jusqu'au point de rencontre, puis chemin identique à celui de la mère du point de rencontre à la fin du chemin maternel.

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.

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.

• main.cxx
• main.h
• types.h

Les paramètres choisis pour la simulation sont les suivants :

• un monde de dimension 20×20
• les points de départ et d'arrivée sont déterminés aleatoirement
• les ancêtres, c'est-à-dire la génération initiale, se voient attribué un programme génétique aleatoire également.

Chacune des générations comporte 100 individus, et l'on fixe la limite temporelle de l'étude à 100 générations. Chaque individu possède 100 gènes.

Il est intéressant de constater que si l'on aurait pu penser, au vu des conditions expériementales, que les mutations n'introduiraient que des individus dégénérés, il n'en est rien. La probabilité de 1% de mutation n'amène en moyenne qu'une mutation par genôme d'individu, mais cela suffit à amelliorer notablement la convergence de l'espèce vers une solution idéale, convergence qui ne se fait en général pas si l'on supprime les mutations.

Quelques exemples

L'aléatoire jouant un grand rôle, on peut constater que si dans la majorité des cas, la convergence vers une solution idéale se fait de facon très rapide (moins de 40 générations), il existe des cas où cette convergence est beaucoup plus lente, même si le parcours à effectuer est en réalité assez court (par exemple du dernier cas du tableau ci-dessus). Il existe de plus des cas où 99 générations ne suffisent pas à obtenir une solution optimale.

C'est pour ces raisons qu'on préfère, lorsque l'on a le choix, utilisé un algorithme déterministes fournissant les solutions: dans ces cas, il est possible d'être tout à la fois assuré tout à la fois d'obtenir la solution, et en plus en maîtrisant le facteur temps. Toutefois, il existe un nombre grandissant de problèmes dans lesquels il n'y a pas unicité de la solution d'une part, et que l'on ne sait pas formellement résoudre d'autres part. Pour ces problèmes, du moment qu'il est possible tout à la fois d'introduire ce que l'on pourrait assimiler à un programme génétique d'une part, et une métrique permettant d'évaluer l'adéquation des différentes hypothèses d'autre part, une approche génétique peut s'avèrer particulièrement intéréssante.