Vie Artificielle

Genetic Algorithm Viewer 1.0  

Le plugin Java étant désormais obsolète vous pouvez :

• Télécharger l'exécutable Linux Gav.run (rendre le fichier exécutable et lancer par ./NomApp.run)
• Télécharger l'exécutable Windows Gav.exe
• Télécharger le jar Gav.jar (java -jar NomApp.jar)

Lancer GAV

GAV est maintenant présenté dans de très nombreuses Universités à travers le monde en introduction aux algorithmes génétiques.

 GAV est une applet de démonstration du fonctionnement d'un Algorithme Génétique (AG). Elle a pour objectif de montrer la puissance des AG et les principaux mécanismes utilisés, tout en permettant une certaine forme de visualisation du fonctionnement général.

     Le problème posé consiste à retrouver le génome d'un Biomorph donné (pour plus d'informations sur les Biomorphs, voir Biomorph Viewer).

     Un Biomorph est une configuration graphique générée à partir de neufs gènes. Les huit premiers gènes codent chacun une longueur et une direction ; le neuvième code le nombre d'embranchements, leur profondeur. Dans GAV, chacun des gènes est codé sur 5 bits. Les 4 premiers représentent la valeur, le cinquième son signe. Chaque gène peut donc avoir une valeur allant de -15 à +15. En ce qui concerne le gène 9, sa valeur est limitée à l'espace 2-9.

      Il existe donc : 8 (nombre de profondeurs possibles) x 2⁴⁰ (les 40 bits de codage des gènes de base) = 8.8 x 10¹² biomorphs possibles, soit quelque 8 800 milliards de combinaisons. Si nous étions capables de tester 1 000 génomes par seconde, il nous faudrait près de 280 ans pour parcourir l'espace de recherche dans sa totalité.

A- Démarrage rapide

      L'utilisation de GAV est très simple. Au lancement un échantillon de 25 biomorphs est présenté. Il suffit de cliquer sur l'un d'entre eux pour qu'il devienne l'individu recherché. Il est naturellement possible, grâce au bouton de tirage aléatoire de générer un nouvel échantillon.

1- Les boutons :

    De gauche à droite :

1. Tirage d'un nouvel échantillon pour sélection de l'individu à rechercher. Si l'on utilise ce bouton alors qu'une recherche est en cours, celle ci sera relancée sur le même biomorph. Cette option permet de lancer une nouvelle recherche en cas de convergence trop rapide, ou si la population initiale était par trop éloignée de l'objectif.
2. Avance pas à pas de la recherche.
3. Marche/Arrêt : Recherche continue, elle ne s'arrêtera qu'une fois l'objectif atteint.
4. Augmente le nombre d'individus visibles.
5. Ajuste le nombre d'individus visibles à la population.
6. Réduit le nombre d'individus visibles. Ceci est particulièrement utile dans le cas de populations importantes et/ou de recherche d'un biomorph ayant un grand nombre d'embranchements, la vitesse de l'algorithme en sera grandement accrue.
7. Réinitialise les paramètres.
8. About comme son nom l'indique !

2- Les paramètres de base :

1. Population : les AG doivent travailler sur des populations importantes. Dans notre cas, il est possible de lancer une recherche à partir de 8 ou 24 biomorphs, mais alors, le fonctionnement est très particulier. Il est à noter qu'à chaque taille de population est associé un taux de mutation par défaut.
2. Taux de mutation : il sera de 1 divisé par la valeur saisie. Notez à quel point les valeurs par défaut sont élevées quand les populations sont faibles.
3. Vitesse : soit le temps de pause entre deux générations en millisecondes.

3- Les paramètres de fonctionnement :

     De haut en bas :

1. Les 5 boutons radios permettent de fixer la méthode de rééchelonnement des valeurs d'adaptation :
   1. Fenêtrage : Réduit l'ensemble des valeurs pour partir de 0.
   2. Exponentiel : Applique une fonction racine carrée aux valeurs d'adaptation.
   3. Transfo. Linéaire : Réalise une transformation linéaire sur les valeurs.
   4. Linéarisation : Linéarise la distribution des valeurs d'adaptation.
   5. Aucune.
2. Elitiste permet de conserver le meilleur individu de chaque génération. Ce paramètre est essentiel en particulier pour les petites populations.
3. Les 2 boutons radio suivants fixent le type de calcul utilisé. La proximité génétique doit-elle se calculer par rapport au phénotype (en l'occurrence à l'apparence) des biomorphs, ou par rapport à leurs génotypes ? Il est évident que ce dernier cas est théoriquement interdit puisque c'est justement le génotype que nous cherchons. Nous avons toutefois maintenu cette fonction à titre de démonstration.
4. Enfin les 2 derniers boutons permettent de choisir entre une fonction de mutation "améliorée" car travaillant au niveau de l'ensemble du gène et non de chacun des bits. Là encore, ceci est indispensable pour les petites populations.

4- Les éléments d'information :

