Les algorithmes évolutionnaires (AE) sont une classe de techniques d'optimisation métaheuristiques basées sur une population, inspirées par les mécanismes de l'évolution biologique, tels que la reproduction, la mutation, la recombinaison et la sélection. Ils sont utilisés pour trouver des solutions approximatives à des problèmes d'optimisation difficiles, lorsque les méthodes exactes ou satisfaisantes sont inconnues. En tant que partie de l'intelligence computationnelle et du calcul évolutionnaire, les AE opèrent sur une population de solutions candidates, évaluant leur qualité via une fonction de fitness et appliquant itérativement des opérateurs évolutionnaires pour améliorer la population au fil des générations. Leur principal avantage réside dans le fait qu'ils font peu d'hypothèses sur le paysage de fitness sous-jacent, ce qui leur permet de traiter une grande variété de problèmes, bien que leur complexité computationnelle provienne souvent du coût d'évaluation de la fitness.
Algorithme générique
L'algorithme évolutionnaire typique suit un processus itératif :
- Générer aléatoirement une population initiale d'individus (la première génération).
- Évaluer la fitness de chaque individu dans la population.
- Vérifier si l'objectif est atteint ; si oui, terminer.
- Sélectionner des individus comme parents, de préférence ceux ayant une fitness élevée.
- Produire une descendance par croisement (imitant la reproduction) et éventuellement par mutation.
- Appliquer des opérations de mutation à la descendance.
- Sélectionner des individus pour le remplacement, de préférence ceux ayant une fitness faible, afin de former la génération suivante.
- Revenir à l'étape 2 et répéter jusqu'à la terminaison.
Ce cadre générique est adapté dans différents types d'AE, chacun avec des représentations et des opérateurs spécifiques.
Types d'algorithmes évolutionnaires
Plusieurs variantes d'AE existent, différant par la représentation génétique et la mise en œuvre :
- Algorithme génétique (AG) : Le type le plus populaire, où les solutions sont représentées par des chaînes de caractères (souvent binaires). Des opérateurs comme le croisement et la mutation sont appliqués. Les AG sont largement utilisés dans les problèmes d'optimisation.
- Programmation génétique (PG) : Les solutions sont des programmes informatiques, et la fitness est déterminée par leur capacité à résoudre des problèmes computationnels. Des variantes incluent la programmation génétique cartésienne, la programmation génétique par expression de gènes, l'évolution grammaticale, la programmation génétique linéaire et la programmation génétique multi-expression.
- Stratégie d'évolution (SE) : Développée dans les années 1960 et 1970 par Ingo Rechenberg, Hans-Paul Schwefel et leurs collègues, la SE se concentre sur l'optimisation numérique et technique. Elle opère sur des vecteurs de nombres réels, utilisant la mutation, la recombinaison et une sélection déterministe. Une caractéristique distinctive est l'auto-adaptation de la distribution de mutation, avec des formes comme (1+1)-SE, (μ, λ)-SE et (μ+λ)-SE. Les développements ultérieurs incluent l'adaptation de matrice de covariance (CMA-ES) et les stratégies d'évolution naturelles.
- Évolution différentielle (ED) : Basée sur les différences vectorielles, principalement adaptée à l'optimisation numérique.
- Optimisation multi-objectif évolutionnaire : Étend les AE aux problèmes avec plusieurs objectifs conflictuels, maintenant une population qui approxime les solutions de compromis sur le front de Pareto.
- Algorithme co-évolutionnaire : Les solutions sont évaluées en fonction de leurs interactions avec d'autres solutions, qui peuvent être compétitives ou coopératives. Utile pour les paysages de fitness dynamiques ou compétitifs.
- Neuroévolution : Les génomes représentent des réseaux de neurones artificiels, encodant la structure et les poids de connexion, soit directement, soit indirectement.
- Système de classifieur d'apprentissage (LCS) : Les solutions sont des ensembles de classifieurs (règles). Le LCS de type Michigan fait évoluer des classifieurs individuels, tandis que le LCS de type Pittsburgh fait évoluer des populations de classifieurs. La fitness est déterminée par l'apprentissage par renforcement ou supervisé.
- Algorithmes de qualité-diversité (QD) : Visent simultanément à obtenir des solutions de haute qualité et diverses, explorant une large variété de solutions dans l'espace de problème.
Contexte théorique
Théorème du « no free lunch »
Le théorème du « no free lunch » en optimisation stipule que, lorsqu'on considère tous les problèmes d'optimisation possibles, toutes les stratégies d'optimisation sont également efficaces. Cela implique qu'aucun algorithme évolutionnaire n'est fondamentalement supérieur à un autre sur l'ensemble des problèmes. Cependant, en pratique, l'ensemble des problèmes est restreint, et les AE peuvent être améliorés en exploitant des connaissances spécifiques au problème, comme le choix de représentations et d'opérateurs appropriés.
Complexité computationnelle
Dans la plupart des applications réelles, la complexité computationnelle des AE est un facteur significatif, principalement en raison du coût de l'évaluation de la fonction de fitness. Des techniques d'approximation de la fitness peuvent atténuer ce problème. Il est intéressant de noter que des AE simples peuvent souvent résoudre des problèmes complexes, ce qui suggère qu'il n'y a pas de lien direct entre la complexité de l'algorithme et celle du problème.
Applications et limites
Les algorithmes évolutionnaires sont appliqués dans divers domaines, notamment l'ingénierie, l'ordonnancement, l'apprentissage automatique (par exemple, la neuroévolution) et l'optimisation multi-objectif. Ils sont particulièrement utiles lorsque l'espace de recherche est vaste, non linéaire ou mal compris. Cependant, leurs performances dépendent du réglage des paramètres et de la représentation du problème. Des techniques issues des AE sont également utilisées pour modéliser la microévolution biologique et les processus cellulaires, bien que cela présente des limites.