Les algorithmes génétiques

1. Introduction

L’Optimisation est l’une des branches les plus importantes des mathématiques appliquées modernes, et de nombreuses recherches, à la fois pratiques et théoriques, lui sont consacrées. Si on met de côté les problèmes d’optimisation discrète ou multicritère, alors la théorie de l’optimisation peut être séparée en deux grandes branches : l’optimisation locale et l’optimisation globale. Si on peut considérer que la première est presque « entièrement connue », la seconde est encore partiellement méconnue et les recherches y sont à leur apogée, comme le confirment les nombreuses parutions récentes [Zhi91]. La tâche principale de l’optimisation globale est la recherche de la solution qui minimisera un critère de coût donné, appelée « optimum global ». L’optimisation globale vise donc à rechercher non seulement un minimum local, mais surtout le plus petit de ces minima locaux.

Il existe deux grandes approches à l’optimisation globale. L’une est dite déterministe : les algorithmes de recherche utilisent toujours le même cheminement pour arriver à la solution, et on peut donc « déterminer » à l’avance les étapes de la recherche. L’autre est aléatoire : pour des conditions initiales données, l’algorithme ne suivra pas le même cheminement pour aller vers la solution trouvée, et peut même proposer différentes solutions. C’est vers cette seconde branche, la recherche globale aléatoire, que vont s’orienter nos travaux, et plus particulièrement vers un type bien précis d’algorithme de recherche aléatoire, les algorithmes génétiques.

2. Les algorithmes génétiques

2.1 Généralités sur les algorithmes génétiques

2.1.1 Introduction

Dans la nature, les êtres vivants croissent et interagissent les uns avec les autres. Chaque individu est caractérisé par un génotype indépendant de l’environnement où il vit. Les opérateurs génétiques fonctionnent au niveau génotypique tandis que le mécanisme de sélection opère au niveau phénotypique (le phénotype d’un individu est l’ensemble des traits caractéristiques d’un individu, alors que le génotype est le codage de ces traits en gènes). Les algorithmes génétiques sont à la base des algorithmes d’optimisation stochastiques, mais peuvent également servir pour l’apprentissage automatique, par exemple. Les premiers travaux dans ce domaine ont commencé dans les années cinquante, lorsque plusieurs biologistes américains ont simulé des structures biologiques sur ordinateur. Puis, entre 1960 et 1970, John Holland [Hol75], sur la base des travaux précédents, développe les principes fondamentaux des algorithmes génétiques dans le cadre de l'optimisation mathématique. Malheureusement, les ordinateurs de l'époque n'étaient pas assez puissants pour envisager l'utilisation des algorithmes génétiques sur des problèmes réels de grande taille. La parution en 1989 de l'ouvrage de référence écrit par D.E. Goldberg [Gol98] qui décrit l'utilisation de ces algorithmes dans le cadre de résolution de problèmes concrets a permis de mieux faire connaître ces derniers dans la communauté scientifique et a marqué le début d'un nouvel intérêt pour cette technique d'optimisation, qui reste néanmoins très récente. Parallèlement, des techniques proches ont été élaborées, dont on peut notamment citer la programmation génétique [Koz92] ou les stratégies évolutionnistes [Sch95]. Dans le même temps, la théorie mathématique associée aux algorithmes génétiques s'est développée mais reste encore bien limitée face à la complexité théorique induite par ces algorithmes.

Comme nous l’avons mentionné précédemment, les algorithmes génétiques s'attachent à simuler le processus de sélection naturelle dans un environnement hostile lié au problème à résoudre, en s'inspirant des théories de l'évolution proposées par Charles Darwin [Dar59] :

1. Dans chaque environnement, seules les espèces les mieux adaptées perdurent au cours du temps, les autres étant condamnées à disparaître.
2. Au sein de chaque espèce, le renouvellement des populations est essentiellement dû aux meilleurs individus de l'espèce.

On parlera ainsi d'individu dans une population et bien souvent l'individu sera résumé par un seul chromosome (individu haploïde). Les chromosomes sont eux-même constitués de gènes qui contiennent les caractères héréditaires de l'individu. On retrouvera aussi les principes fondamentaux de l'évolution naturelle, à savoir les principes de sélection, de croisement, de mutation, etc.

