Algorithmes Génétiques : Guide complet — Principes, Exemples et Implémentation Python

Résumé — Les algorithmes génétiques sont des techniques d’optimisation inspirées de l’évolution naturelle. Une population de solutions candidates évolue à travers des opérateurs de sélection, croisement et mutation, convergeant progressivement vers des solutions optimales ou quasi-optimales. Applicables à des problèmes continus, discrets ou combinatoires, ils excellent là où les méthodes classiques de gradient échouent.

Principe mathématique

Un algorithme génétique modélise un processus évolutif en quatre phases cycliques :

1. Représentation des individus : Chaque solution candidate est encodée comme un chromosome — un vecteur (binaire, entier, réel, ou permutation) de gènes. Par exemple, pour optimiser une fonction f(x,y), le chromosome [x, y] contient deux gènes réels.

2. Fitness (fonction d’évaluation) : Chaque individu se voit attribuer un score de fitness, qui mesure la qualité de sa solution. Pour une maximisation de f, fitness = f(x). Pour un problème de minimisation, fitness = -f(x) ou fitness = 1/(1+f(x)).

3. Opérateurs évolutifs :

a) Sélection : Les individus sont choisis pour la reproduction selon leur fitness. Deux méthodes dominent :
– Sélection par tournoi : Tirer k individus au hasard, garder le meilleur. Taille du tournoi = pression sélective.
– Roue de la fortune (fitness-proportionate) : Probabilité p_i = fitness_i / Σ fitness_j. Les meilleurs ont plus de chances mais les moyens peuvent quand même être sélectionnés.

b) Croisement (Crossover) : Deux parents produisent des enfants en combinant leurs chromosomes.
– Un point : Couper les chromosomes à un point aléatoire, échanger les moitiés.
– Deux points : Deux coupures, échange du segment central.
– Barycentrique (réel) : Enfant = α·parent1 + (1-α)·parent2.

c) Mutation : Modification aléatoire d’un ou plusieurs gènes avec probabilité p_m (typiquement 1-5%). Pour les chromosomes réels : ajouter un bruit gaussien. Pour les binaires : flip le bit.

4. Remplacement et élitisme : La nouvelle génération remplace l’ancienne. L’élitisme consiste à conserver les meilleurs individus intacts, garantissant que le fitness optimal ne diminue jamais d’une génération à l’autre.

Convergence : L’algorithme n’est pas garanti de trouver l’optimum global, mais converge asymptotiquement vers lui sous des conditions théoriques (théorème des schémas de Holland). En pratique, on s’arrête après un nombre fixe de générations ou quand le meilleur fitness stagne.

Intuition

Imaginez un élevage de pigeons voyageurs. Vous commencez avec un groupe varié — certains volent vite, d’autres sont endurants, d’autres bons navigateurs. Votre objectif : créer le pigeon parfait.

Chaque génération, vous :
1. Sélectionnez les meilleurs reproducteurs (ceux qui ont les meilleures performances)
2. Croisez leurs caractéristiques — un pigeon rapide × un pigeon endurant pourrait donner un pigeon rapide ET endurant
3. Mutez occasionnellement — un pigeon naît avec une caractéristique inattendue (meilleure vision nocturne ?) qui pourrait être un avantage

Après des dizaines de générations, vous obtenez des pigeons bien meilleurs que le meilleur individu de la génération initiale. C’est exactement ce que fait un algorithme génétique — sauf qu’au lieu d’élever des pigeons pendant des années, il évalue des millions de solutions en quelques secondes sur un processeur.

La clé : contrairement aux méthodes de gradient qui suivent une pente locale, les algorithmes génétiques explorent simultanément de multiples régions de l’espace de recherche. La mutation introduit de la nouveauté, le croisement combine les bonnes idées, et la sélection élimine les mauvaises combinaisons.

Implémentation Python

Exemple 1 : Implémentation from scratch — optimisation de fonction

import numpy as np
import matplotlib.pyplot as plt

def fitness(x):
    return np.sin(x*3) + np.cos(x*2) + x/5  # fonction multi-modale

