Сравнение шести решателей

Функция, чтобы оптимизировать

В этом примере показано, как минимизировать функцию Рэстриджина с шестью решателями. Каждый решатель имеет свои собственные характеристики. Характеристики приводят к различным решениям и время выполнения. Результаты, исследованные в, Сравнивают Синтаксис и Решения, может помочь вам выбрать соответствующий решатель для своих собственных проблем.

Функция Рэстриджина имеет много локальных минимумов с глобальным минимумом в (0,0):

$Ras (x) = 20 + x_{1}^{2} + x_{2}^{2} - 10 (\cos 2 π x_{1} + \cos 2 π x_{2}) .$

Обычно вы не знаете местоположение глобального минимума вашей целевой функции. Чтобы показать, как решатели ищут глобальное решение, этот пример запускает все решатели вокруг точки [20,30], который далек от глобального минимума.

rastriginsfcn.m файл реализует функцию Рэстриджина. Этот файл идет с программным обеспечением Global Optimization Toolbox. Этот пример использует масштабированную версию функции Рэстриджина с большими областями притяжения. Для получения информации смотрите Области притяжения.

rf2 = @(x)rastriginsfcn(x/10);

Код для генерации фигуры

Этот пример минимизирует rf2 использование настроек по умолчанию fminunc (решатель Optimization Toolbox™), patternsearch, и GlobalSearch. Пример также использует ga и particleswarm с опциями не по умолчанию, чтобы начать с начальной генеральной совокупности вокруг точки [20,30]. Поскольку surrogateopt требует конечных границ, использования в качестве примера surrogateopt с нижними границами -70 и верхние границы 130 в каждой переменной.

fminunc

Решить задачу оптимизации с помощью fminunc Решатель Optimization Toolbox, введите:

rf2 = @(x)rastriginsfcn(x/10); % objective
x0 = [20,30]; % start point away from the minimum
[xf,ff,flf,of] = fminunc(rf2,x0)

fminunc возвращается

Local minimum found.

Optimization completed because the size of the gradient is 
less than the default value of the function tolerance.

xf =
   19.8991   29.8486
ff =
   12.9344
flf =
     1
of =

  struct with fields:

       iterations: 3
        funcCount: 15
         stepsize: 1.7776e-06
     lssteplength: 1
    firstorderopt: 5.9907e-09
        algorithm: 'quasi-newton'
          message: 'Local minimum found.…'

xf точка минимизации.
ff значение цели, rf2, в xf.
flf выходной флаг. Выходной флаг 1 указывает на xf локальный минимум.
of структура output, которая описывает fminunc продвижение вычислений к решению.

patternsearch

Решить задачу оптимизации с помощью patternsearch Решатель Global Optimization Toolbox, введите:

rf2 = @(x)rastriginsfcn(x/10); % objective
x0 = [20,30]; % start point away from the minimum
[xp,fp,flp,op] = patternsearch(rf2,x0)

patternsearch возвращается

Optimization terminated: mesh size less than options.MeshTolerance.
xp =
   19.8991   -9.9496
fp =
    4.9748
flp =
     1
op =

  struct with fields:

        function: @(x)rastriginsfcn(x/10)
     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.'

xp точка минимизации.
fp значение цели, rf2, в xp.
flp выходной флаг. Выходной флаг 1 указывает на xp локальный минимум.
op структура output, которая описывает patternsearch продвижение вычислений к решению.

ga

Решить задачу оптимизации с помощью ga Решатель Global Optimization Toolbox, введите:

rng default % for reproducibility
rf2 = @(x)rastriginsfcn(x/10); % objective
x0 = [20,30]; % start point away from the minimum
initpop = 10*randn(20,2) + repmat(x0,20,1);
opts = optimoptions('ga','InitialPopulationMatrix',initpop);
[xga,fga,flga,oga] = ga(rf2,2,[],[],[],[],[],[],[],opts)

initpop 20 2 матрица. Каждая строка initpop имеет средний [20,30], и каждый элемент нормально распределен со стандартным отклонением 10. Строки initpop сформируйте матрицу начальной генеральной совокупности для ga решатель.

