Contenu principal

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

Effets des options d'algorithmes génétiques

Cet exemple montre les effets de certaines options pour la fonction d'algorithme génétique ga. Vous créez et modifiez des options en utilisant la fonction optimoptions.

Créer un problème pour ga

ga recherche un minimum d'une fonction en utilisant l'algorithme génétique. Pour cet exemple, utilisez ga pour minimiser la fonction fitness shufcn, une fonction à valeur réelle de deux variables.

Tracez shufcn sur la plage = [-2 2;-2 2] en appelant plotobjective, qui est inclus lorsque vous exécutez cet exemple.

plotobjective(@shufcn,[-2 2; -2 2]);

Figure contains an axes object. The axes object contains 2 objects of type surface, contour.

Pour utiliser le solveur ga, fournissez au moins deux arguments en entrée : une fonction fitness et le nombre de variables dans le problème. Les deux premiers arguments de sortie renvoyés par ga sont x, le meilleur point trouvé, et Fval, la valeur de la fonction au meilleur point. Un troisième argument de sortie, exitFlag, indique pourquoi ga s'est arrêté. ga peut également renvoyer un quatrième argument, Output, qui contient des informations sur les performances du solveur.

FitnessFunction = @shufcn;
numberOfVariables = 2;

Exécutez le solveur ga.

rng default % For reproducibility
[x,Fval,exitFlag,Output] = ga(FitnessFunction,numberOfVariables);
ga stopped because the average change in the fitness value is less than options.FunctionTolerance.
fprintf('The number of generations is: %d\n', Output.generations);
The number of generations is: 124
fprintf('The number of function evaluations is: %d\n', Output.funccount);
The number of function evaluations is: 5881
fprintf('The best function value found is: %g\n', Fval);
The best function value found is: -186.199

Si vous exécutez cet exemple sans la commande rng default, vos résultats peuvent différer, car ga est un algorithme stochastique.

Comment fonctionne l'algorithme génétique

L'algorithme génétique fonctionne sur une population en utilisant un ensemble d'opérateurs qui sont appliqués à la population. Une population est un ensemble de points dans l'espace de conception. La population initiale est générée aléatoirement par défaut. L'algorithme calcule la prochaine génération de la population en utilisant la fitness des individus de la génération actuelle. Pour plus de détails, voir Comment fonctionne l'algorithme génétique.

Ajouter une visualisation

Pour visualiser les performances du solveur pendant son exécution, définissez une option 'PlotFcn' à l'aide de optimoptions. Dans ce cas, sélectionnez deux fonctions de tracé dans un cell array. Définissez gaplotbestf, qui trace le meilleur score et le score moyen de la population à chaque génération. Définissez également gaplotstopping, qui trace le pourcentage de critères d’arrêt satisfaits.

opts = optimoptions(@ga,'PlotFcn',{@gaplotbestf,@gaplotstopping});

Exécutez le solveur ga, y compris l'argument opts.

[x,Fval,exitFlag,Output] = ...
    ga(FitnessFunction,numberOfVariables,[],[],[],[],[],[],[],opts);
ga stopped because the average change in the fitness value is less than options.FunctionTolerance.

Figure Genetic Algorithm contains 2 axes objects. Axes object 1 with title Best: -186.71 Mean: -123.753, xlabel Generation, ylabel Fitness value contains 2 objects of type scatter. These objects represent Best fitness, Mean fitness. Axes object 2 with title Stopping Criteria, xlabel Progress contains an object of type bar.

Spécifier les options pour la population

Les options de population peuvent avoir un effet important sur les performances du solveur. La vitesse de chaque itération dépend de la taille de la population : une population plus grande conduit à des itérations plus lentes. À l’inverse, une population plus large conduit à une exploration plus approfondie de ga, ce qui peut conduire à une meilleure solution. De même, une gamme initiale plus large peut conduire à une exploration plus approfondie, mais peut nécessiter une population plus large pour explorer la gamme plus large avec une minutie similaire.

Spécifier la taille de la population