Dans le cadre de l'optimisation, chaque individu représente un point de l'espace d'état auquel on associe la valeur du critère à optimiser. On génère ensuite une population d'individus aléatoirement pour laquelle l'algorithme génétique s'attache à sélectionner les meilleurs individus tout en assurant une exploration efficace de l'espace d'état. Les algorithmes génétiques diffèrent des algorithmes classiques d’optimisation et de recherche essentiellement en quatre points fondamentaux :

1. Les algorithmes génétiques utilisent un codage des éléments de l’espace de recherche et non pas les éléments eux-même.
2. Les algorithmes génétiques recherchent une solution à partir d’une population de points et non pas à partir d’un seul point.
3. Les algorithmes génétiques n’imposent aucune régularité sur la fonction étudiée (continuité, dérivabilité, convexité…). C’est un des gros atouts des algorithmes génétiques.
4. Les algorithmes génétiques ne sont pas déterministes, ils utilisent des règles de transition probabilistes.

La robustesse est une des caractéristiques principales des algorithmes génétiques : ils permettent de fournir une ou plusieurs solutions de « bonne » qualité (pas nécessairement optimales, mais suffisantes en pratique) à des problèmes très variés, en sollicitant un investissement (temps et puissance de calcul) assez faible. En effet, l’heuristique de l’évolution est en quelque sorte « universelle », et très peu d’informations suffisent pour résoudre un problème quelconque. C'est ainsi qu'ils ont donné de bons résultats dans le problème du voyageur de commerce [HSL93], dans le domaine médical [FSJP93] ou dans les problèmes de contrôle du trafic aérien [DASF94]. Ils sont également efficaces sur des problèmes pour lesquels il n’existe pas - encore - d’algorithme de résolution ou dont la taille est rédhibitoire pour les méthodes classiques.

Après avoir exposé le fonctionnement général d’un algorithme génétique, nous détaillerons chacun de ses composants, puis les divers raffinements présents dans les versions modernes, et nous terminerons par les limitations de ce type d’algorithme.

2.1.2 Principes généraux des algorithmes génétiques

A présent, nous allons expliciter rapidement le principe de fonctionnement des algorithmes génétiques. Nous reviendrons plus en détail sur les différentes étapes par la suite.

Les opérations successives utilisées dans les algorithmes génétiques sont illustrées sur la figure ci-après :

1. On commence par générer une population d'individus de façon aléatoire.
   
   
2. On sélectionne un certain nombre d'individus dans la population, afin de générer une population intermédiaire, appelée aussi « mating pool ».
3. Deux parents sont ensuite sélectionnés (P1 et P2) en fonction de leurs adaptations. On applique aléatoirement l'opérateur de croisement avec une probabilité Pc qui génère deux enfants C1 et C2. Si la probabilité de croisement Pc vaut 0.6, par exemple, on appliquera l'opérateur de croisement dans 60% des cas sur les individus P1 et P2. L’opérateur de croisement est traditionnellement l’heuristique prépondérante d’un algorithme génétique. On modifie ensuite certains gènes de C1 et C2 en appliquant l'opérateur de mutation avec la probabilité Pm, ce qui produit deux nouveaux individus C'1 et C'2 pour lesquels on évalue le niveau d'adaptation avant de les insérer dans la nouvelle population. Contrairement à la reproduction et au croisement qui favorisent l’intensification, cet opérateur favorise la diversification des individus. On réitère les opérations de sélection, de croisement et de mutation afin de compléter la nouvelle population, ceci termine le processus d'élaboration d'une génération.
4. On réitère les opérations précédentes à partir de la seconde jusqu’à ce qu’un critère d’arrêt soit satisfait. Différents critères d’arrêt de l’algorithme peuvent être choisis : nombre de générations fixé, limite de convergence de la population, population qui n’évolue plus suffisamment, etc.

Il n’existe pas qu’une seule manière de définir les mécanismes des algorithmes génétiques. Ainsi, le codage et l’évaluation des individus, la sélection, le croisement et la mutation peuvent différer d’un problème à un autre (et chaque utilisateur aura même ses préférences). Pour utiliser un algorithme génétique sur un problème particulier, on doit donc disposer des cinq éléments suivants, que nous décrirons plus loin en détail dans leurs versions les plus classiques et les plus simples à mettre en œuvre, en mentionnant leurs avantages et leurs inconvénients :

