Evolutionary Algorithms

Les algorithmes évolutionnaires (AE) forment une famille d'algorithmes d'optimisation qui imitent la sélection naturelle. Ils maintiennent une population de solutions candidates, évaluent chacune avec une fonction de fitness, permettent aux meilleures de produire une descendance par recombinaison et mutation aléatoire, puis répètent le processus sur de nombreuses générations afin que la population évolue vers de meilleures solutions. Un AE doit uniquement évaluer une solution candidate, sans calculer de gradient ; il convient donc aux problèmes que la descente de gradient ne peut pas traiter : choix discrets, objectifs non différentiables ou bruités et paysages accidentés remplis d'optima locaux. Les AE sont ainsi des outils courants pour le réglage des hyperparamètres, la recherche d'architectures neuronales, la conception technique et la planification.

Fonctionnement des algorithmes évolutionnaires#

Tous les AE reposent sur les mêmes éléments :

1. Représentation : chaque candidat est encodé sous forme de génome, par exemple une chaîne de bits, un vecteur de nombres réels ou un arbre de programme.
2. Initialisation : la première génération est généralement aléatoire, parfois initialisée avec de bonnes solutions connues.
3. Évaluation de la fitness : une fonction de fitness attribue un score à chaque candidat en fonction de l'objectif optimisé.
4. Sélection : les candidats les plus performants ont plus de chances de devenir parents. La sélection par tournoi, par exemple, choisit le meilleur parmi quelques candidats aléatoires ; l'élitisme copie le meilleur candidat sans modification dans la génération suivante.
5. Variation : le croisement combine des parties de deux parents, et la mutation apporte de petites modifications aléatoires pour que la population continue d'explorer.

En apprentissage automatique (ML), la fonction de fitness est souvent une métrique de validation comme la précision ou la précision moyenne (mAP) ; évaluer un candidat signifie donc entraîner et tester un modèle, ce qui constitue de loin l'étape la plus coûteuse. La boucle se répète jusqu'à épuisement du budget ou jusqu'à ce que la fitness cesse de s'améliorer :

La pression de sélection et l'intensité des mutations déterminent l'équilibre entre exploitation et exploration. Une sélection forte associée à de petites mutations converge rapidement, mais peut rester bloquée dans un optimum local ; une sélection faible avec de grandes mutations explore largement, mais gaspille des évaluations.

Principaux types d'algorithmes évolutionnaires#

• Algorithmes génétiques (AG) : les candidats sont encodés sous forme de chaînes, souvent des bits, et le croisement joue un rôle important. John Holland les a formalisés dans son livre de 1975, Adaptation in Natural and Artificial Systems.
• Stratégies d'évolution (SE) : elles optimisent des vecteurs de nombres réels à l'aide de mutations gaussiennes dont la taille des pas s'adapte pendant l'exécution. CMA-ES, qui apprend toute la covariance de sa distribution de mutation, compte parmi les méthodes généralistes les plus performantes pour les problèmes continus en boîte noire.
• Programmation génétique : elle fait évoluer des programmes ou des expressions mathématiques représentés sous forme d'arbres ; elle sert à la régression symbolique et à la conception automatique de programmes.
• Neuroévolution : elle fait évoluer les poids, et parfois la structure, des réseaux neuronaux. En 2017, OpenAI a montré que des stratégies d'évolution exécutées sur plus d'un millier de travailleurs parallèles pouvaient entraîner un humanoïde 3D à marcher en 10 minutes, une solution évolutive de remplacement à l'apprentissage par renforcement.

Un algorithme génétique en code#

Le problème du sac à dos consiste à déterminer quels objets emporter pour maximiser la valeur totale sans dépasser une limite de poids. Il s'agit d'un problème discret sans gradient. Cet algorithme génétique NumPy fait évoluer 50 génomes sous forme de chaînes de bits, avec un bit par objet, en utilisant la sélection par tournoi, le croisement uniforme, la mutation par inversion de bits et l'élitisme, puis compare la solution aux 1,048,576 sélections possibles :

import itertools

import numpy as np

rng = np.random.default_rng(0)
# Knapsack problem: pick from 20 items to maximize total value within a weight limit of 200
values, weights, limit = rng.integers(10, 100, 20), rng.integers(5, 50, 20), 200


def fitness(pop):
    """Return each selection's total value, or 0 if it exceeds the weight limit."""
    return np.where(pop @ weights <= limit, pop @ values, 0)


