Сравните несколько глобальных решателей, основанных на проблеме
В этом примере показано, как минимизировать функцию Рэстриджина с несколькими решателями. Каждый решатель имеет свои собственные характеристики. Характеристики приводят к различным решениям и время выполнения. Результаты, полученные в итоге в, Сравнивают Решатели и Решения, может помочь вам выбрать соответствующий решатель для своих собственных проблем.
Функция Рэстриджина имеет много локальных минимумов с глобальным минимумом в (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]) contains an object of type functionsurface.](../examples/globaloptim/win64/ComparisonOfSeveralGlobalSolversProblemBasedExample_01.png)
Обычно вы не знаете местоположение глобального минимума вашей целевой функции. Чтобы показать, как решатели ищут глобальное решение, этот пример запускает все решатели вокруг точки [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: '...'
objectivederivative: "reverse-AD"
solver: 'fminunc'
fminunc решает задачу в очень немногих вычислениях функции (только пять, как показано в outputf структура), и достигает локального минимума около стартовой точки. Выходной флаг указывает, что решение является локальным минимумом.
patternsearch Решатель
Решить задачу оптимизации с помощью patternsearch Решатель Global Optimization Toolbox, введите:
x0.x = 20; x0.y = 30; [solp,fvalp,eflagp,outputp] = solve(prob,x0,"Solver","patternsearch")
Solving problem using patternsearch. Optimization terminated: mesh size 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: 'Optimization terminated: mesh size less than options.MeshTolerance.'
solver: 'patternsearch'
Как fminunc, patternsearch достигает локального оптимума, как показано в выходном флаге exitflagp. Решение лучше, чем fminunc решение, потому что это имеет более низкое значение целевой функции. Однако patternsearch берет намного больше вычислений функции, как показано в структуре output.
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. Optimization terminated: maximum number of generations exceeded.
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: 'Optimization terminated: maximum number of generations exceeded.'
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. Optimization terminated: change in best function value 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: 'Optimization terminated: change in best function value less than options.FunctionTolerance.'
rngstate: [1x1 struct]
problemtype: 'unconstrained'
temperature: [2x1 double]
totaltime: 0.7909
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: -0.0033
y: 4.7219e-04
fvalsur = 2.2456e-05
eflagsur =
SolverLimitExceeded
outputsur = struct with fields:
elapsedtime: 2.4243
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 -0.0033311 0.00047219 2.2456e-05 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остановки, когда это достигает предела вычисления функции, который по умолчанию является 200 для 2D переменной проблемы.surrogateoptтребует конечных границ.surrogateoptпопытки найти глобальное решение, и в этом случае успешно выполняются. Каждое вычисление функции вsurrogateoptзанимает более длительное время, чем в большинстве других решателей, потому чтоsurrogateoptвыполняет много вспомогательных расчетов как часть его алгоритма.
Смотрите также
solve | patternsearch | ga | particleswarm | simulannealbnd | surrogateopt