Compte-Rendu de GECCO 2013

Bon si ça fait deux semaines que j’ai disparu du podcast c’est que je me faisais reporter à GECCO, une conférence dédiée aux algorithmes évolutionnistes, pour Podcast Science… Bon, reporter pas tout à fait, puisque, moment de fierté, je présentais moi aussi mon article (Je me suis d’ailleurs pas mal loupé dans ma présentation mais là n’est pas le sujet).

Mais pour commencer, quand je vous annonce que je me suis rendu à une conférence dédiée aux algorithmes évolutionnaires, j’imagine que nombre d’entre vous se demandent quelles peuvent bien être ces bêtes-à. Eh bien, ce sont des algorithmes s’inspirant de la sélection naturelle, et ce, généralement, pour résoudre des problèmes.

Le principe consiste donc la plupart du temps à générer une population aléatoire de solutions puis à répéter un processus consistant alternativement à sélectionner les meilleures de ces solutions grâce à une fonction de fitness puis à leur faire subir différents type de modifications plus ou moins aléatoire : mutations, crossover

De manière pratique on va retrouver dans ce genre de conférence différentes thématiques :
la présentation d’algorithmes évolutionnaires résolvant tel ou tel problème ;
de l’optimisation ;
l’étude de certaines propriétés et conséquences de la sélection naturelle via des simulations où l’évolution n’est pas pas dirigée (pas de fonction de fitness explicite) ;
Beaucoup de robotique.

De même on retrouve 5 types de contenus :

  • des “keynotes” (c’est à dire des présentations importantes plus longues et souvent plutôt généralistes qui sont donc l’unique événement quant elles ont lieu, histoire de toucher tous les chercheurs présents et qui sont effectuées par des chercheurs reconnus par la communauté scientifique et directement invités par les organisateurs de la conférence) ;
  • des présentations orales (ici de 20 minutes) d’articles sélectionnés pour publication et rassemblées par session thématique – vie artificielle – algos génétiques – Intelligence Artificielle (IA) pour jeux vidéos ;
  • des posters, c’est à dire des travaux qui cette fois-ci ne feront pas l’objet de présentation (ou alors de présentations très courtes) mais seront affichés dans une salle dédiée. Un temps où les auteurs attendront à côté de leur poster, prêts à répondre aux questions du public est généralement prévu ;
  • des workshops (des sessions qui sont là pour présenter des travaux en cours et pas forcément prêt pour être acceptés dans les sessions principales) ;
  • enfin des tutoriaux (là, il s’agit de présenter des travaux plus anciens ayant déjà fait l’objet de publications, bref des cours ou un état de l’art sur un sujet précis, en quelque sorte.)

Je vais donc maintenant essayer de vous proposer une petite sélection de travaux sympathiques que j’ai eu la chance de croiser au cours de cette conférence.

Il y a un certain nombres d’approches intéressantes que je me contenterai de citer, histoire de ne pas trop étendre le dossier.

Pas le temps, donc, de vous parler de développement artificiel, l’idée étant ici de faire évoluer quelque chose capable justement de se développer (en s’adaptent à son environnement) et non de faire évoluer directement des organismes fonctionnels;

Pas trop le temps non plus de vous parler de l’approche épigénétique qui, à mon sens, “contamine” le domaine de la vie artificielle après celui de la biologie, car cela mériterait un podcast entier et que je suis sans doute isolé dans mes points de vues sur le sujet.

En très gros, tout de même, centrer l’approche de l’évolution sur l’épigénétique comme le font certains, c’est pour moi passer de l’approche de Kepler à celle de Tycho Brahé. C’est même un peu comme si un peuple d’extraterrestres voulant étudier le mouvement de nos étoiles arrivait dans notre galaxie et, après avoir pris comme référentiel évident le trou noir se trouvant au centre de la galaxie, découvrait planètes et satellites et s’empressait de vouloir étudier le mouvement des étoiles en prenant comme référentiels leurs satellites. C’est possible mais c’est vraiment se compliquer la vie et l’on a même pas ici l’excuse comme Tycho Brahé de se trouver nous-mêmes sur l’un de ces satellites.
Du coup il me semble qu’il serait plus intéressant de faire – comme certains l’ont plus ou moins fait – émerger de l’épigénétique à partir de simulation plus simples.

