Algorithme évolutionniste - Définition

Principes de bases

Terminologie

Tous les algorithmes évolutionnaires font évoluer 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é (la « fitness »). Les algorithmes sont conçus de façon à ce que plus la fitness d'un individu est elevée, plus il doit avoir de chances de transmettre son génotype au sein de la population.

À chaque étape de 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.

Algorithme

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 maximum 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 aussi que l'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 + enfants, pour former la génération suivante.

Généralités

Les notions d'intensification (ou exploitation), de diversification (ou exploration) et de processus aléatoires sont au cœur du comportement des opérateurs utilisés par les algorithmes évolutionnaires.

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 évolutionnaire 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 évolutionnaires ayant tendance à être classés parmi les métaheuristiques.