Les algorithmes évolutionnaires – CMA-ES

Juste avant le mondial du modélisme 2011, une délégation de l’association Caliban et du biohacklab « la paillasse » (Dearcham, Benjamin, Théotime et moi-même)  est montée dans le Chnord pour participer à une journée d’un stage intensif en « évolution artificielle ». Nous avons été surpris par le niveau requis pour y assister. Il ne s’agissait pas de parler superficiellement de l’évolution artificielle bla bla et tout mais bel et bien de la comprendre pour l’appliquer plus tard. La journée s’est composée de trois séances :

  • TP sur PC sur l’application des algorithmes d’évolution artificielle avec OCTAVE (Anne Auger, Chargée de Recherche, INRIA Saclay – Ile de France, France)
  • Présentation de l’évolution artificielle en robotique (Nicolas Bredeche, LRI, Université Paris Sud 11)
  • Cours sur la théorie des algorithmes évolutionnaires (Kristian Lehre thrash-workshop)

L’objet de cet article est tout de même de présenter et d’expliquer ce qu’est l’évolution artificielle et de montrer des exemples d’utilisation. Il faut tout de suite préciser que ces techniques sont maintenant bien rodées et sont les techniques d’optimisation les plus performantes qui existent.

L’article sera peut-être complété plus tard par des références plus précises.

Le principe de l’optimisation évolutionnaire – Terroir et robotique

Imaginez un grand champ vert en Auvergne. Imaginez des moutons sur ce grand champ. Sur chaque mouton est inscrit deux nombres compris entre 0 et 100, ces nombres étant inscrits dès la naissance et à vie à partir des nombres inscrits sur les parents ajoutés  ou retranchés de 1.

Imaginez maintenant dans ce monde un berger monomaniaque qui souhaite avoir un troupeau dont chaque mouton a deux nombres dont la somme vaut 50 et la différence vaut 10.

Ce berger pourrait résoudre l’équation sur papier, trouver qu’il faut un mouton avec 30 et 20, trouver les deux moutons mâles et femelles qui porte ces chiffres (s’il en trouve), faire se reproduire ce couple et faire un méga méchoui avec les autres.

Une autre méthode plus efficace consiste à laisser faire la nature. Un troupeau initial de 20 moutons va produire 40 agneaux. Pour chaque agneau, on va faire la somme des chiffres, la différence et regarder s’il est loin du compte. On va garder les 20 agneaux les plus proches de la solution et faire un méchoui avec les autres. On va répéter cette opération plusieurs fois (c’est quand même plus sympa qu’un système 2 équations 2 inconnues non ?) et à la fin le troupeau va contenir que des animaux proches de l’idéal. Et tout ceci sans résoudre d’équation !! Juste en laissant faire la nature et en faisant des méchouis… c’est pas beau la vie ?

On voit donc des éléments indispensables au bon fonctionnement de cette technique d’optimisation :

  • Une population d’individus
  • Un moyen de les noter pour les comparer les uns aux autres
  • Un moyen de croiser les individus pour créer de nouveaux individus inédit
  • Une broche… beh oui pour le méchoui.

Cela s’applique ici à des moutons mais bien sûr dans notre cas, on généralise à n’importe quel problème. La plupart du temps, un problème s’exprime par une application numérique. Une application numérique est un processus qui associe à un individu un nombre que l’on appelle coût.

Individu Moyen de calcul du coût
Eleve Note du contrôle de maths
Journée Température maximale pendant la journée
Mouton Somme des nombres sur le mouton
Robot Distance parcourue en 1 minute
Journée Chiffre d’affaire généré lors de la journée

Le but de nombreux problèmes est de trouver l’individu pour lequel le coût est le plus bas. C’est ce que l’on appelle l’optimisation. Dans de nombreux problèmes, l’individu peut être caractérisé par un ensemble de nombres(a,b,c,d,…) (une sorte de code génétique). Ainsi, pour un ensemble de nombres, on associe un coût. Le sujet de l’optimisation est très vaste et les techniques à utiliser sont plus ou moins rapides en fonction des problèmes. Je ne vais pas les rappeler ici et parler principalement des algorithmes évolutionnaires. La principale force de ces algorithmes c’est que leurs temps de convergence est constant quel que soit la complexité du problème. Il faut par contre faire attention aux minimas locaux. Mais un algorithme spécial robuste a été créé et est d’une efficacité redoutable : L’algorithme Covariance Matrix Adaptation Evolutionary Strategy dit « CMA-ES ».

