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

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

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

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

$Ras (x) =_{20}^{} +_{}^{} x12 + x22 -_{} 10 (_{} cos2íx1$ + cos2āx2).

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

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

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

Код для создания фигуры

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

fminunc

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

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 является структурой вывода, которая описывает fminunc расчеты, ведущие к решению.

patternsearch

Для решения задачи оптимизации с помощью patternsearch Решатель панели инструментов глобальной оптимизации, введите:

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 является структурой вывода, которая описывает patternsearch расчеты, ведущие к решению.

ga

Для решения задачи оптимизации с помощью ga Решатель панели инструментов глобальной оптимизации, введите:

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 является структурой вывода, которая описывает 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 является структурой вывода, которая описывает 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 является структурой вывода, которая описывает 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 является структурой вывода, которая описывает 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`
# Февалы	`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, см. Workflow-процесс для "" "" "" "" "" "" "" "" "" "" "" "

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