def genetic_algorithm(pop_size=100, n_gen=50, x_min=-5, x_max=5,
                      mut_prob=0.1, elite_frac=0.1, seed=42):
    np.random.seed(seed)

    # Initialisation aléatoire uniforme
    population = np.random.uniform(x_min, x_max, pop_size)

    best_history = []
    avg_history = []

    for gen in range(n_gen):
        # Évaluation
        scores = fitness(population)

        # Historique
        best_history.append(scores.max())
        avg_history.append(scores.mean())

        # Sélection par tournoi
        def tournament(pop, scores, k=3):
            idx = np.random.choice(len(pop), k)
            return pop[idx[scores[idx].argmax()]]

        # Élitisme
        n_elite = max(1, int(pop_size * elite_frac))
        elite_idx = np.argsort(scores)[-n_elite:]
        new_pop = list(population[elite_idx])

        # Reproduction
        while len(new_pop) < pop_size:
            p1 = tournament(population, scores, k=3)
            p2 = tournament(population, scores, k=3)

            # Croisement barycentrique
            alpha = np.random.uniform(0.2, 0.8)
            child = alpha * p1 + (1 - alpha) * p2

            # Mutation gaussienne
            if np.random.random() < mut_prob:
                child += np.random.normal(0, 0.5)
                child = np.clip(child, x_min, x_max)

            new_pop.append(child)

        population = np.array(new_pop)

    best_idx = fitness(population).argmax()
    best_sol = population[best_idx]
    best_fit = fitness(best_sol)
    print(f"Solution optimale : x = {best_sol:.4f}, f(x) = {best_fit:.4f}")
    return best_sol, best_fit, best_history, avg_history

# Exécution
solution, optimum, best_hist, avg_hist = genetic_algorithm()

# Visualisation de la convergence
plt.figure(figsize=(8, 4))
plt.plot(best_hist, 'r-', label='Meilleur fitness', linewidth=2)
plt.plot(avg_hist, 'b--', label='Fitness moyen', linewidth=1)
plt.title('Convergence de l\'algorithme génétique')
plt.xlabel('Génération')
plt.ylabel('Fitness')
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('genetic_convergence.png', dpi=150)
print(f"Graphique sauvegardé")

Exemple 2 : Résolution du problème du voyageur de commerce (TSP)

import numpy as np

# Villes (coordonnées)
cities = np.array([
    [60, 200], [180, 200], [80, 180], [140, 180],
    [20, 160], [100, 160], [200, 160], [140, 140],
    [40, 120], [100, 120], [180, 100], [60, 80],
    [120, 80], [180, 60], [20, 40], [100, 40],
    [200, 40], [20, 20], [60, 20], [160, 20],
])
n_cities = len(cities)

def distance_matrix(cities):
    n = len(cities)
    dist = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            dist[i, j] = np.linalg.norm(cities[i] - cities[j])
    return dist

dist = distance_matrix(cities)

def tour_length(route):
    return sum(dist[route[i], route[i+1]] for i in range(len(route)-1)) + dist[route[-1], route[0]]

def ga_tsp(pop_size=50, n_gen=200, mut_prob=0.3):
    np.random.seed(42)

    # Population initiale de permutations
    population = [np.random.permutation(n_cities) for _ in range(pop_size)]
    best_hist = []

    for gen in range(n_gen):
        scores = [-tour_length(r) for r in population]  # négatif pour maximisation

        best_hist.append(-min(tour_length(r) for r in population))

        # Élitisme
        n_elite = 5
        elite_idx = np.argsort(scores)[-n_elite:]
        new_pop = [population[i] for i in elite_idx]

        # Sélection par tournoi
        def tournament(idx_list):
            k = min(3, len(idx_list))
            chosen = np.random.choice(idx_list, k, replace=False)
            return chosen[np.argmax([scores[i] for i in chosen])]

        all_idx = list(range(pop_size))

        while len(new_pop) < pop_size:
            p1 = population[tournament(all_idx)].copy()
            p2 = population[tournament(all_idx)].copy()

            # Croisement Order Crossover (OX)
            start, end = sorted(np.random.choice(n_cities, 2, replace=False))
            child = [None] * n_cities
            child[start:end+1] = p1[start:end+1]
            remaining = [g for g in p2 if g not in child[start:end+1]]
            j = 0
            for i in range(n_cities):
                if child[i] is None:
                    child[i] = remaining[j]
                    j += 1

            # Mutation par swap
            if np.random.random() < mut_prob:
                i1, i2 = np.random.choice(n_cities, 2, replace=False)
                child[i1], child[i2] = child[i2], child[i1]

            new_pop.append(np.array(child))

        population = new_pop

    best_route = min(population, key=tour_length)
    best_dist = tour_length(best_route)
    print(f"Meilleure distance TSP : {best_dist:.2f}")
    return best_route, best_dist, best_hist

route, distance, history = ga_tsp()

Hyperparamètres

Avantages des algorithmes génétiques