Après, tout cela concerne essentiellement les simulations visant à étudier l’évolution; si introduire de l’épigénétique permet de rendre plus rapide des algos dont le but est la recherche ou l’optimisation de solutions, je n’ai évidement rien à y redire.

Et mes maigres connaissances m’amènent d’ailleurs à avoir le même point de vie en biologie : l’intérêt d’une approche épigénétique me semble plus nette en biologie fonctionnelle qu’en biologie évolutionniste.

Petite anecdote au passage sur l’opposition entre biologie fonctionnelle et biologie évolutionniste, je discutais récemment avec un ami qui s’intéresse à ces sujets et il m’avait fait remarquer que cette séparation, proposée initialement par Ernst Mayr était définitivement un truc de biologiste évolutionniste et reviendrait un peu à voir un spécialiste de l’étude des kangourous expliquer que la biologie se découpe en deux catégories : ceux qui étudient les kangourous et ceux qui n’étudient pas les kangourous.

====================================================================

Cette longue introduction pleine de digressions touchant à sa fin je vais commencer à survoler avec vous ce que j’ai pu voir pendant ces 5 jours. Si certains des sujets que je ne vais aborder ici que très rapidement vous intéressent, laissez-nous un petit message et je tâcherai de les développer davantage dans de prochains épisodes de podcast science à la rentrée.

1. (Enhancements to Constrained Novelty Search) Pour commencer une utilisation assez originales des algorithmes évolutionnistes dans le cadre des jeux vidéos. J’ai pu voir un tutoriel sur leur utilisation pour générer des carte de jeux de stratégie en temps réel. Le premier Starcraft plus précisément. La problématique est la suivante : habituellement, une fonction de fitness permet de donner un score à chaque solution, ce qui permet ensuite de classer ces solutions. Mais ici il va être difficile d’évaluer (sans intervention d’un joueur et donc d’une fitness humaine) à quel point ces cartes sont bonnes. Par contre il sera aisé de déterminer si elles sont jouable ou pas jouable du tout.
EMP-TeardropOn peut en effet utiliser des critères assez simple :
Dans un jeux de stratégie en temps réel les joueurs on chacun leur point de départ il est donc nécessaire qu’il en existe au moins deux ;
Il faut aussi qu’il y ait suffisamment de ressources à collecter ;
Enfin, il est nécessaire qu’il existe un passage permettant aux différents joueurs d’atteindre les bases ennemies.
Les chercheurs (Antonios Liapis, Georgios N. Yannakakis & Julian Togelius) ne souhaitent pas ici nécessairement créer la map idéale mais plutôt créer un groupe de cartes. Or si des joueurs utilisent un set de cartes, ils auront envie que celles-ci soient le plus différentes possible les unes des autres.
Les auteurs ont donc opté pour une utilisation de la sélection assez originale : Ils ne sélectionnent pas les cartes sur leur qualité comme on aurait tendance à le faire (et ce qui serait donc ici très compliqué mais aboutirait à obtenir une carte la meilleure possible) mais effectuent leur sélection sur un critère de diversité.

Et pour obtenir à la fois des cartes les plus diverses possibles et un maximum de cartes jouables, ils créent deux groupes :
les cartes jouables ;
et les cartes injouables.
Puis sélectionnent dans chaque catégorie un échantillon le plus divers possible. Cette méthode leur permet de générer les cartes les plus éloignées les unes des autres sans pour autant obtenir une succession complètement aléatoire de cartes généralement injouables.

2. (Combining Fitness-based Search and User Modeling in Evolutionary Robotics)
Une autre tendance consiste à inclure des éléments hétérogènes dans la fonction de fitness.

multimodalFitnessLandscapePetite précision au préalable : vous pouvez vous imaginer les recherches effectuées par un algorithme génétique comme la quête d’un alpiniste aveugle muni d’un altimètre magique lui indiquant la hauteur à laquelle il se trouve sans qu’il ait à utiliser de référentiel. Ce pauvre alpiniste cherche à gravir le toit du monde mais n’a aucune connaissance de la topologie globale du monde. Pour avancer, il essaye de progresser de quelques centaine de mètre dans différentes directions au hasard, relève les différentes altitudes résultant de ses différents parcours, revient au point de départ et choisit finalement celle qui lui permet d’arriver le plus haut. Si on place au pied de l’Everest cette méthode lui suffira peut-être à atteindre le toit du monde.

