Genetic al­go­rithms : tout com­prendre sur les al­go­rithmes gé­né­tiques

Un al­go­rithme génétique est une méthode d’op­ti­mi­sa­tion qui imite les mé­ca­nismes de la sélection naturelle et vise à améliorer de manière itérative des po­pu­la­tions de solutions po­ten­tielles. Les al­go­rithmes gé­né­tiques sont utilisés dans une grande variété de domaines, allant de l’op­ti­mi­sa­tion de systèmes tech­niques au Machine Learning.

Qu’entend-on par al­go­rithmes gé­né­tiques ?

Les al­go­rithmes gé­né­tiques, ou Genetic Al­go­rithms (GA), sont une heu­ris­tique globale pour résoudre des problèmes de décision, basée sur les principes de la sélection naturelle et de la génétique. Les al­go­rithmes gé­né­tiques font partie des al­go­rithmes évo­lu­tion­naires et utilisent des mé­ca­nismes inspirés des processus de sélection naturelle pour améliorer pro­gres­si­ve­ment les solutions à des problèmes complexes. Cela signifie que l’on simule la « survie des plus aptes », qui repose sur les principes suivants :

1. Les individus sont en con­cur­rence pour les res­sources et pour se re­pro­duire.
2. Les individus les plus per­for­mants ou les plus forts en­gendrent plus de des­cen­dants que les autres.
3. Les gènes des parents les plus « en forme » sont transmis de gé­né­ra­tion en gé­né­ra­tion. Ils pro­dui­sent ainsi souvent des des­cen­dants dont les séquences gé­né­tiques sont plus avan­ta­geuses que les leurs.
4. Comme les meilleurs gènes sont transmis à long terme, chaque gé­né­ra­tion est mieux adaptée à son en­vi­ron­ne­ment que la pré­cé­dente.

Les al­go­rithmes gé­né­tiques génèrent une po­pu­la­tion d’individus, chacun cons­ti­tuant une solution po­ten­tielle au problème posé. Ceux qui s’adaptent le mieux à leur en­vi­ron­ne­ment survivent et se re­pro­dui­sent. Chaque individu est codé sous la forme d’un chro­mo­some, exprimé comme une chaîne de ca­rac­tères (que ce soit en ca­rac­tères, bits, floats ou integers). Par ailleurs, ces chro­mo­somes se dé­com­po­sent en gènes, qui re­pré­sen­tent des ca­rac­té­ris­tiques spé­ci­fiques, telles que la couleur des cheveux. Les variantes d’un gène, par exemple blond, brun ou noir, sont appelées allèles.

Pour se rap­pro­cher toujours plus de la solution optimale, les al­go­rithmes gé­né­tiques lancent un processus itératif en plusieurs étapes de calcul et de re­pro­duc­tion. Les chro­mo­somes sont modifiés et combinés sur plusieurs gé­né­ra­tions ou ité­ra­tions par dif­fé­rents opé­ra­teurs gé­né­tiques (sélection, croi­se­ment ou re­com­bi­nai­son, mutation) afin de trouver pro­gres­si­ve­ment de meil­leures solutions. Cela signifie que les al­go­rithmes gé­né­tiques se rap­prochent d’une bonne solution globale par la com­bi­nai­son de bonnes solutions par­tielles.

Comment fonc­tion­nent les al­go­rithmes gé­né­tiques ?

Le processus d’itération se divise ty­pi­que­ment en dif­fé­rentes tâches :

1. Le problème d’op­ti­mi­sa­tion est encodé sous forme d’un chro­mo­some binaire.
2. L’al­go­rithme génétique crée une po­pu­la­tion d’individus et l’ini­tia­lise de manière aléatoire. La po­pu­la­tion de départ est également appelée gé­né­ra­tion 0.
3. Chaque individu se voit attribuer un score d’aptitude sous la forme d’un nombre réel.
4. À l’aide d’une variante de sélection pré­dé­fi­nie, l’al­go­rithme génétique sé­lec­tionne des parents dans la po­pu­la­tion.
5. Les des­cen­dants sont créés sur la base des in­for­ma­tions gé­né­tiques des deux parents.
6. Les ca­rac­té­ris­tiques gé­né­tiques des des­cen­dants (allèles) peuvent muter, ce qui entraîne l’inversion de leurs valeurs.
7. La po­pu­la­tion augmente en fonction des des­cen­dants nou­vel­le­ment créés. Si la taille de la po­pu­la­tion dépasse la limite fixée, un schéma de rem­pla­ce­ment détermine quels individus ne font désormais plus partie de l’ensemble des solutions.
8. Tant qu’aucun critère d’arrêt n’est rempli, l’al­go­rithme génétique répète les étapes 3 à 7 pour se rap­pro­cher toujours plus de la solution optimale du problème. Le critère d’arrêt peut toutefois être conçu de manière très dif­fé­rente. Certains al­go­rithmes passent par un certain nombre de gé­né­ra­tions, tandis que d’autres sont actifs jusqu’à ce qu’il n’y ait plus d’amé­lio­ra­tion par rapport à la gé­né­ra­tion pré­cé­dente.

