Нелинейное программирование (стр. 6 из 7)

(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, т. е. наблюдается уменьшение целевой функции. Новый симплекс образован точками и . В соответствии с алгоритмом следует отразить точку х⁽²⁾, которой соответствует наибольшее значение целевой функции, относительно центра тяжести точек и х⁽³⁾. Итерации продолжаются до тех пор, пока не потребуется применение правил 1, 2 и 3, которые были сформулированы выше.

Изложенный выше алгоритм

- метода имеет несколько очевидных преимуществ.

1. Расчеты и логическая структура метода отличаются сравнительной простотой, и, следовательно, соответствующая программа для ЭВМ оказывается относительно короткой.

2. Уровень требований к объему памяти ЭВМ невысокий, массив имеет размерность (n+1, n+2).

3. Используется сравнительно небольшое число заранее установленных параметров: масштабный множитель

, коэффициент уменьшения множителя (если применяется правило 2) и параметры окончания поиска.

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

Перечисленные факторы характеризуют метод поиска по симплексу как весьма полезный при проведении вычислений в реальном времени.

Алгоритм обладает также рядом существенных недостатков.

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

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

2. Алгоритм работает слишком медленно, так как полученная на предыдущих итерациях информация не используется для ускорения поиска.

3. Не существует простого способа расширения симплекса, не требующего пересчета значений целевой функции во всех точках образца. Таким образом, если

по какой-либо причине уменьшается (например, если встречается область с узким «оврагом» или «хребтом»), то поиск должен продолжаться с уменьшенной величиной шага.

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

Метод, разработанный Хуком и Дживсом, является одним из первых алгоритмов, в которых при определении нового направления поиска учитывается информация, полученная на предыдущих итерациях. По существу процедура Хука—Дживса представляет собой комбинацию «исследующего» поиска с циклическим изменением переменных и ускоряющегося поиска по образцу с использованием определенных эвристических правил. Исследующий поиск ориентирован на выявление характера локального поведения целевой функции и определение направлений вдоль «оврагов». Полученная в результате исследующего поиска информация затем используется в процессе поиска по образцу при движении по «оврагам».

Исследующий поиск.

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

Поиск по образцу.

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

Как только движение по образцу не приводит к уменьшению целевой функция, точка

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