Un algorithme génétique est une technique de recherche et d'optimisation inspirée des principes de la sélection naturelle, dans laquelle une population de solutions candidates est itérativement évoluée à travers des opérations analogues à la mutation, au croisement (recombinaison) et à la sélection, afin d'améliorer la fitness vers un objectif défini au fil des générations successives. Les algorithmes génétiques appartiennent à la famille plus large des méthodes de calcul évolutionnaire dans le cadre de intelligence artificielle et apprentissage automatique.
Mécanisme
Un algorithme génétique commence par une population de solutions candidates générée aléatoirement, chacune typiquement encodée sous forme de chaîne ou de vecteur analogue à un chromosome. Chaque candidate est évaluée à l'aide d'une fonction de fitness qui attribue un score indiquant dans quelle mesure elle résout le problème cible. Les candidates ayant les scores les plus élevés sont plus susceptibles d'être sélectionnées comme « parents », dont les encodages sont combinés par croisement pour produire une progéniture, avec des mutations aléatoires introduites occasionnellement pour maintenir la diversité et éviter une convergence prématurée vers une solution sous-optimale. Ce cycle d'évaluation, de sélection et de recombinaison se répète sur de nombreuses générations, la population dans son ensemble tendant à améliorer sa fitness moyenne au fil du temps, bien que rien ne garantisse la découverte d'un optimum global.
Histoire
Les fondements mathématiques du domaine ont été formalisés par John Holland, dont le livre de 1975 « Adaptation in Natural and Artificial Systems » a introduit les algorithmes génétiques comme un cadre général pour la recherche adaptative, s'appuyant sur des expériences antérieures de calcul évolutionnaire datant des années 1950 et 1960. Les étudiants et collaborateurs de Holland, notamment David Goldberg, ont étendu le fondement théorique du cadre et popularisé les applications pratiques au cours des années 1980 et 1990.
Applications
Les algorithmes génétiques ont été appliqués à des problèmes d'ordonnancement et de routage, à l'optimisation de conception en ingénierie, notamment pour des formes d'antennes et aérodynamiques évaluées par la NASA et d'autres, à la synthèse automatisée de programmes dans le cadre du domaine connexe de la programmation génétique, et à la recherche d'hyperparamètres pour les systèmes d'apprentissage automatique. Ils sont particulièrement privilégiés pour des problèmes présentant des espaces de recherche vastes, complexes et non différentiables, où les méthodes basées sur le gradient sont indisponibles ou inefficaces, car les algorithmes génétiques ne nécessitent que la capacité d'évaluer la fitness d'une candidate, sans avoir à calculer de dérivée de l'objectif.
Neuroévolution
Un domaine d'application notable, la neuroévolution, utilise des méthodes évolutionnaires pour concevoir ou entraîner des architectures et des poids de réseaux de neurones, parfois combinées avec apprentissage par renforcement pour des tâches de contrôle et de jeu. La neuroévolution a été explorée comme alternative ou complément aux réseaux entraînés par rétropropagation dans la recherche en robotique et IA incarnée, où le signal de récompense est clairsemé ou où la topologie du réseau elle-même, et pas seulement ses poids, est une variable de conception.
Limites et pertinence moderne
Les algorithmes génétiques s'adaptent mal aux espaces de paramètres très dimensionnels des réseaux profonds modernes par rapport à l'optimisation basée sur descente de gradient telle que rétropropagation, et ont largement reculé de la recherche dominante lorsque les architectures d'apprentissage profond entraînées par rétropropagation ont pris le dessus après le début des années 2010. Ils restent néanmoins activement utilisés dans des domaines d'optimisation en dehors de l'entraînement supervisé standard, dans des niches de neuroévolution, et comme point de référence conceptuel pour la recherche sur les approches ouvertes et évolutionnaires visant à générer des solutions diverses et novatrices plutôt que d'optimiser un objectif unique fixe.