Genetic Algorithm : Guide Complet

Résumé

L’algorithme génétique (Genetic Algorithm, GA) est une métaheuristique d’optimisation inspirée par les mécanismes de l’évolution naturelle. Imaginé par John Holland dans les années 1970 et popularisé par David Goldberg dans les années 1980, il repose sur quatre opérateurs fondamentaux : la sélection, le croisement (crossover), la mutation et l’élitisme. En maintenant une population de solutions candidates et en les faisant évoluer génération après génération, le Genetic Algorithm explore efficacement des espaces de recherche vastes, multimodaux et non différentiables. Contrairement aux méthodes déterministes comme la descente de gradient, il ne nécessite pas de calcul de dérivées et résiste remarquablement bien aux minima locaux. Ce guide couvre le principe mathématique, l’intuition, une implémentation Python complète, les hyperparamètres, les avantages et limites, ainsi que quatre cas d’usage concrets.

Principe Mathématique

Le fonctionnement d’un algorithme génétique repose sur des concepts probabilistes rigoureux. Voici les composants essentiels formulés mathématiquement.

Représentation de la population

Une population de taille $N$ est un ensemble de $N$ individus (solutions candidates) :

$$P^{(t)} = {x_1^{(t)}, x_2^{(t)}, \dots, x_N^{(t)}}$$

où chaque individu $x_i^{(t)}$ à la génération $t$ est représenté par un chromosome — un vecteur de gènes :

$$x_i^{(t)} = [g_{i,1}^{(t)}, g_{i,2}^{(t)}, \dots, g_{i,L}^{(t)}]$$

avec $L$ le nombre de gènes (longueur du chromosome). Les gènes peuvent être binaires ($g \in {0, 1}$), réels ($g \in \mathbb{R}$), entiers ou permutationnels, selon la nature du problème.

Fonction de fitness

La fonction de fitness $f: \mathbb{R}^L \rightarrow \mathbb{R}$ évalue la qualité de chaque individu. Pour un problème de maximisation, on cherche à trouver :

$$x^* = \arg\max_{x \in P^{(t)}} f(x)$$

Pour un problème de minimisation, la fonction de fitness est généralement transformée :

$$f_{adaptée}(x) = -f_{original}(x) \quad \text{ou} \quad f_{adaptée}(x) = \frac{1}{1 + f_{original}(x)}$$

La fitness détermine la probabilité qu’un individu survive et se reproduise. C’est le moteur de la sélection naturelle artificielle.

Sélection par tournoi

La sélection tournoi est l’une des méthodes les plus utilisées. Le principe est le suivant :

1. Choisir aléatoirement $k$ individus dans la population courante (avec remise).
2. Comparer leurs valeurs de fitness.
3. Conserver l’individu ayant la meilleure fitness.

Formellement, pour un tournoi de taille $k$, la probabilité qu’un individu de rang $r$ (classé par fitness décroissante) soit sélectionné est :

$$P(\text{sélectionné}) = 1 – \left(\frac{r-1}{N}\right)^k$$

Plus $k$ est grand, plus la pression sélective est forte. Un tournoi de taille $k=2$ est le choix le plus courant, offrant un bon équilibre entre exploitation et exploration.

Croisement (Crossover)

Le croisement combine l’information génétique de deux parents pour produire un ou deux enfants. Il existe plusieurs variantes :

One-point crossover : On choisit un point de coupure $c$ aléatoirement avec $1 \leq c < L$. Les deux enfants sont construits ainsi :

$$enfant_1 = [p_{1,1}, \dots, p_{1,c}, p_{2,c+1}, \dots, p_{2,L}]$$
$$enfant_2 = [p_{2,1}, \dots, p_{2,c}, p_{1,c+1}, \dots, p_{1,L}]$$

Two-point crossover : On choisit deux points $c_1 < c_2$. Le segment entre $c_1$ et $c_2$ est échangé, préservant ainsi davantage de structure génétique des parents.

Uniform crossover : Chaque gène de l’enfant provient soit du parent 1, soit du parent 2 avec probabilité $0,5$. C’est la forme la plus disruptive mais aussi la plus exploratoire du croisement.

La probabilité d’appliquer le croisement est contrôlée par le paramètre $p_c$ (crossover_rate), typiquement compris entre $0,6$ et $0,9$. Si le croisement n’est pas appliqué, les enfants sont des copies exactes des parents.

Mutation