Le CMA-ES en bref

Petit rappel de probabilité

Pour la clarté de l’article je raisonne uniquement avec une population d’individu possédant deux nombres (x,y) comme les moutons. Je peux représenter ainsi chaque individu sur un plan avec un repère par un point. Deux individus seront proches si leur points sont proches.

Je peux tirer aléatoirement de manière uniforme un troupeau d’individus sur ce plan. C’est-à-dire que je n’ai pas de préférence pour un coin du plan par rapport à un autre.

Je peux aussi tirer aléatoirement mes points autour d’une position appelée moyenne (Xm,Ym). Plus je m’éloigne de ce point plus il sera rare d’en trouver un. Cette manière de distribuer les points s’appelle une distribution Normale. Elle est caractérisée par sa moyenne (le point central) et sa « matrice de covariance ». La matrice de covariance définie à la fois le rayon de la distribution, son élongation (ovale) et la direction de ses axes (inclinée). L’ellipse ci-dessous est disposée de manière à contenir 95% des points.

L’algorithme CMA-ES – le Kirby de l’optimisation

Cet algorithme consiste à partir d’une population initiale tirée de manière Normale avec une moyenne et une matrice de covariance initiale. Chaque individu va être noté par l’intermédiaire de son coût. L’algorithme CMA-ES va utiliser ses notes pour élaborer une nouvelle moyenne et une nouvelle matrice de covariance pour avoir dans cette future population un maximum de « bons » individus. Et l’opération se poursuit jusqu’à ce que le rayon atteigne une taille assez petite (la précision que l’on souhaite). Nous obtenons donc une sorte de « savon gluant qui glisse et ce rétrécit vers la solution.

Voici différentes vidéos de l’algorithme en jeu sur différentes fonctions à optimiser (plus c’est rouge, plus c’est profond).

[youtube]http://www.youtube.com/watch?v=PdIB4upIdoM[/youtube]

On voit l’ellipse explorer l’espace pour s’affiner d’elle-même et plonger vers le minimum qui n’est pas forcément super clair sur ces fonctions. Il faut dire que la plupart de ces fonctions mettent en échec d’autres techniques classiques d’optimisation.

On y voit aussi le dernier cas qui montre la puissance de la méthode. On voit l’ellipse qui se coince dans un endroit, on a l’impression qu’il a convergé mais l’ellipse va s’agrandir pou « innover », tester un truc et finalement trouver mieux ailleurs pour s’y blottir.

Il faut connaitre les avantages et inconvénients de cette méthode d’optimisation :

  • Inconvénients :
    • Il faut travailler sur des populations et donc la puissance de calcul demandée peut être importante.
    • Comme tout problème d’optimisation, il peut exister un algorithme simple qui évite de sortir l’artillerie lourde.
    • La méthode dépend des conditions initiales et de ses paramètres (taille de population, taille de la descendance sélectionnée, moyenne initiale, diamètre initial de l’ellipse).
  • Avantages :
    • La méthode marche sur de nombreuses fonctions qui mettent en défaut les méthodes classique de descentes
    • Elle peut gérer de manière adéquate les minimums locaux
    • Par sa nature probabiliste elle est robuste aux coûts qui sont bruités
    • On peut bouger la fonction (la translater, la faire tourner, la dilater…) l’algorithme se débrouille.
    • L’algorithme gère les problèmes dit mal conditionnés.
    • Le réglage de la méthode n’est pas compliqué et est robuste
    • La méthode n’utilise pas la dérivée de la fonction

Applications

Cet algorithme est assez jeune mais pourtant, il perce vraiment dans les domaines industriels. Il possède une part d’aléatoire qui peut faire peur aux industriels mais c’est justement cette part qui permet à cet algorithme d’être le seul à pouvoir innover de lui-même.