Score d’adap­ta­tion

Le score d’adap­ta­tion d’un individu indique sa com­pé­ti­ti­vité. L’objectif de l’al­go­rithme génétique est de repérer l’individu avec l’aptitude optimale (ou presque). Les individus ayant de meilleurs scores ont plus de chances d’être sé­lec­tion­nés pour engendrer une des­cen­dance. Il en résulte que les nouvelles gé­né­ra­tions ont en moyenne de meil­leures solutions par­tielles que les pré­cé­dentes.

Quels opé­ra­teurs utilisent les al­go­rithmes gé­né­tiques ?

Les al­go­rithmes gé­né­tiques font appel à dif­fé­rents opé­ra­teurs pour faire évoluer la po­pu­la­tion de départ. Les mé­ca­nismes de base qui per­met­tent l’évolution sont la sélection, la re­com­bi­nai­son et la mutation. Les dif­fé­rents opé­ra­teurs des al­go­rithmes gé­né­tiques sont présentés plus en détail ci-dessous.

Sélection (opérateur de sélection)

La sélection détermine quels individus sont autorisés à engendrer une des­cen­dance et combien de des­cen­dants leur sont autorisés. La sélection des parents est basée sur le score d’aptitude physique, l’al­go­rithme génétique fa­vo­ri­sant les individus ayant de bons scores.

Re­com­bi­nai­son (opérateur d’en­jam­be­ment ou de crossover)

De nouveaux individus sont créés par re­com­bi­nai­son. L’al­go­rithme génétique choisit les sites de croi­se­ment au hasard. Les gènes sont ensuite échangés aux endroits cor­res­pon­dants, ce qui donne naissance à une des­cen­dance dotée de nouvelles ca­rac­té­ris­tiques. L’aperçu ci-dessous montre un exemple de re­com­bi­nai­son :

• Gènes du parent 1 : A|B|C|D|E|F
• Gènes du parent 2 : G|H|I|J|K|L
• Gènes de la pro­gé­ni­ture : A|B|I|J|K|F

Mutation (opérateur de mutation)

L’idée de base des mutations est d’in­tro­duire des mo­di­fi­ca­tions aléa­toires dans certains gènes, et donc de modifier la solution po­ten­tielle d’un problème de décision. Cela permet de maintenir la diversité au sein de la po­pu­la­tion et d’éviter une con­ver­gence pré­ma­tu­rée. Voici un exemple de mutation :

• Gènes avant la mutation : A|B|C|D|E|F
• Gènes après mutation : A|B|L|D|T|F

Dans quels domaines les al­go­rithmes gé­né­tiques sont-ils utilisés ?

Les al­go­rithmes gé­né­tiques sont surtout utilisés dans des domaines où les méthodes ana­ly­tiques tra­di­tion­nelles at­teig­nent leurs limites. C’est prin­ci­pa­le­ment le cas pour les problèmes avec un espace de solutions vaste et complexe. Par exemple, en Deep Learning, les al­go­rithmes gé­né­tiques sont utilisés pour optimiser les poids des réseaux neuronaux.

Les al­go­rithmes gé­né­tiques sont également utilisés dans la pla­ni­fi­ca­tion de la pro­duc­tion, où ils per­met­tent de trouver des horaires et des al­lo­ca­tions de res­sources optimales. Dans l’économie et la finance, les al­go­rithmes gé­né­tiques sont utilisés aussi bien dans le cadre de l’op­ti­mi­sa­tion des por­te­feuilles que pour le dé­ve­lop­pe­ment de stra­té­gies com­mer­ciales complexes. Un autre domaine d’ap­pli­ca­tion est le réglage des hy­per­pa­ra­mètres issus du Machine Learning. Bien qu’elles ne soient pas toujours la méthode la plus efficace, les al­go­rithmes gé­né­tiques sont con­si­dé­rés comme une technique d’op­ti­mi­sa­tion très po­ly­va­lente en raison de leur flexi­bi­lité.

Exemple d’ap­pli­ca­tion des al­go­rithmes gé­né­tiques

Supposons que la tâche d’un al­go­rithme génétique consiste à générer une chaîne de ca­rac­tères cible, par exemple « The fittest survive », formée à partir d’une chaîne de ca­rac­tères aléatoire de même longueur. Dans cet exemple, les dif­fé­rents ca­rac­tères (A à Z, a à z, 0 à 9 et ca­rac­tères spéciaux) re­pré­sen­tent les gènes. La chaîne de ca­rac­tères peut en revanche être con­si­dé­rée comme un chro­mo­some ou une solution. Le score d’adap­ta­tion re­pré­sente le nombre de ca­rac­tères qui s’écartent de la chaîne de ca­rac­tères cible. Par con­sé­quent, les individus ayant un score faible sont favorisés. Le tableau suivant montre à quoi la sortie pourrait res­sem­bler dans ce cas :

Il convient toutefois de noter que la sortie peut varier, du fait que l’al­go­rithme génétique démarre avec des chaînes de ca­rac­tères aléa­toires.