La mutation introduit de la diversité génétique en modifiant aléatoirement un ou plusieurs gènes. Pour une représentation réelle, la mutation gaussienne s’écrit :

$$g’ = g + \epsilon \quad \text{où} \quad \epsilon \sim \mathcal{N}(0, \sigma^2)$$

Pour une représentation binaire, on inverse le bit avec probabilité $p_m$ (mutation_rate), généralement très faible ($0,001$ à $0,05$) pour ne pas trop perturber l’information génétique acquise.

Le paramètre $p_m$ contrôle la probabilité qu’un gène donné soit muté. Pour un chromosome de longueur $L$, le nombre attendu de mutations par individu est $L \times p_m$.

Élitisme

L’élitisme garantit que les meilleurs individus de la génération courante sont transférés intacts dans la génération suivante, sans modification par croisement ni mutation. Si on conserve les $E$ meilleurs individus :

$$P^{(t+1)}_{élite} = \text{top}_E(P^{(t)})$$

Cela assure une convergence monotone : la meilleure fitness ne peut jamais diminuer d’une génération à l’autre. Sans élitisme, un opérateur de croisement malheureux ou une mutation pourrait détruire la meilleure solution trouvée. L’élitisme est généralement appliqué avec $E = 1$ ou $E = 2$.

Schéma du cycle global

Initialiser population P(0) aléatoirement
Évaluer fitness de chaque individu
Pour t = 0 jusqu'à n_generations - 1 :
    Sélectionner les parents par tournoi
    Appliquer croisement avec probabilité p_c
    Appliquer mutation avec probabilité p_m
    Copier les E meilleurs individus (élitisme)
    Former P(t+1)
    Évaluer les nouvelles solutions
Retourner le meilleur individu trouvé

Intuition

Imaginez un éleveur de chiens de berger qui souhaite obtenir le meilleur chien possible, capable de rassembler des moutons avec une efficacité maximale. Comment procède-t-il ?

D’abord, il rassemble un groupe de chiens variés — c’est la population initiale. Certains sont naturellement doués, d’autres moins, mais tous ont un potentiel différent.

Ensuite, il identifie les meilleurs chiens du groupe, ceux qui réussissent le mieux à rassembler les troupeaux — c’est l’évaluation par fitness.

Puis, il croise les meilleurs chiens entre eux, en espérant que leurs chiots hériteront des bonnes qualités des deux parents — c’est le croisement. Mais le résultat n’est pas garanti : parfois un chiot est meilleur que ses deux parents, parfois il est moins bon.

De temps en temps, un chiot naît avec une caractéristique nouvelle, imprévue — c’est la mutation. La plupart du temps, cette nouveauté est nuisible ou neutre. Mais parfois, elle apporte un avantage inattendu : une meilleure vision périphérique, une plus grande endurance, ou une intelligence supérieure pour anticiper les mouvements du troupeau.

Et l’éleveur prend soin de garder ses meilleurs reproducteurs année après année — c’est l’élitisme.

Après plusieurs générations, si le processus est bien mené, on obtient des chiens de berger d’une qualité exceptionnelle, bien supérieurs à n’importe quel individu de la première génération. C’est exactement le principe de l’algorithme génétique, appliqué non pas à des chiens, mais à des solutions numériques.

L’algorithme génétique fait la même chose avec des solutions : on prend les meilleures, on les croise pour produire de nouvelles combinaisons, on introduit de légères variations aléatoires, et après plusieurs générations, on converge vers des solutions d’une qualité remarquable.

Implémentation Python

Voici une implémentation complète d’un Genetic Algorithm from scratch en Python, appliqué à l’optimisation de la fonction de Rastrigin, un problème classique de benchmark multimodal :

import numpy as np
from typing import List, Tuple

# Fonction de Rastrigin (problème de minimisation)
def rastrigin(x: np.ndarray) -> float:
    """
    Fonction de Rastrigin en dimension D.
    Minimum global : f(0) = 0.
    Forte multimodalité : nombreux minima locaux.
    """
    D = len(x)
    return 10 * D + np.sum(x**2 - 10 * np.cos(2 * np.pi * x))


class Individual:
    """Représente un individu (solution candidate)."""

    def __init__(self, genes: np.ndarray, fitness: float = None):
        self.genes = genes
        self.fitness = fitness  # None = non évalué


