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

Comparer plusieurs solveurs globaux, basés sur des problèmes

Ouvrir le live script

Cet exemple montre comment minimiser la fonction de Rastrigin avec plusieurs solveurs. Chaque solveur a ses propres caractéristiques. Les caractéristiques conduisent à des solutions et des temps d'exécution différents. Les résultats, résumés dans Comparer les solveurs et les solutions, peuvent vous aider à choisir un solveur approprié à vos propres problèmes.

La fonction de Rastrigin a de nombreux minima locaux, avec un minimum global à (0,0) :

ras = @(x, y) 20 + x.^2 + y.^2 - 10*(cos(2*pi*x) + cos(2*pi*y));

Tracez la fonction mise à l’échelle par 10 dans chaque direction.

rf3 = @(x, y) ras(x/10, y/10);
fsurf(rf3,[-30 30],"ShowContours","on")
title("rastriginsfcn([x/10,y/10])")
xlabel("x")
ylabel("y")

Figure contains an axes object. The axes object with title rastriginsfcn([x/10,y/10]), xlabel x, ylabel y contains an object of type functionsurface.

Habituellement, vous ne connaissez pas l’emplacement du minimum global de votre fonction objectif. Pour montrer comment les solveurs recherchent une solution globale, cet exemple démarre tous les solveurs autour du point [20,30], qui est loin du minimum global.

fminunc Solveur

Pour résoudre le problème d'optimisation en utilisant le solveur par défaut fminunc Optimization Toolbox™, entrez :

x = optimvar("x");
y = optimvar("y");
prob = optimproblem("Objective",rf3(x,y));
x0.x = 20;
x0.y = 30;
[solf,fvalf,eflagf,outputf] = solve(prob,x0)
Solving problem using fminunc.

Local minimum found.

Optimization completed because the size of the gradient is less than
the value of the optimality tolerance.

solf = struct with fields:
    x: 19.8991
    y: 29.8486


fvalf = 
12.9344

eflagf = 
    OptimalSolution


outputf = struct with fields:
             iterations: 3
              funcCount: 5
               stepsize: 1.7773e-06
           lssteplength: 1
          firstorderopt: 2.0461e-09
              algorithm: 'quasi-newton'
                message: 'Local minimum found....'
    objectivederivative: "reverse-AD"
                 solver: 'fminunc'

fminunc résout le problème en très peu d'évaluations de fonction (seulement cinq, comme indiqué dans la structure outputf) et atteint un minimum local près du point de départ. L'exit flag indique que la solution est un minimum local.

patternsearch Solveur

Pour résoudre le problème d'optimisation à l'aide du solveur patternsearch Global Optimization Toolbox, entrez :

x0.x = 20;
x0.y = 30;
[solp,fvalp,eflagp,outputp] = solve(prob,x0,"Solver","patternsearch")
Solving problem using patternsearch.
patternsearch stopped because the mesh size was less than options.MeshTolerance.

solp = struct with fields:
    x: 19.8991
    y: -9.9496


fvalp = 
4.9748

eflagp = 
    SolverConvergedSuccessfully


outputp = struct with fields:
         function: @(x)fun(x,extraParams)
      problemtype: 'unconstrained'
       pollmethod: 'gpspositivebasis2n'
    maxconstraint: []
     searchmethod: []
       iterations: 48
        funccount: 174
         meshsize: 9.5367e-07
         rngstate: [1x1 struct]
          message: 'patternsearch stopped because the mesh size was less than options.MeshTolerance.'
           solver: 'patternsearch'

Comme fminunc, patternsearch atteint un optimum local, comme indiqué dans l'exit flag exitflagp. La solution est meilleure que la solution fminunc, car elle a une valeur de fonction objectif inférieure. Cependant, patternsearch nécessite beaucoup plus d’évaluations de fonctions, comme indiqué dans la structure de sortie.

ga Solveur

Pour résoudre le problème d'optimisation à l'aide du solveur ga Global Optimization Toolbox, entrez :

