Manuel Clergue
résumé
Les travaux que je vais présenter s'inscrivent dans le domaine de l'évolution artificielle et s'articulent suivant trois thèmes principaux :
- l'étude de la structure des paysages adaptatifs ;
- l'étude de l'évolution des solutions à structure variable ;
- l'étude de l'évolution des populations structurées
L'évolution artificielle est un domaine de recherche qui nait avec l'informatique, puisque dès les années cinquante, certains, dont Alan Turing, évoquent l'idée de concevoir des algorithmes de recherche ou d'optimisation en utilisant comme modèle la théorie darwinienne de l'évolution des espèces naturelles. Mais c'est sous l'impulsion de chercheurs comme John Holland et Lawrence Fogel aux Etats-Unis, et Ingo Rechenberg et Hans-Paul Schwefel en Europe, que ce domaine va connaître un essor important et s'établir comme un domaine scientifique à part entière.
L'objectif de l'évolution artificielle est donc de concevoir des algorithmes en reproduisant in silico les mécanismes de l'évolution des espèces tels qu'ils ont été établis en premier lieu par Charles Darwin au dix-neuvième siècle et complétés tout au long du vingtième siècle : une population d'organismes évolue en se répliquant ; cette réplication n'est pas parfaite, ce qui introduit des variations aléatoires et produit des organismes qui vont réagir différemment à leur environnement ; ces différences vont faire que certains organismes vont être plus à même de se répliquer que d'autre et qu'ils ont donc plus de chances d'être sélectionnés pour constituer la génération suivante. La simplicité et la puissance explicatrice de la théorie darwinienne de l'évolution des espèces permettent au biologiste Richard Dawkins d'affirmer son universalité. Si une vie extra-terrestre existe, il est certain, selon lui, qu'elle sera fondée sur les mêmes principes et utilisera les mêmes mécanismes.
L'application la plus connue de l'évolution artificielle est la conception d'algorithmes évolutionnaires, qui sont des algorithmes de résolution de problèmes d'optimisation, manipulant une population de solutions potentielles, représentées par leur code, dans une boucle évolutionnaire : à partir d'une population à une génération t, sélection des parents, application d'opérateurs de variation et de recombinaison, ce qui permet de construire une population de descendants, qui remplacent les individus de la génération t pour constituer la population à la génération t + 1.
Le premier thème que j'aborderai est l'étude des paysages adaptatifs pour l'évolution artificielle. Ce modèle explicatif, introduit dans les années trente par Sewall Wright est important pour l'étude de l'évolution des espèces naturelles et également comme le montre Stuart Kauffman, pour l'étude de l'évolution des systèmes artificiels. Pour ces derniers, le paysage adaptatif est l'association de trois éléments : l'ensemble des individus ; les relations que les opérateurs de variation induisent entre eux et leur adaptation. Les deux concepts clefs associés aux paysages adaptatifs que nous avons étudiés sont l'évolvabilité et la neutralité. L'évolvabilité mesure la capacité des individus à produire des individus plus adaptés qu'eux. A
n d'estimer l'évolvabilité, nous avons développé un outil d'analyse et de visualisation des paysages adaptatifs : le nuage adaptatif. Cet outil nous permet d'expliquer certains phénomènes dynamiques observés lors de l'évolution des algorithmes que nous étudions. La neutralité est un complément nécessaire aux paysages adaptatifs pour comprendre le fonctionnement de l'évolution artificielle. Comme pour le cas naturel, théorisé par Motoo Kimura, il existe des configurations pour lesquelles les opérateurs de variation n'ont pas d'effets sur l'adaptation des individus. Lorsque la neutralité devient importante, l'évolution procède alors par paliers plutôt que par augmentation progressive de l'adaptation. En utilisant l'évolvabilité dans un contexte de forte neutralité, nous avons montré qu'il est possible de construire des algorithmes de recherche plus efficaces.
Le deuxième thème abordé concerne l'évolution des individus à structure variable. Dans leurs versions de base, les algorithmes évolutionnaires utilisent des structures de taille xe pour représenter les individus. Cependant, dans certains cas, comme par exemple en apprentissage automatique, il est souhaitable de pouvoir faire évoluer des solutions représentées par des structures de taille variable, comme des arbres, des séquences de longueur variable ou des graphes. A la dynamique adaptative, s'ajoute une dynamique d'exploration de la taille des individus. Si cette taille ne participe pas directement à la mesure de l'adaptation, notamment en introduisant un coût adaptatif non négligeable pour les individus de grande taille, la dynamique d'exploration en taille est triviale, puisque l'évolution aura tendance à faire grossir les individus jusqu'à atteindre une taille maximale, celle que le système autorise pour les solutions. Nous avons montré comment, en utilisant des mécanismes de reproductions inspirés de ceux présents dans la nature, il est possible de construire un opérateur de recombinaison, le croisement homologue. Il permet, en échangeant uniquement les parties différentes des parents, de maximiser l'homologie entre les parents et leurs enfants. Cette propriété de notre opérateur modifie profondément la façon dont les tailles évoluent, à tel point qu'il est nécessaire d'ajouter des opérateurs de variation de taille. L'avantage est de pouvoir découpler les deux opérations, l'échange et la variation en taille. Un effet du croisement homologue est de pouvoir faire évoluer efficacement des équipes de prédicteurs dont nous avons montré la pertinence dans la résolution de problème d'apprentissage.
Le troisième thème des travaux que je présenterai porte sur l'étude de l'évolution des populations structurées. Structurer les populations, et contraindre les opérateurs génétiques à respecter cette structure, par exemple en limitant les interactions à celles impliquant des individus proches, introduit une dimension supplémentaire dans l'évolution, en plus de celles induites par la structure du paysage adaptatif, c'est-à-dire par la structure des individus et par la fonction d'adaptation. Les dynamiques de diffusion des informations dans la population structurée modifient le compromis exploration/exploitation c'est à dire l'effort algorithmique consacré à la recherche de nouvelles informations par rapport à celui consacré à l'exploitation des informations disponibles. Les deux types de structures que nous avons utilisées sont d'abord une structure topologique : la population est disposée sur une grille et les individus interagissent uniquement avec leurs voisins sur cette grille. Des opérateurs spécifiques de sélection permettent alors de régler finement le compromis exploration/exploitation. Ensuite, nous avons proposé d'utiliser une structure symbolique pour la population. Dans ce cas, les interactions entre les individus sont principalement limitées à celles impliquant des individus portant le même symbole qui permet d'identifier une espèce d'individus. Un processus global de sélection associé à un opérateur de changement d'espèce, permet d'introduire une dynamique d'échange entre les espèces. Il existe donc deux niveaux : un niveau intra-espèce avec une dynamique évolutive propre à chaque espèce et un niveau inter-espèce mettant en compétition les espèces les unes contre les autres. En utilisant des opérateurs différents pour chacune des espèces, nous avons montré que l'algorithme adapte les ressources, c'est-à-dire le nombre d'individus, affectées à chaque espèce en fonction de leur efficacité.
Pour conclure, je présenterai certains de mes travaux en cours. Dans le cadre de mon intégration récente au sein de l'équipe Ingénierie des Données et de la Connaissance du LAboratoire de Mathématiques d'Informatique et de leurs Applications, j'ai été amené à m'intéresser à deux projets de modélisation de systèmes naturels à partir de données observées. Le premier projet consiste à concevoir un modèle prédictif des crues dans les bassins versants de la Caraïbe à partir des données historiques. Compte tenu de la forte combinatoire et de la difficulté du problème d'optimisation associé à la recherche du modèle, nous avons opté pour l'utilisation d'un algorithme évolutionnaire pour le résoudre. Nous avons montré que l'utilisation d'équipes de prédicteurs élémentaires améliore nettement l'efficacité de notre modèle en terme de qualité des prédictions, notamment parce qu'il devient ainsi plus robuste face aux données manquantes et à leur manque de abilité, phénomènes inévitables lorsqu'il s'agit de traiter des données réelles. Le deuxième projet en cours de réalisation concerne la conception de modèles explicatifs rendant compte de l'évolution conjointe de populations d'organismes dans des eco-systèmes naturels. Les premières études sur les données dont nous disposons nous ont conduit à envisager l'utilisation de modèles statistiques évolués, comme les réseaux bayésiens. Si il existe des méthodes efficaces pour la détermination des paramètres des réseaux bayésiens, la recherche de leur structure, c'est-à-dire du graphe sous-jacent, est un problème d'optimisation difficile. Cette fois encore, les algorithmes évolutionnaires, notamment ceux qui manipulent des solutions de taille variable, sont particulièrement adaptés à la résolution de tels problèmes. Au delà de l'intérêt applicatif de ces projets, ils constituent un terrain d'étude pour améliorer notre compréhension des algorithmes que nous utilisons et ils comportent de nombreuses voies d'exploration dans chacun des thèmes évoqués plus haut. Enfin, à plus long terme, une perspective de recherche prometteuse est de considérer les systèmes évolutifs artificiels comme des systèmes artificiels complexes. Les mécanismes en oeuvre induisent des dynamiques complexes, surtout lorsque des degrés de liberté supplémentaires sont apportés au système, comme lorsque l'on introduit une structure dans la population. Les comportements des algorithmes peuvent devenir imprévisibles et il est alors nécessaire d'adopter de nouveaux outils d'analyse et de nouvelles méthodologies d'étude, qui pourraient s'approcher de ceux utilisés pour les systèmes complexes naturels. C'est l'activité de recherche de fond à laquelle je compte me consacrer dans les prochaines années.