1. Un principe de codage du chromosome. Cette étape associe à chacun des points de l'espace d'état une structure de données qui synthétise toute l'information liée à ces derniers et se place donc après la phase de modélisation mathématique.
   
   
2. Un mécanisme de génération de la population initiale. Ce mécanisme doit être capable de produire une population d'individus uniformément répartis qui servira de base pour les générations futures. Dans la figure suivante, on se rend compte sans difficulté que le cas #1 est plus favorable à la recherche de l'optimum que le cas #2, car la population #1 est mieux distribuée dans l'espace d'état.
   
   

   Les individus sont figurés par les croix, l’optimum par le cercle.

3. Un critère permettant de déterminer l'adaptation d'un individu par rapport à l'environnement afin de classer les individus entre eux. Dans le vocabulaire des algorithmes génétiques, on dénomme par "fitness" (traduction anglaise du mot adaptation) le critère à optimiser.
   
   

   La surface représente la fitness des individus à cet endroit de l’espace, les pics figurent les individus les mieux adaptés à leur environnement. L’objectif est de rapprocher les individus des pics.

4. Des opérateurs permettant de diversifier la population au cours des générations en explorant l'espace d'état. Classiquement, il y a deux opérateurs utilisés qui sont le croisement et la mutation. Le croisement s'attache à brasser les gènes des individus dans la population tandis que l'opérateur de mutation a pour but de générer de nouveaux gènes. La bonne adéquation du principe de codage et des opérateurs par rapport au problème traité conditionne le succès ou l'échec des algorithmes génétiques et il faudra donc attacher un soin très important dans la conception de ces derniers.
5. Des paramètres de dimensionnement (taille de population, nombre de génération à simuler, probabilité d'application des opérateurs).

2.1.3 Codage des individus

Dans la nature, les structures géniques sont codées en base 4, dont les "chiffres" sont les quatre bases azotées : l'adénine (A), la thymine (T), la cytosine (C) et la guanine (G). Dans le cadre des algorithmes génétiques, ce type de codage est bien difficile à utiliser et n'est donc pas retenu. Le principal problème qui se pose est celui concernant la conservation de la topologie du problème par le codage.

Codage binaire classique et codage de Gray

Historiquement le codage utilisé par les algorithmes génétiques était représenté sous forme de chaînes de bits contenant toute l'information nécessaire à la description d'un point dans l'espace d'état. Ce type de codage a pour intérêt de permettre de créer des opérateurs de croisement et de mutation simples (par inversion de bits par exemple). C'est également en utilisant ce type de codage que les premiers résultats de convergence théorique ont été obtenus. Néanmoins, ce type de codage ne conserve pas la topologie de départ. En effet, deux éléments voisins en terme de distance de Hamming (représente le nombre de bits dont diffèrent deux nombres binaires) ne codent pas nécessairement deux éléments proches dans l'espace de recherche : par exemple, dans le cas présenté sur la figure ci-dessus, les individus 1 et 2 sont proches mais ne le sont plus après transposition en binaire (« 001 » et « 010 », donc une distance de Hamming de 2), alors que « 1 » et « 3 » deviennent proches après codage binaire (« 001 » et « 011 »). On peut cependant remédier à ceci en utilisant le codage réfléchi (ou codage de Gray) qui conserve une distance de Hamming de « 1 » entre deux individus consécutifs quelconques, donc la topologie du problème. De plus, pour des problèmes d'optimisation dans des espaces de grande dimension, le codage binaire peut rapidement devenir mauvais. En effet, l'ordre des variables a une importance dans la structure du chromosome binaire, alors qu'il n'en a pas forcément dans la structure du problème. Enfin, la structure binaire empêche l'utilisateur d'accéder à une valeur particulière.

Malgré tout, il est dur de répondre à la question soulevée par ce problème, à savoir « Faut-il conserver la topologie de l’espace de recherche ? ». En effet, un codage qui conserve la topologie favorise généralement l’exploration, c’est-à-dire qu’il a essentiellement tendance à améliorer les individus lors de l’application des opérateurs génétiques. Au contraire, un codage qui ne conserve pas la topologie favorise plutôt l’exploration, car il est possible d’obtenir un individu très distant de ses parents lors d’un croisement ou d’une mutation. La question pourrait alors devenir : « Faut-il favoriser l’exploration ou l’exploitation ? ». C’est un des grands dilemmes des algorithmes génétiques qui met bien en avant la difficulté du problème du codage, et nous ne nous hasarderons pas à donner notre avis dessus.

2.1.4 Génération aléatoire de la population initiale

Si l'on n’a aucune idée de la position de l'optimum dans l'espace d'état, on génère aléatoirement des individus en faisant des tirages uniformes dans chacun des domaines associés aux composantes de l'espace d'état, en veillant à ce que les individus respectent les contraintes du problème. Si par contre on dispose d'informations a priori sur le problème indiquant un sous-domaine où l'on est sûr de trouver l'optimum, il faut alors générer les individus dans ce sous-domaine, afin d'accélérer la convergence. Dans l'hypothèse où cet objectif est trop difficile à atteindre, on peut tenir compte des contraintes en les incluant dans le critère sous forme de pénalités. Ainsi, un individu qui viole une contrainte se verra attribuer une mauvaise fitness et sera éliminé par le processus de sélection. L’avantage de cette solution est qu’elle permet de se passer des propriétés de connexité de l’espace des individus admissibles en assurant une probabilité non nulle de passer d’une population connexe à une autre.

A présent que nous disposons d'une population d'individus aléatoirement répartis, il nous faut être capable d'entretenir la diversité de la population au cours des générations, afin d'entretenir le processus d'exploration de l'espace d'état : c'est le rôle des opérateurs de sélection, de croisement et de mutation, que nous allons à présent aborder.

2.1.5 Principes de sélection

A l'inverse d'autres techniques d'optimisation, les algorithmes génétiques n'ont pas besoin de connaître la dérivée de la fonction objectif, ce qui rend leur domaine d'application plus vaste.

La sélection, comme son nom l'indique, permet d'identifier statistiquement les meilleurs individus d'une population et d'éliminer partiellement les mauvais. Néanmoins, comme dans la Nature, il ne faut pas confondre sélection et élitisme : ce n’est pas parce qu’un individu est bon qu’il survivra nécessairement (les aléas de la vie) et de même ce n’est pas parce qu’il est mauvais qu’il doit disparaître (la chance aide également à survivre). En effet, bien souvent, une espèce « bien adaptée » peut descendre d’un individu décrété « mauvais ». Il existe différents principes de sélection, dont on citera les deux plus classiques [Gol89] :

1. La « roulette wheel selection » (ou sélection par roulette de casino) : elle consiste à associer à chaque individu un segment dont la longueur est proportionnelle à sa fitness. Ces segments sont ensuite concaténés sur un axe gradué que l'on normalise entre 0 et 1. On tire alors un nombre aléatoire de distribution uniforme entre 0 et 1, puis on regarde quel est le segment sélectionné, et on reproduit l’individu correspondant. Avec cette technique, les bons individus seront plus souvent sélectionnés que les mauvais, et un même individu pourra avec cette méthode être sélectionné plusieurs fois. Néanmoins, sur des populations de petite taille, il est difficile d'obtenir exactement l'espérance mathématique de sélection à cause du faible nombre de tirages (le cas idéal d’application de cette méthode est bien évidemment celui où la population est de taille infinie). On aura donc un biais de sélection plus ou moins fort suivant la dimension de la population..
   
   

   Exemple d’application de la roulette wheel selection

2. La « stochastic remainder without replacement selection » : elle évite ce genre de problème, car une partie de la population est sélectionnée de manière purement déterministe. On associe à chaque individu le rapport ri de sa fitness sur la moyenne des fitness puis on prend sa partie entière E(ri) qui indique le nombre de fois à reproduire l’individu i. On assure ainsi un nombre exact de représentants pour la génération suivante, ce qui élimine le biais. Cependant, les individus faibles (fitness inférieure à la fitness moyenne) sont invariablement éliminés avec cette méthode, ce qui est mauvais, car ceux-ci occupent des positions dans l'espace d'état qui associées avec d'autres peuvent nous rapprocher du sous-domaine contenant l'optimum. On associe donc à la sélection déterministe un principe de sélection aléatoire basée sur une roulette wheel selection exécutée sur tous les individus affectés de nouvelles finesses ri-E(ri).

   Application de la stochastic remainder without replacement selection à l’exemple précédent

On ajoute également fréquemment un principe d’élitisme dans le processus de sélection destiné à conserver systématiquement le ou les meilleurs individus de la population courante dans la génération suivante, sans lui faire subir de croisement ou de mutation qui pourraient le détruire. Ce principe confère aussi à l’algorithme génétique la propriété de croissance monotone de la fitness du meilleur individu au cours des générations.

Les résultats issus de la théorie des schémas montrent que le principe de la roulette wheel selection offre le meilleur compromis entre exploration de l’espace de recherche et exploitation des informations obtenues. Cependant, les hypothèses nécessaires à ce résultat sont rarement satisfaites en pratique et les autres principes de sélection sont souvent plus efficaces.

2.1.6 Opérateur de croisement

Le croisement a pour but d'enrichir la diversité de la population en manipulant la structure des chromosomes [QP93, Sys89]. Classiquement, les croisements sont envisagés avec deux parents et génèrent deux enfants. Il consiste à échanger les gènes des parents afin de donner des enfants qui portent des propriétés combinées. Bien qu'il soit aléatoire, cet échange d'informations offre aux algorithmes génétiques une part de leur puissance : quelque fois, de " bons " gènes d'un parent viennent remplacer les " mauvais " gènes d'un autre et créent des fils mieux adaptés aux parents.

Initialement, le croisement utilisé avec les chaînes de bits était le croisement à découpages de chromosomes, ou slicing crossover. Pour effectuer ce type de croisement sur des chromosomes constitués de L gènes, on tire aléatoirement une position inter-gènes dans chacun des parents. On échange ensuite les deux sous-chaînes de chacun des chromosomes, ce qui produit deux enfants C1 et C2. Ce mécanisme présente l'inconvénient de privilégier les extrémités des individus. Et selon le codage choisi, il peut générer des fils plus ou moins proches de leurs parents. Pour éviter ce problème, on peut étendre ce principe en découpant le chromosome non pas en 2 sous-chaînes mais en 3, 4, etc [BG91]. On parle alors de k-point slicing crossover (figures ci-dessous).

a. Slicing crossover classique
b. 2-point slicing crossover

Ce type de croisement à découpage de chromosomes est très efficace pour les problèmes discrets, mais pour les problèmes continus ou des problèmes n'ayant pas recours au codage binaire (codage décimal, codage symbolique), on utilise de préférence un croisement de type barycentrique. Pour cela, on sélectionne deux gènes P1(i) et P2(i) dans chacun des parents à la même position i que l'on associe en pondération afin de créer deux nouveaux points sur la droite qui relie ces derniers : on crée ainsi C1(i) et C2(i),

C1(i) = a P1(i) + (1-a) P2(i)
C2(i) = (1-a) P1(i) + a P2(i)

où a est un coefficient de pondération aléatoire adapté au domaine de définition des gènes. Le croisement barycentrique permet, selon le domaine choisi pour a, de générer des points entre ou à l'extérieur des deux gènes considérés (on utilise ainsi souvent un intervalle de variation égal à [-0,5 ;1.5]).

Dans certains cas particuliers, où la fitness globale est calculée à l'aide d'un ensemble de sous-fitness associées à chacun des gènes, et si ces sous-fitness sont relativement indépendantes, on peut envisager de cibler (statistiquement) le croisement sur les gènes les moins bons [DAN94].

2.1.7 Opérateur de mutation

L'opérateur de mutation apporte aux algorithmes génétiques la propriété d'ergodicité de parcours de l'espace. Cette propriété indique que l'algorithme génétique sera susceptible d'atteindre tous les points de l'espace d'état (sans pour autant nécessairement les adresser tous dans le processus de résolution). En toute rigueur, l'algorithme peut converger sans croisement, et certaines variantes fonctionnent de cette manière, et les propriétés de convergence des algorithmes génétiques sont donc fortement dépendantes de cet opérateur.

Pour des problèmes discrets, l'opérateur de mutation consiste généralement à tirer aléatoirement un gène dans le chromosome et à remplacer ce dernier par une valeur tirée aussi aléatoirement de l'alphabet propre au gène sélectionné. Dans le cas du codage binaire, la méthode classique consiste, après avoir déterminé le locus à muter, d'appliquer un non logique à la valeur de l'allèle correspondant. Bien que ce déplacement puisse paraître petit au niveau des chaînes de bits, il peut être assez important dans la topologie initiale (considérons une mutation transformant " 000 " en " 100 " avec une topologie initiale basée sur la valeur décimale de la chaîne de bits). Ceci introduit un risque de ne pas générer la descendance dans le voisinage des parents. Dans les problèmes continus, on procède un peu de la même manière en tirant aléatoirement un gène dans le chromosome, auquel on ajoute un bruit aléatoire (par exemple un bruit gaussien) en veillant bien évidemment à ce que le gène résultant reste dans le domaine de définition qui lui est propre. L'écart type de ce bruit est délicat et difficile à régler : s'il est trop faible, l'exploration sera ralentie au début et on risque la convergence locale ; s'il est trop grand, les solutions seront modifiées trop brutalement et on ne pourra pas non plus converger localement vers l'optimum.

a. mutation discrète
b. mutation continue

Comme dans le cas du croisement, on peut imaginer de concentrer les mutations sur les gènes faibles lorsque le problème présente une fitness construite à l'aide d'un ensemble de sous-fitness associées à chacun des gènes.

Il existe également un principe de mutation adaptative, permettant d'optimiser le taux de mutation en codant ce dernier dans la structure du chromosome [Bac92]. Ce second chromosome est géré de la même manière que le premier chromosome codant l'espace d'état, c'est-à-dire lui-même soumis aux opérateurs génétiques (croisement et mutation). Au cours du déroulement de l'algorithme, les gènes et les individus ayant des probabilités de mutation élevées auront tendance à disparaître à mesure que la population converge vers l'optimum. De même, les gènes ayant des probabilités de mutation trop faibles ne peuvent évoluer favorablement et tendent à être supplantés.

Principe de la mutation auto-adaptative

Des opérateurs de mutation très efficaces qui effectuant une optimisation locale sont fréquemment utilisés. Par exemple, Marc Schoenauer a hybridé un algorithme génétique avec un algorithme déterministe de type Newton utilisé en lieu et place de l’opérateur de mutation, appelé Surrogate Deterministic Mutation [AbS].

2.2 Améliorations classiques

2.2.1 Introduction

Les processus de sélection que nous venons d'étudier sont très sensibles aux écarts de fitness et dans certains cas, un très bon individu risque d'être reproduit trop souvent et peut même provoquer l'élimination complète de ses congénères. On obtient alors une population homogène contenant un seul type d'individu. Par exemple, dans l'exemple suivant, le mode local (on utilise le terme « mode » pour désigner un optimum d'une fonction) risque d'être le seul reproduit pour la génération suivante, et seule la mutation pourra ensuite nous aider à atteindre l'objectif global, mais au prix de nombreuses générations supplémentaires.

