Pour pouvoir faire évoluer des stratégies avec des algorythmes génétiques
nous devons les encoder de manière à ce que les algorythmes génétiques
puissent les calculer. Voici donc comment cela fonctionne.
Rappelez vous cet exemple de stratégie avec toutes les situations possibles
décrites ainsi que les actions données pour chaque situation possible.
Ce que nous pouvons maintenant faire et de prendre la liste d'actions...
...Rappelez vous l'ordre de la liste des 243 situations possibles...
Nous pouvons donc maintenant détacher la source des actions
Et rappelez vous que la 1ere action correspond à la 1ere situation
Qui est "Tout est vide", la 2eme action correspond à la 2eme situation
qui est "tout est vide sauf une boite sur la position actuelle".. Et ainsi de suite
Maintenant nous prenons cette liste d'actions
et nous pouvons l'encoder suivant un code numérique.
Je vais donc donner à chaque action son numéro de code
allant de 0 a 6 et encoder cette stratégie en cours
en attribuant un code à chaque action de cette liste
Donc un 0 ici en première position veut dire que
la toute première situation qui est "tout est vide"
correspond à l'action "Va vers le nord".
un 6 ici veut dire que cette 3eme situation, quel qu'elle soit dans notre liste de situation,
correspond à l'action "Va au hasard"...et ainsi de suite.
de cette manière nous avons maintenant une liste de chiffres
qui représente une stratégie déterminée.
Quand Robby cherche à entreprendre une action, il regarde la situation autour de lui
il se rapelle de l'ordre de toutes les situations possibles et se dit, par exemple,
Ho je suis dans la situation 201 ! Il cherche la 201eme donnée de cette liste
se repésente ce qu'est le code de cette action et effectue cette action
Et il recommence encore, encore et encore.
ce sera donc le code de notre stratégie
Vous pouvez donc voir cette stratégie, dans un sens métaphorique, comme l'ADN de Robby.
Ce qui évoluera, c'est cette liste de nombre.
Et bien sur cette liste de nombre a 243 valeurs, donc si on veut envisager
chacune de ces valeurs comme un gêne particulier, on peut dire que Robby a 243 gènes.
Bien sur ce n'est qu'une analogie génétique qui ne prétend pas être exacte
mais est de nature grossièrement conceptuelle.
OK, donc maintenant vient la question :
Combien y a t'il ici de stratégies possibles dans notre représentation ?
Nous aimerions trouver une bonne stratégie
mais la question est combien devront nous en essayer avant de trouver la bonne ?
Ou nous pouvons nous demander combien de stratégies totales possibles
Et bien nous regardons les 243 positions possibles
et dans chaque position il y a 7 actions possibles.
car nous avons les chiffres de 0 à 6 qui peuvent s'appliquer ici.
Donc le nombre total de stratégies possibles est de 7 fois 7 fois 7
pour chaque nombre possible que nous pouvons mettre dans chaque position, 243 fois.
La réponse est donc un surprenant 7 puissance 243
qui est un de ces nombres astronomiques que vous n'avez aucun espoir d'atteindre dans votre vie ni même dans celle de tout l'univers.
C'est un nombre de stratégies que personne ne peut parvenir à essayer
l'objectif ici est donc d'avoir un algorythme génétique
qui cherche intelligemment une bonne stratégie dans ce vaste espace
Nous sommes finalement prets à voir comment utiliser un algorythme génétique pour faire évoluer une stratégie
La première chose que nous allons faire est de créer 200 stratégies aléatoires
Le chiffre 200, je l'ai choisi arbitrairement. cela sera notre population de stratégies de départ avec des chiffres choisis au hasard.
Voici donc la liste générée au hasard, quand je lance le G.A. , je génère 200 individus
Pour chaque individu correspond une stratégie, cette séquence de 243 chiffres entre 0 et 6
On voit bien que tout est aléatoire.
OK, maintenant nous allons calculer la pertinence de chaque statégie
en faisant que Robby utilise cette stratégie pour accomplir une série d'actions
dans son monde rempli de vides ou de boites.
Ce que j'appelerai un environnement est un une configuration particulière de vides et de boites dans son monde
Et nous commencerons en placant les vides et boites de facon aléatoire
Et nous laissons Robby suivre une stratégie particulière entrainant un certain nombre d'actions
Nous calculons ses récompenses moins ses pénalités
et nous recommencons avec un environnement différent, donc une autre configuration de boites
Nous le faisons de nombreuses fois et la pertinence d'une stratégie sera la moyenne des récompenses moins pénalités
Pour tous ces environnement différents.
A ce point nous avons séparément calculé la pertinence de 200 stratégies
et maintenant vient la partie reproductive ou les stratégies s'accouplent pour créer une descendance
grace à une recombinaison sexuelle, entre guillemets bien sur car ce ne sont que des chiffres sur un ordinateur,
avec des mutations aléatoires. Plus les parents sont pertinents plus ils créent de descendance
Nous allons donc choisir 2 parents pertinents, choisis par probabilité, avec les plus pertinents ayant le plus de chances d'être choisis
Je vais maintenant créer une descendance en choisissant quelques parties ici
dans la chaine pour les combiner et la descendance aura alors
Cette premiere partie du parent 1 et cette deuxieme partie du parent 2
OK, donc je fabrique l'enfant en copiant la partie parent 1 et la partie parent 2
L'enfant peut alors etre muté aléatoirement en choisissant une position au hasard et la changer par un chiffre, au hasard, entre 0 et 6
Nous avons donc maintenant notre enfant et nous continuons cela encore et encore
jusqu'à ce que l'on ait une nouvelle génération de descendants.
L'ancienne génération disparait totalement, et nous recommencons à l'étape 2
avec la nouvelle génération, en recommencant sur de nombreuses générations
jusqu'à ce que nous soyons contents des stratégies que le G.A. a trouvé ou jusqu'à ce que nous en ayons assez.
Je remarque que la pertinence maximum d'une stratégie est aux environ de 500
car il y a un total de 100 carrés dans le monde de Robby
et chaque fois que Robby démarre dans une nouvel environnement
il y a environ 50 boites c'est a dire qu'environ la moitié des carrés contiennent une boite
quelquefois plus de 50 quelquefois moins à cause du tirage aléatoire
Chaque boite valant 10 points le nombre maximum de points que Robby peut avoir est donc bien environ 500
Avant de lancer le G.A. je commence avec ma propre stratégie faite main
qui est la plus simple stratégie que je puisse envisager ;
"s'il y a une boite sur la position actuelle ramasse la"
"Sinon, s'il y a une boite sur une position adjacente bouge vers cette position"
"Sinon choisi une direction au hasard"
j'ai donc mis en place une stratégie avec une chaine de 243 valeurs, mais un programme peut aussi le faire.
Robby va donc utiliser cette stratégie pour ramasser des boites
dans différents environnements et je note ses scores moyens dans ces différents environnements
La pertinence moyenne a été de 346 sur environ 500 maximum
OK, pas si mal mais j'ai alors lancé l'algorythme génétique , comme je viens de vous l'expliquer,
et trouver que la moyenne des meilleures pertinences, les plus évoluées, tournaient autour de 486.
Presque parfaites. Donc la question est :
Pourquoi est ce que l'algorythme génétique a de meilleurs résultats que moi ?
Qu'est ce que font ces stratégies pour être bien meilleurs ?
Vous verrez que c'est une question pas si facile a répondre
Je connais la logique qui sous tend ma stratégie
Mais l'algorythme, à la fin de son parcours, génère une chaine de 243 chiffres
et dit voici ma stratégie, celle marche bien avec sa haute pertinence
mais il est difficile pour nous de voir exactement comment elle fonctionne
C'est une sorte d'analogie du génome humain
Vous savez que le génome humain est une séquence
Nous savons quel est cette séquence mais il y a une grande différence entre
connaitre sa séquence et savoir comment il fonctionne
Comment les différents gènes génèrent les différentes fonctions
Pour voir la stratégie de l'algorythme génétique je l'ai dessiné sur un graphe
pour un seul algorythme génétique d'abord, j'ai dessiné les meilleurs pertinences pour une population
donc avec le temps voyons comment les pertinences pour les meilleurs individus s'améliorent
Voici la version que j'ai programmé en langage C. Vous pourrez utiliser la version que j'ai faite pour NetLogo
Mais elle est assez lente alors j'utilise la version en C pour obtenir ce résultat.
On peut donc voir que pour les toutes premières générations la pertinence est très faible
en dessous de 0 donc négatives nous verrons pourquoi bientot.
mais très rapidement les meilleurs individus d'une population
commencent à avoir une pertinence de plus en plus élevée
Nous savons que les individus sont différents à chaque génération
La pertinence reste la meme un moment ici puis saute d'un coup et saute encore
jusqu'à atteindre un autre plateau, un petit saut et un autre plateau
Toutes les petites variations ici sont dues au fait que la pertinence elle même est un peu aléatoire
Car si nous créons les boites de facon aléatoire, elles ont toujours le même nombre
et juste leur disposition varie d'un environnement à l'autre
on a donc différentes pertinences pour les mêmes individus ou différentes générations,
ces variations sont liés aux différentes configurations de boites.