Cette page a été traduite par traduction automatique. Cliquez ici pour voir la dernière version en anglais.

Comment fonctionne l'algorithme génétique

Introduction à l'algorithme

Le schéma suivant résume le fonctionnement de l’algorithme génétique :

1. L'algorithme commence par créer une population initiale aléatoire.

2. L'algorithme crée ensuite une séquence de nouvelles populations. À chaque étape, l’algorithme utilise les individus de la génération actuelle pour créer la population suivante. Pour créer la nouvelle population, l'algorithme effectue les étapes suivantes :

   1. Évalue chaque membre de la population actuelle en calculant sa valeur de fitness. Ces valeurs sont appelées scores de condition physique bruts.

   2. Met à l'échelle les scores de fitness bruts pour les convertir en une plage de valeurs plus utilisables. Ces valeurs mises à l’échelle sont appelées valeurs d’espérance.

   3. Sélectionne les membres, appelés parents, en fonction de leurs attentes.

   4. Certains individus de la population actuelle qui ont une condition physique plus faible sont choisis comme élite. Ces individus d’élite sont transmis à la population suivante.

   5. Produit des enfants à partir des parents. Les enfants sont produits soit en apportant des modifications aléatoires à un seul parent (mutation), soit en combinant les entrées vectorielles d'une paire de parents (croisement).

   6. Remplace la population actuelle par les enfants pour former la prochaine génération.

3. L'algorithme s'arrête lorsqu'un des critères d'arrêt est rempli. Voir Conditions d'arrêt de l'algorithme.

4. L'algorithme prend des étapes modifiées pour les contraintes linéaires et entières. Voir Contraintes entières et linéaires.

5. L'algorithme est en outre modifié pour les contraintes non linéaires. Voir Algorithmes de résolution de contraintes non linéaires pour algorithmes génétiques.

Population initiale

L’algorithme commence par créer une population initiale aléatoire, comme le montre la figure suivante.

Dans cet exemple, la population initiale contient 20 individus. Notez que tous les individus de la population initiale se situent dans le quadrant supérieur droit de l’image, c’est-à-dire que leurs coordonnées se situent entre 0 et 1. Pour cet exemple, l'option InitialPopulationRange est [0;1].

Si vous savez approximativement où se trouve le point minimal d'une fonction, vous devez définir InitialPopulationRange de sorte que le point se trouve près du milieu de cette plage. Par exemple, si vous pensez que le point minimal pour la fonction de Rastrigin est proche du point [0 0], vous pouvez définir InitialPopulationRange sur [-1;1]. Cependant, comme le montre cet exemple, l’algorithme génétique peut trouver le minimum même avec un choix moins qu’optimal pour InitialPopulationRange.

Créer la prochaine génération

À chaque étape, l’algorithme génétique utilise la population actuelle pour créer les enfants qui composent la prochaine génération. L'algorithme sélectionne un groupe d'individus dans la population actuelle, appelés parents, qui transmettent leurs gènes (les entrées de leurs vecteurs) à leurs enfants. L’algorithme sélectionne généralement les individus qui ont de meilleures valeurs de condition physique en tant que parents. Vous pouvez spécifier la fonction que l'algorithme utilise pour sélectionner les parents dans l'option SelectionFcn. Voir Selection Options.

L'algorithme génétique crée trois types d'enfants pour la prochaine génération :

• Les enfants élites sont les individus de la génération actuelle qui présentent les meilleures valeurs de condition physique. Ces individus survivent automatiquement à la génération suivante.

• Les enfants issus de croisement sont créés en combinant les vecteurs d'une paire de parents.

• Les enfants issus de mutation sont créés en introduisant des changements aléatoires, ou mutations, dans un seul parent.

Le diagramme schématique suivant illustre les trois types d’enfants.

Mutation et croisement explique comment spécifier le nombre d'enfants de chaque type que l'algorithme génère et les fonctions qu'il utilise pour effectuer le croisement et la mutation.

Les sections suivantes expliquent comment l’algorithme crée des enfants issus de croisement et issus de mutation.

Enfants issus de croisement

L'algorithme crée des enfants issus de croisement en combinant des paires de parents dans la population actuelle. À chaque coordonnée du vecteur enfant, la fonction de croisement par défaut sélectionne aléatoirement une entrée, ou gène, à la même coordonnée de l'un des deux parents et l'attribue à l'enfant. Pour les problèmes avec des contraintes linéaires, la fonction de croisement par défaut crée l'enfant comme une moyenne pondérée aléatoire des parents.

Enfants issus d'une mutation