Les sélections classiques risquent ici de ne reproduire qu’un seul individu

Pour éviter ce comportement très néfaste et pénalisant, il a été développé d'autres méthodes de sélection (notamment le ranking) et des principes (scaling, sharing) qui empêchent les génotypes « forts » d'éliminer totalement les « faibles ». Nous nous contenterons ici de décrire les mécanismes que nous avons utilisés dans nos recherches, à savoir le scaling et le sharing.

2.2.2 Le scaling

Les bons individus, se reproduisant mieux que les moins adaptés, risquent de dominer la population et d’empêcher une évolution équilibrée. Ceci se traduit par une convergence prématurée qui risque de mener la recherche dans un piège local : c’est le cas dans une fonction à fort gradient (à fortes variations). Inversement, si la fonction est à faible gradient, les individus les moins adaptés ne seront pas pénalisés et continuent à se reproduire de la même manière que les bons individus, ce qui empêche la population de converger.

a. Risque de convergence prématurée vers l’optimum local
b. Risque de reproduction forte des mauvais individus

Le scaling, ou mise à l'échelle, modifie les fitness afin de réduire ou d'amplifier artificiellement les écarts entre les individus. On se ramène en fait concrètement à une fitness à gradient modéré. Le processus de sélection ne travaille alors plus sur la fitness réelle fr mais sur son image après scaling, fs. Il existe diverses méthodes utilisées pour cette mise à l'échelle, par exemple le scaling linéaire ou le scaling exponentiel.