La finance est un domaine ou il s’épanoui pour faire un max de fric en un minimum de temps en tapant à droite à gauche et en sélectionnant les bons plans. (oui c’est à cause de lui tout ça)

Sinon, la deuxième conférence de la journée nous a montré l’application à la robotique. Le cas le plus extrême est une expérience qui consiste en une imprimante 3D qui construit un robot généré aléatoirement, monté à la main, il est posé sur une piste puis noté sur la distance qu’il a parcouru. La note est rentrée dans l’ordinateur, qui, en fonction de la note, va construire un autre robot etc.

Ou encore, l’optimisation de la qualité sur une chaine d’assemblage, l’optimisation d’un réseau de neurone pour obtenir un comportement, l’optimisation du réglage d’un contrôleur pour un avion civil, l’optimisation des commandes à envoyer à un drone pour faire un looping lent vers l’extérieur d’un virage (truc impossible à piloter)…

Et enfin, le code

L’imagination est la seule limite des applications de cet algorithme. D’autant plus que les chercheurs (dont Anne Auger) qui nous ont présenté cet algorithme donnent librement l’algorithme sur plusieurs langages ici.

Voici la page avec les supports utilisés lors du stage.

C’est avec leur code simplifié que j’ai fait toutes ces figures et vidéos.

Nous y avons aussi découvert le soft OCTAVE qui est équivalent à Matlab mais en libre. (il ne fait pas autant que Matlab mais fait le principal : le calcul matriciel)

Franchement, merci à l’INRIA pour cette journée.

L’avenir

Je pense que cette méthode va déjà percer très vite tous les domaines industriels mais surtout permettre de développer les algorithmes basés sur un traitement de populations. Je fais notamment référence à mes articles sur la conscience artificielle où je montre que la prise de décision n’est pas une procédure constructive mais plutôt une sélection des meilleures solutions pour garantir la vie. Cela concerne notamment ce que l’on appelle l’évolution artificielle en ligne.

Related posts:

9 Commentaires

  • 17 juin 2012 - 14 h 15 min | Permalien

    Bonjour, je vous remercie d’abord pour cet article, vraiment c’est excellent!
    j’aimerai vous demander si ça sera possible de m’expliquer comment je pourrait préparer une vidéo de l’algorithme comme celle que vous avez présenté
    Merci

  • 22 septembre 2011 - 18 h 29 min | Permalien

    Cette fois j’ai eu le courage de tout lire, mot à mot. Pas de lecture en diagonale, du sérieux.
    Impressionnant, intéressant ! Vraiment merci pour cet article, c’est génial.

  • 21 septembre 2011 - 20 h 56 min | Permalien

    Merci, pour vos commentaires, rien de tel qu’un article pour s’approprier des théories qui peuvent sembler compliquées mais qui dans le principe sont simple si on s’y plonge dans le code. Dearsham, es-tu là ? Si t’as des ajouts à faire, n’hésites pas, je ne sais pas si on peut partager la rédaction d’un article ou bien et si oui si non avec ou pas.

    • 22 septembre 2011 - 12 h 16 min | Permalien

      Coucou !! Tout d’abord bravo pour ce compte rendu ! Je pense comme les autres et ne rajouterai que des BRAVOS !!!
      J’étais sûr que ce séjour chez nos amis de l’INRIA serait des plus intéressant ! ^^

      Pour ce qui est de partager la rédaction d’un article… ça n’a encore jamais été fait sur Cube mais ça doit être possible… Je vais voir comment on peut faire ça…

  • 21 septembre 2011 - 19 h 02 min | Permalien

    Passionnant et très bien résumé.
    Je vous laisse tripatouiller tout ça ; je reviendrais pour brancher. ;-)
    Ils sont vraiment tordus ces bergers auvergnats!

  • 20 septembre 2011 - 22 h 00 min | Permalien

    salut , et merci Thot!
    vraiment passionnant ;-)

  • 20 septembre 2011 - 19 h 22 min | Permalien

    Merci pour ce super compte rendu. Je suis encore plus dégouté de ne pas avoir pu venir :’-( En tous les cas, je vais potasser tout cela avec le plus grand interet.

  • Laisser un commentaire

    Featuring Recent Posts WordPress Widget development by YD