ga crée une population initiale par défaut en utilisant un générateur de nombres aléatoires uniforme. La taille de population par défaut utilisée par ga est de 50 lorsque le nombre de variables de décision est inférieur à 5, et de 200 sinon. La taille par défaut peut ne pas fonctionner correctement pour certains problèmes ; par exemple, une taille de population plus petite peut être suffisante pour des problèmes plus petits. Étant donné que le problème actuel ne comporte que deux variables, spécifiez une taille de population de 10. Définissez la valeur de l'option PopulationSize à 10 dans les options existantes, opts.

opts.PopulationSize = 10;

Spécifier la plage de population initiale

La méthode par défaut pour générer une population initiale utilise un générateur de nombres aléatoires uniforme. Pour les problèmes sans contraintes entières, ga crée une population initiale où tous les points sont compris entre –10 et 10. Par exemple, vous pouvez générer une population de taille trois dans la plage par défaut à l'aide de cette commande :

Population = [-10,-10] + 20*rand(3,2);

Vous pouvez définir la plage initiale en modifiant l'option InitialPopulationRange. La plage doit être une matrice avec deux lignes. Si la plage n'a qu'une seule colonne, c'est-à-dire qu'elle est de 2 par 1, alors la plage de chaque variable est la plage donnée. Par exemple, si vous définissez la plage sur [-1; 1], la plage initiale pour les deux variables est comprise entre –1 et 1. Pour spécifier une plage initiale différente pour chaque variable, vous devez spécifier la plage sous forme de matrice avec deux lignes et numberOfVariables colonnes. Par exemple, si vous définissez la plage sur [-1 0; 1 2], la première variable a la plage de –1 à 1 et la deuxième variable a la plage de 0 à 2 (chaque colonne correspond à une variable).

Modifiez la valeur de l'option InitialPopulationRange dans les options existantes, opts.

opts.InitialPopulationRange = [-1 0; 1 2];

Exécutez le solveur ga.

[x,Fval,exitFlag,Output] = ga(FitnessFunction,numberOfVariables,[],[],[], ...
    [],[],[],[],opts);
ga stopped because the average change in the fitness value is less than options.FunctionTolerance.

Figure Genetic Algorithm contains 2 axes objects. Axes object 1 with title Best: -179.987 Mean: -78.6061, xlabel Generation, ylabel Fitness value contains 2 objects of type scatter. These objects represent Best fitness, Mean fitness. Axes object 2 with title Stopping Criteria, xlabel Progress contains an object of type bar.

fprintf('The number of generations is: %d\n', Output.generations);
The number of generations is: 67
fprintf('The number of function evaluations is: %d\n', Output.funccount);
The number of function evaluations is: 614
fprintf('The best function value found is: %g\n', Fval);
The best function value found is: -179.987

Reproduire les résultats

Par défaut, ga démarre avec une population initiale aléatoire créée à l'aide de générateurs de nombres aléatoires MATLAB ®. Le solveur produit la génération suivante en utilisant les opérateurs ga qui utilisent également ces mêmes générateurs de nombres aléatoires. Chaque fois qu'un nombre aléatoire est généré, l'état des générateurs de nombres aléatoires change. Ainsi, même si vous ne modifiez aucune option, vous pouvez obtenir des résultats différents lorsque vous exécutez à nouveau le solveur.

Exécutez le solveur deux fois pour montrer ce phénomène.

Exécutez le solveur ga.

[x,Fval,exitFlag,Output] = ga(FitnessFunction,numberOfVariables);
ga stopped because the average change in the fitness value is less than options.FunctionTolerance.
fprintf('The best function value found is: %g\n', Fval);
The best function value found is: -186.484

Exécutez ga à nouveau.

[x,Fval,exitFlag,Output] = ga(FitnessFunction,numberOfVariables);
ga stopped because the average change in the fitness value is less than options.FunctionTolerance.
fprintf('The best function value found is: %g\n', Fval);
The best function value found is: -185.867

ga donne des résultats différents dans les deux exécutions car l'état du générateur de nombres aléatoires change d'une exécution à l'autre.

Si vous souhaitez reproduire vos résultats avant d'exécuter ga, vous pouvez enregistrer l'état du flux de nombres aléatoires.

thestate = rng;

Exécutez ga.

