Les algorithmes génétiques appartiennent à la famille 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 (ou que la solution est inconnue) pour le résoudre en un temps raisonnable. Les algorithmes génétiques s'inspirent de la notion de sélection naturelle et l'appliquent à une population de solutions potentielles au problème donné. La solution est approchée par « bonds » successifs, comme dans une procédure de séparation et évaluation (), à ceci près que ce sont des formules qui sont recherchées et non plus directement des valeurs.

Origines L'utilisation d'algorithmes génétiques, dans la résolution de problèmes, est à l'origine le fruit des recherches de John Holland et de ses collègues et élèves de l'Université du Michigan qui ont, dès 1960, travaillé sur ce sujet. La nouveauté introduite par ce groupe de chercheurs a été la prise en compte de l'opérateur d'enjambement () en complément des mutations. Et c'est cet opérateur qui permet le plus souvent de se rapprocher de l'optimum d'une fonction en combinant les gènes contenus dans les différents individus de la population. Le premier aboutissement de ces recherches a été la publication en 1975 de Adaptation in Natural and Artificial System.

La popularisation des algorithmes génétiques sera l'œuvre de David Goldberg à travers son livre Genetic Algorithms in Search, Optimization, and Machine LearningGenetic Algorithms in Search, Optimization, and Machine Learning, David Goldberg, Addison-Wesley Professional, 11 janvier 1989), (1989). Ce livre est encore édité aujourd'hui. En Europe, la première conférence sur ce type de sujet fut l'European Conference on Artificial Life en 1991 (elle a fêté ses 20 ans en 2011), coorganisée par Francisco Varela et Paul Bourgine. Un des premiers ouvrages à présenter en Français les algorithmes génétiques sera le livreIntelligence Artificielle et Informatique Théorique, Jean-Marc Alliot, Thomas Schiex, Éditions Cepadues, 1993, Intelligence Artificielle et Informatique Théorique qui lui consacrera un chapitre dès 1993. La première conférence francophone avec actesEvolution Artificielle 94, 20-23 septembre 1994, ENAC, Toulouse, Jean-Marc Alliot,Evelyne Lutton, Marc Schoenauer, Publisher: Cépaduès Éditions 1995, sur le sujet sera organisée en 1994 par Jean-Marc Alliot (IRIT), Evelyne Lutton (INRIA), Marc Schoenauer (INRIA) et Edmund Ronald.

Présentation Analogie avec la biologie Terminologie commune aux deux disciplines

Les algorithmes génétiques étant basés sur des phénomènes biologiques, il convient de rappeler au préalable quelques termes de génétique.

Les organismes vivants sont constitués de cellules, dont les noyaux comportent des chromosomes qui sont des chaînes d'ADN. L'élément de base de ces chaînes est un nucléotide, identifié par sa base azotée (A, T, C ou G). Sur chacun de ces chromosomes, une suite de nucléotides constitue une chaîne qui code les fonctionnalités de l'organisme (la couleur des yeux par exemple). Ainsi, un gène est une phrase fonctionnelle le long de la chaîne. La position d'un gène sur le chromosome est son locus. L'ensemble des gènes d'un individu est son génotype et l'ensemble du patrimoine génétique d'une espèce est le génome. Les différentes versions d'un même gène sont appelées allèles.

On utilise aussi, dans les algorithmes génétiques, une analogie avec la théorie de l'évolution qui propose qu'au fil du temps, les gènes conservés au sein d'une population donnée sont ceux qui sont le plus adaptés aux besoins de l'espèce vis-à-vis de son environnement. En effet, certaines variations de gènes confèrent aux individus les possédant un avantage compétitif par rapport au reste de la population. Cet avantage compétitif se traduit alors par une meilleure reproduction de ces individus qui permet de transmettre les allèles à l'ensemble de la population après de nombreuses générations.

