Club robotique de Sophia-Antipolis

Accueil > POBOTpedia > Programmation > Explorer > Intelligence Artificielle > Algorithmes génétiques

Algorithmes génétiques

lundi 25 juillet 2011, par Eric P., Julien H.

Le terme génétique en informatique désigne un outil du monde de l’intelligence artificielle, permettant de converger vers un optimum (jeu de coefficients la plupart du temps) de configuration d’un système (matériel ou logiciel). Par rapport à une approche "brutale" consistant à évaluer toutes les combinaisons possibles, cette approche permet de traiter des problèmes dont la combinatoire est telle (dite "explosive") qu’une exploration systématique prendrait des temps infinis même avec des machines très puissantes.

Il faut bien avoir conscience que, du fait des principes utilisés par cette méthode, elle ne garantit pas de trouver l’optimum absolu (qui d’ailleurs n’existe pas la plupart du temps si l’optimisation est de type multi-objectifs) mais de converger vers un optimum représentant un très bon compromis entre le niveau de qualité de la solution et le temps de calcul mis pour la trouver. Ce n’est donc pas une méthode formelle exacte, mais une méthode de résolution approchée. Autre point important : la qualité du résultat dépend également des paramètres de réglage de la méthode (critère d’évaluation des solutions candidates, critères de convergence, méthode et paramètres de combinaison des générations successives,...). Il est donc important de bien garder à l’esprit que ce n’est pas un outil qu’il suffit de lancer pour résoudre une équation, mais d’un outil d’aide à l’exploration de l’espace des solutions permettant de converger rapidement vers une solution approchée de bonne qualité.

En robotique, l’algorithme génétique ne contrôle donc pas le robot, il permet de définir les meilleurs paramètres pour un code de contrôle existant.

Application

Chaque partie du logiciel initial est découpée en gènes paramétrables : par exemple des coefficients dans une équation, des pentes d’accélérations de moteurs, des boucles de calcul etc... Une combinaison de gènes est testée, puis chaque valeur est modifiée pour former une nouvelle combinaison testée à son tour.

Le résultat de chaque test est calibré pour définir un score (la "fitness function") : par exemple la vitesse maximale atteinte, l’autonomie du robot, la précision d’un déplacement, etc... Ce score va être utilisé pour déterminer quels gènes font progresser le programme et de nouvelles associations vont être faites pour une seconde génération, à son tour testée, notée et recombinée, et ainsi de suite jusqu’à obtenir un résultat convenable (nous reviendrons plus bas sur cette notion).

Pourquoi génétique ?

Tout d’abord, cette solution est itérative, mais n’utilise pas la "force brute" consistant à croiser toutes les combinaisons possibles comme cela a été présenté en introduction. Comme en génétique naturelle, il faut que des parents s’assemblent pour donner des enfants, qui à leur tour se croiseront pour refaire des générations successives.

L’analogie avec la génétique du vivant prend tout son sens quand on décortique les mécanismes d’IA : comme en biologie, il faut une part de hasard pour obtenir les meilleures combinaisons. Prendre mécaniquement les meilleurs scores ne permet pas d’atteindre toujours les meilleures solutions génétiques et il faut réintroduire des valeurs plus faibles. Il s’agit en fait de sortir de ce qu’on nomme un "maximum local". L’algorithme génétique a permis d’atteindre un Mont Blanc, mais le logiciel de construction des gènes doit redescendre de ce sommet pour aller voir s’il n’y aurait pas un Everest un peu plus loin.

Par exemple, sur un robot slalomeur, on peut obtenir une vitesse maximum en mettant les moteurs à fond, et avoir une mauvaise précision sur le parcours. Si l’algorithme d’assemblage des gènes ne peut pas réduire la vitesse pour tenter une meilleure variation du cap pour bien réussir son slalom, la solution optimale ne sera pas atteinte.

Le mythe de Frankenstein

Le côté plaisant dans l’étude d’algorithmes génétiques, surtout en robotique, est l’apparence aléatoire et totalement imprévisible des solutions que peut trouver la machine. En réalité, les choses ne sont pas aussi magiques qu’elles en ont l’air, mais on ne peut pas s’empêcher de penser cela parfois.

Pendant l’été qui a suivi la coupe 2004, nous avons mené quelques expérimentations sur le sujet, dans le but d’explorer la voie du traitement des multiples (11) télémètres SHARP qui équipaient le robot. En effet, en parfaits débutants nous avions naïvement tenté l’exploitation de ces capteurs pour l’évitement des obstacles et de l’adversaire avec une approche algorithmique conventionnelle, c’est à dire à base de if-then-else. Inutile de vous faire un dessin concernant le plat de spaghetti qui en a résulté, pour une efficacité proche du zéro absolu. Diverses lectures nous avaient ensuite orienté vers une approche à base de réseau de neurones, utilisant les 11 capteurs comme entrées, et produisant les consignes pour les deux moteurs. Comme il n’est pas vraiment envisageable de régler les coefficients d’un tel réseau à la main, nous avions alors abordé cette tâche par les algos génétiques, le génome du problème étant constitué par les coefficients du réseau de neurones.

L’outil utilisé en tant que fitness fonction était le simulateur développé par Eric, qui permettait de calculer une valeur traduisant la durée de vie du robot (c’est à dire le temps écoulé avant la rencontre d’un obstacle) et le taux de couverture du terrain, et par voie de conséquence la qualité de la solution candidate.

