Les algorithmes génétiques (AG) sont des algorithmes d’optimisation stochastique fondés sur les mécanismes de la sélection naturelle et de la génétique. Ils ont été initialement développés par John Holland (1975/1992)[Holland, 1992], mais c’est à un livre (tiré de sa thèse) d’un doctorant de Holland [Goldberg, 1994] que nous devons leur popularisation. Leurs champs d’application sont très vastes. Outre leurs applications plus spécifiques en économie [69], les AG sont utilisés en programmation génétique, en théorie du contrôle optimal, ou encore en théorie des jeux répétés et dynamiques, ainsi que pour l’optimisation de fonctions mal formée. Les raisons de ce grand nombre d’applications sont la simplicité et l’efficacité de ces algorithmes.

Les AG s’inspirent des mécanismes de l’évolution biologique et les utilisent pour la recherche de solutions adaptées au problème qu’on cherche à résoudre. L’évolution biologique procède en sélectionnant des génotypes (intégrés aux chromosomes), sur la base de l’adaptation relative à leur environnement des phénotypes qu’ils génèrent (la qualité de cette adaptation est alors mesurée par la performance –fitness – relative des phénotypes correspondant à ces génotypes). Les génotypes qui sont les mieux adaptés à leur environnement ont une plus grande facilité à se reproduire et la reproduction sexuée assure le croisement des gènes les plus performants dans la population. Les erreurs de copies de chromosomes pendant la reproduction introduisent par ailleurs de la nouveauté en provoquant des mutations au niveau des gènes, avec les conséquences que cela entraine au niveau du phénotype correspondant. La sélection continue des génotypes avec la performance relative la plus élevée conduit à une amélioration de l’adaptation de cette population à son environnement (cela correspond alors à une augmentation de la performance –fitness– moyenne dans cette population).

Les AG cherchent à reproduire ce processus. La relation qui existe entre les génotypes et les phénotypes correspond alors au codage qu’on retient pour l’espace des paramètres du problème qu’on cherche à résoudre. Les valeurs possibles d’une variable réelle ou entière seront par exemple codées sous la forme d’une chaine binaire, équivalente aux chromosomes des génotypes, formée de $0$ et de $1$ . La forme canonique des AG manipule donc des chaines binaires. Les différentes chaines peuvent représenter les différents états d’un système (ou d’une commande). On peut aussi les utiliser pour représenter n’importe quelle variable discrète. Nous pouvons ainsi coder les nombres entiers dans le codage binaire où la chaîne binaire $\mathbf{1101}$ représente l’entier $13$  : $$\left[\begin{array}{ccccccc} 2^{3} & & 2^{2} & & 2^{1} & & 2^{0}\\ 1 & & 1 & & 0 & & 1 \end{array}\right]\rightarrow\left(\boldsymbol{1}\ast2^{3}\right)+\left(\mathbf{1}\ast2^{2}\right)+\left(\mathbf{0}\ast2^{1}\right)+\left(\mathbf{1}\ast2^{0}\right)=8+4+0+1=13$$

Dans sa version la plus simple, à une variable de contrôle, l’algorithme génétique fera évoluer une population de chromosomes, aléatoirement initialisée, sur la base de la performance relative de chacun d’eux dans le problème en considération. Le croisement et la mutation interviendront alors dans cette population de chromosomes pour permettre l’exploration de l’espace des valeurs de la variable considérée. En établissant une pression sélective forte sur cette population, l’AG cherche à orienter le processus d’évolution dans le sens d’une optimisation, de préférence globale. Comme nous l’avons déjà discuté dans le chapitre précédent, ici l’évolution est délibérément conditionnée vers l’optimisation car l’adaptation au milieu (le fitness) est directement définie comme la capacité à maximiser la valeur de la fonction objective.

Les AG sont basés sur des mécanismes très simples (manipulations élémentaires de chaînes binaires). Ils sont robustes car ils peuvent résoudre des problèmes fortement non-linéaires et discontinus, et efficaces car ils mettent en oeuvre un parallélisme de recherche, en faisant évoluer non pas une solution potentielle unique, mais toute une population de solutions potentielles.

