Algorithme génétique — Optimisation évolutionnaire
- Introduite par
- John Henry Holland
- Année
- 1975
- Type
- Population-based metaheuristic
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
Un algorithme génétique (AG) est une méthode d'optimisation métaheuristique basée sur la population, introduite par John Henry Holland (1975), qui imite les principes de la sélection naturelle.
Il maintient une population de solutions candidates et les améliore itérativement par des opérateurs de sélection, de croisement et de mutation, ce qui le rend particulièrement puissant dans les espaces de recherche discontinus, non convexes et multimodaux où les méthodes classiques basées sur le gradient échouent.
L’intuition derrière la méthode
Imaginez que vous ayez des milliers de réponses possibles à un problème difficile et aucune formule pour trouver la meilleure. Un algorithme génétique traite chaque réponse candidate comme un individu dans une population. À chaque génération, il conserve les individus les plus aptes, les "reproduit" pour mélanger leurs bons traits, et mute occasionnellement la progéniture pour injecter de la nouveauté. Sur de nombreuses générations, la population dérive vers des solutions de plus en plus performantes — non pas en suivant un gradient, mais en imitant la façon dont l'évolution façonne les organismes au fil du temps.
Histoire
L'algorithme génétique a été introduit par John Henry Holland dans son livre de 1975, Adaptation in Natural and Artificial Systems, qui a formalisé la notion de schéma (bloc de construction) et a fourni l'analyse théorique fondamentale expliquant pourquoi le croisement et la sélection dirigent la recherche vers des régions plus aptes. Les étudiants de Holland — notamment David Goldberg — ont popularisé les AG à travers des applications d'ingénierie dans les années 1980. Kalyanmoy Deb a ensuite étendu le cadre aux contextes multi-objectifs, aboutissant à l'algorithme NSGA-II (2002) largement adopté. Aujourd'hui, les AG restent un outil standard en calcul évolutionnaire, avec une recherche active sur les méthodes hybrides qui combinent la recherche évolutionnaire avec le raffinement local.
Quand l’utiliser
Les algorithmes génétiques sont appropriés lorsque l'espace de recherche est vaste, discontinu, non différentiable ou fortement multimodal — conditions dans lesquelles les solveurs basés sur le gradient ne peuvent pas fonctionner ou restent bloqués dans des optima locaux. Ils s'appliquent aux types de variables continues, catégorielles, binaires et ordinales et n'imposent aucune hypothèse de normalité ou de distribution. La seule exigence est une fonction d'aptitude calculable. Pour les problèmes où une formulation analytique ou convexe existe, les méthodes classiques (programmation linéaire, descente de gradient) sont plus rapides et doivent être préférées. Un nombre suffisant d'itérations (généralement bien au-delà de 1 000 générations) est nécessaire pour une convergence significative ; un nombre insuffisant de générations est le mode de défaillance le plus courant.
Limites et points d’attention
- Aucune garantie de convergence vers l'optimum global ; les résultats peuvent varier d'une exécution à l'autre.
- Coûteux en calcul : chaque génération nécessite l'évaluation de l'ensemble de la population, ce qui est prohibitif lorsque la fonction d'aptitude est lente.
- La performance est sensible aux choix des hyperparamètres — taille de la population, probabilité de croisement et taux de mutation — qui nécessitent souvent un ajustement spécifique au problème.
- Pour les problèmes lisses, convexes ou bien structurés, les méthodes classiques basées sur le gradient ou linéaires seront plus rapides et plus fiables.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Fonctionne sur des paysages objectifs discontinus, non différentiables et multimodaux où les méthodes basées sur le gradient échouent.
- N'impose aucune hypothèse de distribution — la seule entrée requise est une fonction d'aptitude calculable.
- Gère naturellement un large éventail de types de variables : continues, binaires, catégorielles et ordinales.
- La diversité de la population permet l'exploration simultanée de multiples régions de l'espace de recherche, réduisant le risque de piégeage prématuré dans un optimum local.
- Hautement extensible : les opérateurs de croisement et de mutation spécifiques au domaine, la gestion des contraintes et les variantes multi-objectifs (par exemple, NSGA-II) sont bien établis dans la littérature.
Applications
- Optimisation de la conception en ingénierie : trouver des configurations de paramètres optimales pour les structures, les circuits ou les systèmes mécaniques.
- Problèmes d'ordonnancement et de routage : ordonnancement d'ateliers, routage de véhicules et élaboration d'horaires où l'espace de recherche combinatoire est trop vaste pour une recherche exhaustive.
- Apprentissage automatique : réglage des hyperparamètres, recherche d'architecture neuronale et sélection de caractéristiques.
- Recherche opérationnelle : optimisation de la chaîne d'approvisionnement, allocation de portefeuille et affectation de ressources sous des contraintes complexes.
- Bioinformatique : alignement de séquences, prédiction de la structure des protéines et inférence de réseaux de régulation génique.
Comment ça marche
Comment ça marche
Une population de solutions candidates (individus) est créée, généralement de manière aléatoire dans l'espace de recherche. Chaque individu encode une solution potentielle — par exemple sous forme de chaîne binaire, de vecteur à valeurs réelles ou de permutation — et la taille de la population est un paramètre clé qui détermine l'étendue de l'échantillonnage de l'espace de recherche dès le départ.
Chaque individu de la population est évalué par une fonction d'aptitude qui quantifie la qualité de cette solution par rapport à l'objectif du problème. La fonction d'aptitude est le seul composant spécifique au domaine que l'utilisateur doit fournir ; elle peut être n'importe quelle mesure calculable — un résultat de simulation, une formule de coût ou une métrique d'erreur de modèle.
Les individus ayant une aptitude plus élevée sont choisis préférentiellement pour devenir les parents de la génération suivante. Les mécanismes de sélection courants incluent la sélection par tournoi, la sélection par roulette (proportionnelle à l'aptitude) et la sélection basée sur le rang. La pression de sélection contrôle le compromis entre l'exploitation de solutions de haute qualité et le maintien de la diversité de la population.
Les parents sélectionnés produisent une progéniture par croisement (recombinaison), où des segments de deux encodages parentaux sont combinés pour former un nouvel individu, et par mutation, où de petits changements aléatoires sont appliqués à des gènes individuels. La probabilité de croisement et le taux de mutation sont des paramètres d'ajustement critiques : trop peu de mutation entraîne une convergence prématurée, trop transforme la recherche en une marche aléatoire.
La boucle évaluer → sélectionner → reproduire se poursuit pendant un nombre défini de générations ou jusqu'à ce qu'un critère de convergence soit atteint (par exemple, aucune amélioration sur une fenêtre de générations). Le meilleur individu trouvé sur toutes les générations est renvoyé comme solution. Étant donné que la convergence vers l'optimum global n'est pas garantie, plusieurs exécutions indépendantes sont recommandées pour les problèmes à enjeux élevés.
Pièges courants
- Exécuter trop peu de générations est l'erreur la plus courante : avec un nombre insuffisant de générations, l'algorithme ne converge pas, de sorte que les méthodes analytiques ou basées sur le gradient doivent être préférées lorsqu'un budget d'itération limité est disponible.
- La convergence prématurée — la perte de diversité de la population trop tôt — produit un résultat localement optimal mais globalement sous-optimal ; maintenir une taille de population et un taux de mutation adéquats pour contrer cela.
- L'utilisation d'une fonction d'aptitude mal définie ou mal spécifiée produit des résultats trompeurs quelle que soit la correction algorithmique ; valider la fonction d'aptitude indépendamment avant d'exécuter l'AG.
- L'application d'un AG à un problème lisse et convexe où la descente de gradient ou la programmation linéaire suffirait gaspille des ressources de calcul et introduit une stochasticité inutile.
- Rapporter une seule exécution comme solution sans vérifier la reproductibilité ; pour les applications à enjeux élevés, exécuter l'algorithme plusieurs fois et rapporter la distribution des résultats.
Questions fréquentes
En quoi un algorithme génétique est-il différent de la descente de gradient ?
La descente de gradient nécessite un objectif différentiable et suit le gradient local en descendant. Un algorithme génétique exige seulement que l'aptitude puisse être calculée pour toute solution candidate ; il recherche en faisant évoluer une population plutôt qu'en suivant un gradient, il peut donc gérer des paysages discontinus, non différentiables et multimodaux où la descente de gradient échoue ou reste bloquée.
Combien de générations et quelle taille de population me faut-il ?
Il n'y a pas de règles universelles ; les deux dépendent de la complexité de l'espace de recherche. Une population trop petite ou une exécution trop courte risque une convergence prématurée. Comme point de départ pratique, des tailles de population de 50 à 200 et des nombres de générations de 100 à 1 000 sont courants dans la littérature, mais les problèmes difficiles en exigent régulièrement davantage. Toujours inspecter les courbes de convergence plutôt que de fixer des critères d'arrêt arbitraires.
Un algorithme génétique est-il garanti de trouver l'optimum global ?
Non. Les AG sont des heuristiques et ne fournissent aucune garantie de convergence vers l'optimum global en temps fini. Pour des garanties déterministes, vous avez besoin de méthodes exactes telles que les solveurs de programmation en nombres entiers. Pour les décisions à enjeux élevés, exécutez l'AG plusieurs fois, rapportez la distribution des résultats et comparez la meilleure solution à toute borne connue.
Quand dois-je choisir un AG plutôt que le recuit simulé ou l'optimisation par essaim de particules ?
Les AG sont généralement préférés lorsque la solution est naturellement encodée comme une structure combinatoire (permutations, chaînes binaires) ou lorsque des extensions multi-objectifs sont nécessaires. L'optimisation par essaim de particules est souvent plus rapide sur les problèmes unimodaux continus. Le recuit simulé est plus simple à implémenter pour les problèmes combinatoires avec un voisinage bien défini. En pratique, il est conseillé de comparer deux ou trois méthodes sur une petite instance de problème avant de s'engager sur l'une d'elles.
Méthodes associées
Sources
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
Ouvrir la référence de la publicationCopié.Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.
ISBN : 9780471873396Copié.