Esta página se ha traducido mediante traducción automática. Haga clic aquí para ver la última versión en inglés.

Comparar varios solucionadores globales basados en problemas

Abrir script en vivo

Este ejemplo muestra cómo minimizar la función de Rastrigin con varios solucionadores. Cada solucionador tiene sus propias características. Las características conducen a diferentes soluciones y tiempos de ejecución. Los resultados, resumidos en Comparar solucionadores y soluciones, pueden ayudarle a elegir un solucionador apropiado para sus propios problemas.

La función de Rastrigin tiene muchos mínimos locales, con un mínimo global en (0,0):

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

Grafique la función escalada por 10 en cada dirección.

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.

Por lo general, no conoces la ubicación del mínimo global de tu función objetivo. Para mostrar cómo los solucionadores buscan una solución global, este ejemplo inicia todos los solucionadores alrededor del punto [20,30], que está lejos del mínimo global.

Solucionador fminunc

Para resolver el problema de optimización utilizando el solucionador predeterminado fminunc Optimization Toolbox™, ingrese:

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 resuelve el problema en muy pocas evaluaciones de función (solo cinco, como se muestra en la estructura outputf) y alcanza un mínimo local cerca del punto de inicio. El indicador de salida señala que la solución es un mínimo local.

Solucionador patternsearch

Para resolver el problema de optimización utilizando el solucionador patternsearch Global Optimization Toolbox, ingrese:

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'

Al igual que fminunc, patternsearch alcanza un óptimo local, como se muestra en el indicador de salida exitflagp. La solución es mejor que la solución fminunc, porque tiene un valor de función objetivo más bajo. Sin embargo, patternsearch toma muchas más evaluaciones de funciones, como se muestra en la estructura de salida.

Solucionador ga

Para resolver el problema de optimización utilizando el solucionador ga Global Optimization Toolbox, ingrese:

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 toma muchas más evaluaciones de funciones que los solucionadores anteriores y llega a una solución cercana al mínimo global. El solucionador es estocástico y puede llegar a una solución subóptima.

Solucionador particleswarm

Para resolver el problema de optimización utilizando el solucionador particleswarm Global Optimization Toolbox, ingrese:

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'

El solucionador realiza menos evaluaciones de funciones que ga y llega a una solución aún más precisa. Nuevamente, el solucionador es estocástico y puede no alcanzar una solución global.

Solucionador simulannealbnd

Para resolver el problema de optimización utilizando el solucionador simulannealbnd Global Optimization Toolbox, ingrese:

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'

El solucionador realiza aproximadamente la misma cantidad de evaluaciones de funciones que particleswarm y llega a una buena solución. Este solucionador también es estocástico.

Solucionador surrogateopt

surrogateopt no requiere un punto de inicio, pero sí requiere límites finitos. Establezca límites de –70 a 130 en cada componente. Para tener el mismo tipo de salida que los otros solucionadores, deshabilite la función de gráfico predeterminada.

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'

El solucionador requiere relativamente pocas evaluaciones de funciones para alcanzar una solución cercana al óptimo global. Sin embargo, la evaluación de cada función requiere mucho más tiempo que la de los otros solucionadores.

Comparar solucionadores y soluciones

Una solución es mejor que otra si el valor de su función objetivo es menor que el de la otra. La siguiente tabla resume los resultados.

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

Estos resultados son típicos:

  • fminunc llega rápidamente a la solución local dentro de su cuenca inicial, pero no explora en absoluto fuera de esta cuenca. Debido a que la función objetivo tiene derivadas analíticas, fminunc utiliza diferenciación automática y requiere muy pocas evaluaciones de la función para alcanzar un mínimo local preciso.

  • patternsearch toma más evaluaciones de funciones que fminunc y busca en varias cuencas, llegando a una mejor solución que fminunc.

  • ga toma muchas más evaluaciones de funciones que patternsearch. Por casualidad llega a una solución mejor. En este caso, ga encuentra un punto cerca del óptimo global. ga es estocástico, por lo que sus resultados cambian con cada ejecución. ga requiere pasos adicionales para tener una población inicial cerca de [20,30].

  • particleswarm toma menos evaluaciones de funciones que ga, pero más que patternsearch. En este caso, particleswarm encuentra un punto con un valor de función objetivo menor que patternsearch o ga. Debido a que particleswarm es estocástico, sus resultados cambian con cada ejecución. particleswarm requiere pasos adicionales para tener una población inicial cercana a [20,30].

  • simulannealbnd toma aproximadamente la misma cantidad de evaluaciones de funciones que particleswarm. En este caso, simulannealbnd encuentra una buena solución, pero no tan buena como particleswarm. El solucionador es estocástico y puede llegar a una solución subóptima.

  • surrogateopt se detiene cuando alcanza un límite de evaluación de función, que por defecto es 200 para un problema de dos variables. surrogateopt requiere límites finitos. surrogateopt intenta encontrar una solución global y en este caso lo logra. Cada evaluación de función en surrogateopt toma más tiempo que en la mayoría de los otros solucionadores, porque surrogateopt realiza muchos cálculos auxiliares como parte de su algoritmo.

Consulte también

| | | | |

Temas