TD/TP : Apprentissage, Evolution Artificielle et
Algorithmes Genetiques

J.D. Zucker jdzucker "chez" gmail "point" com

0- Pendant le cours

Pendant le cours j'utilise cette applet http://www.obitko.com/tutorials/genetic-algorithms/example-function-minimum.php
Chargé aussi le fichier zip td-algogen.zip et lancer le programme MaxofFunction.

Exercices sur les AG:

a) Les hyper-parametres : taux de croisement, mutation et élitisme. Sur ce même modèle, vous pouvez modifier les hyper-paramètres (http://www.obitko.com/tutorials/genetic-algorithms/parameters.php) que sont la probabilité de mutation et de croisement ainsi que le degré d'élitisme. La ligne rouge correspond à la meilleure solution, le bleu à la fitness (performance) moyenne de la population. Modifiez les paramètres et observez le comportement de l'algorithme. Que remarquez-vous ?

b) La fonction objectif. Vous pouvez enfin choisir vous même une fonction et chercher son optimum (http://www.obitko.com/tutorials/genetic-algorithms/example-3d-function.php ).

c) Le type de croisement. Charger la page http://www.obitko.com/tutorials/genetic-algorithms/tsp-example.php . Le bouton "Change View" permet de switcher entre la vue de la meilleure solution et celle de la population. Vous pouvez ajouter ou retirer des villes en cliquant sur le graphe. Essayez différentes valeurs de coefficient de mutation et croisement et notez la différence dans les performances.

d)     L'encodage : c'est l'un des gros problèmes de ces algorithmes. Comparez les approches de codage http://www.obitko.com/tutorials/genetic-algorithms/encoding.php

Pendant le cours j'utilise aussi cette seconde applet  http://alphard.ethz.ch/gerber/approx/default.htm

Exercice sur la PG:

a)     Modifiez les paramètres et observez la convergence de  http://alphard.ethz.ch/gerber/approx/default.html

b)     Dans le même esprit vous pouvez essayer celle-là http://www.urbigene.com/geneticprog/

c)      Experimentez avec la programmation génétique en NetLogo http://www.cs.northwestern.edu/~fjs750/netlogo/final/gpdemo.html 

1- Découverte des notions de mutation, sélection à travers l'analyse de programmes

a)     Ouvrez le modèle http://ccl.northwestern.edu/netlogo/models/run.cgi?GenDriftPglobal.739.442 dont la description est là http://ccl.northwestern.edu/netlogo/models/GenDriftPglobal. Ce modèle décrit des cellules qui au départ ont toutes une couleur aléatoire et qui ensuite choisissent à chaque itération une autre cellule dont ils copient la couleur. Testez le modèle. Que remarquez-vous ? Quelles sont les différences entre ce modèle et celui-là http://ccl.northwestern.edu/netlogo/models/GenDriftTinteract .

b)     Chargez le modèle http://ccl.northwestern.edu/netlogo/models/SimpleGeneticAlgorithm . Quel est l'effet de la taille des populations sur le nombre de générations nécessaire à la résolution du problème. Que se passe-t-il si vous mesurez le temps pris pour résoudre le problème complètement. Quelle est la différence entre reproduction sexuée et asexuée pour résoudre le problème. Que se passe-t-il si le taux de clonage (cloning rate) est 100 ou 0 ? Est-ce que la mutation est bénéfique pour la résolution ? Pouvez-vous trouver le taux de mutation optimal ?

c)      Quel est le problème résolu par cet applet http://www.ads.tuwien.ac.at/raidl/tspga/TSPGA.html ?

d)     Facultatif : Chargez ce modèle http://ccl.northwestern.edu/netlogo/models/ProbLabGenetics et essayez de comprendre ce qu'il fait.

e)     Facultatif : Chargez ce modèle http://alife.co.uk/eosex/ et essayez de comprendre ce qu'il fait.

2- Découvrir les AG et les biomorphs avec l'applet GAV

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 240 (les 40 bits de codage des gènes de base) = 8.8 x 1012 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é.

Allez sur la page de GAV http://www.rennard.org/alife/french/gav.html 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.

3- Codage et Expérimentation avec les AG