[x,Fval,exitFlag,Output] = ga(FitnessFunction,numberOfVariables);
ga stopped because the average change in the fitness value is less than options.FunctionTolerance.
fprintf('The best function value found is: %g\n', Fval);
The best function value found is: -186.467

Réinitialisez le flux et réexécutez ga. Les résultats sont identiques à ceux de l'essai précédent.

rng(thestate);
[x,Fval,exitFlag,Output] = ga(FitnessFunction,numberOfVariables);
ga stopped because the average change in the fitness value is less than options.FunctionTolerance.
fprintf('The best function value found is: %g\n', Fval);
The best function value found is: -186.467

Si vous exécutez ga avant de spécifier de reproduire les résultats, vous pouvez réinitialiser le générateur de nombres aléatoires tant que vous disposez de la structure output.

strm = RandStream.getGlobalStream;
strm.State = Output.rngstate.State;

Réexécutez ga. Encore une fois, les résultats sont identiques.

[x,Fval,exitFlag,Output] = ga(FitnessFunction,numberOfVariables);
ga stopped because the average change in the fitness value is less than options.FunctionTolerance.
fprintf('The best function value found is: %g\n', Fval);
The best function value found is: -186.467

Modifier les critères d'arrêt

ga utilise quatre critères différents pour déterminer quand arrêter le solveur. ga s'arrête lorsqu'il atteint le nombre maximal de Generation ; par défaut, ce nombre est 100 fois le nombre de variables. ga détecte également si la meilleure valeur de fitness ne change pas pendant un certain temps donné en secondes (limite de temps de Stall Time), ou pendant un certain nombre de Generation (nombre maximal de Stall Generation). Un autre critère est la limite de temps maximale en secondes. Modifier les critères d'arrêt pour augmenter le nombre maximum de Generation à 300 et le nombre maximum de Stall Generation à 100.

opts = optimoptions(opts,'MaxGenerations',300,'MaxStallGenerations', 100);

Réexécutez le solveur ga.

[x,Fval,exitFlag,Output] = ga(FitnessFunction,numberOfVariables,[],[],[], ...
    [],[],[],[],opts);
ga stopped because the average change in the fitness value is less than options.FunctionTolerance.

Figure Genetic Algorithm contains 2 axes objects. Axes object 1 with title Best: -186.729 Mean: -186.202, xlabel Generation, ylabel Fitness value contains 2 objects of type scatter. These objects represent Best fitness, Mean fitness. Axes object 2 with title Stopping Criteria, xlabel Progress contains an object of type bar.

fprintf('The number of generations is: %d\n', Output.generations);
The number of generations is: 299
fprintf('The number of function evaluations is: %d\n', Output.funccount);
The number of function evaluations is: 2702
fprintf('The best function value found is: %g\n', Fval);
The best function value found is: -186.729

Spécifier les opérateurs ga

ga commence avec un ensemble aléatoire de points dans la population et utilise des opérateurs pour produire la prochaine génération de la population. Les différents opérateurs sont la mise à l'échelle, la sélection, le croisement et la mutation. La boîte à outils fournit plusieurs fonctions à spécifier pour chaque opérateur. Spécifiez fitscalingprop pour FitnessScalingFcn et selectiontournament pour SelectionFcn.

opts = optimoptions(@ga,'SelectionFcn',@selectiontournament, ...
                        'FitnessScalingFcn',@fitscalingprop);

Réexécutez ga.

[x,Fval,exitFlag,Output] = ga(FitnessFunction,numberOfVariables,[],[],[], ...
    [],[],[],[],opts);
ga stopped because the average change in the fitness value is less than options.FunctionTolerance.
fprintf('The number of generations is: %d\n', Output.generations);
The number of generations is: 52
fprintf('The number of function evaluations is: %d\n', Output.funccount);
The number of function evaluations is: 2497
fprintf('The best function value found is: %g\n', Fval);
The best function value found is: -186.417

La meilleure valeur de fonction peut s’améliorer ou se détériorer en fonction des opérateurs spécifiés. Expérimenter avec différents opérateurs est souvent le meilleur moyen de déterminer quel ensemble d’opérateurs fonctionne le mieux pour votre problème.

Voir aussi

Rubriques