1. Gen : compteur de génération.
2. Sous les boutons de choix du type de mutation, on trouve 3 fois 9 bandes de couleurs. Celle du haut représente le génome (les 9 gènes) du biomorph recherché, la seconde celle du meilleur individu actuel et la troisième celle du pire.
3. En bas à gauche, se trouvent 2 fois 45 bandes de couleurs. Elles représentent le génome (au niveau des bits) du biomorph recherché et du meilleur individu courant. Le bleu correspond à un bit à 1, le noir à 0. Toutes les 5 bandes, on trouve le bit de signe, jaune pour plus et gris pour moins. Ceci permet de visualiser plus facilement la valeur des gènes.
4. En bas au centre, se trouvent les valeurs d'adaptation du meilleur individu et de la moyenne de la population, exprimées en pourcentage.
5. En vis à vis, se trouvent des jauges exprimant ces mêmes valeurs.

     Lorsque la recherche est stoppée, il est possible de sélectionner un individu quelconque qui s'affichera en bleu. Son génome s'affichera alors sur les secondes lignes des représentations des gènes et des bits.

    Il est également possible par un Ctrl-Click de zoomer sur n'importe quel individu (à l'arrêt seulement), son génome et sa valeur d'adaptation s'afficheront alors.

B- Fonctionnement de GAV

     Le principe est le suivant :

     Au départ, l'algorithme de génération d'un individu étant connu, on dispose de l'image d'un Biomorph. Les seules informations directement mesurables sont les positions des points d'embranchement et leur nombre. L'algorithme de base simule le recueil de ces informations.

    Au lancement de la recherche, GAV calcule la distance entre chacun des biomorphs générés et la cible. Cette distance correspond au degré d'adaptabilité (Fitness). Un tirage de type roue de loterie sélectionne ensuite les candidats à la reproduction en fonction de leur fitness, puis les processus de reproduction, croisement et mutation sont lancés. Par mécanisme de roue de loterie, nous entendons le fait que si un individu représente x % de la fitness totale, il a x % de chance d'être sélectionné à chaque reproduction. Un même individu pouvant être sélectionné deux fois au cours du même cycle, il sera à la fois le père et la mère et, hors mutation, le descendant sera naturellement inchangé.

     Le paramétrage permet de tester l'AG dans des conditions très variées :

1- La population : Les populations possibles vont de 8 à 1599. De fait, les populations inférieures à 500 ne permettent pas un fonctionnement "correct" de l'algorithme. En effet, si vous exécutez la recherche pas-à-pas, vous constaterez que l'algorithme converge très rapidement.

2- Le taux de mutation : A chaque reproduction, le nouveau-né est soumis à un processus de mutation. En cas de succès, un gène est modifié. Le type de modification dépend du mode de mutation sélectionné. Pour les populations faibles, vous constaterez que le taux de mutation est très élevé. L'objectif est de contourner le processus de convergence.

3- Le mode Elitiste : A chaque cycle de reproduction, la population originelle est entièrement remplacée par la génération suivante. Afin d'améliorer l'efficacité de l'AG, il est possible de conserver le meilleur individu à chaque génération. Ceci permet de maintenir dans le pool génétique la meilleure configuration génétique jamais générée.

4- Le type de mutation :  Dans GAV, le génome est constitué d'un ensemble de 45 bits stockés dans un entier long. Le mode de mutation classique consiste à transformer un bit unique. Si la condition de probabilité est remplie, un bit est sélectionné au hasard et change de valeur. Cette méthode remplit pleinement son rôle d'élargissement du pool génétique. Il est toutefois possible de l'améliorer. En effet, l'algorithme de base étant connu, il est possible d'écrire une fonction de mutation agissant au niveau de l'ensemble d'un gène et non plus au niveau du bit. Dans ce cas, la valeur du gène mutant varie de plus ou moins un. En association avec le mode Elitiste, ceci permet à l'algorithme de suivre automatiquement un ensemble d'étapes conduisant à l'objectif.

• 5- Le mode de calcul de l'adaptation :

  5.1- L'image (le phénotype) d'un biomorph contient des informations directement mesurables. Il suffit de mesurer la distance en x et en y entre les points d'embranchement. Pour chaque individu, une table contenant la valeur de ces points est créée. Le nombre d'embranchements est également directement visible et stocké dans cette table. Pour chacun de ces points, l'algorithme cumule les distances pour obtenir le degré d'adaptabilité. Dans ce cas, une différence peut exister entre la solution trouvée et le génome de l'individu recherché : pour les valeurs de gènes égales à 0, le bit de signe est indifférent.

  5.2- A titre de démonstration, nous avons maintenu un autre type de calcul de l'adaptation. Celui-ci travaille au niveau du génome, il compare directement les génomes des différents individus avec l'objectif. Dans ce cas, la recherche correspond au génome exact.

     L'utilisation des différentes méthodes de rééchelonnement (cf. partie 1), permet de constater l'efficacité de ces différentes procédures. Il est à noter que vous pouvez en changer en cours de recherche.

     GAV vous permettra de visualiser le fonctionnement d'un AG et de tester l'incidence de nombreux paramètres. Prenez le temps de faire des essais, voyez à quelle vitesse l'algorithme peut trouver la solution, ou, inversement, son incapacité à sortir d'un optimum local. Ce type d'algorithme est d'application trop générale pour se cantonner à la vie artificielle, nous verrons toutefois avec d'autres applications ou applets, comment les AG peuvent nous permettre de faire évoluer des populations virtuelles très diverses. D'une certaine manière, et pour reprendre le cas de Data, nous ne saurions construire cet androïde ex-nihilo ; en revanche il pourrait être envisageable de le considérer comme le résultat de la longue évolution des androïdes ancestraux.

    Jean-Philippe Rennard.  Avril 2000