2) метод поиска Хука--Дживса;

3) метод сопряженных направлений Пауэлла.

Первые два из перечисленных методов относятся к категории эвристических и реализуют принципиально различающиеся стра-тегии поиска. В процессе поиска по S2-методу последовательно опе-рируют регулярными симплексами в пространстве управляемых переменных, тогда как при реализации метода Хука-Дживса используется фиксированное множество (координатных) направле-ний, выбираемых рекурсивным способом. Метод Пауэлла основан на теоретических результатах и ориентирован на решение задач с квадратичными целевыми функциями; для таких задач метод сходится за конечное число итераций. К числу общих особенностей всех трех методов следует отнести относительную простоту соответ-ствующих вычислительных процедур, которые легко реализуются и быстро корректируются. С другой стороны, реализация указанных методов может требовать (и часто требует) более значительных затрат времени по сравнению с методами с использованием производных.

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

Рис 2. Квадратный образец (частный случай кубического образца)

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

Этот тип эволюционной опти-мизации был использован Бок-сом и другими исследователями для анализа функционирования промышленных предприятий, когда эффект варьирования значений переменных, описывающих производственные процессы, измеряется с ошибкой. В задачах большой размерности вычисление значений целевой функции проводится во всех вершинах, а также в центре тяжести гиперкуба (гиперкуб - куб в n-мерном евклидовом пространстве, т.е. множество S= , где а и b - заданные числа ) , т. е. в точках так называемого кубического образца. Если количество переменных (размерность пространства, в котором ведется поиск) равно n, то поиск по кубическому образцу требует +1 вычислений значения функций для одного образца. При увеличении размерности задачи необходимое количество вы-числений значения целевой функции возрастает чрезвычайно быст-ро. Таким образом, несмотря на логическую простоту поиска по кубическому образцу, возникает необходимость использования более эффективных методов прямого поиска для решения возникаю-щих на практике задач оптимизации.

Одна из вызывающих особый интерес стратегий поиска положе-на в основу метода поиска по симплексу, предложенного Спендли, Хекстом и Химсвортом. Следует отметить, что указанный метод и другие подобные методы не имеют отношения к симплекс-методу линейного программирования, а сходство названий носит случай-ный характер. Процедура симплексного поиска Спендли, Хекста и Химсворта базируется на том, что экспериментальным образцом, содержащим наименьшее количество точек, является регулярный симплекс. Регулярный симплекс в n-мерном пространстве пред-ставляет собой многогранник, образованный n+1 равностоящими друг от друга точками-вершинами. Например, в случае двух пере-менных симплексом является равносторонний треугольник; в трех-мерном пространстве симплекс представляет собой тетраэдр. В алго-ритме симплексного поиска используется важное свойство симплек-сов, согласно которому новый симплекс можно построить на любой грани начального симплекса путем переноса выбранной вершины на надлежащее расстояние вдоль прямой, проведенной через центр тяжести остальных вершин начального симплекса. Полученная та-ким образом точка является вершиной нового симплекса, а выбран-ная при построении вершина начального симплекса исключается. Нетрудно видеть, что при переходе к новому симплексу требуется одно вычисление значения целевой функции. Рис 3 иллюстрирует процесс построения нового симплекса на плоскости.

Рис.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