🌿 Introduction aux Algorithmes Génétiques (AG)
Un algorithme génétique (AG) est une méthode d’optimisation inspirée de la théorie de l’évolution de
Darwin, où seules les solutions les plus adaptées survivent et se reproduisent.
L’idée centrale est simple : simuler un processus évolutif pour trouver la meilleure solution à un
problème. Pour cela, on utilise quatre mécanismes principaux : fitness, sélection, croisement, et
mutation. Voyons chacun en détail.
Pourquoi les utiliser ?
- Pour résoudre des problèmes où les méthodes classiques (gradient, programmation linéaire) ne
fonctionnent pas bien.
- Très utiles dans les environnements complexes avec de nombreux minima locaux.
⚙ Principes de base
Un AG manipule une population d’individus (solutions potentielles), chacun représenté par un
chromosome.
Terminologie
Chromosome : En biologie, il est dé.ni comme le porteur de l’information génétique nécessaire à la
construction et au fonctionnement d’un organisme. Dans le cadre des AG, il correspond à un élément
représentant une solution possible d’un problème donné.
Gène : En biologie, il représente une partie du chromosome, chaque chromosome est constitué d’un
certain nombre de gènes. Pour un AG, chaque chromosome est divisé en un ensemble d’unités le
constituant appelé gènes.
Génotype : Dans les systèmes naturels, l’ensemble du "matériel" génétique est appelé le génotype.
Dans les AG, l’ensemble des chaînes est appelé structure.
Phénotype : Dans les systèmes naturels, l’organisme formé par l’interaction de l’ensemble du
"matériel" génétique avec son environnement est appelé phénotype. Dans les AG, les structures
décodées forment un ensemble de paramètres donnés, ou solutions ou bien points de l’espace des
solutions.
Allèle : Dans les systèmes naturels, l’allèle est une composante du gène. Les allèles sont les déférentes
valeurs que peuvent prendre les gènes. Dans les AG, l’allèle est également appelé valeur
caractéristique.
Locus : Le locus est la position d’un gène dans le chromosome.
Individu : En biologie un individu est une forme qui est le produit de l’activité des gènes. Pour un AG,
il est réduit à un chromosome et on l’appelle donc chromosome ou individu pour désigner un même
objet.
Population : Dans un système naturel, une population est simplement un ensemble d’individus. Par
analogie, elle se définit comme l’ensemble des chromosomes. Elle est aussi appelée une génération.
Parents : Dans un système naturel, les individus peuvent se reproduire en créant de nouveaux
individus formant une nouvelle génération afin d’assurer la continuité de la vie.
Étapes clés
1. Initialisation
Une population initiale (aléatoire ou heuristique) est générée.
2. Évaluation (fitness)
Chaque individu est évalué selon une fonction d’adaptation (fitness function).
La fitness mesure la qualité ou l’aptitude d’une solution dans le contexte du problème donné.
- Chaque solution possible est représentée par un chromosome (une suite de données codées, souvent
sous forme binaire).
- La fitness évalue la performance de cette solution selon une fonction spécifique, appelée fonction
d’aptitude.
Exemple : Si le problème est de maximiser la fonction ( f(x) = x^2 ) sur un intervalle donné, alors :
- Si un chromosome représente ( x = 5 ), sa fitness sera ( f(5) = 25 ).
- Plus la fitness est élevée, meilleure est la solution.
Objectif : guider l’algorithme vers les régions prometteuses de l’espace de recherche.
3. Sélection
La sélection consiste à choisir les individus qui participeront à la création de la prochaine génération.
L’idée est simple : les individus avec une fitness élevée ont plus de chances d’être choisis pour se
reproduire. C’est une forme de sélection naturelle.
Méthodes courantes :
- Roulette wheel (Roulette) : la probabilité qu'un individu soit choisi est proportionnelle à sa fitness.
- Tournoi : on sélectionne un sous-ensemble au hasard et on prend le meilleur.
- Élite : on garde directement les meilleurs individus sans modification.
Exemple : Si on a 4 individus avec des fitness de 10, 30, 50 et 70, celui ayant une fitness de 70 a plus
de chances d’être choisi pour se reproduire.
Objectif : privilégier les bonnes solutions tout en laissant une chance (minime) aux solutions moins
performantes pour maintenir la diversité.
4. Croisement (crossover)
Deux individus parents échangent des parties de leurs chromosomes pour créer une descendance.
Le croisement consiste à combiner deux parents pour créer une descendance, dans l’espoir qu’elle
hérite des bonnes caractéristiques des deux.
Techniques courantes :
- Croisement à un point (One-point crossover) : on coupe les deux chromosomes à un point
aléatoire et on échange les segments.
- Croisement à deux points : deux points de coupure pour mélanger encore plus les données.
- Croisement uniforme : chaque gène de l’enfant a 50% de chances de venir du parent 1 ou du
parent 2.
Exemple (avec des chromosomes binaires) : Parents : ( P1 = 10101), ( P2 = 11000 )
Croisement à un point : Point de coupe après le 2ᵉ bit : Enfants : ( 10100 ) et ( 11001 )
Objectif : explorer de nouvelles solutions en combinant les caractéristiques des parents.
5. Mutation
La mutation introduit une légère modification aléatoire dans un chromosome, généralement en
changeant un ou plusieurs de ses gènes.
- Elle a un rôle clé pour prévenir la stagnation (éviter que l’algorithme reste coincé dans un minimum
local).
- La mutation est appliquée avec une faible probabilité pour ne pas déstabiliser l’algorithme.
Exemple (mutation sur un chromosome binaire) : Avant mutation : ( 10101 )
- Mutation sur le 3ᵉ bit : Après mutation : ( 10001 )
Objectif : maintenir la diversité génétique et garantir que chaque point de l’espace de recherche reste
accessible.
6. Remplacement
La nouvelle génération remplace tout ou une partie de la population actuelle.
7. Arrêt
L’algorithme s’arrête si un critère est atteint (max d’itérations, convergence, etc.).
Représentation des solutions
- Binaire : chaque chromosome est une chaîne de 0 et 1.
- Réelle : pour des problèmes à variables continues.
- Permutation : pour les problèmes d’ordonnancement (ex : voyageur de commerce).
📈 Exemple simple : Maximiser une fonction
Problème : Maximiser la fonction suivante :
( )
Représentation : Encodons (x) sous forme binaire sur 5 bits (ex : ( x = 13 ⇒ 01101 )).
Étapes
1. Initialisation (5 individus aléatoires) :
01101 (13)
11000 (24)
00111 (7)
10101 (21)
11110 (30)
2. Évaluation (calcul de la fitness) :
f(13) = 169
f(24) = 576
f(7) = 49
f(21) = 441
f(30) = 900
3. Sélection (roulette wheel par ex.)
4. Croisement (one-point crossover) entre 11000 et 10101 :
11000 + 10101 → 11001 et 10100
5. Mutation (inverser un bit aléatoirement) :
11001 → 11011
6. Nouvelle population :
11011 (27)
10100 (20)
Etc, on répète jusqu’à convergence
🚀 Applications des AG
- Optimisation combinatoire : voyageur de commerce, problèmes de planification.
- Apprentissage automatique : sélection de caractéristiques, hyperparamètres.
- Jeux vidéo : intelligence artificielle des agents.
- Bio-informatique : alignement de séquences ADN.
Avantages :
- Adaptabilité aux problèmes complexes.
- Recherche parallèle.
- Exploration globale de l’espace de recherche.
Inconvénients :
- Convergence lente.
- Sensibilité aux paramètres (mutation, croisement…).
- Difficulté à trouver les bons hyper paramètres.
