Algorithmes génétiques et algorithmes évolutionnaires

Depuis les années 1970, de nombreuses méthodes d’optimisation stochastique ont été développées sur la base de principes simplifiés d’évolution darwinienne. L’anglicisme « algorithmes évolutionnaires (AE) » choisi pour désigner ces méthodes est intentionnel : la communauté française employant ces méthodes a jugé important de distinguer les travaux évolutionnistes, portant sur des modèles biologiques très complexes, des approches évolutionnaires, utilisant des modèles informatiques très simplifiés.

Actuellement, les algorithmes dits « génétiques » (AG) sont les plus médiatisés parmi ces techniques, mais il en existe d’autres (programmation génétique, stratégies d’évolution, évolution grammaticale, par exemple) qui diffèrent par leur interprétation des principes darwiniens. La composante commune de ces techniques est qu’elles font évoluer des populations organisées en générations sous l’action conjuguée de deux catégories d’opérateurs stochastiques produisant :

•  une pression de sélection permettant de sélectionner des individus autorisés à se reproduire : « les meilleurs » au regard d’une fonction définie sur l’espace de recherche considéré, dite « fonction d’évaluation », « fonction de performance », ou « fitness », et qui traduit le problème que l’on cherche à résoudre ;

•  des variations aléatoires qui produisent de nouveaux individus, afin de constituer la génération suivante : croisement par échange d’informations entre plusieurs points, mutation par perturbation locale sur un point, pour faire un parallèle avec la génétique.

Un exemple classique est de faire évoluer une population de points dans l’espace de définition d’une fonction afin de trouver la valeur maximale de cette fonction. L’efficacité de ce schéma est fondée sur l’hypothèse que l’action des opérateurs génétiques sur des individus sélectionnés produit statistiquement des individus de plus en plus proches de la solution recherchée. En d’autres termes, le processus stochastique figuré par les populations successives doit être correctement calibré et paramétré pour converger vers ce que l’on souhaite, c’est-à-dire le plus souvent l’optimum global de la fonction de performance. Une grande part des recherches théoriques sur les algorithmes évolutionnaires est consacrée à cet épineux problème de convergence et à celui de savoir ce qui rend la tâche aisée ou difficile pour un algorithme évolutionnaire (notion d’AE-difficulté). Comme nous le verrons dans ce panorama, des réponses théoriques rassurantes existent (oui, cela converge, si l’on respecte certaines hypothèses), mais d’autres questions cruciales d’un point de vue pratique restent ouvertes (vitesses de convergence, notamment)....