Programmation génétique et Robotique autonome

Mon stage s'est déroulé au laboratoire Leibniz, dans l'équipe Laplace : "méthodes probabilistes appliquées à la perception, l'inférence et l'action".

Ces quelques pages vous donneront un aperçu de ce travail. Si vous voulez en savoir plus, vous pouvez télécharger mon mémoire, sous forme postscript zippé ou stuffité.

la programmation génétique

La programmation génétique fait partie des algorithmes évolutionnaires. L'idée commune à tous ces algorithmes est d'appliquer le principe de la sélection naturelle à des objets informatiques, par exemple des programmes.

La famille des algorithmes évolutionnaires comprend quatre classes principales : la programmation évolutive, les stratégies évolutionnaires, les algorithmes génétiques, et la programmation génétique. La famille des algorithmes génétiques est sans doute la plus connue. La programmation génétique est basée sur le même principe d'évolution mais les applique à des programmes représentés sous forme d'arbres syntaxiques.

Cette discipline est relativement jeune puisque le premier ouvrage exposant les principes de base date de 1992. Une conférence annuelle est consacrée à la programmation génétique depuis trois ans, une douzaine d'ouvrages de référence lui sont consacrés, et un workshop européen a lieu cette année pour la première fois. Vous pouvez visiter le site de John Koza (le pape de la GP) à Stanford. Bill Langdon, à Birmingham maintient une bibliographie. Si vous voulez un aperçu en français des principes de base, cette page est faite pour vous.

Principes de base

L'algorithme consiste à faire évoluer une population constituée d'un grand nombre de programmes (100 à 500). Au départ, la population est constitués de programmes créés aléatoirement. Chaque programme est évalué selon une méthode propre au problème posé. A chaque itération (génération) on classe les programmes en fonction des notes qu'ils ont obtenues, et on crée une nouvelle population, où les meilleurs programmes auront une plus grande chance de survivre ou d'avoir des enfants que les autres (eh oui, même aux mals foutus on laisse une petite chance). Ce principe est le même qu'en algorithmique génétique classique, mais les opérateurs de croisement et de mutation sont un peu différents. En effet, ils travaillent directement sur la structure d'arbre du programme.

Application à la robotique

La page méthode décrit la fonction d'évaluation que j'ai choisie dans le cas du robot Khepera, et les comportements obtenus.

retour page principale