opts опции, которые устанавливают initpop как начальная генеральная совокупность.

Итоговые вызовы линии ga, использование опций.

ga случайные числа использования, и выдают случайный результат. В этом случае ga возвращается:

Optimization terminated: maximum number of generations exceeded.

xga =

   -0.0042   -0.0024


fga =

   4.7054e-05


flga =

     0


oga = 

  struct with fields:

      problemtype: 'unconstrained'
         rngstate: [1×1 struct]
      generations: 200
        funccount: 9453
          message: 'Optimization terminated: maximum number of generations exceeded.'
    maxconstraint: []

xga точка минимизации.
fga значение цели, rf2, в xga.
flga выходной флаг. Выходной флаг 0 указывает на это ga достигнутый предел вычисления функции или предел итерации. В этом случае, ga достигнутый предел итерации.
oga структура output, которая описывает ga продвижение вычислений к решению.

particleswarm

Как ga, particleswarm основанный на населении алгоритм. Таким образом для справедливого сравнения решателей, инициализируйте рой частицы тому же населению как ga.

rng default % for reproducibility
rf2 = @(x)rastriginsfcn(x/10); % objective
opts = optimoptions('particleswarm','InitialSwarmMatrix',initpop);
[xpso,fpso,flgpso,opso] = particleswarm(rf2,2,[],[],opts)

Optimization ended: relative change in the objective value 
over the last OPTIONS.MaxStallIterations iterations is less than OPTIONS.FunctionTolerance.

xpso =

    9.9496    0.0000


fpso =

    0.9950


flgpso =

     1


opso = 

  struct with fields:

      rngstate: [1×1 struct]
    iterations: 56
     funccount: 1140
       message: 'Optimization ended: relative change in the objective value ↵over the last OPTIONS.MaxStallIterations iterations is less than OPTIONS.FunctionTolerance.'

xpso точка минимизации.
fpso значение цели, rf2, в xpso.
flgpso выходной флаг. Выходной флаг 1 указывает на xpso локальный минимум.
opso структура output, которая описывает particleswarm продвижение вычислений к решению.

surrogateopt

surrogateopt не требует стартовой точки, но действительно требует конечных границ. Установите границы –70 к 130 в каждом компоненте. Чтобы иметь тот же вид выхода как другие решатели, отключите функцию построения графика по умолчанию.

rng default % for reproducibility
lb = [-70,-70];
ub = [130,130];
rf2 = @(x)rastriginsfcn(x/10); % objective
opts = optimoptions('surrogateopt','PlotFcn',[]);
[xsur,fsur,flgsur,osur] = surrogateopt(rf2,lb,ub,opts)

Surrogateopt stopped because it exceeded the function evaluation limit set by 
'options.MaxFunctionEvaluations'.

xsur =

   -0.0033    0.0005


fsur =

   2.2456e-05


flgsur =

     0


osur = 

  struct with fields:

    elapsedtime: 2.3877
      funccount: 200
       rngstate: [1×1 struct]
        message: 'Surrogateopt stopped because it exceeded the function evaluation limit set by ↵'options.MaxFunctionEvaluations'.'

xsur точка минимизации.
fsur значение цели, rf2, в xsur.
flgsur выходной флаг. Выходной флаг 0 указывает на тот surrogateopt остановленный, потому что это исчерпало вычисления функции или время.
osur структура output, которая описывает surrogateopt продвижение вычислений к решению.

GlobalSearch

Решить задачу оптимизации с помощью GlobalSearch решатель, введите:

rf2 = @(x)rastriginsfcn(x/10); % objective
x0 = [20,30]; % start point away from the minimum
problem = createOptimProblem('fmincon','objective',rf2,...
    'x0',x0);
gs = GlobalSearch;
[xg,fg,flg,og] = run(gs,problem)

problem структура задачи оптимизации. problem задает fmincon решатель, rf2 целевая функция и x0=[20,30]. Для получения дополнительной информации об использовании createOptimProblem, смотрите Создают Структуру задачи.