Mais si vous faites commencez cet alpiniste dans les Alpes, il n’atteindra au mieux que le Mont-Blanc… Et je vous laisse méditer sur ce qui se passera si vous proposez à ce courageux sportif de commencer son périple dans le massif du Jura…

Eh bien pour revenir à nos algorithmes génétiques, le Mt-Blanc et le massif du Jura sont ce que l’on appelle des optimums locaux. Et le rêve des chercheurs s’intéressant aux algorithmes évolutionnistes et de se débarrasser de ces encombrants “amis”.

Petit exemple concret de ce que peut être un optimum local :
Imaginons un robot devant atteindre un point situé à 100 mètres devant lui, la fonction de fitness est ici assez simple : nous évaluons la fitness de notre robot par sa proximité avec l’objectif. Une fois l’algorithme exécuté. Si nous avons 10 robots virtuels nous garderons les 5 robots qui seront les plus proches de l’objectif.

Si il n’y a pas d’obstacle tout est pour le mieux dans le meilleur des mondes… Mais maintenant, que se passe-t-il s’il existe un mur perpendiculaire au segment de droite reliant le robot à son objectif et qu’il faille obligatoirement le contourner…

L’affaire devient plus compliquée, notre robot arrivera aisément jusqu’au mur à force de sélections. Mais imaginons ce mur assez large. Dans ce cas, une fois obtenu un comportement permettant au robot de rejoindre le point de jonction entre le mur et le segment reliant son pont de départ à son objectif, plus aucun autre comportement ne sera sélectionné. En effet, aller un peu plus à gauche ou un peu plus à droite, ce qui permettrait à terme de contourner le mur, semblera éloigner le robot de son objectif…

Nous sommes en haut du massif du Jura, ce qui semble être une progression depuis notre point de départ dans le bassin parisien, mais maintenant plus aucun chemin ne nous faisant pas redescendre n’est susceptible de nous conduire en haut de l’Everest.

Comment faire donc ?

On pourrait utiliser une autre fonction de fitness, par exemple calculer le chemin idéal et mesurer la fitness de notre robot par rapport à son éloignement de ce chemin. C’est une bonne idée quand il est facile de calculer un chemin idéal, et c’est le cas avec cet exemple. Mais dans de nombreux cas, c’est impossible et dans d’autres c’est justement ce chemin idéal que nous cherchons à trouver via un algorithme génétique.

L’idée développée par Josh Bongard & Gregory Hornby consiste à faire intervenir l’utilisateur dans le calcul de la fonction de fitness : quand on arrive à un optimum local, et donc que la fonction de fitness stagne, l’utilisateur indique lui-même quelles solutions il préfère parmi les meilleures. Pour reprendre notre exemple, en réitérant plusieurs fois ce processus, on arrive alors à faire contourner le mur par la droite ou la gauche à notre robot (ou l’on force notre alpiste à prendre un chemin le faisant sortir du massif du jura pour se rapprocher un peu de l’Everest ou du Mt-Blanc).

Vous pouvez voir ici le résultat en vidéo :

S’il existe bien d’autres méthodes pour faire franchir ce mur à notre robot, ces fonction de fitness que l’on pourrait qualifier d’hétérogène pourraient être très utiles dans la résolution de tâches plus complexes.

Par ailleurs si vous avez envie d’expérimenter vous-même ce genre d’expériences, le logiciel utilisé est gratuit et pour peu de suivre les différentes étapes du tutoriel vidéo, ce serait presque un jeu d’enfant

3. (High Resilience in Robotics with a Multi-Objective Evolutionary Algorithm)

