Technique de recherche stochastique basée sur une population, inspirée de la sélection naturelle, qui applique itérativement sélection, croisement (recombinaison) et mutation à une population de solutions codées, en utilisant une fonction d'aptitude pour orienter la recherche vers de meilleures solutions.

Principe

Maintenir une population diverse de génotypes, appliquer des opérateurs de variation (croisement, mutation) pour générer des descendants, évaluer l'aptitude, et sélectionner des individus pour la génération suivante de sorte que les solutions les plus aptes soient plus susceptibles de se propager tout en conservant l'exploration par le hasard.

Démonstration

Résoudre un problème d'ordonnancement en encodant les plannings comme chromosomes (par ex. vecteurs de permutation), définir une fonction d'aptitude pénalisant conflits et retards, initialiser une population, appliquer un croisement qui respecte la structure de permutation et des mutations qui échangent des éléments, puis itérer sélection et variation jusqu'à obtenir un planning satisfaisant ; surveiller la diversité pour éviter la convergence prématurée.

Mauvaise application

Utiliser des encodages pauvres qui détruisent la structure du problème (de sorte que le croisement produit des descendants invalides ou dénués de sens), négliger la pression de sélection ou la diversité conduisant à une convergence prématurée, ou appliquer un AG là où des algorithmes exacts en temps polynomial existent et sont préférables.

Conséquence

Capacité à explorer des espaces de recherche complexes, multimodaux et discrets et à produire des solutions approchées de haute qualité sans information de gradient ; les résultats sont stochastiques, nécessitant souvent plusieurs runs et un réglage soigneux des paramètres (taille de population, taux de mutation, pression de sélection).

Inversion

Méthodes d'optimisation déterministes (p. ex. descente de gradient, branch-and-bound) qui exploitent la structure analytique du problème et peuvent fournir des garanties ou des solutions exactes lorsque c'est applicable, mais qui peuvent échouer sur des paysages non différentiables ou très discontinus.

Limite

S'emploie mieux pour des problèmes dont les solutions peuvent être encodées et évaluées par une fonction d'aptitude et pour lesquels l'information dérivée est indisponible ou peu fiable ; il ne garantit pas l'optimum global et peut être coûteux lorsque l'évaluation de l'aptitude est onéreuse.

Tension sémantique

Tension entre exploration et exploitation contrôlée par le taux de mutation, la conception du croisement et la pression de sélection ; recouvre et diffère d'autres méthodes évolutionnaires (stratégies d'évolution, programmation génétique) principalement par la représentation, les opérateurs et l'accent mis sur la recombinaison vs la mutation.

Synthèse

Les algorithmes génétiques font évoluer une population de candidats codés via sélection et variation, équilibrant la préservation des bonnes structures et l'introduction de nouveauté ; leur succès dépend de la représentation, du design des opérateurs et des paramètres, et ils constituent une méthode robuste et stochastique pour l'optimisation sur des paysages de recherche complexes.