Après avoir fait tourner le dispositif pendant un week-end complet, nous avons eu la surprise de découvrir un champion, qui non seulement avait tenu les 90 secondes sans heurter d’obstacle, mais de plus en couvrant le plus de terrain. Pour visualiser son comportement, nous en avons chargé la configuration dans le simulateur. A notre grande surprise, le champion est parti en marche arrière et a fait tout son match de la sorte, pour aboutir au résultat annoncé. Autant dire que la configuration en question ne faisait pas usage des capteurs, disposés en face avant uniquement. Comment cela est-il possible ? Et bien parce que les générations successives ont fini par "apprendre" la disposition des obstacles sur le terrain, et ont de plus constaté que le fait de rouler en marche arrière permet de ne pas être "perturbé" par les informations retournées par ces capteurs (on n’a pas peur des obstacles si on ne les voit pas !!). Rien de magique ni diabolique dans tout cela.

Notre erreur a été d’utiliser un protocole expérimental invalide, car introduisant un biais par le fait de n’évaluer les solutions candidates que sur une unique configuration de l’environnement dans lequel évolue le robot. Nous avons donc modifié l’outillage de manière à ce que la fitness fonction travaille sur plusieurs configuration du terrain, générées de manière aléatoire. Et là, le résultat a été tout autre, et le meilleur robot faisait son parcours en marche avant cette fois-ci.

La morale de cette histoire

Outre les résultats concernant l’utilisation d’algos génétiques pour entraîner un réseau de neurones, cette expérimentation nous a fourni un enseignement capital, et à appliquer dans tous les domaines : un protocole expérimental mal conçu peut faire dire n’importe quoi à n’importe quelle expérience.

Il y a une dimension ludique à jouer avec ces algorithmes : on ne sait pas ce qui va arriver et le créateur du robot génétiquement modifié a une part de responsabilité très importante dans le résultat. Non seulement c’est lui qui a construit la mécanique (le logiciel de combinaison des gènes et de notation des générations) mais c’est aussi lui qui détermine les valeurs initiales et les variations possibles.

Le docteur Frankenstein était jugé responsable des crimes de son monstre parce qu’il avait utilisé des cadavres de criminels pour le construire. C’est un peu la même chose en algos génétiques : si vous n’avez pas une bonne intuition suffisante du résultat attendu au départ, toutes vos générations n’aboutiront pas à grand chose d’autre que des monstres au comportement erratique.

Bilan de la génétique en robotique

Cette construction successive de nouvelles versions par combinaison de gènes présente néanmoins quelques défauts intrinsèques :

 l’algorithme génétique peut passer à côté de la meilleure solution même au bout de plusieurs milliers de génération si la descente des maximums locaux n’est pas correctement prévue par l’insertion de gènes faibles. C’est précisément le rôle des mutations introduites au moment de la reproduction que d’éviter ces convergences prématurées, mais si le mécanisme de mutation n’est pas correctement configuré, il peut se révéler inefficace.

 comme nous l’avons vu plus haut, la définition de la fitness function est la clé de la validité de la solution. Or ce n’est pas toujours simple, et surtout c’est assez difficile de trouver un protocole permettant de la valider à priori (c’est à dire avant d’avoir observé les résultats de son application). Ce qui veut dire qu’il faut donc être en mesure de modéliser le plus parfaitement possible et de manière théorique le calcul de la qualité d’une solution.

Il n’y a donc pas de magie : il faut une bonne dose de réflexion préalable, ainsi qu’une bonne dose de logique et de patience, sans doute plus qu’avec un autre type d’algorithme plus conventionnel. Mais encore faut-il qu’un algorithme conventionnel soit concevable et que son temps d’exécution soit acceptable.

Par contre pour affiner un résultat complexe selon des critères bien maitrisés, cette intelligence artificielle peut vous faire gagner du temps, car dès qu’on peut simplifier le problème en réduisant les degrés de liberté et/ou les domaines de variation des gènes, la convergence du processus en est d’autant plus accélérée et fiabilisée.

Expérimentation

Si cet article vous a donné envie d’essayer par vous-même, mais que vous manquez de temps (refrain connu), essayez la robotique virtuelle avec Robocode - déjà utilisé chaque année par Pobot pour des compétitions d’informatique - grâce à JGAP, un logiciel open-source d’algorithmes génétiques.

Site de Robocode avec JGAP

Documents

Si l’expérience avec Robocode a été concluante, ou pas, vous serez peut être intéressée par la lecture (un peu ardue) de cette thèse dédiée à cette plateforme de robotique virtuelle :

Génétique avec Robocode

Dans le domaine de la robotique mobile ludique, voici une lecture intéressante : une étude réalisée il y a quelques années par un élève ingénieur mêlant algorithmes génétiques et réseaux de neurones dans le cadre expérimental de la Coupe Eurobot de robotique mobile.

Algos génétiques au LRDE

Un message, un commentaire ?

modération a priori

Attention, votre message n’apparaîtra qu’après avoir été relu et approuvé.

Qui êtes-vous ?

Pour afficher votre trombine avec votre message, enregistrez-la d’abord sur gravatar.com (gratuit et indolore) et n’oubliez pas d’indiquer votre adresse e-mail ici.

Ajoutez votre commentaire ici

Ce champ accepte les raccourcis SPIP {{gras}} {italique} -*liste [texte->url] <quote> <code> et le code HTML <q> <del> <ins>. Pour créer des paragraphes, laissez simplement des lignes vides.