Qu'est-ce qu'un algorithme génétique ?
Un algorithme génétique est une méthode permettant de résoudre les problèmes d'optimisation avec et sans contraintes, basée sur la sélection naturelle, le processus qui pilote l'évolution biologique. L'algorithme génétique modifie à plusieurs reprises une population de solutions individuelles. À chaque étape, l’algorithme génétique sélectionne des individus de la population actuelle pour être parents et les utilise pour produire les enfants de la génération suivante. Au fil des générations successives, la population « évolue » vers une solution optimale. Vous pouvez appliquer l'algorithme génétique pour résoudre une variété de problèmes d'optimisation qui ne sont pas bien adaptés aux algorithmes d'optimisation standard, y compris les problèmes dans lesquels la fonction objectif est discontinue, non différentiable, stochastique ou hautement non linéaire. L'algorithme génétique peut résoudre les problèmes de programmation mixte en nombres entiers, où certains composants sont limités à des valeurs entières.
Ce diagramme de flux décrit les principales étapes algorithmiques. Pour plus de détails, voir Comment fonctionne l'algorithme génétique.
L'algorithme génétique utilise trois principaux types de règles à chaque étape pour créer la prochaine génération à partir de la population actuelle :
Les règles de sélection sélectionnent les individus, appelés parents, qui contribuent à la population de la génération suivante. La sélection est généralement stochastique et peut dépendre des scores des individus.
Les règles de croisement combinent deux parents pour former des enfants pour la génération suivante.
Les règles de mutation appliquent des changements aléatoires aux parents individuels pour former des enfants.
L'algorithme génétique diffère d'un algorithme d'optimisation classique basé sur les dérivées de deux manières principales, comme le résume le tableau suivant :
| Algorithme classique | Algorithme génétique |
|---|---|
Génère un seul point à chaque itération. La séquence de points se rapproche d'une solution optimale. | Génère une population de points à chaque itération. Le meilleur point de la population se rapproche d’une solution optimale. |
Sélectionne le point suivant de la séquence par un calcul déterministe. | Sélectionne la population suivante par calcul qui utilise des générateurs de nombres aléatoires. |
Converge généralement rapidement vers une solution locale. | Il faut généralement de nombreuses évaluations de fonctions pour converger. Peut ou non converger vers un minimum local ou global. |