class Population:
    """Gère une population d'individus."""

    def __init__(
        self,
        size: int,
        gene_dim: int,
        bounds: Tuple[float, float],
        fitness_fn,
        rng: np.random.Generator = None
    ):
        self.size = size
        self.gene_dim = gene_dim
        self.bounds = bounds
        self.fitness_fn = fitness_fn
        self.rng = rng or np.random.default_rng()
        self.individuals = self._initialize()

    def _initialize(self) -> List[Individual]:
        """Initialisation aléatoire uniforme dans les bornes."""
        individuals = []
        low, high = self.bounds
        genes = self.rng.uniform(low, high, size=(self.size, self.gene_dim))
        for g in genes:
            ind = Individual(genes=g.copy())
            ind.fitness = self.fitness_fn(g)
            individuals.append(ind)
        return individuals

    def evaluate_all(self) -> None:
        """Évalue la fitness de tous les individus non évalués."""
        for ind in self.individuals:
            if ind.fitness is None:
                ind.fitness = self.fitness_fn(ind.genes)

    def best(self) -> Individual:
        """Retourne le meilleur individu (fitness minimale)."""
        return min(self.individuals, key=lambda ind: ind.fitness)

    def tournament_selection(self, k: int = 2) -> Individual:
        """Sélection par tournoi de taille k."""
        indices = self.rng.choice(len(self.individuals), size=k, replace=False)
        candidates = [self.individuals[i] for i in indices]
        return min(candidates, key=lambda ind: ind.fitness)

    @staticmethod
    def one_point_crossover(
        parent1: Individual,
        parent2: Individual,
        rng: np.random.Generator
    ) -> Tuple[np.ndarray, np.ndarray]:
        """Croisement à un point."""
        L = len(parent1.genes)
        point = rng.integers(1, L)  # dans [1, L-1]
        child1 = np.concatenate([parent1.genes[:point], parent2.genes[point:]])
        child2 = np.concatenate([parent2.genes[:point], parent1.genes[point:]])
        return child1, child2

    @staticmethod
    def gaussian_mutation(
        genes: np.ndarray,
        rate: float,
        sigma: float,
        bounds: Tuple[float, float],
        rng: np.random.Generator
    ) -> np.ndarray:
        """Mutation gaussienne avec clipping aux bornes."""
        mutated = genes.copy()
        mask = rng.random(len(mutated)) < rate
        noise = rng.normal(0, sigma, size=len(mutated))
        mutated[mask] += noise[mask]
        low, high = bounds
        mutated = np.clip(mutated, low, high)
        return mutated


class GeneticAlgorithm:
    """Algorithme génétique complet pour minimisation."""

    def __init__(
        self,
        population_size: int = 80,
        gene_dim: int = 5,
        bounds: Tuple[float, float] = (-5.12, 5.12),
        fitness_fn=rastrigin,
        crossover_rate: float = 0.85,
        mutation_rate: float = 0.15,
        mutation_sigma: float = 0.5,
        n_generations: int = 200,
        tournament_k: int = 3,
        elitism_count: int = 2,
        seed: int = 42
    ):
        self.pop_size = population_size
        self.bounds = bounds
        self.crossover_rate = crossover_rate
        self.mutation_rate = mutation_rate
        self.mutation_sigma = mutation_sigma
        self.n_generations = n_generations
        self.tournament_k = tournament_k
        self.elitism_count = elitism_count

        rng = np.random.default_rng(seed)
        self.population = Population(
            size=population_size,
            gene_dim=gene_dim,
            bounds=bounds,
            fitness_fn=fitness_fn,
            rng=rng
        )
        self.rng = rng
        self.history = []

    def run(self, verbose: bool = True) -> Individual:
        """Exécute l'algorithme génétique sur n_generations."""
        self.population.evaluate_all()

        for gen in range(self.n_generations):
            elite = sorted(
                self.population.individuals,
                key=lambda ind: ind.fitness
            )[:self.elitism_count]

            new_individuals = []

            for copy in elite:
                new_individuals.append(
                    Individual(genes=copy.genes.copy(), fitness=copy.fitness)
                )

            while len(new_individuals) < self.pop_size:
                p1 = self.population.tournament_selection(self.tournament_k)
                p2 = self.population.tournament_selection(self.tournament_k)

                if self.rng.random() < self.crossover_rate:
                    g1, g2 = self.population.one_point_crossover(p1, p2, self.rng)
                else:
                    g1, g2 = p1.genes.copy(), p2.genes.copy()

                g1 = self.population.gaussian_mutation(
                    g1, self.mutation_rate, self.mutation_sigma,
                    self.bounds, self.rng
                )
                g2 = self.population.gaussian_mutation(
                    g2, self.mutation_rate, self.mutation_sigma,
                    self.bounds, self.rng
                )

                child1 = Individual(genes=g1)
                child1.fitness = self.population.fitness_fn(g1)
                new_individuals.append(child1)

                if len(new_individuals) < self.pop_size:
                    child2 = Individual(genes=g2)
                    child2.fitness = self.population.fitness_fn(g2)
                    new_individuals.append(child2)

            self.population.individuals = new_individuals
            best = self.population.best()
            self.history.append(best.fitness)

            if verbose and (gen % 20 == 0 or gen == self.n_generations - 1):
                print(f"Génération {gen:4d} | "
                      f"Meilleure fitness : {best.fitness:.6f} | "
                      f"Meilleur individu : {best.genes.round(4)}")

        return self.population.best()