Tout cela va me servir de transition pour aller vers un autre sujet celui de la robotique : vous avez peut être entendu parler du “projet Gollem” d’Hod Lipson qui consiste, en gros, à passer le reality gap et à tester dans le monde réel des objet créés dans un univers virtuel via des algorithmes évolutionnistes.
L’une des réalisations les plus impressionnantes, digne de skynet, est ce robot araignée capable de trouver comment se mouvoir même s’il est endommagé.
L’idée est la suivante : on crée un modèle virtuel de notre robot et on obtient un comportement via un algorithme évolutionniste. On charge ce comportement sur le robot physique et on le laisse agir. Si le comportement du robot devient incohérent, celui-ci va commencer par tester ses différents capteurs et effecteurs pour déterminer quelle est sa configuration physique exacte, puis il va relancer un algorithme évolutionniste pour trouver à partir de sa configuration physique et du modèle 3D qui en est déduit comment effectuer efficacement la tâche qu’il doit réaliser. Le résultat est impressionnant et cela donne en quelque sorte des robots capables d’adaptation et d’imagination. Si un jour des robots prennent le contrôle de la planète, je parie sur ce modèle.

hexapodUne équipe française a néanmoins réussi à fortement simplifier le processus. L’une des étapes les plus longues est en effet de tester les différents capteurs et effecteurs, et un groupe de chercheur de l’ISIR, Sylvain Koos, Antoine Cully et Jean-Baptiste Mouret ont en effet tout simplement supprimé cette étape. À la place, ils font évoluer le modèle originel avec toute sa structure, tous ses effecteurs et tous ses capteurs initiaux. Et, pour éviter de se retrouver avec un comportement inutilisable, alternent de nombreuses simulations avec quelques tests de comportement en environnement réel. Résultat : ça marche aussi bien et c’est beaucoup plus rapide !

4. (Ribosomal Robots: Evolved Designs Inspired by Protein Folding)

Je vous parlais précédemment d’Hod Lipson et bien deux membres de son équipe, Sebastian Risi et Daniel Cellucci, ont eux aussi présenté quelques innovations dont des robots pliables… Explication : l’une des problématiques de la vie artificielle façon “robotique” par rapport à la vie artificielle façon “simulation” est que s’il n’est pas coûteux de tester différents comportement sur des robots il est de façon assez évidente, bien plus complexe de tester différentes morphologies dans le monde réel qu’en utilisant des simulations.
Les imprimantes 3D et les robots modulables permettent d’y arriver quelque peu mais cela reste des solutions coûteuses en temps.
L’équipe d’Hod Lipson propose ici d’utiliser des robots “fils de fer”, ceux-ci ont l’avantage d’être pliables et repliables donc réutilisables et assez faciles à configurer par une machine.
Bien sûr, le fil de fer utilisé ici est assez spécial : il n’est pas vraiment en fer et contient des moteur positionnés régulièrement.
Comme c’est assez visuel, je vous conseille d’aller faire un tour sur le site. On arrive à faire évoluer virtuellement comment tordre ces fils de fer pour obtenir le mouvement désiré puis à les imprimer et les plier dans le monde réel et obtenir un robot effectuant l’action désirée.

Et une petite vidéo de la chose :

5. Mais il arrive fréquemment que l’on ait besoin de robots bien plus perfectionnés que ces robots pliables pour effectuer des simulations. Or ces robots coûtent habituellement très cher : de plusieurs centaines d’euros à quelques milliers d’euros l’unité.
IMG_0119On a donc aussi pu voir à GECCO des avancées très pratiques. Vous imaginez que quand la simulation consiste à faire interagir et évoluer simultanément une centaines de robots, le coût devient rapidement un problème. Jean-Marc Montanier et d’autres chercheurs de l’université NTNU à Trondheim ont réussi à construire des robots au coût bien moins élevé (plutôt de l’ordre de la centaine d’Euros, voire moins) en utilisant entre autre des arduinos et une imprimante 3D. Le projet est très jeune mais en plein developpement, avec déjà un premier utilisateur à Paris. Pour ceux que cela intéresse, il y aura une presentation du projet lors du workshop “2nd International Workshop on the Evolution of Physical Systems” à l’ECAL. En attendant vous pouvez vous rendre sur la page du projet régulièrement tenue à jour. Je vous laisse avec une photo et une vidéo pour vous donner envie de vous constituer votre population personnelle de robots intelligents.