rng default % For reproducibility
x0.x = 10*randn(20) + 20;
x0.y = 10*randn(20) + 30; % Random start population near [20,30];
[solg,fvalg,eflagg,outputg] = solve(prob,"Solver","ga")
Solving problem using ga.
ga stopped because it exceeded options.MaxGenerations.

solg = struct with fields:
    x: 0.0064
    y: 7.7057e-04


fvalg = 
8.1608e-05

eflagg = 
    SolverLimitExceeded


outputg = struct with fields:
      problemtype: 'unconstrained'
         rngstate: [1x1 struct]
      generations: 200
        funccount: 9453
          message: 'ga stopped because it exceeded options.MaxGenerations.'
    maxconstraint: []
       hybridflag: []
           solver: 'ga'

ga nécessite beaucoup plus d'évaluations de fonctions que les solveurs précédents et arrive à une solution proche du minimum global. Le solveur est stochastique et peut atteindre une solution sous-optimale.

particleswarm Solveur

Pour résoudre le problème d'optimisation à l'aide du solveur particleswarm Global Optimization Toolbox, entrez :

rng default % For reproducibility
[solpso,fvalpso,eflagpso,outputpso] = solve(prob,"Solver","particleswarm")
Solving problem using particleswarm.
Optimization ended: relative change in the objective value 
over the last OPTIONS.MaxStallIterations iterations is less than OPTIONS.FunctionTolerance.

solpso = struct with fields:
    x: 7.1467e-07
    y: 1.4113e-06


fvalpso = 
4.9631e-12

eflagpso = 
    SolverConvergedSuccessfully


outputpso = struct with fields:
      rngstate: [1x1 struct]
    iterations: 120
     funccount: 2420
       message: 'Optimization ended: relative change in the objective value ...'
    hybridflag: []
        solver: 'particleswarm'

Le solveur prend moins d'évaluations de fonctions que ga et arrive à une solution encore plus précise. Encore une fois, le solveur est stochastique et peut ne pas parvenir à une solution globale.

simulannealbnd Solveur

Pour résoudre le problème d'optimisation à l'aide du solveur simulannealbnd Global Optimization Toolbox, entrez :

rng default % For reproducibility
x0.x = 20;
x0.y = 30;
[solsim,fvalsim,eflagsim,outputsim] = solve(prob,x0,"Solver","simulannealbnd")
Solving problem using simulannealbnd.
simulannealbnd stopped because the change in best function value is less than options.FunctionTolerance.

solsim = struct with fields:
    x: 0.0025
    y: 0.0018


fvalsim = 
1.8386e-05

eflagsim = 
    SolverConvergedSuccessfully


outputsim = struct with fields:
     iterations: 1967
      funccount: 1986
        message: 'simulannealbnd stopped because the change in best function value is less than options.FunctionTolerance.'
       rngstate: [1x1 struct]
    problemtype: 'unconstrained'
    temperature: [2x1 double]
      totaltime: 1.1845
         solver: 'simulannealbnd'

Le solveur prend à peu près le même nombre d'évaluations de fonction que particleswarm et atteint une bonne solution. Ce solveur est également stochastique.

surrogateopt Solveur

surrogateopt ne nécessite pas de point de départ, mais nécessite des limites finies. Définissez des limites de –70 à 130 dans chaque composant. Pour obtenir le même type de sortie que les autres solveurs, désactivez la fonction de tracé par défaut.

rng default % For reproducibility
x = optimvar("x","LowerBound",-70,"UpperBound",130);
y = optimvar("y","LowerBound",-70,"UpperBound",130);
prob = optimproblem("Objective",rf3(x,y));
options = optimoptions("surrogateopt","PlotFcn",[]);
[solsur,fvalsur,eflagsur,outputsur] = solve(prob,...
    "Solver","surrogateopt",...
    "Options",options)
Solving problem using surrogateopt.
surrogateopt stopped because it exceeded the function evaluation limit set by 
'options.MaxFunctionEvaluations'.

solsur = struct with fields:
    x: 9.9494
    y: -9.9502


fvalsur = 
1.9899

