Les Algorithmes Évolutionnistes

Les algorithmes évolutionnistes constituent une suite de règles formelles dont le principe s’inspire du Darwinisme pour résoudre divers problèmes en informatique. Ce sont donc des procédés de prévision bio-inspirées*.

Le concept est de faire évoluer un ensemble de solutions à un problème donné afin de produire les meilleurs résultats. Ce sont des algorithmes dits stochastiques* car ils utilisent itérativement des processus aléatoires.

La grande majorité de ces procédés est utilisée pour solutionner des problèmes d’optimisation*. Ces procédés sont en cela des métaheuristiques*, bien que le cadre général ne soit pas nécessairement dédié aux algorithmes d’optimisation au sens strict. On classe ces algorithmes parmi les méthodes d’intelligence artificielle*.

Genèse 

Les algorithmes évolutionnistes traitent des populations de solutions. Ils s’inspirent de l’évolution des êtres vivants, en considérant que celle-ci tend à produire des organismes plus adaptés à leur environnement.

Selon le Darwinisme, plusieurs mécanismes sont à l’œuvre pour ce faire. Schématiquement :

• les caractéristiques d’un organisme sont en grande partie codées dans ses gènes ;
• chaque population d’organismes est composée d’individus tous différents ;
• les individus sont plus ou moins adaptés à leur environnement ;
• les organismes transmettent une partie de leurs caractéristiques à leurs descendants ;
• les individus les plus adaptés se reproduisent plus « efficacement », leurs caractéristiques ont donc tendance à davantage se répandre dans la population.

Les fondamentaux

Terminologie

Tous les algorithmes évolutionnistes font progresser un ensemble (une « population ») de solutions (les « individus »). Les individus sont représentés par leur génotype, qui s’exprime sous la forme d’un phénotype, auxquels on associe une qualité, l’aptitude (fitness). Les algorithmes sont conçus de façon que plus l’aptitude d’un individu est élevée, plus il a de chances de transmettre son génotype au sein de la population.

À chaque étape, l’algorithme est associé un « opérateur », qui décrit la façon de manipuler les individus. On regroupe parfois les différents opérateurs sous des termes génériques :

• opérateurs de sélection pour la sélection et le remplacement ;
• opérateurs de variation pour la mutation et le croisement.

Méthode

Pour ce faire, on utilise l’algorithme général suivant :

construction et évaluation d’une population initiale ;

jusqu’à atteindre un critère d’arrêt :

  sélection d’une partie de la population,

  reproduction des individus sélectionnés,

  mutation de la descendance,

  évaluation du degré d’adaptation de chaque individu,

  remplacement de la population initiale par une nouvelle population.

Après avoir initialisé une première population d’individus, on itère un nombre fini de fois, jusqu’à atteindre un critère d’arrêt (par exemple un nombre N de générations).

La première étape de sélection permet de séparer les individus qui participeront à la reproduction de ceux qui n’y participeront pas.

Les individus sélectionnés (les « parents ») se reproduisent (on dit alors qu’on effectue des croisements), donnant un ensemble d’« enfants » partageant une partie des caractéristiques de leurs ascendants.

Ces enfants subissent alors une étape de mutation, qui modifie aléatoirement leur génotype.

Les nouveaux individus sont alors évalués (on met à jour leur valeur en faisant appel à la fonction objectif).

Enfin, on choisit un nombre d’individus déterminé parmi l’ensemble parents et enfants, pour constituer la génération suivante.

Généralités

Il existe toujours au moins un opérateur utilisant un processus aléatoire, au minimum pour la construction de la population initiale et pour la mutation, mais souvent pour la sélection et la reproduction également. Selon les méthodes, on met l’accent sur l’un ou l’autre des opérateurs.

Une pratique courante reste de maintenir suffisamment longtemps la « diversité génétique » de la population, afin d’éviter une convergence prématurée. Quand un algorithme évolutionniste utilise une procédure de recherche locale à chaque individu, il est appelé « algorithme mémétique* ». 

Dans la terminologie historique, on cherche à maximiser la valeur de la fonction objective, à l’aide d’opérateurs montrant des comportements d’exploitations ou d’exploration. Ces termes correspondent aux notions d’intensification et à la diversification, plutôt utilisés dans le domaine des métaheuristiques, où l’on cherche en général à minimiser la valeur de la fonction objectif. Néanmoins, ces deux domaines sont tout à fait similaires, les algorithmes évolutionnistes ayant tendance à être classés parmi les méta-heuristiques.

Principales catégories

Historiquement, trois grandes catégories d’algorithmes ont été développées indépendamment, entre la moitié des années 1960 et 70. 

Les premières méthodes furent les stratégies d’évolution*, proposées par I. Rechenberg en 1965, pour résoudre des problèmes d’optimisations continus. 

L’année suivante, Fogel, Owens et Walsh conçoivent la programmation évolutionnaire* comme une méthode d’intelligence artificielle pour la conception d’automates à états finis*. 

Enfin, en 1975, J. H. Holland propose les premiers algorithmes génétiques*, pour l’optimisation combinatoire. La parution en 1989 du livre de D. E. Goldberg sur les algorithmes génétiques rendra ceux-ci particulièrement populaires.

Par la suite, ces différentes approches ont beaucoup évolué et se sont rapprochées, pour finir par êtres regroupées sous le terme générique d’algorithmes évolutionnistes.

Aujourd’hui, la littérature sur le sujet est extrêmement abondante, et ces algorithmes sont considérés comme un domaine de recherche très prolifique.

Quelques définitions

*Le darwinisme (théorie de l’évolution) désigne, en son sens strict, la théorie formulée en 1859 par le naturaliste anglais Charles Darwin, qui explique « l’évolution biologique des espèces par la sélection naturelle et la concurrence vitale ».

*La bioinspiration ou bio-inspiration est un changement de paradigme qui conduit des concepteurs à s’inspirer de la nature pour développer de nouveaux systèmes.

*Le stochastique désigne un indicateur technique utilisé notamment par les intervenants en bourse.

*L’optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble.

*Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficiles pour lesquels on ne connaît pas de méthode classique plus efficace.

*L’intelligence artificielle est un ensemble de théories et de techniques permettant de réaliser des machines capables de simuler l’intelligence humaine.

*Les algorithmes d’optimisation cherchent à déterminer le jeu de paramètres d’entrée d’une fonction donnant à cette fonction la valeur maximale ou minimale.

*Les algorithmes mémétiques appartiennent à la catégorie des algorithmes évolutionnistes. Leur but est d’obtenir une solution approchée à un problème d’optimisation, lorsqu’il n’existe pas de méthode de résolution pour résoudre le problème de manière exacte en un temps raisonnable. 

*Les stratégies d’évolution forment une catégorie de métaheuristiques d’optimisation. Elles sont inspirées de la théorie de l’évolution, et appartiennent à ce titre à la classe des algorithmes évolutionnistes.

*La programmation génétique est une méthode automatique inspirée par le mécanisme de la sélection naturelle tel qu’il a été établi par Charles Darwin pour expliquer l’adaptation plus ou moins optimale des organismes à leur milieu. 

*Un automate fini est un modèle mathématique de calcul, utilisé dans de nombreuses circonstances, allant de la conception de programmes informatiques et de circuits en logique séquentielle aux applications dans des protocoles de communication, en passant par le contrôle des processus, la linguistique et même la biologie.

*Les algorithmes génétiques appartiennent à la catégories des algorithmes évolutionnistes. Leur but est d’obtenir une solution approchée à un problème d’optimisation, lorsqu’il n’existe pas de méthode exacte pour le résoudre en un temps raisonnable.