Примечание

Необходимо задать fmincon как решатель для GlobalSearch, даже для неограниченных проблем.

gs GlobalSearch по умолчанию объект. Объект содержит опции для того, чтобы решить задачу. Вызов run(gs,problem) запуски problem от нескольких стартовых точек. Стартовые точки случайны, таким образом, следующий результат также случаен.

В этом случае запуск возвращается:

GlobalSearch stopped because it analyzed all the trial points.

All 10 local solver runs converged with a positive local solver exit flag.

xg =

   1.0e-07 *

   -0.1405   -0.1405


fg =

     0


flg =

     1


og = 

  struct with fields:

                funcCount: 2350
         localSolverTotal: 10
       localSolverSuccess: 10
    localSolverIncomplete: 0
    localSolverNoSolution: 0
                  message: 'GlobalSearch stopped because it analyzed all the trial points.↵↵All 10 local solver runs converged with a positive local solver exit flag.'

xg точка минимизации.
fg значение цели, rf2, в xg.
flg выходной флаг. Выходной флаг 1 указывает на все fmincon запуски сходились правильно.
og структура output, которая описывает GlobalSearch продвижение вычислений к решению.

Сравните синтаксис и решения

Одно решение лучше, чем другой, если его значение целевой функции меньше, чем другой. Следующая таблица обобщает результаты, с точностью до одного десятичного числа.

Результаты	fminunc	patternsearch	ga	particleswarm	surrogateopt	GlobalSearch
решение	[19.9 29.9]	[19.9 -9.9]	[0 0]	[10 0]	[0 0]	[0 0]
цель	12.9	5	0	1	0	0
# Fevals	15	174	9453	1140	200	2178

Эти результаты типичны:

fminunc быстро достигает локального решения в его стартовой области, но не исследует вне этой области вообще. fminunc имеет простой синтаксис вызова.
patternsearch берет больше вычислений функции, чем fminunc, и перерывает несколько областей, находя лучшее решение, чем fminunc. patternsearch вызов синтаксиса совпадает с вызовом fminunc.
ga берет намного больше вычислений функции, чем patternsearch. Случайно это нашло лучшее решение. В этом случае, ga найденный точкой около глобального оптимума. ga является стохастическим, таким образом, его изменение результатов с каждым запуском. ga имеет простой синтаксис вызова, но существуют дополнительные шаги, чтобы иметь начальную генеральную совокупность около [20,30].
particleswarm берет меньше вычислений функции, чем ga, но больше, чем patternsearch. В этом случае, particleswarm найденный точкой с более низким значением целевой функции, чем patternsearch, но выше, чем ga. Поскольку particleswarm является стохастическим, его изменение результатов с каждым запуском. particleswarm имеет простой синтаксис вызова, но существуют дополнительные шаги, чтобы иметь начальную генеральную совокупность около [20,30].
surrogateopt остановки, когда это достигает предела вычисления функции, который по умолчанию является 200 для 2D переменной проблемы. surrogateopt имеет простой синтаксис вызова, но требует конечных границ. surrogateopt попытки найти глобальное решение, и в этом случае следовавший. Каждое вычисление функции в surrogateopt занимает более длительное время, чем в большинстве других решателей, потому что surrogateopt выполняет много вспомогательных расчетов как часть его алгоритма.
GlobalSearch run берет тот же порядок величины вычислений функции как ga и particleswarm, поисковые запросы много областей, и находят хорошее решение. В этом случае, GlobalSearch найденный глобальным оптимумом. Подготовка GlobalSearch более включен, чем подготовка других решателей. Когда пример показывает, прежде, чем вызвать GlobalSearch, необходимо создать обоих GlobalSearch объект (gs в примере), и структура задачи (problem). Затем вы вызываете run метод с gs и problem. Для получения дополнительной информации о том, как запустить GlobalSearch, смотрите Рабочий процесс для GlobalSearch и MultiStart.

Документация