Pour cet exercice, bootez de préférence sous Linux (en théorie, tout peut s'effectuer indifféremment sous Linux ou Windows, mais l'exercice nécessitant de lancer java depuis un terminal, Linux sera probablement plus commode que Windows...).

• Créez un répertoire pour ce TP, nommé par exemple TP-genAlgo
• Chargez le fichier tp-algoGen.zip dans votre répertoire TP-genAlgo;
• Décompressez le fichier en question ("unzip tp-algoGen.zip") : vous devriez obtenir (dans le répertoire où vous avez décompressé) 4 fichiers jar "auto-exécutables", et plusieurs fichiers de données.

A Difficulté du choix de la fonction d'évaluation des individus

Pour démarrer, exécutez le fichier demo-GA-labyrExit.jar (double-cliquez dessus, ou bien faire java -jar demo-GA-labyrExit.jar dans un "terminal"). Dans ce problème, un "robot" se déplace dans un labyrinthe (comme dans le TP sur l'apprentissage par renforcement), et s'arrête dès qu'il se cogne contre un mur, revient sur un emplacement qu'il a déjà visité, ou a atteint la sortie. Le but est de trouver un parcours menant à la sortie (marquée par une croix verte). On va donc utiliser une population dans laquelle chaque individu correspond à un ensemble de décisions de direction à prendre (et sera représenté uniquement par sa trajectoire dans le labyrinthe). Vous voyer le lien avec le TP 1 et l'apprentissage par renforcement.

 

 

1. De nombreux types de codages très différents sont envisageables, depuis une succession d'ordres "Droite-Droite-Bas-Gauche-..." jusqu'à la représentation d'une fonction de décision dépendant de ce que le robot "voit" dans son environnement immédiat et de l'historique complet de ses actions et perceptions antérieures. Ici le codage indique au robot quelle direction il doit prendre en fonction de son seul emplacement : comme il y a pour chaque case 4 orientations possibles dans l'absolu (indépendamment des murs) et N cases constituant le labyrinthe, on a adopté comme génome pour chaque individu une séquence de 2*N bits (2 bits par case). Donner un exemple de chromosome.
2. La taille de la population et la probabilité de mutation ont une influence sur l'efficacité de l'algorithme génétique, mais l'intérêt essentiel de cet exemple est de mettre en évidence l'importance et la difficulté du choix de la fonction d'évaluation des individus :

1. une approche simpliste  ("ExitFound") consiste à donner une "note" ne dépendant que du fait que le robot ait atteint ou non la sortie ; l'ennui est qu'alors tous les robots ne trouvant PAS la sortie ont la même note, ce qui fait que l'algorithme génétique se résume alors à une recherche totalement au hasard : pour qu'un algorithme génétique soit efficace, il FAUT une fonction d'évaluation qui augmente "progressivement" à mesure qu'on s'approche de la bonne solution.
2. une fonction d'évaluation qui respecte le critère précédent est par exemple celle consistant à mesurer de quelle distance le robot s'est rapproché de la sortie par rapport à sa position de départ ("MaximizeExitProximity") ; le problème est que l'évolution peut alors avoir tendance à se bloquer sur des étapes intermédiaires de parcours où il est nécessaire de s'éloigner (temporairement) de la sortie.
3. une troisième approche ("MaximizeCellsVisited") peut consister à compter le nombre d'emplacements visités, pour favoriser les robots explorant le labyrinthe par rapport à ceux qui "foncent dans le premier mur qu'ils rencontrent" et à ceux qui se bloquent dans un virage éloignant de la sortie ; mais ceci peut évidemment conduire à trouver des individus qui font une grande boucle dans le labyrinthe au lieu de trouver la sortie.
4. en fin de compte, la fonction d'évaluation la plus efficace pour résoudre ce problème est probablement une sorte de combinaison des trois précédentes (et peut-être d'autres !), telle que "MixedStrategy", qui vous permet de tester les combinaisons linéaires des trois précédentes.

Testez les fonctions d'évaluation présentées ci-dessus et comparez leurs efficacités respectives à faire émerger un individu trouvant la sortie du labyrinthe.

