Skip to content
Retour aux résultats

Algorithme Génétique Stochastique — Recherche Évolutionnaire Aléatoire pour l'Optimisation

Introduite par
Holland, J. H.
Année
1975
Type
Stochastic evolutionary metaheuristic
Famille
Simulation / optimization

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

L'Algorithme Génétique Stochastique (AGS) est une métaheuristique basée sur la population qui imite l'évolution biologique — sélection, croisement et mutation — pour rechercher des solutions quasi optimales dans des espaces complexes, non linéaires ou combinatoires.

Ses opérateurs aléatoires le rendent robuste face aux optima locaux et largement applicable en ingénierie, en planification, en apprentissage automatique et en recherche opérationnelle.

L’intuition derrière la méthode

Imaginez une population de solutions candidates en compétition pour la survie. Les meilleures solutions sont plus susceptibles d'être choisies comme parents ; leur descendance hérite et recombine de bons traits, tandis que des mutations aléatoires occasionnelles introduisent de la nouveauté. Sur de nombreuses générations, ce processus converge vers des régions de haute qualité de l'espace de recherche sans nécessiter d'informations de gradient. L'étiquette « stochastique » souligne que la sélection, le croisement et la mutation impliquent tous des tirages probabilistes, ce qui distingue l'AG canonique des rares variantes déterministes et lui confère une capacité de recherche globale.

Histoire

John Holland a introduit les fondements théoriques des algorithmes génétiques à l'Université du Michigan en 1975, s'appuyant sur les travaux antérieurs de Fraser (1957) sur les systèmes génétiques simulés. Le manuel de David Goldberg de 1989 a popularisé les AG pour l'optimisation en ingénierie. La nature stochastique de la sélection a été formalisée par le théorème du schéma, et la méthode est devenue une pierre angulaire de l'informatique évolutionnaire et de l'intelligence computationnelle.

Quand l’utiliser

Utilisez un algorithme génétique stochastique lorsque : (1) l'espace de recherche est grand, multimodal ou discontinu et que les méthodes basées sur le gradient échouent ou sont inapplicables ; (2) la fonction objectif est une boîte noire, bruyante ou coûteuse à évaluer mais traitable pour un échantillonnage au niveau de la population ; (3) les problèmes combinatoires ou à variables mixtes n'ont pas de solveurs exacts efficaces ; (4) une solution quasi optimale trouvée dans un nombre raisonnable d'évaluations est acceptable. N'utilisez PAS l'AGS lorsque : le problème est convexe ou que le gradient est disponible et peu coûteux — l'optimisation classique converge plus rapidement ; lorsque les évaluations de fonction sont extrêmement coûteuses (dizaines ou centaines), les méthodes basées sur la population peuvent épuiser le budget ; ou lorsqu'une solution prouvablement optimale est requise, car les AG n'offrent aucune garantie d'optimalité.

Limites et points d’attention

  • Aucune garantie de trouver l'optimum global ; la qualité de la solution dépend de la taille de la population, des choix d'opérateurs et du nombre de générations.
  • Coûteux en calcul par rapport aux méthodes basées sur le gradient pour les problèmes lisses et de faible dimension — de nombreuses évaluations de fonction sont nécessaires.
  • L'ajustement des hyperparamètres (taille de la population, taux de croisement, taux de mutation) dépend du problème et nécessite souvent de l'expérimentation.
  • Une convergence prématurée peut se produire si la pression de sélection est trop élevée ou si le taux de mutation est trop faible, piégeant la recherche dans des régions sous-optimales.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Ne nécessite pas d'informations de gradient — applicable aux objectifs de type boîte noire, discontinus ou non différentiables.
  • Gère naturellement les espaces de recherche combinatoires, à variables mixtes et de permutation avec un encodage approprié.
  • Parallélisable par conception : la population peut être évaluée en parallèle, réduisant le temps d'exécution réel.
  • Robuste contre les optima locaux grâce à la diversité de la population et à l'exploration stochastique.
  • Très extensible : les opérateurs, les encodages et les schémas de sélection peuvent être personnalisés pour des contraintes spécifiques au domaine.

Applications

  • Ordonnancement d'ateliers (job-shop et flow-shop) dans la fabrication et la logistique
  • Sélection de caractéristiques et réglage des hyperparamètres dans les pipelines d'apprentissage automatique
  • Optimisation structurelle et topologique en ingénierie mécanique et civile
  • Problèmes du voyageur de commerce et de routage de véhicules en recherche opérationnelle
  • Prédiction de la structure des protéines et découverte de médicaments en bioinformatique
  • Recherche d'architecture de réseaux neuronaux et optimisation des poids

Comment ça marche

Comment ça marche

1

Générer une population initiale de N solutions candidates (chromosomes) de manière aléatoire ou par ensemencement heuristique. Chaque chromosome encode un point réalisable dans l'espace de décision — chaînes binaires, vecteurs réels, permutations ou arbres selon la représentation du problème choisie.

2

Calculer la fitness f(x_i) pour chaque individu de la population à l'aide de la fonction objectif (ou d'un substitut). La fitness quantifie la qualité de la solution ; une fitness plus élevée signifie une meilleure solution. Pour les problèmes de minimisation, la fitness est souvent définie comme l'inverse ou une transformation de la fonction de coût.

