Материал: Пособие в_4_20_деф_мн

Лабораторная работа 4. Методы многомерного поиска Метод деформируемого многогранника

Нелдер и Мид усовершенствовали метод регулярного симплекса, сохранив его достоинства, и предложили методику ускорения поиска в удачно выбранном направлении. В методе деформированного многогранника (метод Нелдера Мида) также строят исходный регулярный симплекс, определяют значения целевой функции в вершинах симплекса.

При работе с алгоритмом метода деформируемого многогранника используются следующие соглашения:

первый индекс координаты входного параметра определяет порядковый номер вершины симплекса. Количество вершин симплекса равно п+1;

второй индекс координаты входного параметра обозначает порядковый номер оси координат (координата направления). Для целевой функции двух переменных максимальное значение второго индекса j=2.

В двухмерный массив координат вершин симплекса (п+1 вершина) добавлены координаты:

п + 2 - центра тяжести; п + З -отображенной вершины;

п + 4 - растянутой вершины; п + 5 - сжатой вершины.

Для удобства обозначений в выражениях используются индексы: h - номер вершины симплекса, которой принадлежит максимальное значение целевой

функции

f xhk max f xhk , где

l - номер вершины симплекса, которой принадлежит минимальное значе-

к— номер шага (итерации) алгоритма.

Для определения координат центра тяжести симплекса используют выражение:

1

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

Количество столбцов матрицы D соответствует количеству вершин симплекса (п+1), а строки матрицы D содержат координаты вершин симплекса. Количество строк равно п.

Значения элементов матрицы D вычисляют по формулам:

где t— расстояние между вершинами симплекса. Для большинства задач t=1. Над отображаемой вершиной в методе деформируемого многогранника

могут быть выполнены следующие процедуры. 1.Отображение вершины.

2.В случае поиска минимума целевой функции через центр тяжести отображается вершина h с наибольшим значением целевой функции.

В случае поиска максимума целевой функции – вершина l. Отображение вершины симплекса выполняется с использованием выражения:

xnk 3, j xnk 2, j xnk 2 xhk, j ,

где 0 коэффициент отображения.

Если значение целевой функции в отображенной вершине (п+3) меньше, чем в вершине хh, и больше, чем в вершине хl, то координаты вершины хh заменяют на координаты отображенной вершины.

3.Растяжение вершины.

4.Если после отображения вершины симплекса оказалось, что значение целевой функции в отображаемой вершине меньше, чем во всех остальных вершинах или равно значению целевой функции в вершине хl, то выбранное направление удачное, т. е. где-то в этом направлении нахо-

2

дится экстремум. Поэтому отображаемую вершину надо продвинуть в

направлении отображения.

xnk 4, j xnk 2, j xnk 3 xnk 2, j ,

где 1 коэффициент растяжения.

5.Если значение целевой функции в растянутой вершине меньше, чем значение целевой функции в отображенной вершине, то координаты вершины хh заменяются на координаты растянутой вершины. В противном случае координаты вершины хh заменяются на координаты растянутой вершины.

6.Сжатие вершины.

Если после отображения вершины симплекса оказалось, что значение целевой функции в отображенной вершине больше или равно значению целевой функции в вершине хh, то направление отображения выбрано неудачно и отображенную вершину надо приблизить к центру тяжести. Сжатие вершины выполняется по формуле:

xnk 5, j xnk 2, j xhk, j xnk 2, j , (1)

где 0 1 - коэффициент сжатия.

Если после выполнения процедуры сжатия значение целевой функции в сжатой вершине будет меньше, чем в вершине хh, то выполняем замену координат вершины xh, на координаты сжатой вершины. В противном случае выполняется процедура редукции вершин симплекса.

По формуле (1) симплекс сжимается к вершине хl. Можно преобразовать формулу (1) и симплекс будет сжиматься к центру тяжести.

4. Редукция вершин.

