Le cadre général de mes travaux de recherche est l'étude, la mise au point et l'analyse de mécanismes d'apprentissage basés sur les théories de l'évolution naturelle, l'évolution artificielle.
Ces travaux peuvent se classer en deux grandes parties. Tout d'abord la mise au point de méthodes évolutionnaires pour l'apprentissage automatique. Ensuite, l'étude des algorithmes évolutionnaires en tant que méthodes d'optimisation.
Les travaux menés durant mon stage de DEA ont consisté à étudier des mécanismes de morphogenèse. La morphogenèse, étymologiquement l'élaboration de la forme, est le processus qui permet de passer d'un génotype (i.e. le code génétique manipulé par l'algorithme évolutionnaire), à un phénotype (i.e. l'entité réellement confrontée à l'environnement, c'est à dire au problème à résoudre). Le terme de morphogenèse était, dans le cadre de ce stage, appliqué à la génération de réseaux de neurones. L'objectif était alors d'obtenir une méthode robuste et efficace pour générer automatiquement des réseaux de neurones devant répondre à une tàche donnée. Nous avons appliqué avec succés cette méthode à un problème de référence, le "cart-pole problem", et dans un deuxième temps au contrôle de robots miniatures.
Je suis revenu à ces problèmatiques d'apprentissage aprés ma thèse. J'ai en effet encadré un doctorant (Michaël Defoin Platel, thése soutenue en 1994) dont le sujet était le développement de méthodes évolutionnaires, la programmation génétique, pour la découverte automatique de programmes, limités dans notre cas à des expressions arithmétiques, pour la régression symbolique. L'un des défauts majeurs de la programmation génétique est de faire croître en taille les solutions décourvertes au fur et à mesure de la recherche, sans que la qualité de ces solutions augmente, phénomène appelé bloat en anglais. La démarche originale du travail a consisté à revenir aux fondements de l'approche évolutionnaire, et notamment les études du croisement (opérateur permettant de combiner deux solutions pour en obtenir une troisième). Il a été énoncé des propriétés pour cet opérateur, pour qu'il soit efficace dans la recherche de meilleures solutions, notamment la propriété de respect, qui stipule que les caractéristiques communes aux deux parents doivent se retrouver chez les enfants. L'intégration de cette notion en programmation génétique n'est pas simple, puisqu'il s'agit de trouver les points communs entre des solutions structurées en arbre ou en chaîne de symboles de longueur variables, suivant les choix de représentation. Un (bref) détour par la biologie nous a permis de connaître les mécanismes d'appariement des chromosomes naturels, et de proposer une méthode d'appariement des programmes représentés sous formes de chaîne de symboles de longueur variable. Cette méthode est basée sur la distance d'édition, qui permet d'identifier l'appariement conduisant à la préservation maximale des points communs entre les parents. L'étude de cet opérateur de croisement, le croisement par maximum d'homologie, nous a permis de constater son efficacité et surtout qu'il réduisait de façon drastique le bloat.
En ce qui me concerne, ces travaux ont été initiés lors de ma thèse et continués jusqu'à maintenant, soit directement, soit par l'encadrement de stagiaires de DEA et de doctorants, et également lors de collaboration avec d'autres équipes de recherche, notamment celle de Marco Tomassini de l'Université de Lausanne.
Mes travaux de thèse concernaient l'étude du comportement des populations d'algorithmes génétiques. Communément, l'apprentissage est vu comme la capacité qu'un individu possède à effectuer de mieux en mieux une tàche. Si on se place au niveau d'une espèce, on peut considérer que si celle-ci est de mieux en mieux adaptée à son environnement au cours des générations successives, il y a une forme d'apprentissage, qualifié alors de phylogénétique. Considérer l'évolution comme une forme d'apprentissage modifie la perception classique de ce phénomène. En effet, on quitte une logique de compétition, ``struggle for life'', ce qui a été longtemps la conception de la théorie de l'évolution des espèces de Darwin, pour une logique de coopération, qui semble aujourd'hui plus proche de la réalité. En ce qui concerne les algorithmes génétiques, cela nécessite de ne pas les considérer comme de simples optimiseurs de fonctions, mais comme de véritables systèmes adaptatifs artificiels.
Dans cette optique, on peut considérer que la population manipulée par un algorithme génétique est composée d'agents autonomes (les individus). Ces individus évoluent ensemble, on dit alors qu'ils co-évoluent, non pas pour atteindre un objectif individuel, en général être le plus adapté, mais pour que la population dans sa globalité atteigne un état cible. Mes travaux sont axés autour de cette notion de coopération dans un algorithme génétique. Dans ce but nous utilisons les Algorithmes Génétiques Duaux: une extension des Algorithmes Génétiques standards, développée par Philippe Collard, membre de notre équipe. Cette nouvelle classe d'Algorithmes Génétiques semble plus apte à permettre de tels comportements coopératifs au sein de la population.
On s'aperçoit rapidement que cette problématique de la co-évolution, est en fait liée à celle de la diversité, ou polymorphisme. En effet, une condition pour qu'il y ait co-évolution, telle qu'elle a été définie plus haut, est qu'il se maintienne une certaine diversité au sein de la population. Ceci nous a amené à étudier les conditions d'apparition et de maintient de la diversité dans les Algorithmes Génétiques en général, et dans les Algorithmes Génétiques Duaux en particulier.
La coopération implique qu'il y ait des couplages entre les individus. Ces couplages peuvent induire des comportements et des dynamiques complexes. Pour pouvoir les étudier un modèle a été élaboré, l'Espace Dual Minimal. Ce modèle, basé sur un modèle équationnel des Algorithmes Génétiques Duaux, bien que minimal, permet de mettre en évidence des comportements non triviaux. En effet, lorsque l'on introduit dans l'Espace Dual Minimal une forme de couplage entre les individus, des comportements cycliques et chaotiques émergent.
L'étude des comportements dynamiques d'un Algorithme Génétique, nous a conduit à analyser un outil d'étude statique, la \emph{corrélation fitness-distance}, et à en étendre la signification, d'une part, dans le cadre de la dualité, et d'autre part en formulant la conjecture de corrélation entre instabilité et distance de Hamming.
L'aspect statique de la corrélation fitness-distance, nous a amené a définir un outil de visualisation dynamique. Le tracé des trajectoires de population dans le plan fitness-distance à l'optimum, permet de mettre en évidence les dynamiques de population. Par ailleurs, nous avons développé un outil d'analyse directement lié à l'observation de l'évolution de la diversité. Cela nous a permis de renforcer notre conjecture de forte corrélation entre l'instabilité liée aux opérateurs de croisement et la distance de Hamming.
En collaboration avec Lausanne (Marco Tomassini et Leonardo Vanneschi), nous avons transféré ces études de difficultés du monde simplifié des chaînes binaires de longueur fixe, au monde plus complexe de la programmation génétique, manipulant des solutions structurées en arbres. Cela nous a conduit à developper la notion de distance d'arbre, et nous a permis de constater que le coefficient de corrélation fitness distance pouvait être dans certains cas un indicateur de difficulté pour la programmation génétique, même si des contre exemples pouvaient être construit. Une autre perspective ouverte par mes travaux de thèse est l'étude des algorithmes génétiques et plus généralement des metaheuristiques sous l'angle de la neutralité. L'étude du dualisme nous a en effet conduit à formuler une analogie avec la théorie neutraliste de l'évolution. Cette théorie est fondée sur l'observation d'un polymorphisme important dans les populations naturelles. Selon cette théorie, l'évolution est surtout le fait de mutations sélectivement neutres, c'est-à-dire ne procurant pas d'avantage sélectif. Les individus, suite à ces mutations neutres, se diffusent dans des réseaux de neutralité. Occasionnellement, une mutation permet un changement de réseau de neutralité, avec un gain sélectif. Le dualisme introduit, à partir d'une fonction d'adaptation quelconque, des réseaux de neutralité. En effet deux individus duaux sont deux individus qui sont, par construction, phénotypiquement équivalents et génotypiquement différents. L'opérateur miroir, qui transforme un individu en son dual, peut être alors vu comme une mutation neutre. L'étude du dualisme et de ses possibles extensions dans la perspective de la neutralité a fait l'objet d'un stage de DEA.
L'analyse des paysages de fitness sous l'angle de la neutralité, a fait l'objet d'une thèse (Sébastien Verel, soutenue en 2005), que j'ai également co-encadrée. De même que nous avions transféré avec succés les notions de difficultés liées au coefficient de corrélation, toujours en collaboration avec l'équipe de Lausanne, devenue depuis l'équipe de Lausanne (M. Tomassini) et l'équipe de Milan (L. Vanneschi), c'est l'idée de la neutralité que nous avons intégrée à la programmation génétique, à savoir la vision des espaces de recherche non pas comme des paysages vallonnés mais plutôt comme des suites de plateaux.