Genetic algorithms : tout comprendre sur les algorithmes génétiques

Un algorithme génétique est une méthode d’optimisation qui imite les mécanismes de la sélection naturelle et vise à améliorer de manière itérative des populations de solutions potentielles. Les algorithmes génétiques sont utilisés dans une grande variété de domaines, allant de l’optimisation de systèmes techniques au Machine Learning.

Qu’entend-on par algorithmes génétiques ?

Les algorithmes génétiques, ou Genetic Algorithms (GA), sont une heuristique 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 algorithmes génétiques font partie des algorithmes évolutionnaires et utilisent des mécanismes inspirés des processus de sélection naturelle pour améliorer progressivement 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 concurrence pour les ressources et pour se reproduire.
2. Les individus les plus performants ou les plus forts engendrent plus de descendants que les autres.
3. Les gènes des parents les plus « en forme » sont transmis de génération en génération. Ils produisent ainsi souvent des descendants dont les séquences génétiques sont plus avantageuses que les leurs.
4. Comme les meilleurs gènes sont transmis à long terme, chaque génération est mieux adaptée à son environnement que la précédente.

Les algorithmes génétiques génèrent une population d’individus, chacun constituant une solution potentielle au problème posé. Ceux qui s’adaptent le mieux à leur environnement survivent et se reproduisent. Chaque individu est codé sous la forme d’un chromosome, exprimé comme une chaîne de caractères (que ce soit en caractères, bits, floats ou integers). Par ailleurs, ces chromosomes se décomposent en gènes, qui représentent des caractéristiques spécifiques, 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 rapprocher toujours plus de la solution optimale, les algorithmes génétiques lancent un processus itératif en plusieurs étapes de calcul et de reproduction. Les chromosomes sont modifiés et combinés sur plusieurs générations ou itérations par différents opérateurs génétiques (sélection, croisement ou recombinaison, mutation) afin de trouver progressivement de meilleures solutions. Cela signifie que les algorithmes génétiques se rapprochent d’une bonne solution globale par la combinaison de bonnes solutions partielles.

Comment fonctionnent les algorithmes génétiques ?

Le processus d’itération se divise typiquement en différentes tâches :

1. Le problème d’optimisation est encodé sous forme d’un chromosome binaire.
2. L’algorithme génétique crée une population d’individus et l’initialise de manière aléatoire. La population de départ est également appelée génération 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éfinie, l’algorithme génétique sélectionne des parents dans la population.
5. Les descendants sont créés sur la base des informations génétiques des deux parents.
6. Les caractéristiques génétiques des descendants (allèles) peuvent muter, ce qui entraîne l’inversion de leurs valeurs.
7. La population augmente en fonction des descendants nouvellement créés. Si la taille de la population dépasse la limite fixée, un schéma de remplacement 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’algorithme génétique répète les étapes 3 à 7 pour se rapprocher 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 différente. Certains algorithmes passent par un certain nombre de générations, tandis que d’autres sont actifs jusqu’à ce qu’il n’y ait plus d’amélioration par rapport à la génération précédente.

Score d’adaptation

Le score d’adaptation d’un individu indique sa compétitivité. L’objectif de l’algorithme 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électionnés pour engendrer une descendance. Il en résulte que les nouvelles générations ont en moyenne de meilleures solutions partielles que les précédentes.

Quels opérateurs utilisent les algorithmes génétiques ?

Les algorithmes génétiques font appel à différents opérateurs pour faire évoluer la population de départ. Les mécanismes de base qui permettent l’évolution sont la sélection, la recombinaison et la mutation. Les différents opérateurs des algorithmes 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 descendance et combien de descendants leur sont autorisés. La sélection des parents est basée sur le score d’aptitude physique, l’algorithme génétique favorisant les individus ayant de bons scores.

Recombinaison (opérateur d’enjambement ou de crossover)

De nouveaux individus sont créés par recombinaison. L’algorithme génétique choisit les sites de croisement au hasard. Les gènes sont ensuite échangés aux endroits correspondants, ce qui donne naissance à une descendance dotée de nouvelles caractéristiques. L’aperçu ci-dessous montre un exemple de recombinaison :

• 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 progéniture : A|B|I|J|K|F

Mutation (opérateur de mutation)

L’idée de base des mutations est d’introduire des modifications aléatoires dans certains gènes, et donc de modifier la solution potentielle d’un problème de décision. Cela permet de maintenir la diversité au sein de la population et d’éviter une convergence prématuré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 algorithmes génétiques sont-ils utilisés ?

Les algorithmes génétiques sont surtout utilisés dans des domaines où les méthodes analytiques traditionnelles atteignent leurs limites. C’est principalement le cas pour les problèmes avec un espace de solutions vaste et complexe. Par exemple, en Deep Learning, les algorithmes génétiques sont utilisés pour optimiser les poids des réseaux neuronaux.

Les algorithmes génétiques sont également utilisés dans la planification de la production, où ils permettent de trouver des horaires et des allocations de ressources optimales. Dans l’économie et la finance, les algorithmes génétiques sont utilisés aussi bien dans le cadre de l’optimisation des portefeuilles que pour le développement de stratégies commerciales complexes. Un autre domaine d’application est le réglage des hyperparamètres issus du Machine Learning. Bien qu’elles ne soient pas toujours la méthode la plus efficace, les algorithmes génétiques sont considérés comme une technique d’optimisation très polyvalente en raison de leur flexibilité.

Exemple d’application des algorithmes génétiques

Supposons que la tâche d’un algorithme génétique consiste à générer une chaîne de caractères cible, par exemple « The fittest survive », formée à partir d’une chaîne de caractères aléatoire de même longueur. Dans cet exemple, les différents caractères (A à Z, a à z, 0 à 9 et caractères spéciaux) représentent les gènes. La chaîne de caractères peut en revanche être considérée comme un chromosome ou une solution. Le score d’adaptation représente le nombre de caractères qui s’écartent de la chaîne de caractères cible. Par conséquent, les individus ayant un score faible sont favorisés. Le tableau suivant montre à quoi la sortie pourrait ressembler dans ce cas :

Il convient toutefois de noter que la sortie peut varier, du fait que l’algorithme génétique démarre avec des chaînes de caractères aléatoires.