population = rng.random((50, 20)) < 0.2  # 50 random genomes, one bit per item
for generation in range(100):
    scores = fitness(population)
    # Tournament selection: each parent is the better of two random genomes
    pairs = rng.integers(50, size=(50, 2))
    parents = population[np.where(scores[pairs[:, 0]] > scores[pairs[:, 1]], pairs[:, 0], pairs[:, 1])]
    # Uniform crossover with the next parent, then flip each bit with probability 0.05
    children = np.where(rng.random((50, 20)) < 0.5, parents, np.roll(parents, 1, axis=0))
    children ^= rng.random((50, 20)) < 0.05
    children[0] = population[scores.argmax()]  # elitism: keep the best genome
    population = children

all_selections = np.array(list(itertools.product([0, 1], repeat=20)))
print(f"GA best: {fitness(population).max()}, true optimum: {fitness(all_selections).max()}")

Il affiche GA best: 811, true optimum: 811. L'algorithme a trouvé le meilleur remplissage possible après 5,000 évaluations de fitness, soit environ 0.5 % du million de sélections qu'il aurait fallu vérifier par force brute.

Faire évoluer les hyperparamètres#

Les paramètres d'entraînement tels que le taux d'apprentissage, les poids de la fonction de perte et l'intensité de l'augmentation interagissent de façon imprévisible par une formule, et chaque candidat nécessite un entraînement complet ; la recherche évolutionnaire est donc adaptée. La méthode tune() utilisée par Ultralytics YOLO applique cette approche aux modèles YOLO26 : à chaque itération, elle choisit un parent parmi les neuf meilleures configurations obtenues jusque-là, pondérées selon leur fitness, fait muter environ la moitié des 26 hyperparamètres de l'espace de recherche par défaut à l'aide de pas gaussiens proportionnels à leurs plages de recherche, entraîne un modèle et enregistre sa fitness, soit mAP_50-95 pour la détection d'objets. Après 30 résultats, certaines mutations tiennent également compte de la covariance des 20 % de meilleures configurations, une technique empruntée à CMA-ES. Le guide de réglage des hyperparamètres répertorie tout l'espace de recherche :

from ultralytics import YOLO

# Charger un modèle nano YOLO26 pré-entraîné
model = YOLO("yolo26n.pt")

# Faire évoluer les hyperparamètres : 30 itérations, chacune entraînant pendant 10 époques une configuration mutée
model.tune(data="coco8.yaml", epochs=10, iterations=30, plots=False)

Le régleur écrit chaque configuration et sa fitness dans tune_results.ndjson et enregistre la meilleure dans best_hyperparameters.yaml, prête à être utilisée lors d'un entraînement complet.

Autres applications#

• Recherche d'architectures neuronales : AmoebaNet de Google est issu de l'évolution régularisée, un AE à sélection par tournoi qui élimine les modèles les plus anciens plutôt que les moins performants ; il a atteint une précision top-1 de 83.9 % sur ImageNet en 2018.
• Conception technique : la mission Space Technology 5 de la NASA a embarqué en 2006 une antenne en bande X conçue par ordinateur grâce à l'évolution. Sa forme irrégulière en fil métallique courbé offrait des performances comparables à celles d'une antenne conçue de façon conventionnelle.
• Découverte d'algorithmes : annoncé par Google DeepMind en mai 2025, AlphaEvolve associe des modèles Gemini qui proposent des modifications de code à des évaluateurs automatiques et à une base de données évolutionnaire de programmes. Une heuristique de planification qu'il a fait évoluer pour les centres de données de Google récupère en moyenne 0.7 % des ressources de calcul mondiales de l'entreprise.

Algorithmes évolutionnaires et méthodes connexes#

• Descente de gradient : elle suit le gradient d'une fonction de perte différentiable et s'avère bien plus efficace pour entraîner les poids d'un réseau comprenant des millions de paramètres. Les AE conviennent aux problèmes comportant peu de paramètres, dont l'évaluation est coûteuse ou qui ne possèdent pas de gradient.
• Intelligence en essaim : des méthodes comme l'optimisation par essaim particulaire déplacent un ensemble persistant d'agents dans l'espace de recherche ; chaque agent ajuste sa position en fonction de son meilleur résultat et de ceux de ses voisins, sans remplacement générationnel, croisement ni mutation.
• Optimisation bayésienne : elle ajuste un modèle probabiliste de l'objectif et choisit chaque essai suivant là où ce modèle prévoit la plus grande amélioration. Elle nécessite moins d'évaluations qu'un AE dans les espaces de recherche petits et réguliers, mais passe moins bien à l'échelle lorsque le nombre de paramètres et de travailleurs parallèles augmente.