Formule
f(x_i), \quad i = 1, \ldots, N
3

Appliquer un opérateur de sélection stochastique pour choisir les parents. La sélection par roulette (proportionnelle à la fitness) attribue à chaque individu une probabilité proportionnelle à sa fitness. La sélection par tournoi, la sélection par rang et l'élitisme sont des variantes courantes qui contrôlent la pression de sélection.

Formule
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}
4

Avec une probabilité p_c (généralement 0,6–0,9), recombiner des paires de parents sélectionnés pour produire une descendance. Le croisement à un point, à deux points ou uniforme échange du matériel génétique entre les chromosomes parents, créant des enfants qui héritent des traits des deux. Cet opérateur favorise l'exploitation de bons blocs de construction.

5

Avec une faible probabilité p_m (généralement 0,001–0,05 par gène), modifier aléatoirement des gènes individuels dans chaque chromosome de la descendance. La mutation maintient la diversité génétique, empêche la convergence prématurée et garantit que l'algorithme peut échapper aux optima locaux. Le taux de mutation est un paramètre critique ajusté au problème.

6

Remplacer la population actuelle par la descendance (remplacement générationnel) ou utiliser des mises à jour en régime permanent. Évaluer à nouveau la fitness et répéter à partir de l'étape de sélection jusqu'à ce qu'un critère d'arrêt soit satisfait — nombre maximal de générations, un seuil de fitness, ou aucune amélioration sur un nombre défini de générations.

Pièges courants

  • L'utilisation d'un taux de mutation trop élevé réduit l'algorithme à une recherche aléatoire et détruit les gains de fitness accumulés.
  • Ignorer l'élitisme dans la stratégie de remplacement peut entraîner la perte de la meilleure solution trouvée entre les générations.
  • L'application d'opérateurs de croisement à valeurs réelles à des problèmes encodés en binaire (ou vice versa) brise l'encodage et produit une descendance irréalisable.
  • Un arrêt trop précoce — générations insuffisantes — est la raison la plus courante d'une mauvaise qualité de solution en pratique.
  • Négliger la gestion des contraintes : le croisement et la mutation non contraints violent fréquemment les contraintes du problème ; des fonctions de pénalité ou des opérateurs de réparation doivent être explicitement intégrés.

Questions fréquentes

En quoi un algorithme génétique stochastique est-il différent d'un algorithme génétique standard ?

L'étiquette « stochastique » souligne que tous les opérateurs fondamentaux — sélection, croisement et mutation — impliquent des tirages probabilistes. L'AG canonique introduit par Holland est intrinsèquement stochastique. L'étiquette est utilisée dans la littérature sur la simulation/optimisation pour le distinguer des rares variantes déterministes (par exemple, le crowding déterministe) et pour clarifier que le comportement de l'algorithme varie d'une exécution à l'autre en raison de l'aléatoire.

Quelle doit être la taille de la population ?

Un point de départ courant est de 50 à 200 individus pour les problèmes de dimension modérée. Des populations plus grandes améliorent la diversité et réduisent la convergence prématurée, mais augmentent le coût de calcul par génération. Des règles empiriques basées sur la longueur du chromosome (par exemple, 10 fois le nombre de gènes) existent, mais un ajustement empirique ou une méta-optimisation est souvent nécessaire.

Quand devrais-je préférer l'optimisation par essaim de particules ou le recuit simulé à un algorithme génétique ?

L'optimisation par essaim de particules (PSO) est souvent plus rapide sur les problèmes continus à valeurs réelles car elle exploite les informations de vitesse. Le recuit simulé (SA) est plus simple à implémenter et peut être efficace pour la recherche de trajectoire de solution unique. Les AG sont préférés lorsque l'espace de recherche est combinatoire, lorsque le croisement recombine de manière significative les structures de solution, ou lorsque la diversité de la population est précieuse pour les paysages multimodaux.

L'algorithme génétique stochastique s'adapte-t-il aux problèmes de grande dimension ?

Les performances se dégradent dans les très grandes dimensions (des centaines à des milliers de variables) car la population doit être suffisamment grande pour échantillonner adéquatement l'espace. Des variantes spécialisées — telles que les AG d'apprentissage de liens, les algorithmes d'estimation de distribution ou les modèles d'îles avec migration — abordent l'évolutivité mais ajoutent de la complexité.

Comment gérer les contraintes dans un algorithme génétique ?

Trois stratégies principales sont utilisées : (1) les fonctions de pénalité qui réduisent la fitness en cas de violation des contraintes ; (2) les opérateurs de réparation qui projettent la descendance infaisable dans la région faisable ; (3) les encodages et opérateurs spécialisés qui ne produisent que des solutions faisables par construction. Les méthodes basées sur les pénalités sont les plus faciles à implémenter mais nécessitent un étalonnage minutieux des coefficients de pénalité.

Méthodes associées

Sources

  1. Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.

    ISBN : 978-0262581110
    Copié.
  2. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.

    ISBN : 978-0201157673
    Copié.