Основы теории оптимизации (стр. 75 )

7.1. Анализ методов прямого поиска

Метод поиска по симплексу

Метод основан на том, что экспериментальным образцом, содержащим наименьшее количество точек, является симплекс.

Регулярный симплекс в N-мерном пространстве – это многогранник, образованный N+1 равноотстоящими точками – вершинами симплекса.

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

  Пример для двухмерного случая.

в точке x(1) наихудшее значение функции; в точке xc центр тяжести.

Работа алгоритма начинается с построения регулярного симплекса в пространстве независимых переменных задачи и оценивания значения целевой функции в его вершинах. Затем точка с наибольшим значением функции отражается через центр тяжести остальных точек. Новая точка используется как вершина нового симплекса. Итерации продолжаются до тех пор, пока либо не будет накрыта точка минимума, либо не начнётся циклическое движение по двум или более симплексам. При этом следует пользоваться тремя правилами:

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

·  Если некоторая вершина симплекса не исключается более, чем на N итерациях, то уменьшить размеры симплекса с помощью некоторого коэффициента и построить новый симплекс, используя в качестве базовой точку с наименьшим значением функции. Количество итераций не исключения вершины: M=1,65ЧN+0,05ЧN2.

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

Реализация алгоритма использует две основные процедуры: построение регулярного симплекса при заданной базовой точке и масштабном множителе (шаге) симплекса; расчёт отражённой точки.

Пусть x(j) - точка для отражения.

 центр масс.

Все точки прямой, проходящей через x(j) и xc определяются формулой  при λ=0 x= x(j) , при λ=1 x=xc .

Для получения нового регулярного симплекса λ=2 , тогда .

Достоинства метода:

·  простота;

·  малое количество заранее установленных параметров;

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

Недостатки метода:

·  возникают трудности связанные с масштабированием задачи ( в реальных задачах разные переменные часто не сопоставимы между собой по значениям);

·  алгоритм работает медленно (не используется информация предыдущих итераций);

·  не существует простого способа изменения размеров симплекса без пересчёта всех значений целевой функции.

Метод Нелдера-Мида

Это модифицированный метод поиска по симплексу (или метод деформируемого многоугольника). Он частично устраняет недостатки предыдущего.

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

Деформирование осуществляется с помощью трёх операций:

операция	коэффициент для процедур в методе
отражение	1
сжатие	0,5
растяжение	2

  Используемые процедуры.

 Регуляризация симплекса.

 x(0)- начальная точка, h – шаг.

  Расчёт значений функции в вершинах симплекса.

Сортировка симплекса.

  Точки симплекса нумеруются в порядке возрастания значений функции. Лучшая точка имеет номер 1, а худшая – номер N+1.

  Нахождение пробной точки (на прямой, соединяющей худшую точку и центр масс).

  Возможно получение трёх различных точек:

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

 xβ - результат растяжения симплекса, лежит на рaсстоянии в два раза большем, чем xα от центра масс.

xγ - результат сжатия симплекса, лежит в два раза ближе к центру масс, чем точка xα.

  Редукция симплекса.

  Все точки симплекса сближаются к лучшей точке на половину расстояния.

  На каждой итерации действия алгоритма описываются набором следующих правил:

Рассчитывается xα.

Если , то выполняется растяжение симплекса и находится точка xβ. Лучшая из точек xα, xβ записывается на место  и производится сортировка симплекса.

Если  и , то точка xα записывается на место  и производится сортировка симплекса.

Если , то производится сжатие симплекса и находится точка xγ . Если , то xγ записывается на место  в противном случае производится редукция симплекса.

Недостаток: метод работает работает эффективно при N≤6.

Метод поиска Хука-Дживса

Стратегию поиска по симплексу можно усовершенствовать путём введения множества векторов, задающих направления поиска. Эти вектора должны быть линейно-независимы и образовывать базис в пространстве независимых переменных. Этому удовлетворяет система координатных направлений.

Метод Хука-Дживса - это комбинация исследующего поиска по направлениям и поиска по образцу.

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

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

Новая точка строится по формуле:

xp(k+1) = x(k)+(x(k)-x(k-1)),

где:

  x(k) - текущая базовая точка;

  x(k-1) - предыдущая базовая точка;

  xp(k+1) - точка, построенная при движении по образцу;

  x(k+1) - новая базовая точка.

Если движение по образцу не приводит к уменьшению целевой функции, то точка xp(k+1) фиксируется в качестве временной базовой точки и вновь проводится исследующий поиск из этой точки. Если в результате получается точка со значением функции меньшим, чем в x(k), то она рассматривается как новая базовая точка x(k+1).

Если исследующий поиск неудачен, то нужно вернуться в x(k) и провести поиск в противоположном направлении. Если он также не приводит к успеху, то нужно уменьшить величину шага и возобновить исследующий поиск. Поиск завершается, когда величина шага становится достаточно малой.

Алгоритм метода.

1. Определить начальную точку x(0), приращения по координатным направлениям Di, i=1,...,N, коэффициент уменьшения шага α>1 и параметр окончания поиска ε.

2. Провести исследующий поиск.

3. Проверка успешности исследующего поиска. Если успешно, перейти к шагу 5, если нет, продолжать поиск.

4. Проверка на окончание поиска:

 

Если условие выполняется, поиск прекратить, если не выполняется, уменьшить шаг D и перейти к шагу 2.

 

5. Провести поиск по образцу, то есть найти точку

xp(k+1) = x(k)+(x(k)-x(k-1))

6. Провести исследующий поиск из точки xp(k+1) и получить точку x(k+1).

7. Если f(x(k+1)) < f(x(k)),

  то:  x(k-1) = x(k);

  x(k) = x(k+1);

  goto 5.

  иначе, goto 4.

  Пример.

f(x) = 8x12+4x1x2+5x22

  1) x(0) = [-4;-4];  f(x(0)) = 272;

D= [1,1];  α = 2;  ε= 10-4.