Эффекты параметров поиска шаблона

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

Настройте проблему для поиска шаблона

Проблемой минимизировать является квадратичная функция шести переменных, удовлетворяющих линейному равенству и ограничениям неравенства. Целевая функция, lincontest7, включен с Global Optimization Toolbox.

type lincontest7
%   Copyright 2003-2004 The MathWorks, Inc.

x = x';
%Define a quadratic problem in terms of H and f (From web unknown source)
H = [36 17 19 12 8 15; 17 33 18 11 7 14; 19 18 43 13 8 16;
12 11 13 18 6 11; 8 7 8 6 9 8; 15 14 16 11 8 29];
 f = [ 20 15 21 18 29 24 ]';
 
 y = 0.5*x'*H*x + f'*x;

Задайте указатель на функцию @lincontest7 как целевая функция.

objectiveFcn = @lincontest7;

Целевая функция принимает вектор-строку из длины шесть. Задайте начальную точку для оптимизации.

x0 = [2 1 0 9 1 0];

Создайте линейные ограничительные матрицы, представляющие ограничения Aineq*x <= Bineq и Aeq*x = Beq. Для получения дополнительной информации смотрите Линейные Ограничения (Optimization Toolbox).

Aineq = [-8 7 3 -4 9 0 ];
Bineq = [7];
Aeq = [7 1 8 3 3 3; 5 0 5 1 5 8; 2 6 7 1 1 8; 1 0 0 0 0 0];
Beq = [84 62 65 1];

Запустите patternsearch решатель и примечание количество итераций и вычислений функции, требуемых достигнуть решения.

[X1,Fval,Exitflag,Output] = patternsearch(objectiveFcn,x0,Aineq,Bineq,Aeq,Beq);
Optimization terminated: mesh size less than options.MeshTolerance.
fprintf('The number of iterations is: %d\n', Output.iterations);
The number of iterations is: 248
fprintf('The number of function evaluations is: %d\n', Output.funccount);
The number of function evaluations is: 1920
fprintf('The best function value found is: %g\n', Fval);
The best function value found is: 2189.03

Добавьте визуализацию

Контролируйте процесс оптимизации путем определения опций тот выбор две функции построения графика. Функция построения графика psplotbestf строит лучшее значение целевой функции в каждой итерации и функцию построения графика psplotfuncount строит число раз, целевая функция выполнена в каждой итерации. Установите эти две функции построения графика в массиве ячеек.

opts = optimoptions(@patternsearch,'PlotFcn',{@psplotbestf,@psplotfuncount});

Запустите patternsearch решатель, включая opts аргумент. Поскольку проблема не имеет никаких верхних или нижних границ ограничений и никаких нелинейных ограничений, пустые массивы передачи ([]) для седьмых, восьмых, и девятых аргументов.

[X1,Fval,ExitFlag,Output] = patternsearch(objectiveFcn,x0,Aineq,Bineq, ...
    Aeq,Beq,[],[],[],opts);
Optimization terminated: mesh size less than options.MeshTolerance.

Настройки сетки

Поиск шаблона включает выполнение целевой функции в точках в mesh. Размер mesh может влиять на скорость решения. Можно управлять размером mesh с помощью опций.

Начальный размер Mesh

Mesh в каждой итерации является промежутком набора поисковых направлений, которые добавляются к текущей точке, масштабируемой текущим размером mesh. Решатель запускается с начального размера mesh 1 по умолчанию. Запустить начальный размер mesh в 10, установите InitialMeshSize опция.

options = optimoptions(opts,'InitialMeshSize',10);

Поймайте в сети масштабирование

Можно масштабировать mesh, чтобы улучшить минимизацию плохо масштабированной задачи оптимизации. Масштабирование вращает шаблон определенной степенью и шкалами вдоль поисковых направлений. ScaleMesh опция идет (true) по умолчанию, но можно выключить его, если проблема хорошо масштабируется. В общем случае, если проблема плохо масштабируется, устанавливая эту опцию на true может сократить количество вычислений функции. Для этой проблемы, набор ScaleMesh к false, потому что lincontest7 хорошо масштабируемая целевая функция.

opts = optimoptions(opts,'ScaleMesh',false);

Поймайте в сети акселератор