Scaling linéaire

Dans ce cas, la fonction de scaling est une fonction affine, dont le coefficient directeur est généralement inférieur à un, ce qui permet de réduire les écarts de fitness et donc de favoriser l'exploration de l'espace. Néanmoins, ce scaling est statique par rapport au numéro de génération et devient donc gênant en fin de convergence lorsqu'on désire favoriser les dominants pour accélérer le processus de recherche. Le scaling exponentiel permet d’éviter ce phénomène.

Scaling exponentiel

Le scaling exponentiel est défini de la façon suivante : fs = fr^k(n), où n représente le numéro de la génération courante. Il est nécessaire d'introduire un coefficient exposant variable, car les phénomènes résultant du scaling varient avec sa valeur.

1. Pour k proche de zéro, on réduit fortement les écarts de fitness. Aucun individu n'est vraiment favorisé et l'algorithme génétique se comporte comme un algorithme de recherche aléatoire et permet d'explorer l'espace.
2. Pour k proche de 1 : le scaling est presque inopérant. Les individus sont triés juste selon leur adaptabilité propre, quasiment non modifiée. Le scaling ne favorise aucun individu, mais n'en défavorise également aucun.
3. Pour k > 1 : les écarts sont exagérés et seuls les bons individus sont sélectionnés ce qui produit l'émergence des modes.