ChIRP Box Pushing Demo from Anders Rye on Vimeo.

6. (Evolution of Altruism: Spatial Dispersion and Consumption Strategies) Pour lier davantage la robotique à l’étude de l’évolution telle qu’elle se produit dans le vivant, voici un petit exemple des travaux de Jean Marc Montanier et Nicolas Bredeche. Le système utilisé mEDEA fonctionne sur un principe assez ingénieux. On part d’une population de robots avec des comportements aléatoires et une durée de vie fixée à l’avance. L’énergie est limitée et les robots doivent récolter de la nourriture virtuelle disposée aléatoirement sur l’espace que parcourent les robots. Quand un robot consomme une zone de nourriture, elle disparaît et ne réapparaît qu’après un temps proportionnel à la quantité d’énergie extraite. Par ailleurs, à chaque fois qu’un robot en croise un autre, ils ajoutent leurs génomes respectifs à une liste – personnelle à chaque robot – de génomes récoltés. Quand un robot meurt, son génome est effacé puis remplacé par un nouveau génome choisi aléatoirement parmi ceux qu’il a récolté et après avoir fait muter ce génome. La liste des génomes récoltés est ensuite effacée et con compteur de vie réinitialisé. mEDEA est entre autre souvent utilisé pour effectuer des recherches sur les «common goods» les bien commun et l’altruisme.

Le travail présenté lors de GECCO concerne les liens entre altruisme et éparpillement géographique des robots. Dans un paradigme évolutionniste, il existe un lien direct entre altruisme et proximité génétique (l’altruisme peut s’expliquer par le fait que l’on partage des gènes avec les individus vis-à-vis de qui nous sommes altruistes). De même, il existe des liens entre éparpillement géographique et proximité génétique.
L’idée ici est d’étudier tout cela en utilisant comme mesure de l’altruisme un chiffre inversément proportionnel à la quantité d’énergie qu’un robot va consommer quand il va trouver de la nourriture. La nourriture qu’il va laisser derrière lui, en quelque sorte. S’il consomme tout ce qu’il peut consommer et qu’il maximise la durée avant laquelle la ressource sera à nouveau disponible, il est très égoïste. À l’inverse, s’il ne consomme rien, il est très altruiste.

7. Pour finir je suis aussi allé à un tutoriel sur la théorie des jeux par Marco Tomassini et comme Alan m’a confirmé que le sujet n’avait pas été vraiment abordé dans Podcast Science, je vais vous en proposer un rapide aperçu. Puis sauter directement à des conclusion en zappant un peu les développements.

Les jeux étudié en théorie des jeux le sont généralement car ils représentent des dilemmes plus généraux auxquels nous pouvons être confrontés, je vais ici en présenter 4.

Le classique des classique, d’abord: le dilemme du prisonnier. Un criminel et son complice sont arrêtés. Si personne ne parle, ils sortiront l’un et l’autre de prison. Si seul l’un d’entre eux parle, il sera récompensé d’une prime tandis que son complice écopera d’une peine lourde. Enfin, si l’un et l’autre parlent, il écoperont tous deux d’une peine moyenne. On cherche à étudier ici la coopération ainsi que le problème des “common goods”, des biens communs déjà évoqué plus haut.

Deuxième jeu : main gauche / main droite. J’ai une pièce cachée dans l’une de mes mains et l’objet du jeu est de deviner dans quelle main elle se trouve. Chaque joueur a, ici aussi, deux choix, mais le gain sera toujours le même.

Troisième jeu : le jeu de la poule mouillée. Si tu acceptes de sauter de la falaise je le fais aussi. Ici, si l’un seulement des joueurs se dit capable de sauter de la falaise il gagne la mise. Si personne ne s’en dit capable, personne ne gagne rien. Et si les deux s’en disent capables et bien ils sautent et meurent l’un et l’autre. Ce jeu était entre autre utilisé pour étudier la course à l’armement pendant la guerre froide ^^

Quatrième jeu : la chasse. Ici, il faut partir chasser le cerf ou le lapin. si les deux joueurs vont chasser le lapin, ils se partageront un lapin. Si les deux joueurs partent chasser le cerf il se retrouveront avec un cerf à se partager. Enfin, si l’un part chasser le cerf tandis que l’autre part chasser le lapin celui qui part chasser le cerf rentrera bredouille tandis que le chasseur de lapin aura un lapin.

