Diese Seite wurde mithilfe maschineller Übersetzung übersetzt. Klicken Sie hier, um das englische Original zu sehen.

Vergleich mehrerer globaler Solver, problembasiert

Live Script öffnen

Dieses Beispiel zeigt, wie man die Rastrigin-Funktion mit verschiedenen Solvern minimiert. Jeder Solver hat seine eigenen Charakteristika. Die Eigenschaften führen zu unterschiedlichen Lösungen und Laufzeiten. Die Ergebnisse, zusammengefasst unter Vergleich von Solvern und Lösungen, können Ihnen bei der Auswahl eines geeigneten Solvers für Ihre eigenen Probleme helfen.

Die Rastrigin-Funktion besitzt viele lokale Minima, mit einem globalen Minimum bei (0,0):

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

Stellen Sie die Funktion in jeder Richtung mit dem Faktor 10 dar.

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.

Normalerweise kennt man die Lage des globalen Minimums der Zielfunktion nicht. Um zu zeigen, wie die Solver nach einer globalen Lösung suchen, startet dieses Beispiel alle Solver um den Punkt [20,30], der weit vom globalen Minimum entfernt ist.

fminunc-Solver

Um das Optimierungsproblem mit dem Standard-Solver fminunc der Optimization Toolbox™ zu lösen, geben Sie Folgendes ein:

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.

<stopping criteria details>

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.↵↵Optimization completed because the size of the gradient is less than↵the value of the optimality tolerance.↵↵<stopping criteria details>↵↵Optimization completed: The first-order optimality measure, 1.278784e-09, is less ↵than options.OptimalityTolerance = 1.000000e-06.'
    objectivederivative: 'reverse-AD'
                 solver: 'fminunc'

fminunc löst das Problem mit sehr wenigen Funktionsauswertungen (nur fünf, wie die outputf-Struktur zeigt) und erreicht ein lokales Minimum in der Nähe des Startpunkts. Das Exit-Flag signalisiert, dass es sich bei der Lösung um ein lokales Minimum handelt.

patternsearch-Solver

Um das Optimierungsproblem mit dem Solver patternsearch der Global Optimization Toolbox zu lösen, geben Sie Folgendes ein:

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: [1×1 struct]
          message: 'patternsearch stopped because the mesh size was less than options.MeshTolerance.'
           solver: 'patternsearch'

Wie fminunc erreicht auch patternsearch ein lokales Optimum, wie das Exit-Flag exitflagp zeigt. Die Lösung ist besser als die fminunc-Lösung, da sie einen niedrigeren Zielfunktionswert aufweist. Allerdings benötigt patternsearch wesentlich mehr Funktionsauswertungen, wie die Ausgabestruktur zeigt.

ga-Solver

Um das Optimierungsproblem mit dem Solver ga der Global Optimization Toolbox zu lösen, geben Sie Folgendes ein:

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: [1×1 struct]
      generations: 200
        funccount: 9453
          message: 'ga stopped because it exceeded options.MaxGenerations.'
    maxconstraint: []
       hybridflag: []
           solver: 'ga'

ga benötigt wesentlich mehr Funktionsauswertungen als die vorherigen Solver und gelangt zu einer Lösung nahe dem globalen Minimum. Der Lösungsalgorithmus ist stochastisch und kann zu einer suboptimalen Lösung führen.

particleswarm-Solver

Um das Optimierungsproblem mit dem Solver particleswarm der Global Optimization Toolbox zu lösen, geben Sie Folgendes ein:

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: [1×1 struct]
    iterations: 120
     funccount: 2420
       message: 'Optimization ended: relative change in the objective value ↵over the last OPTIONS.MaxStallIterations iterations is less than OPTIONS.FunctionTolerance.'
    hybridflag: []
        solver: 'particleswarm'

Der Solver benötigt weniger Funktionsauswertungen als ga und kommt zu einer noch genaueren Lösung. Auch hier handelt es sich um einen stochastischen Lösungsalgorithmus, der möglicherweise keine globale Lösung findet.

simulannealbnd-Solver