Outils bioinspirés (issus de la biologie) La génétique a mis en évidence l'existence de processus importants au sein d'un groupe d'organismes d'une même espèce (ou d'espèces proches chez les bactéries) donnant lieu au brassage génétique. Ces processus interviennent lors de la phase de reproduction lorsque les chromosomes de deux organismes fusionnent en créant un nouvel organisme.

Ces opérations sont « imitées » par les algorithmes génétiques afin de faire évoluer les populations de solutions de manière progressive.

Sélection Pour déterminer quels individus sont plus enclins à obtenir les meilleurs résultats, une sélection est opérée. Ce processus est analogue à un processus de sélection naturelle, les individus les plus adaptés gagnent la compétition de la reproduction tandis que les moins adaptés meurent avant la reproduction, ce qui améliore globalement l'adaptation. Étant donné que la sélection est le résultat d'une intervention humaine ou, du moins, l'application d'un critère défini par l'homme, les algorithmes génétiques devraient donc plutôt être rapprochés de la telle que la pratiquent les agriculteurs que de la sélection naturelle, qui œuvre « en aveugle ».

Enjambement, croisement ou recombinaison Lors de cette opération, deux chromosomes s'échangent des parties de leurs chaînes, pour donner de nouveaux chromosomes. Ces enjambements peuvent être simples ou multiples. Dans le premier cas, les deux chromosomes se croisent et s'échangent des portions d'ADN en un seul point. Dans le deuxième cas, il y a plusieurs points de croisement. Pour les algorithmes génétiques, c'est cette opération (le plus souvent sous sa forme simple) qui est prépondérante. Sa probabilité d'apparition lors d'un croisement entre deux chromosomes est un paramètre de l'algorithme génétique et dépend du problème et de la technique de recombinaison.

Mutations De façon aléatoire, un gène peut, au sein d'un chromosome, être substitué à un autre. De la même manière que pour les enjambements, on définit ici un taux de mutation lors des changements de population qui est généralement compris entre 0,001 et 0,01. Il est nécessaire de choisir pour ce taux une valeur relativement faible, de manière à ne pas tomber dans une recherche aléatoire et à conserver le principe de sélection et d'évolution. La mutation sert à éviter une convergence prématurée de l'algorithme. Par exemple, lors d'une recherche d'extremum, la mutation sert à éviter la convergence vers un extremum local.

Principe Les algorithmes génétiques, afin de permettre la résolution de problèmes, se basent sur les différents principes décrits ci-dessus. Le problème théorique de la convergence a été résoluRaphaël Cerf, Une théorie asymptotique des algorithmes génétiques, thèse de doctorat, Université Montpellier-II (France), 1994. par Raphaël Cerf, en se basant sur la théorie de et des perturbations stochastiques des systèmes dynamiques. La démonstration de Cerf montre d'ailleurs que le processus de convergence dépend essentiellement de la mutation, le croisement pouvant être éliminé en théorie. Cependant, la preuve théorique de convergence n'a que peu d'utilité dans la pratique, où l'opérateur de croisement fait bien souvent toute la richesse de l'algorithme génétique par rapport à des méthodes de type recuit simulé.

De manière globale, on commence avec une population de base qui se compose le plus souvent de chaînes de caractères correspondant chacune à un chromosome. Nous reviendrons par la suite sur les différentes structures de données possibles (voir Codage) mais nous retiendrons pour le moment l'utilisation du codage binaire (ex. : 0100110).

Le contenu de cette population initiale est généré aléatoirement. On attribue à chacune des solutions une note qui correspond à son adaptation au problème. Ensuite, on effectue une sélection au sein de cette population.

Il existe plusieurs techniques de sélection. Voici les principales utilisées :

Sélection par rang Cette technique de sélection choisit toujours les individus possédant les meilleurs scores d'adaptation, le hasard n'entre donc pas dans ce mode de sélection. En fait, si n individus constituent la population, la sélection appliquée consiste à conserver les k meilleurs individus (au sens de la fonction d'évaluation) suivant une probabilité qui dépend du rang (et pas de la fonction d'évaluation).

Probabilité de sélection proportionnelle à l'adaptation Appelé aussi « roulette » ou « roue de la fortune », pour chaque individu, la probabilité d'être sélectionné est proportionnelle à son adaptation au problème. Afin de sélectionner un individu, on utilise le principe de la roue de la fortune biaisée. Cette roue est une roue de la fortune classique sur laquelle chaque individu est représenté par une portion proportionnelle à son adaptation. On effectue ensuite un tirage au sort homogène sur cette roue.

Sélection par tournoi Cette technique utilise la sélection proportionnelle sur des paires d'individus, puis choisit parmi ces paires l'individu qui a le meilleur score d'adaptation.

Sélection uniforme La sélection se fait aléatoirement, uniformément et sans intervention de la valeur d'adaptation. Chaque individu a donc une probabilité 1/P d'être sélectionné, où P est le nombre total d'individus dans la population.

Lorsque deux chromosomes ont été sélectionnés, on réalise un croisement. On effectue ensuite des mutations sur une faible proportion d'individus, choisis aléatoirement. Ce processus nous fournit une nouvelle population. On réitère le processus un grand nombre de fois de manière à imiter le principe d'évolution, qui ne prend son sens que sur un nombre important de générations. On peut arrêter le processus au bout d'un nombre arbitraire de générations ou lorsqu'une solution possède une note suffisamment satisfaisante.

Considérons par exemple les deux individus suivants dans une population où chaque individu correspond à une chaîne de 8 bits : et . On ajuste la probabilité d'enjambement à 0,7 ( alors on va croiser 6 bits sur les 8 bits des deux mots). Chromosome ContenuA 00:110010B 01:010100A′ 00 010100B′ 01 110010 Supposons ici que l'enjambement ait lieu, on choisit alors aléatoirement la place de cet enjambement (toutes les places ayant la même probabilité d'être choisies). En supposant que l'enjambement ait lieu après le deuxième allèle, on obtient A′ et B′ (« : » marquant l'enjambement sur A et B). Ensuite, chacun des gènes des fils (ici, chacun des bits des chaînes) est sujet à la mutation. De la même manière que pour les combinaisons, on définit un taux de mutation (très bas, de l'ordre de 0,001 – ici on peut s'attendre à ce que A′ et B′ restent identiques).

En effectuant ces opérations (sélection de deux individus, enjambement, mutation), un nombre de fois correspondant à la taille de la population divisée par deux, on se retrouve alors avec une nouvelle population (la première génération) ayant la même taille que la population initiale, et qui contient globalement des solutions plus proches de l'optimum. Le principe des algorithmes génétiques est d'effectuer ces opérations un maximum de fois de façon à augmenter la justesse du résultat.

Il existe plusieurs techniques qui permettent éventuellement d'optimiser ces algorithmes, on trouve par exemple des techniques dans lesquelles on insère à chaque génération quelques individus non issus de la descendance de la génération précédente mais générés aléatoirement. Ainsi, on peut espérer éviter une convergence vers un optimum local.

Codage d'un algorithme génétique Pour les algorithmes génétiques, un des facteurs les plus importants, si ce n'est le plus important, est la façon dont sont codées les solutions (ce que l'on a nommé ici les chromosomes), c'est-à-dire les structures de données qui coderont les gènes.

Codage binaire