Рис.3.Построение нового симплекса.
а – начальный симплекс
б – новый симплекс
Работа алгоритма симплексного поиска начинается с построения регулярного симплекса в пространстве независимых переменных и оценивания значений целевой функции в каждой из вершин симплекса. При этом определяется вершина, которой соответствует наибольшее значение целевой функции. Затем найденная вершина проецируется через центр тяжести остальных вершин симплекса в новую точку, которая используется в качестве вершины нового симплекса. Если функция убывает достаточно плавно, итерации продолжаются до тех пор, пока либо не будет накрыта точка минимума, либо не начнется циклическое движение по двум или более симплексам. В таких ситуациях можно воспользоваться следующими тремя правилами.
Правило 1. «Накрытие» точки минимума
Если вершина, которой соответствует наибольшее значение целевой функции, построена на предыдущей итерации, то вместо нее берется вершина, которой соответствует следующее по величине значение целевой функции.
Правило 2. Циклическое движение
Если некоторая вершина симплекса не исключается на протяжении более чем М итераций, то необходимо уменьшить размеры симплекса с помощью коэффициента редукции и построить новый симплекс, выбрав в качестве базовой точку, которой соответствует минимальное значение целевой функции. Спендли, Хекст и Химс-ворт предложили вычислять М по формуле
M=1,65n+0,05
где n — размерность задачи, а М округляется до ближайшего целого числа. Для применения данного правила требуется установить величину коэффициента редукции.
Правило 3. Критерий окончания поиска
Поиск завершается, когда или размеры симплекса, или разности между значениями функции в вершинах становятся достаточно малыми. Чтобы можно было применять эти правила, необходимо задать величину параметра окончания поиска.
Реализация изучаемого алгоритма основана на вычислениях двух типов: (1) построении регулярного симплекса при заданных базовой точке и масштабном множителе и (2) расчете координат отраженной точки. Построение симплекса является достаточно простой процедурой, так как из элементарной геометрии известно, что при заданных начальной (базовой) точке и масштабном множителе координаты остальных n вершин симплекса в n-мерном пространстве вычисляются по формуле
(7)
для i и j=1,2,3,…,n
Приращения и , зависящие только от n и выбранного масштабного множителя, определяются по формулам
(8)
(9)
Заметим, что величина масштабного множителя выбирается исследователем, исходя из характеристик решаемой задачи. При =1 ребра регулярного симплекса имеют единичную длину. Вычисления второго типа, связанные с отражением относительно центра тяжести, также представляют несложную процедуру. Пусть — точка, подлежащая отражению. Центр тяжести остальных n точек расположен в точке
(10)
Все точки прямой, проходящей через и хс, задаются формулой
(11)
При =0 получаем исходную точку , тогда как значение =1 соответствует центру тяжести хс. Для того чтобы построенный симплекс обладал свойством регулярности, отражение должно быть симметричным. Следовательно, новая вершина получается при =2. Таким образом,
(12)
Проиллюстрируем вычислительную схему метода следующим примером.
Пример 5. Вычисления в соответствии с методом поиска по симплексу
Минимизировать f(x)=
Решение.
Для построения исходного симплекса требуется задать начальную точку и масштабный множитель. Пусть x =и =2. Тогда
Используя эти два параметра, вычислим координаты двух остальных вершин симплекса:
которым соответствуют значения целевой функции, равные =0,2374 и 3,0658. Так как 5, необходимо отразить точку относительно центра тяжести двух остальных вершин симплекса
Используя формулу (12), получаем
В полученной точке 2,3027, т. е. наблюдается уменьшение целевой функции. Новый симплекс образован точками и. В соответствии с алгоритмом следует отразить точку х(2), которой соответствует наибольшее значение целевой функции, относительно центра тяжести точек и х(3). Итерации продолжаются до тех пор, пока не потребуется применение правил 1, 2 и 3, которые были сформулированы выше.
Изложенный выше алгоритм - метода имеет несколько очевидных преимуществ.
1. Расчеты и логическая структура метода отличаются сравнительной простотой, и, следовательно, соответствующая программа для ЭВМ оказывается относительно короткой.
2. Уровень требований к объему памяти ЭВМ невысокий, массив имеет размерность (n+1, n+2).
3. Используется сравнительно небольшое число заранее установленных параметров: масштабный множитель , коэффициент уменьшения множителя (если применяется правило 2) и параметры окончания поиска.
4. Алгоритм оказывается эффективным даже в тех случаях, когда ошибка вычисления значений целевой функции велика, поскольку при его реализации оперируют наибольшими значениями функции в вершинах, а не наименьшими.
Перечисленные факторы характеризуют метод поиска по симплексу как весьма полезный при проведении вычислений в реальном времени.
Алгоритм обладает также рядом существенных недостатков.
1. Не исключено возникновение трудностей, связанных с масштабированием, поскольку все координаты вершин симплекса зависят от одного и того же масштабного множителя . Чтобы обойти трудности такого рода, в практических задачах следует промасштабировать все переменные с тем, чтобы их значения были сравнимыми по величине.
2. Алгоритм работает слишком медленно, так как полученная на предыдущих итерациях информация не используется для ускорения поиска.
3. Не существует простого способа расширения симплекса, не требующего пересчета значений целевой функции во всех точках образца. Таким образом, если по какой-либо причине уменьшается (например, если встречается область с узким «оврагом» или «хребтом»), то поиск должен продолжаться с уменьшенной величиной шага.
Метод, разработанный Хуком и Дживсом, является одним из первых алгоритмов, в которых при определении нового направления поиска учитывается информация, полученная на предыдущих итерациях. По существу процедура Хука—Дживса представляет собой комбинацию «исследующего» поиска с циклическим изменением переменных и ускоряющегося поиска по образцу с использованием определенных эвристических правил. Исследующий поиск ориентирован на выявление характера локального поведения целевой функции и определение направлений вдоль «оврагов». Полученная в результате исследующего поиска информация затем используется в процессе поиска по образцу при движении по «оврагам».
Исследующий поиск.
Для проведения исследующего поиска необходимо задать величину шага, которая может быть различной для разных координатных направлений и изменяться в процессе поиска. Исследующий поиск начинается в некоторой исходной точке. Если значение целевой функции в пробной точке не превышает значения функции в исходной точке, то шаг поиска рассматривается как успешный. В противном случае необходимо вернуться в предыдущую точку и сделать шаг в противоположном направлении с последующей проверкой значения целевой функции. После перебора всех N координат исследующий поиск завершается. Полученную в результате точку называют базовой точкой.
Поиск по образцу.
Поиск по образцу заключается в реализации единственного шага из полученной базовой точки вдоль-прямой, соединяющей эту точку с предыдущей базовой точкой. Новая точка образца определяется в соответствии с формулой
Как только движение по образцу не приводит к уменьшению целевой функция, точка фиксируется в качестве временной базовой точки и вновь проводится исследующий поиск. Если в результате получается точка с меньшим значением целевой функции, чем в точке , то она рассматривается как новая базовая точка . С другой стороны, если исследующий поиск неудачен, необходимо вернуться в точку и провести исследующий поиск с целью выявления нового направления минимизации. В конечном счете, возникает ситуация, когда такой поиск не приводит к успеху. В этом случае требуется уменьшить величину шага путем введения некоторого множителя и возобновить исследующий поиск. Поиск завершается, когда величина шага становится достаточно малой. Последовательность точек, получаемую в процессе реализации метода, можно записать в следующем виде:
- текущая базовая точка,
- предыдущая базовая точка,
- точка, построенная при движении по образцу,
- следующая (новая) базовая точка.
Приведенная последовательность характеризует логическую структуру поиска по методу Хука — Дживса.
Структура метода поиска Хука — Дживса
Шаг 1 . Определить:
начальную точку ,
приращения
коэффициент уменьшения шага ,
параметр окончания поиска .
Ш а г 2. ровести исследующий поиск.
Ш а г 3. Был ли исследующий поиск удачным (найдена ли точка с меньшим значением
целевой функции)?
Да: перейти к шагу 5.
Нет: продолжать.
Ш а г 4. Проверка на окончание поиска.
Выполняется ли неравенство ?
Да: прекратить поиск; текущая точка аппроксимирует точку оптимума.
Нет: уменьшить приращения по формуле
Перейти к шагу 2.
Ш а г 5. Провести поиск по образцу:
Шаг 6. Провести исследующий поиск, используя в качестве базовой точки;
пусть полученная в результате точка.
Ш а г 7. Выполняется ли неравенство ?
Да: положить Перейти к шагу 5.
Нет: перейти к шагу 4.
Пример 6 Поиск по методу Хука — Дживса
Найти точку минимума функции используя начальную точку .
Для того чтобы применить метод прямого поиска .Хука — Дживса, необходимо задать следующие величины:
векторная величина приращения = ,
коэффициент уменьшения шага = 2,
параметр окончания поиска = 10-4.
Итерации начинаются с исследующего поиска вокруг точки , которой соответствует значение функции Фиксируя , дадим приращение переменной :
Успех.
Следовательно, необходимо зафиксировать и дать приращение переменной :
Таким образом, в результате исследующего поиска найдена точка
Поскольку исследующий поиск был удачным, переходим к поиску по образцу:
Далее проводится исследующий поиск вокруг точки , который оказывается удачным при использовании положительных приращений переменных х1 и х2. В результате получаем точку
Поскольку , поиск по образцу следует считать успешным, и становится новой базовой точкой при следующем проведении поиска по образцу. Итерации продолжаются, пока уменьшение величины шага не укажет на окончание поиска в окрестности точки минимума. Последовательные шаги реализации метода показаны на рисунке.
Из примера следует, что метод Хука — Дживса характеризуется несложной стратегией поиска, относительной простотой вычислений и невысоким уровнем требований к объему памяти ЭВМ, который оказывается даже ниже, чем в случае использования метода поиска по симплексу.
Итерации поиска по методу Хука-Дживса на примере
Страницы: 1, 2, 3, 4