Dans la pratique, on fait donc varier k des faibles valeurs vers des valeurs fortes au cours des générations, en utilisant par exemple une formule de ce type (n est l’indice de la génération actuelle, N celui de la dernière génération à calculer).

Ce type de scaling donne de meilleurs résultats que le scaling linéaire.

2.2.3 Le sharing

De la même façon que le scaling, le sharing consiste à modifier la fitness utilisée par le processus de sélection. Pour éviter le rassemblement des individus autour d'un mode dominant, il faut pénaliser la fitness en fonction du taux d'agrégation de la population dans le voisinage d'un individu : plus les individus sont regroupés, plus leur fitness est faible, et des individus proches les uns des autres doivent partager leur fitness. Dans la pratique, pour estimer ce taux d'agrégation, on ouvre un domaine autour d'un individu, puis on calcule les distances entre les individus contenus dans ce voisinage et ce dernier. Il faut donc pouvoir définir une distance représentative entre deux individus, ce qui n’est pas toujours évident lorsqu’on manipule des structures de données complexes (des graphes ou des arbres, par exemple).

a. sans sharing : concentration des individus sur un seul mode
b. avec sharing : répartition des individus sur l’ensemble des modes

Dans la pratique, cette méthode donne de bons résultats, et favorise bien l'émergence des modes secondaires, mais au prix de n^² calculs supplémentaires par génération, où n représente la taille de la population.

