Sciences

Algorithmes évolutionnaires

Dossier - Bio-inspirations, fractales, complexité et émergence
DossierClassé sous :Mathématiques , modélisation , fractales

-

La modélisation, l'analyse et le contrôle de la complexité sont des mots-clés de plus en plus cités dans les programmes de recherche nationaux et internationaux. Ce thème est commun à de nombreuses préoccupations scientifiques modernes : sciences et technologies du vivant, société de l'information, transports et environnement. Il correspond à un "verrou théorique et technologique'' C'est sans doute un des grands défis de ces prochaines années, qui nécessite un effort de recherche fondamentale et multidisciplinaire

  
DossiersBio-inspirations, fractales, complexité et émergence
 

L'une des approches de la complexité abordée au projet FRACTALES est fondée sur les algorithmes évolutionnaires. Ces techniques sont connues essentiellement pour leur potentiel en tant que méthode d'optimisation stochastique, et représentent la transposition informatique de la théorie de l'évolution selon Darwin.

Fractales. © FS domaine public

Le terme algorithme évolutionnaire correspond à l'ensemble des techniques fondées sur ce modèle biologique, dont les plus connues sont les algorithmes génétiques, mais on parle aussi dans ce cadre de programmation génétique, de stratégies d'évolution, de programmation évolutionnaire, selon la façon dont on traduit les principes Darwiniens dans le modèle artificiel.

Le principe de base est de copier le comportement de populations d'êtres vivants, qui s'adaptent à leur environnement à l'aide de phénomènes comme la sélection naturelle, et l'héritage génétique. La version informatique de ce modèle naturel est bien évidemment extrêmement simplifiée, c'est ce que l'on appelle aussi le Darwinisme artificiel.

La caractéristique commune à ces toutes ces méthodes est qu'elles sont fondées sur la manipulation d'une population artificielle, par exemple dans le cas de l'optimisation, des points d'un espace de recherche (les solutions potentielles au problème). L'évolution de cette population est simulée grâce à des opérations aléatoires de deux types :

  • une sélection, fondée sur la "performance" des individus, c'est-à-dire sur leur plus ou moins bonne correspondance avec ce que l'on recherche (dans le cas de la maximisation d'une fonction, cette performance sera la fonction elle-même), pour désigner les "bons" individus, autorisés à générer des descendants
  • des opérateurs génétiques, usuellement, croisement et mutation, qui produisent de nouveaux individus dans la population.

Ces opérations sont répétées en boucle, souvent sous forme de "générations", jusqu'à ce que la population converge. Si cette boucle est correctement calibrée, le processus stochastique associé converge vers la solution désirée (l'optimum global d'une fonction par exemple).

Un bonne part des recherches théoriques sur le Darwinisme artificiel est consacrée à l'épineux problème de savoir quand, pourquoi et comment converge un tel processus : on sait actuellement sous quelles conditions des modèles simples de ce processus convergent. Il reste a étudier les vitesses de convergence, l'influence des jeux de paramètres, et à progresser vers des modèles de plus en plus réalistes : c'est encore beaucoup de travail mathématique ardu et passionnant ...

Le succès pratique de ces méthodes vient du fait qu'elles représentent des outils d'optimisation adaptés à des fonctions, des problèmes difficiles, complexes, irréguliers. La mécanique évolutionnaire a cependant un coût calculatoire (c'est une méthode itérative, une recherche par "tatonnement" aléatoire dirigé) qui peut devenir important. Ces méthodes sont en fait complémentaires des méthodes d'optimisation plus "standard" comme les méthodes d'optimisation déterministes qui font le plus souvent des hypothèses de régularité sur les fonctions à optimiser.

Malgré l'apparente simplicité d'un processus évolutionnaire (ce qui a conduit de nombreux programmeurs à écrire très vite "leur" algorithme génétique, parfois bien décevant), fabriquer un algorithme évolutionnaire efficace est une tâche difficile, car les processus évolutionnaires sont très sensibles aux choix algorithmiques et paramétriques, aux représentations du problème notamment. Le design des ingrédients de base d'un algorithme évolutionnaire efficace est n'est pas une tâche simple, et l'expérience prouve que les grandes réussites sont fondées sur une très bonne connaissance du problème a traiter, sur beaucoup de créativité, et sur une bonne compréhension des mécanismes évolutionnaires. Il est tout bonnement hasardeux de considérer ces techniques en "boite noire", comme un "optimiseur universel". Cela dit, les "success-stories" sont nombreuses, et les techniques évolutionnaires ne sont pas très loin de faire partie de notre quotidien, il suffit par exemple d'aller visiter le site du reseau Europeen Evonet pour s'en convaincre ...

Pour en revenir au sujet de la complexité, outre le fait que l'on peut considérer le Darwinisme artificiel comme un modèle (simplifié !) de comportement complexe (une population d'agents en interaction, obéissant à des règles simples) -- ce qui pose le problème des outils de modélisation théorique de ces techniques, problème encore loin d'être entièrement exploré -- on peut aussi voir l'utilité des approches d'optimisation évolutionnaire d'un point de vue algorithmique : le contrôle et/ou la commande de systèmes complexes ne peut souvent être qu'indirecte, et les algorithmes évolutionnaires sont un des outils qu'il est possible d'utiliser pour orienter l'évolution de ces systèmes.