# ─── Exemple d'utilisation ───
if __name__ == "__main__":
    print("=" * 60)
    print("Optimisation de la fonction de Rastrigin (D=5)")
    print("Minimum global connu : f(0,0,0,0,0) = 0")
    print("=" * 60)

    ga = GeneticAlgorithm(
        population_size=80,
        gene_dim=5,
        bounds=(-5.12, 5.12),
        fitness_fn=rastrigin,
        crossover_rate=0.85,
        mutation_rate=0.15,
        mutation_sigma=0.5,
        n_generations=200,
        tournament_k=3,
        elitism_count=2,
        seed=42
    )

    best_solution = ga.run(verbose=True)

    print("\n" + "=" * 60)
    print("RÉSULTAT FINAL")
    print(f"Meilleure fitness : {best_solution.fitness:.8f}")
    print(f"Meilleure solution : {best_solution.genes.round(6)}")
    print(f"Nombre d'évaluations : {ga.pop_size * (ga.n_generations + 1)}")
    print("=" * 60)

Explication du code

Classe Individual : Chaque individu est un objet simple contenant un vecteur de gènes (représentation réelle) et sa valeur de fitness. La fitness est calculée en différé pour éviter des évaluations inutiles.

Classe Population : Gère l’ensemble des individus. L’initialisation crée une population aléatoire uniforme dans les bornes spécifiées. La sélection par tournoi (tournament_selection) choisit $k$ individus au hasard et retourne le meilleur. Le croisement (one_point_crossover) échange les segments de gènes après un point de coupure aléatoire. La mutation gaussienne ajoute un bruit normal $N(0, \sigma^2)$ aux gènes sélectionnés.

Classe GeneticAlgorithm : Orchestre le cycle complet : évaluation, sélection, croisement, mutation, élitisme. L’historique des meilleures fitness permet de suivre la convergence de l’algorithme génération après génération.

La fonction de Rastrigin est un excellent benchmark car elle possède un minimum global à $f(0, \dots, 0) = 0$ mais contient $10^D$ minima locaux, testant ainsi la capacité de l’algorithme à échapper aux pièges locaux.

Hyperparamètres

Le choix des hyperparamètres influence profondément la qualité de la recherche. Voici les cinq paramètres clés :

population_size (100–500)

La taille de la population détermine la diversité initiale et la capacité d’exploration. Une petite population (30–50) converge rapidement mais risque la convergence prématurée. Une grande population (200–500) explore davantage d’espace mais augmente le coût computationnel. Pour la plupart des problèmes pratiques, 100 à 200 individus constituent un bon compromis.

crossover_rate (0,6–0,95)

La probabilité d’appliquer le croisement à une paire de parents. Une valeur élevée (≥ 0,8) favorise l’exploitation en combinant activement l’information génétique des parents. Une valeur trop faible laisse les individus inchangés, ce qui réduit la capacité de l’algorithme à combiner les bonnes solutions.

mutation_rate (0,005–0,15)

La probabilité qu’un gène donné soit muté. C’est le paramètre le plus sensible : une mutation trop élevée transforme l’algorithme génétique en recherche aléatoire ; une mutation trop faible peut conduire à un appauvrissement génétique et une stagnation prématurée. Pour les problèmes réels, on commence souvent avec 0,05–0,15 et on ajuste selon les performances observées.

n_generations (50–2000)