2.3 Bilan et conclusions

2.3.1 Convergence théorique

Les premiers théorèmes de convergence stochastiques des algorithmes génétiques ont été établis par John Holland sur le codage par chaîne de bits avec la roulette wheel selection, le slicing crossover et la mutation classique. Ils utilisent la théorie des schémas : un schéma H de longueur l(H) est une séquence particulière de gènes de longueur l(H) représentée par une chaîne de caractères issus de l’alphabet {0,1,*} (pour le codage binaire), où * représente 0 ou 1. On dit qu’un chromosome A est une instance d’un certain schéma si la substitution des * par 0 ou 1 peut fournir un chromosome identique : ainsi, le chromosome 1010 est une instance des schémas 10**, 1**0 ou encore 101* (parmi d’autres). L’ordre o(H) d’un schéma est le nombre de symboles différents de * qu’il contient, et sa longueur fondamentale d(H) est la distance séparant les positions des symboles différents de * les plus proches des extrémités : les trois schémas de l’exemple précédent ont donc des ordres respectifs de 2, 2 et 3 ; des longueurs fondamentales respectives de 2, 4, 3. Enfin, l’adaptation f(H) (f pour fitness) d’un schéma est l’adaptation moyenne de toutes ses instances Ai, i entier dans [1,2^l(H)-o(H)] :