Прямые методы поиска требуют многих вычислений функции по сравнению с основанными на производной методами оптимизации. Алгоритм поиска шаблона может быстро найти окружение оптимальной точки, но может быть медленным в обнаружении самого минимума. patternsearch решатель может сократить количество вычислений функции при помощи акселератора. Когда акселератор работает (opts.AccelerateMesh = true), решатель сокращает размер mesh быстро после некоторого минимального размера mesh. Эта опция рекомендуется только для сглаженных проблем; в других типах проблем можно потерять некоторую точность. AccelerateMesh опция выключена (false) по умолчанию. Для этой проблемы, набор AccelerateMesh к true потому что целевая функция является гладкой.

opts = optimoptions(opts,'AccelerateMesh',true);

Запустите patternsearch решатель.

[X2,Fval,ExitFlag,Output] = patternsearch(objectiveFcn,x0,Aineq,Bineq, ...
    Aeq,Beq,[],[],[],opts);
Optimization terminated: mesh size less than options.MeshTolerance.

fprintf('The number of iterations is: %d\n', Output.iterations);
The number of iterations is: 202
fprintf('The number of function evaluations is: %d\n', Output.funccount);
The number of function evaluations is: 1330
fprintf('The best function value found is: %g\n', Fval);
The best function value found is: 2189.03

Настройки опции mesh сокращают количество итераций и количество вычислений функции, и нет никакой очевидной потери точности.

Критерий остановки и допуски

MeshTolerance допуск на размере mesh. Если размер mesh меньше MeshTolerance, остановки решателя. StepTolerance минимальный допуск на изменении в текущей точке к следующему вопросу. FunctionTolerance минимальный допуск на изменении в значении функции от текущей точки до следующего вопроса.

Установите MeshTolerance к 1e-7, который в десять раз меньше, чем значение по умолчанию. Эта установка может увеличить число вычислений функции и итераций, и может привести к более точному решению.

opts.MeshTolerance = 1e-7;

Методы поиска в поиске шаблона

Алгоритм поиска шаблона может использовать дополнительный метод поиска в каждой итерации, на основе значения SearchFcn опция. Когда вы задаете метод поиска с помощью SearchFcn, patternsearch выполняет заданный поиск сначала, перед поиском mesh. Если метод поиска успешен, patternsearch пропускает поиск mesh, обычно вызывал функцию опроса, для той итерации. Если метод поиска неудачен в улучшении текущей точки, patternsearch выполняет поиск mesh.

Можно задать различные методы поиска для SearchFcn, включая searchga и searchneldermead, которые являются алгоритмами оптимизации. Используйте эти два метода поиска только в первой итерации, которая является настройкой по умолчанию. Используя любой из этих методов в каждой итерации не может улучшить результаты и может быть в вычислительном отношении дорогим. Однако можно использовать searchlhs метод, который генерирует латинские точки гиперкуба в каждой итерации или возможно каждых 10 итерациях.

Другой выбор для методов поиска включает методы опроса, такие как положительное основание N+1 или положительное основание 2 Н. Рекомендуемая стратегия состоит в том, чтобы использовать положительное основание N+1 (который требует в большинстве точек N+1, чтобы создать шаблон) как метод поиска, и положительное основание 2 Н (который требует, чтобы 2 Н указали, чтобы создать шаблон) как метод опроса.

Обновите структуру опций, чтобы использовать positivebasisnp1 как метод поиска. Поскольку положительным основанием 2 Н является значение по умолчанию для PollFcn опция, не устанавливайте ту опцию.

opts.SearchFcn = @positivebasisnp1;

Запустите patternsearch решатель.

[X5,Fval,ExitFlag,Output] = patternsearch(objectiveFcn,x0,Aineq,Bineq,Aeq,Beq, ...
    [],[],[],opts);
Optimization terminated: mesh size less than options.MeshTolerance.

fprintf('The number of iterations is: %d\n', Output.iterations);
The number of iterations is: 67
fprintf('The number of function evaluations is: %d\n', Output.funccount);
The number of function evaluations is: 840
fprintf('The best function value found is: %g\n', Fval);
The best function value found is: 2189.03

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

Для просмотра документации необходимо авторизоваться на сайте