au sommaire
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 stochastiquestochastique, et représentent la transposition informatique de la théorie de l'évolutionthéorie de l'évolution selon DarwinDarwin.
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étiquesgé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 naturellesé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 DarwinismeDarwinisme artificiel.
La manipulation d'une population artificielle
La caractéristique commune à 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).
Une 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 à é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 « tâtonnement » 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.
Les algorithmes évolutionnaires (génétiques) : des outils efficaces
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 algorithmiquesalgorithmiques et paramétriques, aux représentations du problème notamment.
Le design des ingrédients de base d'un algorithme évolutionnaire efficace n'est pas une tâche simple. L'expérience prouve que les grandes réussites sont fondées sur une très bonne connaissance du problème à 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 « boîte 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 réseau 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 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.