1. Pas de gradient nécessaire : Fonctionnent sur des fonctions non dérivables, discontinues, bruitées ou black-box — là où les méthodes de gradient sont inapplicables.
2. Recherche globale : L’exploration multi-points réduit le risque de rester piégé dans un optimum local, contrairement à la descente de gradient.
3. Flexibilité extrême : Applicables à des problèmes continus, discrets, combinatoires (TSP, scheduling), et même à la conception de réseaux de neurones (neuroévolution).
4. Parallélisation naturelle : L’évaluation des fitness est indépendante — parfaitement parallélisable sur des clusters ou des GPUs.
5. Simplicité conceptuelle : Le cœur de l’algorithme tient en quelques lignes de code, le rendant accessible et facile à adapter.

Limites des algorithmes génétiques

1. Pas de garantie d’optimalité : Aucune borne sur la qualité de la solution finale — on obtient une “bonne” solution, pas nécessairement la meilleure.
2. Réglage des hyperparamètres : La performance dépend fortement du choix de la taille de population, des taux de mutation et de croisement — peu de règles universelles.
3. Coût computationnel : Des milliers d’évaluations de fitness sont nécessaires — problématique si chaque évaluation est coûteuse (simulation CFD, entraînement de réseaux).
4. Convergence prématurée : En cas de pression sélective trop forte, la population converge rapidement vers un optimum local et la diversité génétique s’effondre.
5. Pas de réponse en temps réel : Le processus itératif (générations) est intrinsèquement séquentiel — inadapté aux décisions qui doivent être prises en millisecondes.

4 cas d’usage concrets

1. Optimisation de tournées de livraison (logistique)

Les entreprises de livraison utilisent les algorithmes génétiques pour optimiser les itinéraires de leurs flottes de camions — le célèbre problème du voyageur de commerce (TSP) et ses variantes (VRP, CVRP). Chaque chromosome représente une séquence de livraison, et le fitness est la distance totale ou le coût. Les contraintes (capacité des véhicules, fenêtres horaires) sont intégrées dans la fonction de fitness comme pénalités.

2. Conception de composants aéronautiques

Airbus et Boeing utilisent des approches évolutionnaires pour optimiser la forme des ailes d’avions. Le chromosome encode la géométrie (courbure, épaisseur, envergure), et le fitness est le rapport portance/traînée évalué par simulation CFD. La flexibilité des AG permet d’explorer des formes contre-intuitives que les ingénieurs n’auraient pas envisagées.

3. Apprentissage automatique — sélection de features et tuning de modèles

Les algorithmes génétiques sont utilisés pour sélectionner les variables les plus informatives dans un jeu de données (chaque bit du chromosome = inclusion ou exclusion d’une feature). Combinés avec un classifieur comme score de fitness, ils trouvent souvent des sous-ensembles de features plus performants que les méthodes forward/backward classiques. Des frameworks comme TPOT automatisent même la conception de pipelines ML entiers par approche génétique.

4. Planification de production et emploi du temps

Dans l’industrie manufacturière, l’ordonnancement des tâches sur les machines (job-shop scheduling) est un problème NP-difficile. Les algorithmes génétiques trouvent des planning quasi-optimaux qui minimisent le temps total de production et les temps d’attente, tout en respectant les contraintes de ressources et de séquencement. Chaque chromosome encode un ordre d’exécution des tâches.

Bonnes pratiques

• Démarrer avec des paramètres standards : population=100, crossover=0.8, mutation=0.05, elitisme=5 — puis affiner.
• Surveiller la diversité : Si la variance des fitness dans la population chute brutalement, c’est un signe de convergence prématurée — augmenter la mutation ou la taille de la population.
• Utiliser l’élitisme systématiquement : Conserver au moins le meilleur individu évite la régression entre générations.
• Hybridation : Combiner un AG avec une méthode locale (gradient, Nelder-Mead) pour affiner les meilleures solutions — c’est l’approche “memetic algorithm”.
• Reproductibilité : Fixer la graine aléatoire pour que les résultats soient reproductibles, surtout en recherche ou production.

Conclusion

Les algorithmes génétiques représentent une approche puissante et élégante pour résoudre des problèmes d’optimisation complexes là où les méthodes classiques échouent. Leur force réside dans leur capacité à explorer de vastes espaces de recherche sans hypothèses sur la structure du problème — ni dérivabilité, ni convexité, ni continuité requises.

Ils ne sont cependant pas une solution universelle : pour des problèmes convexes et bien conditionnés, la descente de gradient sera toujours plus rapide et plus précise. Les algorithmes génétiques brillent là où le paysage des solutions est accidenté, discontinu, ou combinatoire.

Voir aussi

• Multiplier des chaînes de caractères avec Python
• Maîtrisez l’Art du Reverse Engineering en Python : Guide Complet pour Débutants et Experts