L'algorithme crée des enfants issus de mutation en modifiant aléatoirement les gènes de chaque parent. Par défaut, pour les problèmes sans contraintes, l'algorithme ajoute un vecteur aléatoire d'une distribution gaussienne au parent. Pour les problèmes bornés ou linéairement contraints, l'enfant reste faisable.

La figure suivante montre les enfants de la population initiale, c'est-à-dire la population de la deuxième génération, et indique s'il s'agit d'enfants élites, issus de croisement ou issus de mutation.

Tracés des générations futures

La figure suivante montre les populations aux itérations 60, 80, 95 et 100.

À mesure que le nombre de générations augmente, les individus de la population se rapprochent et se rapprochent du point minimum [0 0].

Conditions d'arrêt de l'algorithme

L'algorithme génétique utilise les options suivantes pour déterminer quand s'arrêter. Consultez les valeurs par défaut pour chaque option en exécutant opts = optimoptions('ga').

• MaxGenerations — L’algorithme s’arrête lorsque le nombre de générations atteint MaxGenerations.

• MaxTime — L'algorithme s'arrête après avoir été exécuté pendant une durée en secondes égale à MaxTime.

• FitnessLimit — L’algorithme s’arrête lorsque la valeur de la fonction fitness pour le meilleur point de la population actuelle est inférieure ou égale à FitnessLimit.

• MaxStallGenerations — L'algorithme s'arrête lorsque la variation relative moyenne de la valeur de la fonction fitness sur MaxStallGenerations est inférieure à Function tolerance.

• MaxStallTime — L'algorithme s'arrête s'il n'y a pas d'amélioration de la fonction objectif pendant un intervalle de temps en secondes égal à MaxStallTime.

• FunctionTolerance — L'algorithme s'exécute jusqu'à ce que la variation relative moyenne de la valeur de la fonction fitness sur MaxStallGenerations soit inférieure à Function tolerance.

• ConstraintTolerance — Le ConstraintTolerance n'est pas utilisé comme critère d'arrêt. Il est utilisé pour déterminer la faisabilité par rapport aux contraintes non linéaires. De plus, max(sqrt(eps),ConstraintTolerance) détermine la faisabilité par rapport aux contraintes linéaires.

L'algorithme s'arrête dès que l'une de ces conditions est remplie.

Sélection

La fonction de sélection choisit les parents pour la prochaine génération en fonction de leurs valeurs mises à l'échelle par la fonction de mise à l'échelle de la condition physique. Les valeurs de condition physique mises à l’échelle sont appelées valeurs attendues. Un individu peut être sélectionné plus d’une fois comme parent, auquel cas il transmet ses gènes à plus d’un enfant. L'option de sélection par défaut, @selectionstochunif, trace une ligne dans laquelle chaque parent correspond à une section de la ligne de longueur proportionnelle à sa valeur mise à l'échelle. L'algorithme se déplace le long de la ligne par pas de taille égale. À chaque étape, l’algorithme alloue un parent de la section sur laquelle il atterrit.

Une option de sélection plus déterministe est @selectionremainder, qui effectue deux étapes :

• Dans la première étape, la fonction sélectionne les parents de manière déterministe en fonction de la partie entière de la valeur mise à l’échelle pour chaque individu. Par exemple, si la valeur mise à l'échelle d'un individu est de 2,3, la fonction sélectionne cet individu deux fois comme parent.

• Dans la deuxième étape, la fonction de sélection sélectionne des parents supplémentaires en utilisant les parties fractionnaires des valeurs mises à l'échelle, comme dans la sélection uniforme stochastique. La fonction trace une ligne en sections, dont les longueurs sont proportionnelles à la partie fractionnaire de la valeur mise à l'échelle des individus, et se déplace le long de la ligne par pas égaux pour sélectionner les parents.

  Notez que si les parties fractionnaires des valeurs mises à l'échelle sont toutes égales à 0, comme cela peut se produire avec la mise à l'échelle Top, la sélection est entièrement déterministe.

Pour plus de détails et d'options de sélection, voir Selection Options.

Options de reproduction

Les options de reproduction contrôlent la manière dont l’algorithme génétique crée la prochaine génération. Les options sont

• EliteCount — Le nombre d’individus ayant les meilleures valeurs de condition physique dans la génération actuelle et qui sont assurés de survivre à la génération suivante. Ces individus sont appelés enfants élites.

  Lorsque EliteCount est au moins égal à 1, la meilleure valeur de fitness ne peut que diminuer d’une génération à l’autre. C’est ce que vous souhaitez qu’il se passe, puisque l’algorithme génétique minimise la fonction fitness. Définir EliteCount sur une valeur élevée amène les individus les plus aptes à dominer la population, ce qui peut rendre la recherche moins efficace.