Remarque 1 : On pourra constater que si tout se passe bien, l'algorithme génétique est capable de trouver un chemin jusqu'à la sortie en environ 150 générations (voire moins) de taille égale à environ 200 individus (voire moins), ce qui implique qu'on a réellement testé au maximum 150x200~30000 hypothèses avant de trouver une solution convenable, alors que le cardinal total de l'espace exploré est 2⁹⁸~10³¹ (il y a 2 bits pour chacune des 49 cases, donc 98 bits) : ceci illustre la très grande capacité des algorithmes génétiques à "trouver une aiguille dans une botte de foin"...
 
Remarque 2: cette démonstration reste toutefois à but essentiellement illustratif et pédagogique, puisqu'il existe des algorithmes "classiques" capables de trouver la sortie de tout labyrinthe, et ce de façon plus efficace que les algorithmes génétiques c'est par exemple le cas des algorithmes par renforcement (cf. TP 1).

---

---

---

 

B : Facultatif  Recherche du maximum d'une fonction à une variable (proche de l'exercice vu en cours)

Pour démarrer, exécutez le fichier demo-GA-maxFonc.jar (double-cliquez dessus, ou bien faire java -jar demo-GA-maxFonc.jar dans un "terminal").
NOTE : si le double-clic sur le fichier jar ne fonctionne pas, il suffit, dans l'explorateur de fichier, de faire clic-droit à la souris sur un fichier .jar, d'aller dans l'onglet "Ouvrir avec", puis d'appuyer sur le bouton "Ajouter", et enfin de mettre à l'endroit prévu la commande "java -jar %s" (ceci définira pour la suite l'action que l'ordinateur effectuera quand on double-clique sur un fichier de type .jar).

