XIV Аттетков и др. Методы оптимизации (1081420), страница 42
Текст из файла (страница 42)
Отметим еще одну модификацию метода Хука — Джинса, позволяющую определить точку минимума целевой функции двух переменных за один шаг поиска. Графическая иллюстрация этого метода дана на рис. 6.20. Обратим внимание на то, что процесс поиска точки ж в этом варианте совпадает с процессом ее поиска в варианте, представленном на рис. 6.19, 6. Проводя исследующий поиск в точке ж с помощью метода циклического покоординатного спуска и выбирая на этапе спуска ускоряющий множитель по условию минимума целевой функции в установленном направлении спуска, получим точку жз, совпадающую с точкой минимума рассматриваемой функции. 6.6.
Методы Роэенброка и Пауэлла Рассмотрим еще одну стратегию поиска точки минимума ограниченной снизу целевой функции )'(а), ж е Вв. Метод, реализующий эту стратегию поиска, также предусматривает проведение исследующего поиска на каждом Й-м шаге. Целью исследующего поиска является выбор текущего направления спуска с учетом информации о поведении целевой функции в окрестности точки и ', найденной на предыдущем шаге. Отличие этого метода от метода Хука †.
Джинса состоит в способе выбора направлений исследующего поиска. Если в методе Хука Дживса они фиксированы и коллинеарны направлениям векторов стандартного базиса в 1~", то в рассматриваемом методе выбор этих направлений проводят в процессе минимизации целевой функции путем построения на каждом й-м шаге поиска нового ортонормированного базиса в ПР. Итогом выполнения этого этапа является нахождение точки в~, для которой ~(т~) ( ) (т~ л).
Тогда вектор ж~ — ж~ 1 определит направление спуска на й-м шаге. 293 6.6. Ъ|етоды Розеяброка и Паузлла зе =0; а + 3 у = 1, и. зе~~ ~ -к-О. Скез Базара М., Шеляти К. Такая стратегия поиска впервые была реализована в 1960 году и получила название метода Розенброка'. В первоначальном варианте метода Розенброка процедура нахождения точки хи (как и в методе Хука — — Дживса) была основана на дискретных шагах исследующего поиска по выбранным направлениям. Опишем модификацию этого метода, в которой на каждом К-м шаге поиска выбор координат точки ж"' проводят методом модифицированного циклическоггг покоордннатногл> спуска. Пусть выбраны начальная точка ва б Ки и параметр е > 0 точности поиска. Возьмем в качестве векторов р1, з = 1, и, определяющих направления исследующего поиска на первом шаге, векторы е стандартного базиса в Б!и.
Полагаем и — з' — 1, т1 — — и и переходим к основной части алгоритма. 1. Минимизируя функцию ф~ ~(зе) = )'(ж~+ зер~), находим значение зе С К, вычисляем щ „д — — хз + х. р: и переходим к ОО .. -я -а И) а п. 2. 2. Если з < и, то принимаем з': = з'+ 1 и возвращаемся к п. 1. В противном случае полагаем х = ж„+1 и переходим к п.3. 3. Если (ха — ха '~ < е, где е > 0 - достаточно малое число, характеризующее точность выполнения этапа исследующего поиска, то дальнейший поиск точки минимума прекращаем, принимая х* — ща и 1(а*) — ~(ж~).
В противном случае переходим к п.4. 4. На й-м шаге поиска строим новый ортонормированный базис„векторы р +, у = 1, и, которого задают направления а-~-! исследующего поиска на (а+1)-м шаге. При построении этого базиса используем процесс ортогонализации Грэма Шмидта и проводим его следующим образом. Полагаем 294 6.
АЛГОРИТМЫ ПРЯМОГО ПОИСКА Далее вычисляем а+ 1 — 1 /с+) Х 1' с+1 Ьт)) 1-)-1 ~.=) ь"' = 1 у' = 2, и, Рис. 6.21 Пример 6.6. Используем метод Розенброка для минимизации функции из примеров 6.4 и 6.5. Выберем начальную точку ьт! ь, Р. = 2=1 п. ~ь' " !' у После вычисления векторов р, у = 1, и, переходим к п.1, Ь -)- 1 полагая 1:= 1,х, ~ = хь и затем й:= Й + 1. 1 На рис. 6.21 иллюстрируя)тся этапы одного шага поиска точки минимума целевой функции двух переменных из началь- ной точки хе.
Отметим, что рассмотренный алгоритм можно модифицировать, вводя дополнительные правила выбора точ- ки х на каждом Й-м шаге при проведении этапа исследующего поиска 1см. 6.4). 295 6.6. Ъ|етоды Рооеиорока и Пауэлла шо = ( — 2, 1) и точность поиска с = 0,01. Графическая иллюстрация первых трех шагов метода дана на рис.
6.22. Результаты поиска точки минимума по методу Розенброка приведены в табл. 6.7. Рис. 6.22 Таблица 6.7 Из табл. 6.7 видно, что для рассматриваемой функции использование метода Розенброка не приводит к повышению эффективности поиска по сравнению, например, с модифицированным методом циклического покоординатного спуска (см. пример 6А), поскольку при той же точности поиска необходимое число Х шагов поиска не уменьшается. 296 6.
АЛГОРИТМЫ ПРЯЫОГО ПОИСКА Рассмотрим еще один алгоритм прямого поиска, предложенный в 1964 году и называемый обычно методом Пауэлла' Предварительный этап и первые два пункта основной части этого алгоритма практически совпадают с алгоритмом метода Розенброка. Отличие состоит в построении системы векторов, определяющих направления спуска на каждом последующем шаге поиска и проявляется начиная с п.
3 описанного выше алгоритма метода Розенброка. В методе Пауэлла вычисления в п. 3 носят итерационный характер. Поэтому на предварительном этапе для номера 1 итерации принимают 1 = 1. 1. Минимизируя функцию ф~. ~(н) = ~(х~ь + мр~)., находим значение н Е К, вычисляем ш~~~, = х" +и р" и переходим к п.2. 2. Если 1 < п, то полагаем 1: = 1+ 1 и возвращаемся к п. 1. В противном случае переходим к п.3. 3. Полагаем р = х~~„~ — х~~ и находим значение ж, минимизируя функцию 4(н) = ~(:в„ь1 + хр), а затем вычисляем я, = = х~ „, + йр. Если г < и, то для всех 1 = 1,п — 1 заменяем р~': на р",, полагаем р„= р, ж1~ — — ян 4 = 1, г:= 1+1 и переходим к п.1 рассматриваемого алгоритма.
В противном случае, т.е. при г = н, переходим к п. 4. 4. Принимаем жь = я„. Если ~жь — ш" 1~ < е., то вычисления прекращаем и полагаем ж' ш~ и ~(ж*) 1(.в~). В противном случае считаем, что х ' = х~', 1 = 1, 1 = 1, Й:= Й+ 1, и возвращаемся к п. 1 рассматриваемого алгоритма. Рис. 6.23 иллюстрирует один шаг поиска точки минимума целевой функции двух переменных из начальной точки ж . Можно доказать, что в случае квадратичной целевой функции 1'(я) = Яж, х)/2+ (с, х) с положительно определенной матрицей Я с помощью алгоритма метода Пауэлла за один шаг поиска строится система векторов р ч 1 = 1, н, сопряженных относительно этой матрицы.
При этом точка ж~, полученная в конце Смэ Бизаря М., Шэп~ти К. 297 6.6. Методы Рооеяйрока и Пауэлла Рис. 6.23 первого шага, совпадает с искомой точкой х' минимума такой целевой функции. Покажем это на конкретном примере. Пример 6.7. Используем метод Пауэлла для минимизации ранее рассмотренной функции (см. примеры 6.1, 6.4 — 6.6). Выберем начальную точку х" = ( — 2, 1) и точность поиска е = 0,01. Графическая иллюстрация метода представлена на рис. 6.24.
На рисунке видно, что точка х* минимума целевой функции достигается за один шаг поиска. В результате этого поиска получаем х' — ( — 2,236, — 4,472) и ~(х*) — — 28,0, что с точностью 5.10 ' совпадает с точным решением ( — ~/5, — 2~ээб) задачи. ф Известно много модификаций метода Пауэлла. На рис. 6.25 представлена одна из таких модификаций в применении к функции из примеров 6.1, 6.4. 6.7. В качестве начальной выбрана точка хо = (1, 1). Алгоритм, реализующий этот вариант метода Пауэлла., включает проведение на каждом й-м шаге поиска одной дополнительной итерации циклического покоординатного спуска в направлении вектора* р".
При минимизации Сьи: Ренлейтие Г., Рейвиндрин Д., Рвгедел К., а также: Хилинельблаи Д. 298 6. А,ЛГОРИТМЫ ПРЯМОГО ПОИСКА Рис. 6.25 Рис. 6.24 функции, не являющейся квадратичной, дополнительная итерация гарантирует линейную независимость векторов, опредеяяющих направление спуска на каждом Й-м шаге поиска. Вопросы и задачи 6.1. Перечислите методы прямого поиска., выделите те из них, в которых поиск точки минимума целевой функции проводится в соответствии с рекуррентным соотношением (6.8). Объясните, почему при построении алгоритмов таких методов направления поиска должны быть линейно независимыми. Графически проиллк1стрируйте на примере решения двумерной задачи минимизации возможные подходы к построению таких направлений поиска.
6.2. В задаче Дхмхз) = 11х1, + бхз хе+ Зхз~ — 2ъ~ГО(х1 — Зхз) — 22 — ~ пйп., 299 Вопросы и задачи выбрав в качестве начальной точку х" = (~~ГО, О), найдите уравнение линии уровня целевой функции, проходящей через точку хо. При помощи ортогонального преобразования приведите уравнение, описывающее эту линию уровня, к каноническому виду и постройте эту кривую в исходной системе координат. 6.3.
Проведите поиск минимума целевой функции в задаче 6.2 из заданной начальной точки хо с точностью е = 0,01 методами поиска при помощи регулярного и нерегулярного симплексов, циклического покоординатного спуска, методами Хука - . Джинса, Розенброка и Пауэлла. Оптимизируйте процесс поиска при реализации алгоритма метода Нелдера - Мида путем изменения параметров алгоритма: выбора способа построения исходного симплекса и его размеров, коэффициентов отражения, растяжения, сжатия и редукции симплекса; при реализации алгоритма метода Хука —. Джинса изменением вектора перемещений и коэффициента дробления шага на этапе исследующего поиска, а также подбором ускоряв>щего множителя на этапе спуска.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