Um das Optimierungsproblem mit dem Solver simulannealbnd der Global Optimization Toolbox zu lösen, geben Sie Folgendes ein:

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.8311e-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: [1×1 struct]
    problemtype: 'unconstrained'
    temperature: [2×1 double]
      totaltime: 0.6141
         solver: 'simulannealbnd'

Der Solver benötigt ungefähr die gleiche Anzahl an Funktionsauswertungen wie particleswarm und erreicht eine gute Lösung. Auch dieser Solver ist stochastisch.

surrogateopt-Solver

surrogateopt benötigt keinen Startpunkt, erfordert aber endliche Grenzen. Setzen Sie in jeder Komponente Grenzen von –70 bis 130. Um die gleiche Art von Ausgabe wie die anderen Solver zu erhalten, deaktivieren Sie die Standard-Plotfunktion.

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: 2.9748
          funccount: 200
    constrviolation: 0
               ineq: [1×1 struct]
           rngstate: [1×1 struct]
            message: 'surrogateopt stopped because it exceeded the function evaluation limit set by ↵'options.MaxFunctionEvaluations'.'
             solver: 'surrogateopt'

Der Solver benötigt vergleichsweise wenige Funktionsauswertungen, um eine Lösung nahe dem globalen Optimum zu erreichen. Die Auswertung jeder einzelnen Funktion benötigt jedoch wesentlich mehr Zeit als die der anderen Lösungsverfahren.

Vergleichen Sie Solver und Lösungen

Eine Lösung ist besser als eine andere, wenn ihr Zielfunktionswert kleiner ist als der der anderen. Die Ergebnisse sind in der folgenden Tabelle zusammengefasst.

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.0017923    1.8311e-05      1986  
    surrogateopt          9.9494       -9.9502        1.9899       200

Diese Ergebnisse sind typisch:

  • fminunc erreicht schnell die lokale Lösung innerhalb seines Startbeckens, erkundet aber überhaupt keinen Bereich außerhalb dieses Beckens. Da die Zielfunktion analytische Ableitungen besitzt, verwendet fminunc die automatische Differenzierung und benötigt nur sehr wenige Funktionsauswertungen, um ein genaues lokales Minimum zu erreichen.

  • patternsearch benötigt mehr Funktionsauswertungen als fminunc und durchsucht mehrere Becken, wodurch eine bessere Lösung als fminunc gefunden wird.

  • ga benötigt wesentlich mehr Funktionsauswertungen als patternsearch. Durch Zufall gelangt man zu einer besseren Lösung. In diesem Fall findet ga einen Punkt nahe dem globalen Optimum. ga ist stochastisch, daher ändern sich die Ergebnisse mit jedem Durchlauf. ga benötigt zusätzliche Schritte, um eine Anfangspopulation nahe [20,30] zu erhalten.

  • particleswarm benötigt weniger Funktionsauswertungen als ga, aber mehr als patternsearch. In diesem Fall findet particleswarm einen Punkt mit einem niedrigeren Zielfunktionswert als patternsearch oder ga. Da particleswarm stochastisch ist, ändern sich die Ergebnisse bei jedem Durchlauf. particleswarm erfordert zusätzliche Schritte, um eine Anfangspopulation nahe [20,30] zu erhalten.

  • simulannealbnd benötigt ungefähr die gleiche Anzahl an Funktionsauswertungen wie particleswarm. In diesem Fall findet simulannealbnd eine gute Lösung, aber nicht so gut wie particleswarm. Der Lösungsalgorithmus arbeitet stochastisch und kann zu einer suboptimalen Lösung gelangen.

  • surrogateopt stoppt, sobald die maximale Anzahl an Funktionsauswertungen erreicht ist, die bei einem Problem mit zwei Variablen standardmäßig bei 200 liegt. surrogateopt erfordert endliche Schranken. surrogateopt versucht, eine globale Lösung zu finden, was in diesem Fall jedoch nicht gelingt. Die Auswertung jeder Funktion in surrogateopt dauert länger als bei den meisten anderen Solvern, da surrogateopt im Rahmen seines Algorithmus viele Hilfsberechnungen durchführt.

Siehe auch

| | | | |

Themen