Questa pagina è stata tradotta con la traduzione automatica. Fai clic qui per vedere l'ultima versione in inglese.

Confronta diversi risolutori globali, basati sui problemi

Apri live script

Questo esempio mostra come minimizzare la funzione di Rastrigin con diversi risolutori. Ogni risolutore ha le sue caratteristiche. Le caratteristiche portano a soluzioni e tempi di esecuzione diversi. I risultati, riassunti in Confronta risolutori e soluzioni, possono aiutarti a scegliere il risolutore più adatto ai tuoi problemi.

La funzione di Rastrigin ha molti minimi locali, con un minimo globale in (0,0):

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

Rappresenta graficamente la funzione scalata di 10 in ogni direzione.

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

Di solito non si conosce la posizione del minimo globale della funzione obiettivo. Per mostrare come i risolutori cercano una soluzione globale, questo esempio avvia tutti i risolutori attorno al punto [20,30], che è lontano dal minimo globale.

Risolutore fminunc

Per risolvere il problema di ottimizzazione utilizzando il risolutore predefinito fminunc di Optimization Toolbox ™, immettere:

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 risolve il problema in pochissime valutazioni della funzione (solo cinque, come mostrato nella struttura outputf) e raggiunge un minimo locale vicino al punto di partenza. Il flag di uscita indica che la soluzione è un minimo locale.

Risolutore patternsearch

Per risolvere il problema di ottimizzazione utilizzando il risolutore patternsearch di Global Optimization Toolbox, immettere:

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'

Come fminunc, patternsearch raggiunge un ottimo locale, come mostrato nel flag di uscita exitflagp . La soluzione è migliore della soluzione fminunc, perché ha un valore della funzione obiettivo inferiore. Tuttavia, patternsearch richiede molte più valutazioni di funzione, come mostrato nella struttura di output.

Risolutore ga

Per risolvere il problema di ottimizzazione utilizzando il risolutore ga di Global Optimization Toolbox, immettere:

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 esegue molte più valutazioni di funzioni rispetto ai risolutori precedenti e arriva a una soluzione prossima al minimo globale. Il risolutore è stocastico e può raggiungere una soluzione subottimale.

Risolutore particleswarm

Per risolvere il problema di ottimizzazione utilizzando il risolutore particleswarm di Global Optimization Toolbox, immettere:

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'

Il risolutore richiede meno valutazioni delle funzioni rispetto a ga e arriva a una soluzione ancora più accurata. Anche in questo caso, il risolutore è stocastico e potrebbe non riuscire a raggiungere una soluzione globale.

Risolutore simulannealbnd

Per risolvere il problema di ottimizzazione utilizzando il risolutore simulannealbnd di Global Optimization Toolbox, immettere:

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: 0.8019
         solver: 'simulannealbnd'

Il risolutore esegue all'incirca lo stesso numero di valutazioni di funzione di particleswarm e raggiunge una buona soluzione. Anche questo risolutore è stocastico.

Risolutore surrogateopt

surrogateopt non richiede un punto di partenza, ma richiede limiti finiti. Impostare limiti da -70 a 130 in ciascun componente. Per ottenere lo stesso tipo di output degli altri risolutori, disabilitare la funzione di grafico predefinita.

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

Il risolutore richiede relativamente poche valutazioni delle funzioni per raggiungere una soluzione vicina all'ottimo globale. Tuttavia, ogni valutazione della funzione richiede molto più tempo rispetto a quelle degli altri risolutori.

Confronta Risolutori e Soluzioni

Una soluzione è migliore di un'altra se il valore della sua funzione obiettivo è minore dell'altra. La tabella seguente riassume i risultati.

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

Questi risultati sono tipici:

  • fminunc raggiunge rapidamente la soluzione locale all'interno del suo bacino di partenza, ma non esplora affatto al di fuori di questo bacino. Poiché la funzione obiettivo ha derivate analitiche, fminunc utilizza la differenziazione automatica e richiede pochissime valutazioni della funzione per raggiungere un minimo locale accurato.

  • patternsearch esegue più valutazioni di funzioni rispetto a fminunc e cerca in più bacini, arrivando a una soluzione migliore di fminunc.

  • ga richiede molte più valutazioni di funzioni rispetto a patternsearch. Per caso si giunge a una soluzione migliore. In questo caso, ga trova un punto vicino all'ottimo globale. ga è stocastico, quindi i suoi risultati cambiano a ogni esecuzione. ga richiede passaggi extra per avere una popolazione iniziale vicina a [20,30].

  • particleswarm richiede meno valutazioni di funzione rispetto a ga, ma più di patternsearch. In questo caso, particleswarm trova un punto con un valore della funzione obiettivo inferiore a patternsearch o ga. Poiché particleswarm è stocastico, i suoi risultati cambiano a ogni esecuzione. particleswarm richiede passaggi aggiuntivi per avere una popolazione iniziale vicina a [20,30].

  • simulannealbnd richiede all'incirca lo stesso numero di valutazioni di funzione di particleswarm. In questo caso, simulannealbnd trova una buona soluzione, ma non buona quanto particleswarm. Il risolutore è stocastico e può giungere a una soluzione subottimale.

  • surrogateopt si arresta quando raggiunge un limite di valutazione della funzione, che per impostazione predefinita è 200 per un problema a due variabili. surrogateopt richiede limiti finiti. surrogateopt tenta di trovare una soluzione globale e in questo caso ci riesce. Ogni valutazione di funzione in surrogateopt richiede più tempo rispetto alla maggior parte degli altri risolutori, perché surrogateopt esegue molti calcoli ausiliari come parte del suo algoritmo.

Vedi anche

| | | | |

Argomenti