Maintenant, parlons stratégie. On va considérer qu’il en existe deux types : les stratégies simples et les stratégies complexes. Une stratégie simple serait par exemple de toujours dénoncer son complice dans le jeu du prisonnier. À l’inverse, une stratégie complexe consiste ici à alterner entre deux stratégies simples : faire la poule mouillée une fois sur deux, par exemple. Aujourd’hui on ne va s’intéresser qu’aux stratégie simples.

On va parler d’optimum de Pareto. C’est un état où l’on ne peut améliorer le bien-être d’un individu sans réduire celui d’un autre. C’est la moins mauvaise solution, pas dans le sens où elle nous donne le meilleur bonheur moyen, mais dans le sens ou elle lèse le moins possible celui qui éventuellement reçoit le moins. Dit autrement, les solutions qui ne sont pas des optimums de pareto, sont les solutions qui peuvent être améliorées sans que personne n’y perde. On devrait donc gagner à éliminer ces solutions non-pareto.

Puis parlons d’équilibre de Nash du nom de John Forbes Nash, un mathématicien qui s’est intéressé à la théorie des jeux.
En partant du principe que les jeux soient répétés, Uun équilibre de Nash c’est une position où aucun joueur ne peut modifier seul sa stratégie sans y perdre.

L’intérêt de ces équilibres, c’est que l’on comprend aisément que si l’on branche une simulation évolutionniste là-dessus, ces équilibres de Nash vont être des optimum locaux. Le sommet du Jura. En gros, si tous nos prisonniers virtuels dénoncent leur complice, on n’arrivera jamais à obtenir l’optimum de pareto ou un autre optimum car tous nos prisonniesr vont avoir quelque chose à perdre à dévier de cette stratégie.

Reprenons notre jeu du prisonnier et remplaçons les année de prisons par des points, un prisonnier qui dénonce son petit camarade remportera 20 points tandis que son camarade en perdra 10, si personne ne dénonce personne ils remporteront tous les deux 10 points. Enfin s’ils se dénoncent l’un l’autre, ils ne perdront ni ne gagneront aucun point.

Si les stratégies sont équitablement réparties, la stratégie “toujours dénoncer” devrait donc rapporter 10 points ((20+0 ) : 2), en moyenne, tandis que la stratégie “toujours coopérer” ne rapportera en moyenne aucun point ((10-10) : 2).

En cumulant cette information, ainsi que celle concernant notre équilibre de Nash ici situé à la double dénonciation, on se dit qu’une simulation évolutionniste a toutes les raisons de créer une population de prisonnier égoïstes.

Et en effet, si l’on a une population de joueurs accumulant des points en jouant aléatoirement avec d’autres membres de la population au jeu du prisonnier et si les joueurs accumulant le moins de points imitent régulièrement ceux qui en accumulent le plus, on obtiendra rapidement une population de traîtres se dénonçant perpétuellement mutuellement.

Pourtant, on arrive à avoir des stratégies altruistes en mélangeant simulation évolutionniste et théorie des jeux. Imaginons une grille remplie de personnes jouant au jeu du prisonnier (accumulant gains et pertes avec la succession des parties) avec leurs voisins les plus proches et uniquement avec leurs voisins. Imaginons aussi que, régulièrement, les joueurs avec le moins de points imitent les joueurs qui accumulent le plus de points dans leur entourage. Et bien, dans ce cas, contrairement au cas précédent, nous allons voir des groupes d’individus alltruistes apparaître. Ces groupes, contrairement aux individus altruistes isolés, ne seront pas immédiatement convertis par imitation à l’égoïsme. Or, un groupe d’individus altruiste accumulera les gains tandis qu’un groupe d’individus égoistes accumulera les pertes. Avec le temps, ces groupes altruistes accumuleront plus de “succès” que les individus égoïstes… Les individus égoïstes les imiteront donc et au final, on verra peu à peu ces groupes s’étendre jusqu’à atteindre une population totalement altruiste.

Derniers épisodes