#Algorithmes génétiquesCopier le lien

Prérequis : notion de recherche exhaustive et de son coût exponentiel ; hasard et probabilités élémentaires ; chapitre Complexité des problèmes (NP-difficulté) pour situer quand les métaheuristiques deviennent pertinentes.

Objectifs d'apprentissage : concevoir les quatre ingrédients d'un algorithme génétique (encodage, adaptation, opérateurs, pression de sélection) ; régler les compromis population/mutation/sélection ; interpréter les courbes de convergence ; connaître les limites de la méthode.

#1. PrincipeCopier le lien

Les algorithmes génétiques s'inspirent de la sélection naturelle : une population de solutions candidates évolue par générations. Chaque itération enchaîne :

1. Évaluation : mesurer l'adaptation (fitness) de chaque individu.
2. Sélection : favoriser les mieux adaptés comme parents.
3. Croisement : combiner deux parents pour produire des descendants.
4. Mutation : perturber aléatoirement certains gènes pour maintenir la diversité.
5. Remplacement : la nouvelle génération prend la place de l'ancienne, souvent en préservant les meilleurs (élitisme).

Le parallèle biologique est une métaphore efficace mais pas un modèle : en optimisation, l'objectif est la convergence vers une bonne solution, pas le réalisme des mécanismes.

#Animation interactiveCopier le lien

Entrées : taille de population, taux de mutation, nombre de générations, fonction d'adaptation affichée. Sorties : le meilleur individu par génération et la courbe d'adaptation. Lecture conseillée : montez le taux de mutation et observez la courbe osciller (la population ne se stabilise plus) ; baissez-le et observez la stagnation prématurée (plateau sous-optimal). Le bon réglage vit exactement entre ces deux échecs.

#2. Les quatre ingrédientsCopier le lien

Encodage : le choix du génome décide de la puissance de la méthode. Chaîne de caractères pour deviner un mot, vecteur de bits pour un sous-ensemble, permutation pour un circuit (voyageur de commerce), vecteur de réels pour un paramétrage continu. L'encodage doit rendre naturels les croisements et les mutations : croiser deux permutations nécessite un opérateur dédié (OX, PMX) sous peine de produire des solutions invalides.

Fonction d'adaptation : elle seule relie l'algorithme au problème. Exigences : distinguer les solutions (pas de plateau plat), être calculable vite (des milliers d'évaluations par génération), et correspondre au vrai objectif (une adaptation de contournement se retourne vite contre son auteur).

Opérateurs : croisement (un point, deux points, uniforme) exploite la structure déjà découverte ; mutation (bit inversé, gène remplacé, voisinage permuté) explore hors des combinaisons existantes.

Pression de sélection : la sélection par tournoi (prendre le meilleur de k individus tirés au hasard) offre un réglage simple : k petit, pression faible, population diversifiée ; k grand, convergence rapide vers les meilleurs courants, risque de consanguinité.

#3. Implémentation : deviner une phraseCopier le lien

Objectif pédagogique : retrouver une phrase cible, l'adaptation étant le taux de lettres correctes. Le problème est artificiellement facile (l'adaptation guide lettre par lettre) mais rend visibles tous les mécanismes.

1import random2import string3 4ALPHABET = string.ascii_uppercase + ' '5 6def adaptation(genome, cible):7    """Taux de positions correctes, entre 0 et 1."""8    return sum(g == c for g, c in zip(genome, cible)) / len(cible)9 10def individu_aleatoire(taille):11    return [random.choice(ALPHABET) for _ in range(taille)]12 13def croisement(parent_a, parent_b):14    coupe = random.randrange(1, len(parent_a))

Vérification observable : le score monte par paliers (blocs de lettres qui se fixent progressivement) et atteint 1.0 en général en quelques dizaines à quelques centaines de générations avec ces réglages ; un taux_mutation à 0.5 fait exploser la diversité et bloque le progrès, un taux à 0 fait stagner la population dès le premier plateau.

#4. Exercice : maximiser une fonctionCopier le lien

Maximiser $f(x) = x^2$ sur les entiers de 0 à 31. L'encodage naturel est 5 bits, l'adaptation est la valeur de la fonction :

1import random2 3def en_valeur(genome):4    return sum(bit << i for i, bit in enumerate(reversed(genome)))5 6def adaptation(genome):7    return en_valeur(genome) ** 28 9def croisement(a, b):10    coupe = random.randrange(1, len(a))11    return a[:coupe] + b[coupe:]12 13def muter(genome, taux=0.02):14    return [1 - g if random.random() < taux else g for g in genome]

Vérification : l'algorithme converge vers x = 31 (f = 961) en quelques générations. Observez le défaut de l'exemple : maximiser $x^2$ n'a aucun intérêt (le maximum est connu), et l'adaptation écrasante du 31 tend à capturer toute la population dès qu'il apparaît : c'est la démonstration visuelle de la pression de sélection.

#5. Réglage : trois compromisCopier le lien

Méthode de réglage : commencer par les valeurs standards (population 50 à 200, mutation 1 à 5 %, tournoi k = 3 à 7), tracer l'adaptation du meilleur et la moyenne de la population. Meilleur qui plafonne loin de la moyenne : population trop homogène, augmenter mutation ou baisser la pression. Moyenne qui colle au meilleur : convergence rapide peut-être prématurée ; relancer plusieurs fois avec des graines différentes pour mesurer la variabilité des résultats.

#6. Évaluer honnêtement la méthodeCopier le lien

Les algorithmes génétiques n'offrent aucune garantie d'optimalité, ni de borne d'approximation, ni de complexité autre que le budget fixé (générations × population × coût d'une évaluation). Leurs vrais terrains :

• Espace de recherche énorme et mal structuré, sans gradient exploitable (fonction non différentiable, bruitée, discrète).
• Solutions intermédiaires utiles : une bonne solution acceptable suffit, l'optimal exact est hors de portée.
• Facilité de parallélisation : chaque évaluation est indépendante.

Quand un problème admet une heuristique dédiée (glouton prouvé, programmation dynamique, recherche locale à voisinage structuré), elle bat presque toujours un algorithme génétique en temps et en qualité ; la métaheuristique est le recours quand rien de tout cela n'existe. Comparer les deux sur le même budget reste la démarche par défaut.

#7. ApplicationsCopier le lien

1. Ordonnancement et tournées : emploi du temps, tournées de véhicules (encodage par permutation).
2. Conception : formes, antennes, paramètres de circuits (le célèbre brevet d'antenne évolutionnaire de la NASA).
3. Recherche d'hyperparamètres : balayage d'espaces de configuration pour l'apprentissage automatique.
4. Bioinformatique : alignements de séquences, repliement.
5. Jeux et création : stratégie, contenu procédural (niveaux, créatures).