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

Функция для оптимизации

Этот пример показывает, как минимизировать функцию Растригина с помощью шести решателей. Каждый решатель имеет свои характеристики. Характеристики приводят к различным решениям и времени запуска. Результаты, рассмотренные в Compare Syntax and Solutions, могут помочь вам выбрать подходящий решатель для собственных задач.

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

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

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

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

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

Код для генерации рисунка

Этот пример минимизирует rf2 использование настроек по умолчанию для fminunc (Оптимизационный Toolbox™ решатель), patternsearch, и GlobalSearch. Пример также использует ga и particleswarm с опциями nondefault, чтобы начать с начальной генеральной совокупности вокруг точки [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 для задачи с двумя переменными. surrogateopt имеет простой синтаксис вызова, но требует конечных границ. surrogateopt пытается найти глобальное решение, и в этом случае это удалось. Каждое вычисление функции в surrogateopt занимает больше времени, чем в большинстве других решателей, потому что surrogateopt выполняет множество вспомогательных расчетов в составе его алгоритма.
GlobalSearch run принимает тот же порядок величины вычислений функции, что и ga и particleswarm, ищет много умывальные раковины, и приходит к хорошему решению. В этом случае GlobalSearch нашел глобальный оптимум. Настройка GlobalSearch Это больше, чем настройка других решателей. Как показывает пример, перед вызовом GlobalSearch, вы должны создать оба GlobalSearch объект (gs в примере) и структуру задачи (problem). Затем вы вызываете run метод с gs и problem. Для получения дополнительной информации о том, как запускать GlobalSearch, см. Рабочий процесс для GlobalSearch и MultiStart.

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