Le théorème des schémas explique et quantifie la manière dont sont manipulés les schémas par un algorithme génétique : le nombre m(H,t+1) de représentants du schéma H dans la population à la génération t+1 vérifie l’inéquation

où fm est la fitness moyenne des individus à la génération t et l = l(H) est la longueur commune fixée des chromosomes et des schémas. Ce résultat montre que le nombre de représentants d’un schéma dans la population suit une progression géométrique au cours des générations, et que les schémas favorisés sont ceux qui ont une fitness supérieure à la moyenne des fitness et un ordre ainsi qu’une longueur fondamentale faibles. D’autres résultats issus de la théorie des schémas montrent de plus qu’un algorithme génétique muni des trois opérateurs classiques réalise un compromis « quasi optimal » entre l’exploration de l’espace de recherche et l’exploitation des solutions déjà visitées. En outre, le nombre de schémas manipulés pour une population de taille n est de l’ordre de n³, propriété appelée le parallélisme implicite [Gol89].

Cependant, la démonstration de l’efficacité des algorithmes génétiques repose sur l’hypothèse des building blocks, c’est-à-dire de l’existence de schémas de longueur fondamentale et d’ordre faibles qui, incorporés au chromosome d’un individu, tentent de faire accroître sa fitness. Néanmoins, ces hypothèses sont en pratique peu probables sur des problèmes difficiles traités par les algorithmes génétiques, à moins de fournir un effort intensif lors du codage des données.

Hormis les nombreux raffinements sur la théorie des schémas, d’autres tentatives ont été conduites pour rendre compte des performances des algorithmes génétiques. Raphaël Cerf [Cer94] notamment présente des résultats de convergence asymptotique en utilisant une modélisation par les chaînes de Markov et la théorie de Freidlin-Wentzell sur les perturbations aléatoires de systèmes dynamiques, pour un algorithme génétique muni des trois opérateurs classiques avec des gènes sur des ensembles finis (et non pas binaires). Il montre que l’algorithme converge asymptotiquement vers tous les optima quand la population dépasse une taille critique dépendant fortement du problème d’optimisation, en utilisant la mutation et non pas le croisement comme opérateur prépondérant.

L ‘ensemble de ces théories est en outre la preuve d’un intérêt croissant pour les algorithmes génétiques et les algorithmes évolutionnistes en général.

2.3.2 Limitations des algorithmes génétiques

Comme nous l’avons dit précédemment, les algorithmes génétiques sont des outils efficaces pour une classe de problèmes très large. De plus, ils permettent de traiter des problèmes où la fonction à optimiser ne présente aucune propriété de continuité ou de dérivabilité, par exemple. Néanmoins, les sections précédentes mettent en avant un certain nombre de limitations à leur sujet :

1. Ils sont moins efficaces qu’un algorithme déterministe spécifique (lorsqu’il en existe un) dédié à un problème donné.
2. Les nombreux paramètres qui les contrôlent sont délicats à régler (probabilités de croisement et de mutation notamment), ainsi que le codage des chromosomes qui peut faire varier radicalement la vitesse de convergence.
3. Afin de garantir la robustesse des algorithmes évolutifs, le calcul d’un très grand nombre de fitness (parfois de l’ordre de plusieurs centaines de milliers) est généralement nécessaire avant l’obtention d’une bonne solution. Ce nombre de calcul important peut s’avérer problématique lorsque le coût de calcul (ressources systèmes ou temporelles) de la fitness est important, lorsqu’on travaille en grande dimension sur des fonctions à complexité importante par exemple.
4. Ils peuvent éprouver des difficultés à gérer des contraintes nombreuses et complexes car la technique des pénalités intégrées à la fonction de coût utilise des contraintes a posteriori de manière passive.

Références

Auteur : Matthieu D.

Date de mise en ligne : 2002-09-03

Réagir à cet article

Aucun commentaire pour l'instant.