몇 가지 전역 솔버 비교하기(문제 기반)
이 예제에서는 몇 가지 솔버를 사용하여 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")
일반적으로 목적 함수의 전역 최솟값 위치는 모릅니다. 솔버가 전역해를 찾는 방법을 보여주기 위해 이 예제에서는 전역 최솟값에서 멀리 떨어진 점 [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.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.7852
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: 9.9494
y: -9.9502
fvalsur = 1.9899
eflagsur = SolverLimitExceeded
outputsur = struct with fields:
elapsedtime: 4.3250
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.0018028 1.8386e-05 1986 surrogateopt 9.9494 -9.9502 1.9899 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
가 알고리즘의 일부로 많은 보조 계산을 수행하기 때문입니다.
참고 항목
solve
| patternsearch
| ga
| particleswarm
| simulannealbnd
| surrogateopt