• CrossoverFraction — La fraction d’individus de la génération suivante, autres que les enfants élites, qui sont créés par croisement. La rubrique « Définition de la fraction de croisement » dans Vary Mutation and Crossover décrit comment la valeur de CrossoverFraction affecte les performances de l'algorithme génétique.

Étant donné que les individus d’élite ont déjà été évalués, ga ne réévalue pas la fonction fitness des individus d’élite pendant la reproduction. Ce comportement suppose que la fonction d’aptitude d’un individu n’est pas aléatoire, mais est une fonction déterministe. Pour modifier ce comportement, utilisez une fonction de sortie. Voir EvalElites dans The State Structure.

Mutation et croisement

L’algorithme génétique utilise les individus de la génération actuelle pour créer les enfants qui composent la prochaine génération. Outre les enfants élites, qui correspondent aux individus de la génération actuelle avec les meilleures valeurs de fitness, l'algorithme crée

• Croiser les enfants en sélectionnant des entrées vectorielles, ou des gènes, à partir d'une paire d'individus de la génération actuelle et les combiner pour former un enfant

• Mutation des enfants en appliquant des changements aléatoires à un seul individu de la génération actuelle pour créer un enfant

Les deux processus sont essentiels à l’algorithme génétique. Le croisement permet à l’algorithme d’extraire les meilleurs gènes de différents individus et de les recombiner pour obtenir des enfants potentiellement supérieurs. La mutation ajoute à la diversité d’une population et augmente ainsi la probabilité que l’algorithme génère des individus avec de meilleures valeurs de fitness.

Voir Créer la prochaine génération pour un exemple de la manière dont l’algorithme génétique applique la mutation et le croisement.

Vous pouvez spécifier le nombre d'enfants de chaque type que l'algorithme crée comme suit :

• EliteCount spécifie le nombre d'enfants élites.

• CrossoverFraction spécifie la fraction de la population, autre que les enfants élites, qui sont des enfants issus de croisement.

Par exemple, si PopulationSize est 20, EliteCount est 2 et CrossoverFraction est 0.8, le nombre de chaque type d'enfants dans la génération suivante est le suivant :

• Il y a deux enfants élites.

• Il y a 18 individus autres que les enfants élites, donc l'algorithme arrondit 0,8*18 = 14,4 à 14 pour obtenir le nombre d'enfants issus de croisement.

• Les quatre individus restants, autres que les enfants élites, sont des enfants issus de mutation.

Contraintes entières et linéaires

Lorsqu'un problème comporte des contraintes entières ou linéaires (y compris des bornes), l'algorithme modifie l'évolution de la population.

• Lorsque le problème comporte à la fois des contraintes entières et linéaires, le logiciel modifie tous les individus générés pour qu'ils soient réalisables par rapport à ces contraintes. Vous pouvez utiliser n'importe quelle fonction de création, de mutation ou de croisement, et l'ensemble de la population reste réalisable par rapport aux contraintes entières et linéaires.

• Lorsque le problème n'a que des contraintes linéaires, le logiciel ne modifie pas les individus pour qu'ils soient réalisables par rapport à ces contraintes. Vous devez utiliser des fonctions de création, de mutation et de croisement qui maintiennent la faisabilité par rapport aux contraintes linéaires. Dans le cas contraire, la population peut devenir irréalisable et le résultat peut être irréalisable. Les opérateurs par défaut maintiennent la faisabilité linéaire : gacreationlinearfeasible ou gacreationnonlinearfeasible pour la création, mutationadaptfeasible pour la mutation et crossoverintermediate pour le croisement.

Les algorithmes internes pour la faisabilité entière et linéaire sont similaires à ceux de surrogateopt. Lorsqu'un problème comporte des contraintes entières et linéaires, l'algorithme crée d'abord des points linéairement réalisables. L'algorithme tente ensuite de satisfaire les contraintes d'entiers en arrondissant les points linéairement réalisables à des entiers à l'aide d'une heuristique qui tente de maintenir les points linéairement réalisables. Lorsque ce processus ne parvient pas à obtenir suffisamment de points réalisables pour construire une population, l'algorithme appelle intlinprog pour essayer de trouver davantage de points réalisables par rapport aux limites, aux contraintes linéaires et aux contraintes entières.

Plus tard, lorsque la mutation ou le croisement crée de nouveaux membres de la population, les algorithmes garantissent que les nouveaux membres sont entiers et linéairement réalisables en suivant des étapes similaires. Chaque nouveau membre est modifié, si nécessaire, pour être le plus proche possible de sa valeur d'origine, tout en satisfaisant les contraintes et limites entières et linéaires.

Voir aussi

Rubriques

• Genetic Algorithm Terminology
• Algorithmes de résolution de contraintes non linéaires pour algorithmes génétiques