Algorithme Génétique
Un algorithme génétique (AG) est une métaheuristique d’optimisation et de recherche inspirée par le processus de sélection naturelle et les mécanismes de l’évolution biologique. Il appartient à la classe plus large des algorithmes évolutionnaires. Les AG sont couramment utilisés pour générer des solutions de haute qualité à des problèmes d’optimisation et de recherche complexes, particulièrement lorsque les méthodes d’optimisation traditionnelles (basées sur le gradient ou l’énumération exhaustive) sont insuffisantes ou inapplicables en raison de la taille de l’espace de recherche, de la non-linéarité, de la discontinuité ou de la nature multimodale de la fonction objectif.
Les concepts fondamentaux des algorithmes génétiques reposent sur une analogie directe avec la biologie. Une population de solutions candidates potentielles, appelées individus ou chromosomes, est créée initialement, souvent de manière aléatoire. Chaque individu représente une solution au problème et est généralement encodé sous forme de chaîne de caractères (binaire, réelle, etc.), appelée chromosome, composée de gènes. La qualité de chaque solution est évaluée à l’aide d’une fonction d’évaluation, appelée fonction fitness, qui mesure à quel point l’individu est une bonne solution au problème. Plus le score de fitness est élevé, meilleure est la solution. Le processus évolutif se déroule ensuite sur plusieurs générations. À chaque génération, des individus sont sélectionnés en fonction de leur fitness pour devenir les parents de la génération suivante. Les individus ayant une meilleure fitness ont une probabilité plus élevée d’être sélectionnés. Les opérateurs génétiques, principalement le croisement (crossover) et la mutation, sont appliqués aux parents sélectionnés pour créer de nouveaux individus (descendants). Le croisement combine les informations génétiques de deux parents pour créer un ou plusieurs enfants, tandis que la mutation introduit de petites modifications aléatoires dans le chromosome d’un individu, favorisant ainsi la diversité génétique et évitant la convergence prématurée. La nouvelle population remplace l’ancienne (ou une partie de celle-ci), et le cycle de sélection, croisement et mutation se répète jusqu’à ce qu’un critère d’arrêt soit atteint (par exemple, un nombre maximal de générations, une stagnation de la meilleure solution trouvée, ou l’atteinte d’un seuil de fitness prédéfini).
L’importance des algorithmes génétiques réside dans leur capacité à explorer efficacement de vastes espaces de recherche complexes et mal compris. Contrairement aux méthodes de recherche locale qui peuvent rester bloquées dans des optima locaux, les AG maintiennent une population de solutions et utilisent des opérateurs stochastiques (sélection probabiliste, croisement, mutation) pour équilibrer l’exploration (recherche de nouvelles régions de l’espace) et l’exploitation (amélioration des solutions existantes). Cette robustesse les rend particulièrement pertinents pour les problèmes d’optimisation non différentiables, discontinus, bruités ou multimodaux, fréquents en ingénierie, en économie, en biologie et dans de nombreux autres domaines scientifiques et industriels. Ils permettent de découvrir des solutions innovantes et contre-intuitives que les approches traditionnelles pourraient manquer. Leur impact est significatif dans l’optimisation de systèmes complexes où une solution optimale exacte est difficile, voire impossible, à trouver dans un temps raisonnable.
Les applications pratiques des algorithmes génétiques sont nombreuses et variées. En ingénierie, ils sont utilisés pour l’optimisation de formes (par exemple, profils d’ailes d’avion), la conception de structures, l’optimisation de paramètres de contrôle, ou la conception de circuits électroniques. Dans le domaine de la logistique et de la recherche opérationnelle, ils sont appliqués à des problèmes d’ordonnancement complexes (comme l’ordonnancement d’ateliers), de routage de véhicules (incluant le problème du voyageur de commerce), et d’allocation de ressources. En finance, les AG aident à l’optimisation de portefeuilles d’actifs, à la découverte de stratégies de trading algorithmique et à la modélisation de risques. L’apprentissage automatique bénéficie également des AG, notamment pour la sélection de caractéristiques pertinentes dans de grands jeux de données, l’optimisation des hyperparamètres des modèles (comme les réseaux de neurones), et la conception d’architectures de réseaux neuronaux (Neuroévolution). En bio-informatique, ils servent à l’alignement de séquences d’ADN, à la prédiction de la structure des protéines et à la conception assistée par ordinateur de médicaments. Des applications existent aussi dans des domaines créatifs comme l’art génératif et la composition musicale assistée par ordinateur.
Il existe plusieurs nuances et variations autour du concept standard d’algorithme génétique. La manière dont les solutions sont représentées (encodage) peut varier considérablement : encodage binaire (le plus classique, proposé par Holland), encodage à valeurs réelles (pour les problèmes continus), encodage par permutation (pour les problèmes d’ordonnancement), ou encodage sous forme d’arbres (utilisé en programmation génétique). Les opérateurs génétiques eux-mêmes connaissent de multiples variantes : différents mécanismes de sélection (sélection par roulette biaisée, sélection par tournoi, sélection par rang), divers types de croisement (à un point, à deux points, uniforme, arithmétique) et de mutation (bit flip, gaussienne). Pour accélérer la convergence ou traiter des problèmes très larges, des algorithmes génétiques parallèles et distribués ont été développés. Les algorithmes génétiques multi-objectifs (MOGA) sont conçus pour les problèmes où plusieurs objectifs conflictuels doivent être optimisés simultanément, produisant un ensemble de solutions de compromis (front de Pareto). Des approches hybrides combinent les AG avec d’autres techniques, comme les algorithmes memétiques qui intègrent une phase de recherche locale (exploitation) après les opérateurs génétiques pour affiner les solutions.
Les algorithmes génétiques s’inscrivent dans un cadre plus large et sont liés à plusieurs autres concepts. Ils sont une composante majeure du Calcul Évolutionnaire, qui englobe d’autres techniques inspirées par l’évolution comme la Programmation Génétique (évolution de programmes informatiques), les Stratégies d’Évolution (souvent utilisées pour l’optimisation de paramètres réels) et la Programmation Évolutionnaire. D’autres métaheuristiques partagent des similarités dans leur approche stochastique de l’optimisation, telles que l’Optimisation par Essaim Particulaire (inspirée du comportement social des oiseaux ou poissons), le Recuit Simulé (inspiré du processus de recuit en métallurgie), ou l’Optimisation par Colonies de Fourmis. Ces méthodes, tout comme les AG, sont des formes d’Optimisation Stochastique et appartiennent à la catégorie des Heuristiques ou Métaheuristiques, car elles visent à trouver de bonnes solutions (proches de l’optimum) dans un temps raisonnable, sans garantir l’optimalité. En opposition, on trouve les méthodes d’optimisation déterministes, comme les méthodes basées sur le gradient (descente de gradient), et les méthodes exactes, comme la programmation linéaire ou dynamique, qui garantissent de trouver l’optimum global (sous certaines conditions) mais sont souvent limitées à des classes de problèmes spécifiques ou à des tailles de problèmes plus petites.
L’origine des algorithmes génétiques remonte aux années 1960 et 1970, avec les travaux pionniers de John Holland à l’Université du Michigan. Holland a formalisé les AG en s’inspirant explicitement de l’évolution biologique et de la génétique, introduisant les concepts de population, chromosome, gènes, fitness, croisement et mutation. Son livre « Adaptation in Natural and Artificial Systems » (1975) est considéré comme fondateur. Parallèlement, en Allemagne, Ingo Rechenberg et Hans-Paul Schwefel développaient les Stratégies d’Évolution dès les années 1960. Bien que distincts initialement, ces travaux ont contribué à l’émergence du domaine plus large du Calcul Évolutionnaire. Les AG ont gagné en popularité dans les années 1980 et 1990, notamment grâce aux travaux de David E. Goldberg et à l’augmentation de la puissance de calcul disponible. Depuis lors, ils ont connu un développement continu, avec de nombreuses variantes, améliorations théoriques et applications dans des domaines toujours plus diversifiés, s’intégrant de plus en plus aux techniques d’intelligence artificielle et d’apprentissage automatique.
Les algorithmes génétiques présentent plusieurs avantages notables. Leur principal atout est leur robustesse et leur capacité à traiter des problèmes d’optimisation complexes, non linéaires, non différentiables et multimodaux, là où d’autres méthodes échouent. Ils effectuent une recherche globale, réduisant le risque de se limiter à des optima locaux. Ils sont intrinsèquement parallèles, ce qui permet de les distribuer facilement sur plusieurs processeurs pour accélérer la recherche. Cependant, ils ont aussi des inconvénients et des limitations. La convergence vers une solution de haute qualité peut être lente, nécessitant parfois un grand nombre de générations. Le réglage des paramètres (taille de la population, taux de croisement, taux de mutation, stratégie de sélection) peut être délicat et a un impact significatif sur la performance ; il nécessite souvent une expertise ou des expérimentations. Il existe un risque de convergence prématurée, où la population perd sa diversité et converge vers un optimum local suboptimal. De plus, étant des méthodes stochastiques, les AG ne garantissent pas de trouver l’optimum global et peuvent produire des résultats légèrement différents à chaque exécution. La conception d’une représentation (encodage) appropriée et d’une fonction fitness efficace peut être un défi majeur pour certains problèmes. Enfin, pour des problèmes bien structurés où des algorithmes spécialisés existent, les AG peuvent être moins performants en termes de vitesse ou de qualité de la solution finale.