Utilisation des Algorithmes Evolutionnaires dans la
Conception des Logiciels

Le principe des Algorithmes Evolutionnaires

La suite de cette section va détailler les principaux algorithmes évolutionnaires, en donnant un exemple illustratif concret. Mais nous allons au préalable définir quelques notions-clés pour la compréhension du fonctionnement de ces algorithmes en pratique.

Le paradigme Darwinien

La théorie de Darwin lors de la conception des Algorithmes Évolutionnaires est basée sur l’idée de l’apparition d’espèces adaptées au milieu qui est la conséquence de la conjonction de deux phénomènes [Allaire, 2006] :  La sélection naturelle imposée par le milieu (les individus les plus adaptés survivent et se reproduisent).  Et des variations non dirigées du matériel génétique des espèces. Ce sont ces deux principes qui sous-tendent les algorithmes évolutionnaires. Précisons tout de suite que le paradigme darwinien qui a inspiré ces algorithmes ne saurait en aucun cas être une justification pour leur emploi. 

Les notions principales

La notion principale de l’algorithme, qui est même en fait préalable à toutes les autres, est la représentation, ou choix de l’espace de recherche. Dans de nombreux cas, l’espace de recherche est totalement déterminé par le problème (i.e. c’est l’espace O sur lequel est définie la fonction objectif J). Mais il est toujours possible de transporter son problème dans un espace habilement choisi (“changement de variables”) dans lequel il sera plus aisé de définir des opérateurs de variations efficaces. Cet espace est alors appelé espace génotypique, et l’espace de recherche initial O, dans lequel est calculé la performance des individus, est alors aussi appelé espace phénotypique. On peut alors répartir les diverses étapes de l’algorithme en deux groupes:  les étapes relatives au darwinisme (la sélection et le remplacement), qui ne dépendent que des valeurs prises par J, et pas de la représentation choisie, (i.e. pas de l’espace génotypique) et les étapes qui sont intimement liées à la nature de cet espace de recherche.  l’initialisation et les opérateurs de variation sont spécifiques aux types de génotypes, mais par-contre ne dépendent pas de la fonction objectif J (c’est le principe Darwinien des variations aveugles, ou non dirigées). Le terme de diversité génétique désigne la variété des génotypes présents dans la population. Elle devient nulle lorsque tous les individus sont identiques, on parle alors de convergence de l’algorithme. Mais il est important de savoir que lorsque la diversité génétique devient très faible, il y a très peu de chances pour qu’elle augmente à nouveau. Et si cela se produit trop tôt, la convergence a lieu vers un optimum local. On parle alors de convergence prématurée. Il faut donc préserver la diversité génétique, sans pour autant empêcher la convergence. Un autre point de vue sur ce problème est celui du dilemme exploration-exploitation. A chaque étape de l’algorithme, il faut effectuer le compromis entre explorer l’espace de recherche, pour éviter de stagner dans un optimum local et exploiter les meilleurs individus obtenus, afin d’atteindre de meilleurs valeurs aux alentours. Trop d’exploitation entraîne une convergence vers un optimum local, alors que trop d’exploration entraîne la non-convergence de l’algorithme. Typiquement, les opérations de sélection et de croisement sont des étapes d’exploitation, alors que l’initialisation et la mutation sont des étapes d’exploration (mais de multiples variantes d’algorithmes évolutionnaires s’écartent de ce schéma général). On peut ainsi régler les parts respectives d’exploration et d’exploitation en jouant sur les divers paramètres de l’algorithme (probabilités d’application des opérateurs, pression de sélection, …etc). Cependant, il n’existe pas de règles universelles de réglages et seuls les résultats expérimentaux donnent une idée du comportement de diverses composantes des algorithmes.

Les Composants Evolutionnaires

Soit à optimiser une fonction J à valeurs réelles définie sur un espace métrique Ω. Le parallèle avec l’évolution naturelle a entraîné l’apparition d’un vocabulaire spécifique (et qui peut paraître légèrement ésotérique) [Siarry, 2014 ] :  La fonction objectif J est appelée fonction de performance, ou la fonction d’adaptation (fitness en anglais) ;  Les points de l’espace de recherche Ω sont appelés des individus ;  Les tuples d’individus sont appelés des populations ;  On parlera d’une génération pour la boucle principale de l’algorithme.  La population de taille fixe P, à la génération I. Fig.1.1.Squelette d’un Algorithme Evolutionnaire. Le temps de l’évolution est supposé discrétisé, et on notera la pression de l’environnement qui est simulée à l’aide de la fonction objective J, et les Initialisation Evaluation Meilleur individu Stop ? Croisement, Mutation,.. Parents Sélection Evaluation Remplacement Enfants Géniteurs principes darwiniens de sélection naturelle et de variation s’aveugles sont implantés dans l’algorithme de la manière suivante dans la Figure.1.1 [Siarry, 2014] montre le squelette d’un algorithme évolutionnaire :  Initialisation de la population Π en choisissant P individus dans Ω, généralement par tirage aléatoire avec une probabilité uniforme sur Ω ;  Évaluation des individus de Π00 (i.e. calcul des valeurs de J pour tous les individus) ; A partir de la population Π ;  La génération I construit la population Π ;  La sélection des individus les plus performants de Π au sens de J (les plus adaptés se reproduisent);  Application (avec une probabilité donnée) des opérateurs de variation aux parents sélectionnés, ce qui génère de nouveaux individus, les enfants; On parlera de mutation pour les opérateurs unaires, et de croisement pour les opérateurs binaires (ou n-aires); A noter que cette étape est toujours stochastique :  Évaluation des enfants ;  Remplacement de la population Π par une nouvelle population créée à partir des enfants et/ou des “vieux” parents de la population Π au moyen d’une sélection darwinienne (les plus adaptés survivent).  L’évolution stoppe quand le niveau de performance souhaité est atteint, ou qu’un nombre fixé de générations s’est écoulé sans améliorer l’individu le plus performant. Il est important de noter que, dans les applications la plupart des problèmes numériques réels, l’essentiel du coût-calcul de ces algorithmes, provient de l’étape d’évaluation (calcul des performances) : les tailles de populations sont de l’ordre de quelques dizaines et le nombre de générations de quelques centaines, ce qui donne lieu le plus souvent à plusieurs dizaines de milliers de calculs de J. Nous allons maintenant passer en revue les différentes méthodes de sélection possible, en gardant à l’esprit qu’elles sont génériques et quasiment interchangeable quel que soit le problème traité. 