Le nombre de générations détermine la durée de la recherche. On peut fixer un nombre fixe ou utiliser un critère d’arrêt adaptatif : arrêt lorsque la meilleure fitness ne s’améliore pas pendant $N$ générations consécutives (critère de patience).

tournament_k (2–5)

La taille du tournoi contrôle la pression sélective. Avec $k=2$, la sélection est douce et préserve la diversité. Avec $k=5$, seuls les individus de haute qualité sont sélectionnés, ce qui accélère la convergence mais réduit la diversité. Le choix classique est $k=3$, offrant un bon équilibre.

Avantages et Limites

Avantages

• Pas de gradient requis : Le Genetic Algorithm ne nécessite aucune dérivée de la fonction objectif. Il fonctionne avec des fonctions discontinues, non différentiables, bruitées ou même simulées par un programme externe.
• Résistance aux minima locaux : Grâce à la diversité de la population et à la mutation, l’algorithme explore plusieurs régions simultanément et évite le piège classique de la descente de gradient dans les minima locaux.
• Large applicabilité : Il s’applique à des problèmes discrets, continus, mixtes, combinatoires et multi-objectifs avec des adaptations minimes.
• Parallélisation naturelle : L’évaluation de la fitness de chaque individu est indépendante, permettant une parallélisation embarrassante sur GPU, clusters ou calcul distribué.

Limites

• Coût computationnel : Chaque génération nécessite l’évaluation de $N$ fonctions de fitness. Pour des simulations coûteuses (CFD, simulations financières), le coût total peut devenir prohibitif.
• Pas de garantie d’optimalité : Le Genetic Algorithm ne garantit pas la convergence vers le minimum global. Il fournit une bonne approximation dans un temps raisonnable, mais pas de preuve d’optimalité.
• Réglage des hyperparamètres : Les performances dépendent fortement du choix des hyperparamètres. Un mauvais réglage peut conduire à une convergence prématurée ou une recherche inefficace.
• Sensibilité à la représentation : Le choix de la représentation (binaire, réelle, permutationnelle) influence considérablement l’efficacité du croisement et de la mutation. Une mauvaise représentation peut empêcher l’algorithme de trouver de bonnes solutions.

Cas d’Usage Concrets

1. Optimisation hyperparamétrique de réseaux neuronaux

Un Genetic Algorithm peut rechercher automatiquement la meilleure architecture de réseau neuronal — nombre de couches, nombre de neurones, taux d’apprentissage, fonctions d’activation. Chaque individu encode une configuration complète. La fitness est la performance du réseau sur l’ensemble de validation. Des travaux comme ceux de Real et al. (2019) ont montré que les algorithmes génétiques peuvent rivaliser avec le Bayesian Optimization pour la recherche d’architecture neuronale, notamment sur des espaces d’architecture discrets.

2. Planification de production industrielle

Dans les usines, l’ordonnancement des tâches sur plusieurs machines avec des contraintes complexes (délais, priorités, disponibilité des ressources) est un problème NP-difficile. Un algorithme génétique avec représentation permutationnelle encode l’ordre d’exécution des tâches. Le croisement OX (Order Crossover) et la mutation par inversion préservent les contraintes de faisabilité. Des entreprises comme Siemens et Airbus utilisent ces approches pour optimiser leurs lignes de production.

3. Conception aérodynamique

L’optimisation de la forme d’une aile d’avion pour minimiser la traînée tout en maximisant la portance est un problème multi-objectif complexe. La fonction de fitness est évaluée par simulation CFD (Computational Fluid Dynamics), extrêmement coûteuse en temps de calcul. Un algorithme génétique couplé à un modèle de substitution (surrogate model) permet de réduire le nombre d’évaluations CFD nécessaires de l’ordre de 80 à 90 % par rapport à l’évaluation directe.

4. Planification de portefeuille

La sélection et la pondération optimale d’actifs financiers pour maximiser le rendement attendu tout en minimisant le risque est un problème d’optimisation combinatoire continue. Un algorithme génétique peut encoder à la fois les actifs sélectionnés (partie binaire du chromosome) et leurs poids d’allocation (partie réelle). Cette approche hybride permet de gérer simultanément le problème de sélection d’actifs et celui de pondération, ce qui est difficile avec les méthodes classiques de Markowitz.

Voir aussi

• Explorez la Conjecture de Goldbach en Python : Guide Pratique pour les Passionnés de Programmation
• Résolution des Équations Diophantiennes III avec Python : Guide Complet et Astuces