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.