La Sélection naturelle

D’un point de vue technique, la différence essentielle entre l’étape de sélection et l’étape de remplacement est qu’un même individu peut être sélectionné plusieurs fois durant l’étape de sélection (ce qui correspond au fait d’avoir plusieurs enfants), alors que durant l’étape de remplacement, chaque individu est sélectionné une fois (et il survit) ou pas du tout (et il disparaît à jamais). On distingue deux catégories de procédures de sélection ou de remplacement (par abus de langage, nous appellerons sélection les deux types de procédures) [Randy, 2004] :  Les procédures déterministes.  Les procédures stochastiques.

La Sélection déterministe

On sélectionne les meilleurs individus (au sens de la fonction objective). Si un nombre d’individus est sélectionné, cela suppose un tri de l’ensemble de la population, Cependant cela implique un problème de temps calcul que pour les grosses tailles de population. Les individus les moins performants sont totalement éliminés de la population, et le meilleur individu est toujours sélectionné, on dit que cette sélection est élitiste. La Sélection élitiste: Les membres les plus adaptés de chaque génération doivent être sélectionnés. La plupart des Algorithmes Evolutionnaires n’utilisent l’élitisme pur, à moins qu’ils sont modifiés de chaque génération un reproduites dans la prochaine génération. 

La Sélection stochastique

En générale, les meilleurs individus sont toujours favoriser, mais de manière stochastique, ce qui laisse une chance aux individus les moins performants. Par contre, il se peut que le meilleur individu ne soit pas sélectionné, et qu’aucun des enfants n’atteigne une performance aussi bonne que celle du meilleur parent. Le tirage de roulette : Elle est la plus célèbre des sélections stochastiques. Supposant un problème de maximisation avec uniquement des performances positives, elle consiste à donner à chaque individu une probabilité d’être sélectionné proportionnellement à sa performance. Une illustration de la roulette est donnée dans la Figure.1.2. On lance la boule dans la roulette, et on choisit l’individu dans le secteur du quel la boule a fini sa course. Fig.1.2. Sélection par Tirage de Roulette Le tirage de roulette présente toutefois de nombreux inconvénients, en particulier reliés à l’échelle de la fonction objective, alors qu’il est théoriquement équivalent d’optimiser J et αJ + β, pour tout α > 0. Il est clair que le comportement de la sélection par roulette va fortement dépendre de α. dans ce cas. Sachant qu’il existe des procédures ajustant les paramètres α et β pour chaque génération (mécanismes de mise à l’échelle). La sélection par rang : Elle consiste à faire une sélection en utilisant une roulette dont les secteurs sont proportionnels aux rangs des individus (P pour le meilleur, 1 pour le moins bon, pour une population de taille P). La variante linéaire utilise directement le rang et les variantes polynomiales remplacent ces valeurs par Pα, α > 0. Le point essentiel de cette procédure de sélection est que les valeurs de J n’interviennent plus. Seuls comptent les positions relatives aux individus entre eux. Optimiser J et αJ + β sont alors bien totalement équivalents. La sélection par tournoi : Elle n’utilise que des comparaisons entre individus et ne nécessite même pas de tri de la population. Elle possède un paramètre T (taille du tournoi) pour sélectionner un individu, on tire T uniformément dans la population, et on en sélectionne le meilleur de ces individus. On choisit des sous-groupes d’individus parmi la grande population et les membres de chaque sous-groupe sont en concurrence les uns avec les autres. Un seul de chaque sous-groupe est choisi pour se reproduire. La progéniture des individus sélectionnés de chaque génération remonte au pool génétique préexistant remplaçant ainsi les membres les moins adaptés de la génération précédente.

La Sélection multi-critères

Toutes les techniques de sélection présentées ci-dessus concernent le cas d’une fonction objective à valeurs réelles. Cependant, la plupart des problèmes réels sont en fait des problèmes multi-critères, que l’on cherche à optimiser simultanément. (Typiquement, maximiser la qualité d’un produit en minimisant son prix de revient). Or les Algorithmes Evolutionnaires sont une des rares méthodes d’optimisation permettant la prise en compte de telles situations. Il suffit de modifier les étapes Darwiniennes d’un Algorithme Evolutionnaire pour en faire un algorithme d’optimisation multi-critère.