Algorithmes génétiques : optimisation inspirée de l'évolution

Les algorithmes génétiques (AG) sont une famille de techniques d'optimisation métaheuristiques inspirées de la sélection naturelle. Ils maintiennent une population de solutions candidates qui évoluent au fil des générations par sélection, croisement et mutation — convergeant vers des solutions optimales ou quasi-optimales pour des problèmes où les méthodes basées sur le gradient échouent.

Mécanisme central

Un algorithme génétique fonctionne en boucle :

Boucle d'un algorithme génétique
=================================

Initialiser population aléatoire P(0)
     │
     ▼
┌──────────────────────────┐
│  Évaluer fitness f(x)    │◄──────────────┐
│  pour chaque individu    │               │
└──────────┬───────────────┘               │
           ▼                               │
┌──────────────────────────┐               │
│  Sélection               │               │
│  (tournoi / roulette)    │               │
└──────────┬───────────────┘               │
           ▼                               │
┌──────────────────────────┐               │
│  Croisement              │               │
│  (un point / uniforme)   │               │
└──────────┬───────────────┘               │
           ▼                               │
┌──────────────────────────┐               │
│  Mutation                │               │
│  (bit-flip / gaussienne) │               │
└──────────┬───────────────┘               │
           ▼                               │
     Nouvelle génération P(t+1) ───────────┘
     jusqu'à convergence

Opérateurs clés

La sélection détermine quels individus se reproduisent. Stratégies courantes :

Le croisement combine le matériel génétique de deux parents :

• Un point : couper à un index, échanger les queues
• Deux points : échanger un segment entre deux points de coupe
• Uniforme : chaque gène choisi indépendamment d'un parent (tirage à pile ou face)
• Arithmétique : moyenne pondérée des gènes des parents (encodage réel)

La mutation introduit une variation aléatoire pour maintenir la diversité :

• Bit-flip : inverser un bit aléatoire (encodage binaire)
• Gaussienne : ajouter un bruit $\mathcal{N}(0, \sigma^2)$ à un gène (valeur réelle)
• Échange : permuter deux positions (problèmes de permutation comme le TSP)
• Scramble : réordonner aléatoirement une sous-séquence

Stratégies d'encodage

Le choix de l'encodage détermine quels opérateurs sont naturels :

Réglage des hyperparamètres

Hyperparamètres clés et leurs plages typiques :

• Taille de population : 50–500 (plus grand pour des paysages complexes)
• Taux de croisement ($p_c$) : 0.6–0.9
• Taux de mutation ($p_m$) : 0.001–0.05 (faible pour préserver les bonnes solutions)
• Nombre d'élites : 1–5% de la population
• Générations : 100–10 000 (avec arrêt prématuré)

L'équilibre entre exploration (mutation, grande population) et exploitation (pression de sélection, croisement) est critique. Trop d'exploitation mène à une convergence prématurée ; trop d'exploration gaspille du calcul.

AG vs autres méthodes d'optimisation

Applications concrètes

Recherche d'architecture neuronale (NAS) : les AG font évoluer les topologies de réseaux neuronaux — nombre de couches, unités par couche, fonctions d'activation, connexions résiduelles. AmoebaNet de Google a utilisé des méthodes évolutionnaires pour découvrir des architectures compétitives avec NAS-RL à moindre coût de calcul.

Sélection de features : encoder les sous-ensembles de features comme chromosomes binaires. Fitness = performance du modèle sur le jeu de validation. Recherche efficacement $2^n$ combinaisons de features.

Optimisation d'hyperparamètres : chaque individu encode une configuration d'hyperparamètres. Plus robuste que le grid search pour des espaces de paramètres de haute dimension et de types mixtes.

Supply chain et ordonnancement : les AG à encodage par permutation gèrent l'ordonnancement d'atelier (job-shop), le routage de véhicules (VRP) et l'optimisation de disposition d'entrepôt là où les solveurs exacts ne passent pas à l'échelle.

IA de jeu et génération procédurale : faire évoluer des stratégies de jeu, des dispositions de niveaux ou des comportements de personnages. Utile quand le paysage de fitness est non différentiable.

DEAP : un framework Python pour les AG

from deap import base, creator, tools, algorithms
import random

# Maximiser une fonction de fitness
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)

toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat, creator.Individual,
                 toolbox.attr_bool, n=100)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

def eval_onemax(individual):
    return (sum(individual),)  # Simple : maximiser le nombre de 1

toolbox.register("evaluate", eval_onemax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.02)
toolbox.register("select", tools.selTournament, tournsize=3)

pop = toolbox.population(n=300)
result, log = algorithms.eaSimple(pop, toolbox,
                                   cxpb=0.7, mutpb=0.2,
                                   ngen=50, verbose=False)
best = tools.selBest(result, k=1)[0]

Quand utiliser les AG

Les AG excellent quand l'espace de recherche est grand, discontinu ou non différentiable, et quand on a besoin d'une solution « suffisamment bonne » plutôt qu'une solution prouvée optimale. Ils ne sont pas le bon outil quand l'information de gradient est disponible et que le problème est lisse — l'optimisation standard convergera plus vite.

L'avantage clé est la généralité : les AG ne nécessitent qu'une fonction de fitness et un encodage. Pas de gradient, pas de hessien, pas d'hypothèse de convexité. Cela en fait l'approche de référence pour l'optimisation combinatoire, les problèmes multi-objectifs (via NSGA-II) et tout domaine où l'objectif est une simulation boîte noire.