eflagsur = 
    SolverLimitExceeded


outputsur = struct with fields:
        elapsedtime: 3.7364
          funccount: 200
    constrviolation: 0
               ineq: [1x1 struct]
           rngstate: [1x1 struct]
            message: 'surrogateopt stopped because it exceeded the function evaluation limit set by ...'
             solver: 'surrogateopt'

Le solveur nécessite relativement peu d’évaluations de fonctions pour atteindre une solution proche de l’optimum global. Cependant, chaque évaluation de fonction prend beaucoup plus de temps que celles des autres solveurs.

Comparer les solveurs et les solutions

Une solution est meilleure qu’une autre si sa valeur de fonction objectif est inférieure à celle de l’autre. Le tableau suivant résume les résultats.

sols = [solf.x solf.y;
    solp.x solp.y;
    solg.x solg.y;
    solpso.x solpso.y;
    solsim.x solsim.y;
    solsur.x solsur.y];
fvals = [fvalf;
    fvalp;
    fvalg;
    fvalpso;
    fvalsim;
    fvalsur];
fevals = [outputf.funcCount;
    outputp.funccount;
    outputg.funccount;
    outputpso.funccount;
    outputsim.funccount;
    outputsur.funccount];
stats = table(sols,fvals,fevals);
stats.Properties.RowNames = ["fminunc" "patternsearch" "ga" "particleswarm" "simulannealbnd" "surrogateopt"];
stats.Properties.VariableNames = ["Solution" "Objective" "# Fevals"];
disp(stats)
                              Solution            Objective     # Fevals
                      ________________________    __________    ________

    fminunc               19.899        29.849        12.934         5  
    patternsearch         19.899       -9.9496        4.9748       174  
    ga                 0.0063672    0.00077057    8.1608e-05      9453  
    particleswarm     7.1467e-07    1.4113e-06    4.9631e-12      2420  
    simulannealbnd      0.002453     0.0018028    1.8386e-05      1986  
    surrogateopt          9.9494       -9.9502        1.9899       200

Ces résultats sont typiques :

  • fminunc atteint rapidement la solution locale dans son bassin de départ, mais n'explore pas du tout en dehors de ce bassin. Étant donné que la fonction objectif possède des dérivées analytiques, fminunc utilise la différenciation automatique et nécessite très peu d’évaluations de fonction pour atteindre un minimum local précis.

  • patternsearch prend plus d'évaluations de fonctions que fminunc et recherche dans plusieurs bassins, arrivant à une meilleure solution que fminunc.

  • ga nécessite beaucoup plus d'évaluations de fonctions que patternsearch. Par hasard, il arrive à une meilleure solution. Dans ce cas, ga trouve un point proche de l'optimum global. ga est stochastique, donc ses résultats changent à chaque exécution. ga nécessite des étapes supplémentaires pour avoir une population initiale proche de [20,30].

  • particleswarm nécessite moins d'évaluations de fonctions que ga, mais plus que patternsearch. Dans ce cas, particleswarm trouve un point avec une valeur de fonction objectif inférieure à patternsearch ou ga. Étant donné que particleswarm est stochastique, ses résultats changent à chaque exécution. particleswarm nécessite des étapes supplémentaires pour avoir une population initiale proche de [20,30].

  • simulannealbnd nécessite à peu près le même nombre d'évaluations de fonctions que particleswarm. Dans ce cas, simulannealbnd trouve une bonne solution, mais pas aussi bonne que particleswarm. Le solveur est stochastique et peut arriver à une solution sous-optimale.

  • surrogateopt s'arrête lorsqu'il atteint une limite d'évaluation de fonction, qui par défaut est de 200 pour un problème à deux variables. surrogateopt nécessite des limites finies. surrogateopt tente de trouver une solution globale et, dans ce cas, réussit. Chaque évaluation de fonction dans surrogateopt prend plus de temps que dans la plupart des autres solveurs, car surrogateopt effectue de nombreux calculs auxiliaires dans le cadre de son algorithme.

Voir aussi

| | | | |

Rubriques