A l’inverse des méthodes traditionnelles de résolutions numériques, de type gradient par exemple, les AG ne sont pas basés sur une approche analytique mais sur une approche itérative et heuristique. En cela, leur utilisation nécessite peu d’information : l’espace de recherche possible et un critère d’efficacité correspondant au fitness. Ces propriétés fort vertueuses et la facilité de leur mise en application ont conduit à un nombre croissant de travaux en économie et en finance ces dernières années.

A un niveau très général, le fonctionnement d’un AG est alors basé sur les phases suivantes (voir Figure 7.4↑ pour un exemple délibérément très simple) :

Il existe plusieurs méthodes pour représenter la reproduction. La méthode la plus connue et la plus utilisée est sans nul doute, la sélection par roulette biaisée (roulette wheel) de [Goldberg, 1994]. Selon cette méthode, chaque chromosome sera dupliqué dans une nouvelle population proportionnellement à sa performance relative par rapport à la moyenne de la population. La sélection par tournoi est aussi une méthode souvent utilisée. Dans ce cas, un chromosome qui sort gagnant de ses rencontres avec d’autres chromosomes, car il a un fitness plus élevé, est reconduit dans la nouvelle population.

Dans notre exemple (voir Figure 7.5↑) un croisement localisé à la troisième position a eu lieu entre les individus 2 et 3. Ce la permet dans ce cas, la création de deux nouveaux individus (solutions potentielles) dans la population. Toutefois, un individu sélectionné lors de la reproduction ne subit pas nécessairement l’action d’un croisement. Ce dernier ne s’effectue qu’avec une certaine probabilité. Plus cette probabilité est élevée et plus la population subira de changement. On peut aussi imaginer que le croisement a lieu entre plusieurs zones différentes des chaînes (plutôt qu’entre deux zones seulement comme dans cet exemple).

Quoi qu’il en soit, il se peut que l’action conjointe de la reproduction et du croisement soit insuffisante pour assurer la capacité de l’AG à correctement explorer l’espace des solutions potentielles et à déterminer les solutions optimales. Ainsi, dans le cas du codage binaire, certaines chaînes peuvent totalement disparaître de la population. Par exemple si aucun individu de la population initiale ne contient de $1$ en dernière position de la chaîne, et que cette valeur fasse partie de la chaîne optimale à trouver, aucun croisement ne peut faire apparaitre cet élément. Ce dernier ne peut s’introduire dans la population que si l’on permet l’expérimentation au hasard et c’est, entre autre, pour remédier à ce problème que l’opérateur de mutation est utilisé.

Dans notre exemple de la Figure 7.4↑, une mutation a eu lieu, à l’étape (e), en deuxième position du premier chromosome et elle a transformé ce bit de zéro à un.

La mutation est traditionnellement considérée comme un opérateur intervenant à la marge, dans la mesure où sa probabilité est en général fixée assez faible (de l’ordre de 1%). Mais elle confère aux algorithmes génétiques une propriété très importante : l’ergodicité (i.e. tous les points de l’espace de recherche peuvent être atteints). Cet opérateur est donc d’une grande importance et il est loin d’être marginal. Il a de fait un double rôle : celui d’effectuer une recherche locale et/ou de sortir d’une trappe (optima locaux).

Comme pour l’évolution biologique, ces algorithmes ne conduisent pas toujours à l’optimum recherché. Un des problèmes les plus courant est la convergence prématurée qui correspond à une homogénéisation trop rapide de la population, de sorte que la sélection ne puisse améliorer la performance globale du système. S’il n’y a que des solutions très mauvaises en concurrence, il n’y a aucune raison qu’une solution meilleure domine la population. Le mécanisme de mutation cherche notamment à éliminer ce problème en introduisant des nouveautés dans le système.

Liens :

Les AG et d’autres algorithmes qui s’en inspirent (les système classificateurs, les programmes génétiques, etc.) mobilisent donc l’algorithme de l’évolution pour résoudre un ensemble très large de problèmes. Cela démontre à la fois la nature algorithmique de l’idée de Darwin et la puissance des opérations simples répétées de manière successive. Cette puissance est aussi derrière le développement de l’approche évolutionniste en économie.