XIV Аттетков и др. Методы оптимизации (1081420), страница 41
Текст из файла (страница 41)
(6.10) Значение о Е К находят из решения задачи одномерной мини- мизации (см. 2) ~р~я (о) — ) пшь х.(ст) =|(х +ое ). (6.11) Подчеркнем, что индекс у изменяется циклически, пробегая на каждом шаге покоординатпного спуска все значения от 1 до и., причем значение а в отличие от значения оь в (6.8) может ь быть как положительным, так и отрицательным. Пусть выбраны значения е1 и (или) ез в (6.9) и перед к-м шагом циклического покоординатного спуска по найденной на предыдущем шаге точке х вычислено значение |(х ) целевой функции (на первом шаге значенис | (хс) вычисляют в выбранной начальной точке хе).
Тогда для каждого значения | = 1, п из решения задачи (6.11) находят значение о, и затем вычисляют х =х +~~ ое (6.12) и значение |'(х~). Далее проверяют выполнение условий (6.9) или того из них, которое выбрано в качестве условия прекращения поиска. При положительном результате поиск точки х* 283 6.4. Циклический локоординатяый спуск минимума функции 1"(х) прекращают на Й-м шаге и принимают х* х и 1(х*) — 1(х ). В противном случае переходят к следующему шагу метода, полагая й: = Й+ 1.
Рассмотренный алгоритм прост в реализации, но эффективен лишь в случаях, когда минимизируемая функция является сепарабсльноа, т.е. представляет собой сумму функций., каждая из которых зависит лишь от одной координаты: ~(х) = ~> Ьа(хз), х Е Б'.". э=1 В этом случае решение задачи минимизации можно получить за один шаг поиска. В самом деле, так как и а ~(х') = шш ~(х) = ~ шш 6, 1х ) = ~ 6,(х'), жеи", аз еи ~'.— 1 а=1 то достаточно на первом шаге поиска последовательно решить и задач одномерной минимизации функций Ьз (х,), у = 1, и, что позволит найти все и координат х* искомой точки х*. Для функций более общего вида может нарушаться даже условие релаксационности последовательности (х~), т.е.
1(х" 1) — 1(хь) ) 0 для некоторых номеров к. Поэтому обычно используют модификацию этого метода, состоящую в следующем. На каждом шаге при спуске по очередной координате х учитывают результаты, полученные на этом шаге для координат хб 1 = 1, ~ — 1. В этом случае значение о. находят из решеа ния задачи (6.11), в которой полагают ~р (о) = 11х „+ ае1), где 1-1 х, =х +~о~ген После перебора всех п координат вычисляют хь = х~ 1+ ссре„.
Рис. 6.14 иллюстрируют этапы покоординатного спуска для первых двух шагов метода в случае функции двух переменных. 284 6. ЛЛГОРИтьгЫ ПРЯМОГО ПОИСКЛ Рис. 6.16 Рис. 6.14 Пример 6.4. С помощью модифицированного метода циклического покоординатного спуска найдем решение задачи минимизации функции ,г(х~ яз): бхг, 4хгхз+ Зля~+ 4Л(глг + 2из) + 22 рассмотренной в примерах 6.1 и 6.2. В качестве начальной выберем точку ягз = ( — 2, 1), в которой г'(ягз) = 57, а в первом из условий (6.8) прекращения поиска положим сг = 0,01. На рис.
6.15 дана графическая иллюстрация первых двух шагов процесса поиска точки минимума и* = ( — ъ'5, — 2у'5) этой функции, а в табл. 6.3 приведены результаты вычислений (заметим, что ъ~5 2,2361). Из этих результатов видно, что при заданной точности поиска решение задачи получается за шесть шагов. гг- 285 б.5. Метод Хука — джинса Таблица 6.3 6.5.
Метод Хука — Джинса Эффективность прямого поиска точки минимума ограниченной снизу целевой функции можно повысить, если на каждом й-м таге поиска соответствующим образом выбирать направление спуска. Для этого на каждом а-м шаге выделяют предварительный этап исследующего поиска. Целью этого этапа является выбор направления спуска путем исследования поведения целевой функции 1(х) в окрестности точки х найденной на предыдущем шаге. В результате выполнения этапа исследующего поиска находится точка х, для которой 11х") ( 1'Сх~ ').
Направление спуска, завершающего Ь-й шаг поиска, определяется вектором х~ — х~ . Такая стратегия поиска, предложенная в 1961 году, получила название метода Хука Дживса'. Опишем один из алгоритмов исследующего поиска. Пусть т выбрана начальная точка х" и вектор Ь = (Ьс ...
Ь„), удовлетворяющий условию ~Ь| > е, где е > 0 заданный параметр точности исследующего поиска. Координаты вектора Ь, называемого аектпором перемещении, определяют приращения координат точки хо на этапе исследующего поиска. Полагаем к=о=1, х =х =х, 1 =1(х ) и переходим к основной части алгоритма исследующего поиска.
1. Вычисляем . = 11х" + Ь е1) и 1 . = 1(х". — Ь е ), Смл Визири М., Шепипи К. 286 6. АЛГОРИТМЫ ПРЯЫОГО ПОИСКА где ем ..., е„— стандартный базис в К', находим точку х, +!Ье, -л х' — бе, -ь хо' .<!. и ! <!„.; — я х,(, во всех остальных случзях, полагаем !" 1 — — !'(х", ) и переходим к п. 2. 2. Если ! < п, то принимаем 1: = ! + 1 и переходим к и. 1. В противном случае переходим к п. 3. 3. Е<ли х!„'., ~ х~, то переходим к п. 4. В противном случае уменьшаем длину вектора Ь, полагая Ь:= Ь/-!, где у ) 1- коэффиниенш дробления шага исследующего поиска, и., полагая ! = 1, х~~ = х~, ул = 1(х~), возвращаемся к и.1. 4. Если ~х„' 1 — х ~ < е, то дальнейший поиск точки минимума прекращаем, .полагая х* = х" 1 и Дх*) = 1(х~ ').
В противном случае полагаем я~+1 = хь+, и переходим на к-м шаге поиска к этапу спуска в направлении вектора х~+ — х~, имея при этом 1!х + ) < !(х ) < !(х ). На этапе спуска по формуле х =х +аь(х ~ — х ), (6.13) подбирзя так называемый ускоряющий мнолсигпель аь > О, находим такую точку х~., чтобы !1х~) < !'(х""~).
С увеличением аь увеличивается длина а~~х + — х ~ ~нага спуска в направлении вектора х~~' — х'1 Значение аь можно подобрать из условия минимума функции !1х) при смещении точки х в направлении этого вектора. Может оказаться, что аь е (О, Ц. После нахождения точки х~ переходим к следующему шагу поиска (к п. 1 этапа исследующего поиска), полагая !' = 1, х +' = о = хл ~' = хь ! ч' = 1 !х~) и затем Й: = Й+ 1.
1 В простейшем варианте метода Хука Джинса значение ая в (6.13) не подбирают, а задают постоянным, причем обычно полагают ая = 2. На рис. 6.16 иллюстрируются этапы исследу- 287 б.ац Лсетол Хука — Диивса Рис. 6.17 Рис. 6.16 ющего поиска и спуска для первых двух шагов поиска точки ж' минимума целевой функции двух переменных при 61 = пз = 2, 7 = 2 и начальной точке шо. Известно много модификаций метода Хука Дживса. Одна из модификаций связана с введением дополнительных правил выбора точки хь на каждом а-м шаге при проведении этапа исследующего поиска. Например, координаты этой точки можно выбирать, используя модифицированный мелос) циклического покоорг)инаьчноео спуска,*.
На рис. 6.17 иллюстрируется первый шаг поиска точки х* минимума целевой функции двух переменных с применением на этапе исследующего поиска модифицированного метода циклического покоординатного спуска, а на этапе спуска — процедуры подбора ускоряющего множителя ая = а~ ) 0 в формуле (6.13), исходя из условия минимума целевой функции в направлении вектора в Для определения точки т~ на й-м шаге при проведении этапа исследующего поиска можно также использовать процедуры случайного поиска'*. *Смл Базауа М., П1етти К. * Смл Василева Ф.П.
288 6. АЛГОРИТМ| ПРЯМОГО ПОИСКА Другой путь повышения эффективности поиска точки минимума функции состоит в выполнении на каждом шаге повторного этапа исследующего поиска'. В случае квадратич- 1 ной целевой функции ~(х) = — (|,1х, х) + (с, х) с положительно определенной матрицей Ч порядка п эта модификация метода Хука — Дживса позволяет получить точку минимума за один шаг, если на этапах исследующего поиска использовать модифицированный метод циклического покоординатного спуска, а выбор ускоряющего множителя на этапе спуска осуществлять исходя из условия минимума целевой функции в установленном направлении спуска. Пример 6.5. Используем метод Хука Дживса для минимизации функции из примера 6.1.
Выберем начальную точку хо = ( — 2, 1) и положим е = 0,01, ав = 2, | = 2. На рис. 6.18 представлена графическая иллюстрация процесса поиска точки минимума этой функции для различных начальных векторов Ь. Результаты поиска приведены в табл. 6.4. Таблииа 6.4 Из табл. 6.4 видно, что изменение начальной длины вектора Ь в два раза практически не повлияло на точность нахождения точки х" и значения |" (х*), но привело к уменьшению необходимого числа Х шагов поиска. При заданной на и1льной длине вектора Ь уменьшения необходимого числа Д| шагов поиска можно также достичь, изменив коэффициент дробления шага у > 1 на этапе исследующего поиска. Так, например, при Смв Летн В.В., Лиеввеч Ю.П.
290 6. АЛГОРИТМЫ ПРЯЫОГО ПОИСКА т Ь = (1, 1) (вариант а) наименьшее количество шагов Ю = 11 достигается при у = 5, в то время как при у = 4 и у = 20 имеем гав =12, а при у =10 имеем % =15. Рассмотрим некоторые модификации метода Хука — Джинса, позволяющие повысить эффективность поиска. В табл. 6.5 приведены результаты поиска, в котором на каждом Й-м шаге используется не постоянное значение ускоряющего множителя, равное двум, а переменное, выбираемое из условия минимума целевой функции в направлении вектора а + — х . Та,блица б.б Из табл. 6.5 видно, что рассмотренный способ выбора ускоряющего множителя позволяет уменьшить необходимое число Х шагов поиска.
На рис. 6.19 дана графическая иллюстрация первых двух шагов поиска точки минимума функции, в котором на этапе исследующего поиска использован модифицированный метод циклического покоординатного спуска, а ускоряющий множитель на этапе спуска выбирался двумя способами: в варианте а он постоянный и равен двум, а в варианте б он опредеяяется исходя из условия минимума целевой функции в направлении вектора т~ ~1 — т~. Соответствующие результаты приведены в табл. 6.6. Таблица б.б 292 а АлГОРитмы пРяыОГО пОискА Из табл. 6.6 видно, что рассмотренные варианты метода Хука — Дживса приводят к заметному уменьшению количества шагов поиска, практически не изменяя точности нахождения точки минимума и значения функции в этой точке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