Dans ce problème, une fonction présentant plusieurs maxima locaux (ce qui rend inapplicables les algorithmes les plus simples de recherche de maximum) est définie sur un certain intervalle et le but est de déterminer à l'aide des algorithmes génétiques l'abscisse du maximum global (sur l'intervalle) de la fonction. On va donc utiliser une population dans laquelle chaque individu correspond à une abscisse située dans l'intervalle (et sera représenté par un trait vertical allant du bas de la fenêtre jusqu'à la valeur de la fonction en ce point).

1. Une des premières questions qui se posent est celle du codage : à quelle séquence de gènes faire correspondre une abscisse de l'intervalle ? On a fait le choix de prendre chaque gène égal à un bit, et de faire correspondre à chaque génome (du type 10011100...) l'abscisse x = xMin + N*(xMax-xMin)/Nmax où N est l'entier dont la représentation binaire est donnée par le génome, et Nmax est le plus grand entier représentable avec le nombre de bits correspondant à taille du génome. Il ne reste donc plus qu'à choisir le nombre de bits constituant le génome de chaque individu.
   Testez diverses valeurs pour cette taille de génome et générez pour chacune plusieurs populations initiales aléatoires en cliquant sur le bouton "(RE-)INITIALISATION", et constatez qu'il faut qu'elle soit suffisamment grande (typiquement >=10) pour qu'assez de valeurs d'abscisse soient atteignables. 
2. Testez ensuite l'impact du nombre d'individus de la population :  si celui-ci est trop petit, il faut beaucoup plus de générations pour atteindre le maximum, car il n'y a pas assez de variété dans la population initiale, et seules les mutations finissent par permettre à l'algorithme de converger.
3. Testez enfin l'influence de la probabilité de mutation : si elle est trop faible, l'algorithme est susceptible de se bloquer dans un maximum local au lieu de converger vers le maximum global. Expliquez

Remarque : cette démonstration a un but uniquement pédagogique et illustratif, puisque vous constaterez que le nombre total d'abscisses testées avant d'atteindre le maximum global (égal au nombre de générations multiplié par la taille de la  population) est généralement tel qu'on aurait un aussi bon résultat en répartissant simplement ce nombre d'abscisses uniformément sur l'intervalle puis en cherchant Max(f(Xi)). L'intérêt des algorithmes génétiques pour la recherche de maximum de fonction n'est en pratique réel que dans le cas d'une fonction à beaucoup de variables, car alors toute exploration systématique de l'espace des n-uplets possibles devient prohibitive, tandis qu'un algorithme génétique peut rester efficace. Malheureusement, la visualisation de la recherche du maximum d'une fonction à n variables est problématique pour n=2, et devient carrément impossible (ou en tout cas incompréhensible) pour n>=3...

C : Facultatif  Importance et difficulté du choix de la fonction d'évaluation des individus

Pour commencer, visualisez l'environnement dans lequel évolue le "robot", et voyez le comportement inefficace du robot quand son "cerveau" neuronal est inadapté :

dans un "terminal", faire java -jar demo-GA-testAnimat.jar ratherStupidBrain.dat, puis appuyez sur le bouton start.

Le but serait que le robot explore l'espace pour y trouver et "manger" la "nourriture" (les F, comme Food, disséminés aléatoirement sur la grille), tout en ne consommant pas le "poison" (les P disposés eux-aussi aléatoirement) s'il vient à passer dessus.

 

Le comportement du robot est déterminé par un petit réseau neuronal totalement bouclé(donc ayant un "état" interne) dont les sorties décident de son action (tourner, avancer, manger) en fonction de ce qu'il perçoit (présence de murs, de nourriture ou de "poison" juste en face, en face à gauche ou en face à droite). Ce réseau, illustré ci-dessus à droite, possède 5 entrées correspondant à 5 "senseurs" locaux (présence ou non de "quelque chose"  là oÃ1 il se trouve et sur les 3 cases adjacentes face/gauche/droite, "odeur" ou non de nourriture) et 10 neurones totalement connectés entre eux, dont 4 servent de sorties déterminant le comportement du robot : une sortie détermine s'il faut avancer, une autre s'il faut pivoter à droite, une troisième s'il faut pivoter à gauche, et la dernière sortie décide si le robot tente de "manger" ce qui serait éventuellement présent là oÃ1 il se trouve. Le réseau contient donc 160 poids de connexions et biais pour lesquels il s'agit de trouver une combinaison de valeurs telle que le comportement résultant du robot soit le plus proche possible de celui recherché (ie trouver et manger tous les F, mais ne manger aucun P).

Il s'agit donc d'un problème d'apprentissage par renforcement, au sens où on n'indiquera pas au réseau quelle décision prendre (donc quelles sorties produire) en fonction de ses entrées, et où ce qu'on cherche à optimiser n'est donc pas une simple erreur entre sorties désirées et sorties obtenues, mais un critère autre, en l'occurence la proportion de F "mangés" (diminuée du nombre de P consommés). On va effectuer cet apprentissage en utilisant des algorithmes génétiques, avec comme fonction d'évaluation ("fitness") la mesure (nbFood-nbPoison)/maxFood, où nbFood et nbPoison sont les quantités respectives de F et P "mangés" et maxFood la quantité totale de F disponibles ; pour que le comportement appris soit "général", cette mesure de fitness est moyennée sur N (=5) simulations du même robot dans des environnements aléatoires différents (seules les positions des F et des P variant), avec à chaque fois une position initiale et orientation initiale aléatoires pour le robot. Le codage employé pour le génome est ici directement la représentation binaire des 160 valeurs des poids et biais (autrement dit, une mutation appliquée correspond à inverser 1 bit de l'encodage IEEE-754 d'un de ces double).

Pour démarrer l'apprentissage par algorithmes génétiques, exécutez le fichier demo-GA-animat.jar (double-cliquez dessus, ou bien faire java -jar demo-GA-animat.jar dans un "terminal").

1. Créez une population initiale.
2. Faire évoluer la population : à chaque génération (ou bien toutes les G générations, si une valeur G est mise dans frequAffich) sont affichées diverses évaluation de la population : moyenne, ecart-type, minimum et enfin et surtout maximum de la fitness. A votre avis, pourquoi l'évaluation du meilleur individu (dernière valeur de chaque ligne) n'est-elle pas strictement croissante, même quand tailleElite>0 ?
3. Poursuivre l'évolution jusqu'à obtenir une génération dont le meilleur individu ait un score > 0.8 (voire même, idéalement, >0.9)
4. Arrêtez alors l'évolution, et sauvegardez le meilleur individu.
5. Testez le comportement de cet indivividu en lançant, dans un terminal la commande suivante :
         java -jar demo-GA-testAnimat.jar evolved-xxgen-blaBla.dat
      où evolved-xxgen-blaBla.dat doit être remplacé par le nom exact du fichier qui a été créé par la sauvegarde du meilleur individu.
6. Compte tenu des exercices précédents de ce TP, et aussi de ce qui a été évoqué (durant les séances consacrées au réseaux neuronaux) sur l'influence des valeurs absolues des poids d'un réseau sur sa "complexité", quelles modifications pourrait-on envisager dans la façon d'utiliser les Algorithmes Génétiques sur ce problème, en vue d'obtenir des résultats encore plus satisfaisants ?

4-Autres ressources

Une applet qui va vous rappelez le premier TP/TD http://www.sambee.co.th/MazeSolver/mazega.htm

Un tutorial sur la programmation génétique http://www.geneticprogramming.com/Tutorial/index.html

FSA-GA Ants	Finite State Automata -- GA Ants	Ants is a program to explore genetic programming and learning. When Ants starts, you'll see a large green "food area" in the center of the screen. Across the top of the screen, will be some "ants" aimlessly milling about. In the title bar is the pro
Genetic Java!!!!	Sample Genetic Algorithm Applet:	This applet is designed to be a tool by which interested people can learn some of the basics of genetic algorithms (GAs) while being able to experiment with a real GA. Users can select values for the GA's search parameters and can modify the paramete
Manna Mouse	Food, Bugs, Evolution	Among interactive artificial life simulations, Manna Mouse is uniquely simple: A creature's genome is only an encoding of its position on the screen. With your Mouse you paint Manna--the reward function. By visualizing the fitness landscape, and you
Travelling Salesman	TSP interactive applet	This program utilises a genetic algorithm to find solutions for the Travelling Salesman Problem. Briefly, a random route is created, mutated offspring routes are produced, and the best of these (in terms of total length of route) is selected as the n
Truck Demo	A GP Interactive Truck Applet	A GP Interactive Truck Applet
Bugs in Delphi	Evolving bugs in Delphi	The program simulates the history and life of a small population of small "bugs" that move according to a simple genetic code
eFloys - Evolving Floys	Floys evolving by Genetic Algorithm	eFloys (evolving Floys), are social, territorial, evolving artificial life creatures, implemented in Java. They belong to the flocking Alife creatures variety, sharing with them the social tendency to stick together, and the lifelike emergent behavio
A Fast TSP Solver	A Fast TSP Solver using GA	This JAVA applet is based on the algorithm proposed in `A Fast TSP Solution using Genetic Algorithm' (Information Processing Society of Japan 46th Nat'l Conv., 1993).
Genetic Algorithms	GA Tutorial	The following is an updated excerpt from my books Genetic Algorithms in C++ (M&T Books, 1995) and Active Visual J++ (Microsoft Press, 1997). Note: This page is long. You may want to print or download it for reading offline.
Optimization by Evolution	A Java TSP applet	TSPbyGA is a Java applet that lets you experiment with optimizing a Traveling Salesman (TSP problem using a genetic algorithm.
GA - Maze Solver	A configurable GA Java maze solver	Maze solver is a configurable genetic algorithm It does not find the optimal path,but usually finds a path to the target.
GA Commercial Software	a general purpose package for Excel	Genetic Algorithm Software Products: GENERATOR a general purpose package for solving a variety of problems. GENERATOR-TFV a financial version of Generator. CHEMSOLVER a version of Generator for solving problems in chemistry. Downloadable Sample Probl
Genetic Algorithms Software	Catalog of GA software (various platforms)	Catalog of GA software (various platforms)
TSP Using EP	TSP Using Evolutionary Programming	This is an applet I decided to write after seeing how evolutionary programming could be used to solve hard problems. This applet works by taking the best city path and multiplying it by the population size. In the process the strings are mutated to
Gamelan GA	Gamelan GA Java Resources	Gamelan GA Java Resources
Echo	GA-oriented ecology system	GA-oriented ecology system
TSP Applet	The travelling salesman problem	The travelling salesman problem
Biomorph	Interactive Biomorph Applet	Interactive Biomorph Applet
Echo	GA-oriented ecology system	Echo is a simulation tool developed to investigate mechanisms which regulate diversity and information-processing in systems comprised of many interacting adaptive agents, or complex adaptive systems (CAS). Echo agents interact via combat, mating and
Memetic Algorithms	Memetic Algorithms' Home Page	Memetic Algorithms is a population-based approach for heuristic search in optimization problems. They have shown that they are orders of magnitude faster than traditional Genetic Algorithms for some problem domains. Basically, they combine local sear