몇 가지 전역 솔버 비교하기(문제 기반)

라이브 스크립트 열기

이 예제에서는 몇 가지 솔버를 사용하여 Rastrigin 함수를 최소화하는 방법을 보여줍니다. 솔버마다 고유한 특성이 있습니다. 이러한 특성으로 인해 해와 실행 시간이 달라집니다. 솔버와 해 비교하기에 요약된 결과는 자신의 문제에 적합한 솔버를 선택하는 데 도움이 될 수 있습니다.

Rastrigin 함수는 (0,0)에서의 전역 최솟값을 포함하여 다수의 국소 최솟값을 가지고 있습니다.

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

각 방향으로 10씩 스케일링된 함수를 플로팅합니다.

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.

일반적으로 목적 함수의 전역 최솟값 위치는 모릅니다. 솔버가 전역해를 찾는 방법을 보여주기 위해 이 예제에서는 전역 최솟값에서 멀리 떨어진 점 [20,30]의 주변에서 모든 솔버를 시작합니다.

`fminunc` 솔버

디폴트 fminunc Optimization Toolbox™ 솔버를 사용하여 최적화 문제를 풀려면 다음을 입력합니다.

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는 매우 적은 수의 함수 실행(outputf 구조체에 표시된 것처럼 5회만 실행)으로 문제를 풀고 시작점 근처의 국소 최솟값에 도달합니다. 종료 플래그는 해가 국소 최솟값임을 나타냅니다.

`patternsearch` 솔버

patternsearch Global Optimization Toolbox 솔버를 사용하여 최적화 문제를 풀려면 다음을 입력합니다.

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'

fminunc와 마찬가지로 patternsearch는 종료 플래그 exitflagp에 표시된 것처럼 국소 최적해에 도달합니다. 이 해는 목적 함수 값이 낮기 때문에 fminunc 해보다 더 적합합니다. 그러나 출력 구조체에 표시된 것처럼 patternsearch는 훨씬 더 많은 함수 실행을 행합니다.

`ga` 솔버

ga Global Optimization Toolbox 솔버를 사용하여 최적화 문제를 풀려면 다음을 입력합니다.

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는 이전 솔버들보다 훨씬 더 많은 함수 실행을 행하고, 전역 최솟값에 가까운 해에 도달합니다. 이 솔버는 확률적이며, 준최적해에 도달할 수 있습니다.

`particleswarm` 솔버

particleswarm Global Optimization Toolbox 솔버를 사용하여 최적화 문제를 풀려면 다음을 입력합니다.

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'

이 솔버는 ga보다 더 적은 함수 실행을 행하지만 훨씬 더 정확한 해에 도달합니다. 이 솔버 역시 확률적이며, 전역해에 도달하는 데 실패할 수 있습니다.

`simulannealbnd` 솔버

simulannealbnd Global Optimization Toolbox 솔버를 사용하여 최적화 문제를 풀려면 다음을 입력합니다.

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: [1x1 struct]
    problemtype: 'unconstrained'
    temperature: [2x1 double]
      totaltime: 1.4791
         solver: 'simulannealbnd'

이 솔버는 particleswarm과 거의 동일한 횟수로 함수 실행을 행하며 양호한 해에 도달합니다. 이 솔버 역시 확률적입니다.

`surrogateopt` 솔버

surrogateopt는 시작점이 필요하지 않지만 유한 범위는 필요합니다. 각 성분에 -70~130의 범위를 설정합니다. 다른 솔버와 동일한 종류의 출력값을 가지려면 디폴트 플롯 함수를 비활성화합니다.

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: -1.3383
    y: -0.3022

fvalsur = 3.5305

eflagsur = 
    SolverLimitExceeded

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

이 솔버는 비교적 적은 함수 실행을 행하여 전역 최적해에 가까운 해에 도달합니다. 그러나 각 함수 실행은 다른 솔버의 함수 실행에 비해 훨씬 많은 시간이 소요됩니다.

솔버와 해 비교하기

어떤 해의 목적 함수 값이 다른 해의 목적 함수 값보다 작으면 그 해는 다른 해보다 더 적합합니다. 다음 표에 결과가 요약되어 있습니다.

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         -1.3383      -0.30217        3.5305       200

다음 결과가 일반적입니다.

fminunc는 시작 유역 내에서 국소해에 빠르게 도달하지만 이 유역 외부는 전혀 탐색하지 않습니다. 목적 함수에는 해석적 도함수가 있기 때문에 fminunc는 자동 미분을 사용하고 매우 적은 함수 실행만으로 정확한 국소 최솟값에 도달합니다.
patternsearch는 fminunc보다 더 많은 함수 실행을 행하고, 여러 유역을 탐색하여 fminunc보다 더 양호한 해에 도달합니다.
ga는 patternsearch보다 훨씬 더 많은 함수 실행을 행합니다. 운이 좋으면 더 양호한 해에 도달합니다. 이 경우 ga는 전역 최적해 근처의 점을 구합니다. ga는 확률적이므로 실행할 때마다 결과가 달라집니다. ga가 [20,30] 근처에 초기 모집단을 두려면 추가 스텝이 필요합니다.
particleswarm은 함수 실행 횟수가 ga보다는 적지만 patternsearch보다는 많습니다. 이 경우 particleswarm은 patternsearch 또는 ga보다 목적 함수 값이 더 낮은 점을 구합니다. particleswarm은 확률적이므로 실행할 때마다 결과가 달라집니다. particleswarm은 [20,30] 근처에 초기 모집단을 두려면 추가 스텝이 필요합니다.
simulannealbnd는 particleswarm과 거의 동일한 횟수로 함수 실행을 행합니다. 이 경우, simulannealbnd는 양호한 해를 구하지만 particleswarm만큼 양호한 해는 아닙니다. 이 솔버는 확률적이며, 준최적해에 도달할 수 있습니다.
surrogateopt는 함수 실행 한도에 도달하면 멈춥니다. 변수가 2개인 문제의 경우 디폴트 값은 200회입니다. surrogateopt는 유한 범위가 필요합니다. surrogateopt는 전역해를 구하려고 시도하며, 이 경우에는 성공합니다. surrogateopt의 각 함수 실행은 대부분의 다른 솔버보다 시간이 더 오래 걸립니다. surrogateopt가 알고리즘의 일부로 많은 보조 계산을 수행하기 때문입니다.

참고 항목

몇 가지 전역 솔버 비교하기(문제 기반)

fminunc 솔버

patternsearch 솔버

ga 솔버

particleswarm 솔버

simulannealbnd 솔버

surrogateopt 솔버