Если в результате выполнения процедур отображения и сжатия оказалось, что выполнить замену координат вершины хh, нельзя, то выполняется процедура редукции вершин симплекса, в результате чего геометрические размеры симплекса уменьшаются, как правило, в 2 раза. Редукция вершин симплекса выполняется по формуле:

xi,kj xl ,kj 0,5 xi,kj xl ,kj , j 1, n 1 .

Процедура редукции выполняется в том случае, когда нет возможности отобразить вершину хh, т. е. симплекс находится в окрестности экстремума и надо уточнить координаты экстремальной точки.

3

Для всех процедур — отображение, растяжение, сжатие, редукция и определение координат центра тяжести – вычисления по указанным формулам надо выполнить для каждого индекса (для каждого координатного направления).

При выполнении процедур растяжения и сжатия исходный регулярный симплекс изменяет свои геометрические размеры и теряет свойство регулярности.

5. Критерий окончания поиска.

Критериев окончания поиска можно указать несколько. Наилучшего критерия окончания поиска нет. Авторы метода деформируемого многогранника рекомендуют в качестве критерия окончания поиска использовать выражение:

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

Используемый деформируемый многогранник (симплекс) наиболее удачно приспособлен к топографии целевой функции, т. е. изменяет свою форму в зависимости от «рельефа» целевой функции.

Авторы метода деформируемого многогранника провели ряд исследований и рекомендуют следующие значения коэффициентов: 1; 0,5 и 2 . Другие исследователи этого метода рекомендуют 1; 0,4 0,6 и 2,8 3,0 . Предложенные рекомендации хорошо себя показали на многих це-

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

Практическое задание. Найти оптимальные значения x x1; x2 для целевой

функции F x x12 x2 11 2 x1 x22 7 2 min в окрестностях точки x0 5; 5 методом деформируемого многогранника. Создать и выполнить приведенный ниже скриптфайл, иллюстрирующий выполнение минимизации.

% Демонстрация метода деформируемого многогранника (сим- плекс-метод Нелдера-Мида)

clc; close all % График ЦФ

xi1 = -5.5:0.1:5.5; xi2 = -5.5:0.1:5.5;

4

[X1, X2] = meshgrid(xi1,xi2);

Fun = (X1.^2 + X2 - 11).^2 + (X1 + X2.^2 - 7).^2; figure

meshc(X1, X2, Fun); grid on figure

contour(X1, X2, Fun, 120); grid on

%линии уровня вблизи x1 = [5; 5] xi1 = 3.5:0.02:5.5;

xi2 = 3.5:0.02:5.5;

[X1, X2] = meshgrid(xi1,xi2);

Fun = (X1.^2 + X2 - 11).^2 + (X1 + X2.^2 - 7).^2; figure

contour(X1, X2, Fun, 50); hold on; axis equal

%встроенная ЦФ

F = inline('(x(1).^2 + x(2) - 11).^2 + (x(1) + x(2).^2 - 7).^2');

n = 2; % размерность задачи

b = 0.2; % длина ребра симплекса alpha = 1; % коэффициент отображения gamma = 2; % коэффициент растяжения beta = 0.5; % коэффициент сжатия

MaxNumIter = 100; % максимальное количество итераций

x1 = [5; 5]; % стартовая точка

TolFun = 0.0001;

% строим исходный регулярный симплекс

x2 = zeros(2,1); % координаты второй точки симплекса x2(1) = x1(1) + (sqrt(n+1)-1) / (n*sqrt(2)) * b; x2(2) = x1(2) + (sqrt(n+1)+n-1) / (n*sqrt(2)) * b;

x3 = zeros(2,1); % координаты третьей точки симплекса x3(1) = x1(1) + (sqrt(n+1)+n-1) / (n*sqrt(2)) * b; x3(2) = x1(2) + (sqrt(n+1)-1) / (n*sqrt(2)) * b;

x = zeros(2,3);

% записываем в массив 2*3 координаты симплекса x(:,1) = x1;

x(:,2) = x2; x(:,3) = x3;

for i=1:MaxNumIter, % цикл по номеру sprintf('Симплекс № %d', i)

5