XIV Аттетков и др. Методы оптимизации (1081420), страница 40
Текст из файла (страница 40)
6.9, е иллюстрирует нахождение вершины ш„, ' в Б'. при 7 = 1,/2. йп-Цп-'с1 2 Если же ~(яйся/'" й1) ) /" (я/й:п+1), то новую вершину определяют по формуле й-~-1,п-~-1 й, / й,п-~-1 й1 7 ~ ~й,г + й,п-/-1 — *с ~ 71* *с/— и г=1 На рис.
6.9, е представлена процедура нахождения вершины х,~ ' в этом случае при 7 = 1/2. йй1, й1 6.3. Поиск при покеснпи нерегулярного симплекса 273 После сжатия симплекса вычисляют значение у(х,~ ' ) Я-~-1,п-е1 1с-Е1,пУ1 функции 11х) в найденной вершине х„, ' ' и сравнивают его со значением у(ха ""'). Если у'(х„~ '"~ ) ( у1хк " '1), то далее Я-Е1,п-~-1 используют симплекс Яьу1 с найденной вершиной х,„' и п вершинами х ' Е Яы г = 1, и, и переходят к этапу 1 при й:= 1+1. В противном случае этап сжатия не приводит к уменьшению значения функции в найденной вершине. Поэтому далее рассматривают симплекс Яь и переходят к этапу 4— редукции этого симплекса.
4. Редукция симплекса Яа состоит в уменыпении длин всех его ребер в 1/д раз., где д Е (0,1) - заданный ноэффициенп1 редукции. Вершины нового симплекса Яя 11 находят по формуле хь "= хкд+о1х~л — хвд), .г =2, п+1. Симплексы Яя и Я1ее1 до и после редукции при д = 1/2 изображены на рис. 6.9, д. После вычисления значений у(ха е1') функции у(х) в найденных вершинах х"У1', г = 2, и+1, переходят к этапу 1 при й: = и+ 1. Помимо описанных этапов периодически (после Х шагов поиска) следует проводить так называемую операцию восстпановления си нпленса. Она состоит в следующем: сохраняют две,.лучшиеи точки текущего симплекса я~, .расстояние между которыми принимают за длину ребра вновь генерируемого симплекса.
Это позволяет ликвидировать излишние деформации симплекса, накопившиеся за предшествующие Х шагов поиска. Рассмотренную схему алгоритма Нелдера — — Мида следует дополнить условием прекращения поиска. Выбор этого условия диктуют те же правила, что и в методах поиска при помощи регулярного симплекса (см. 6.2). Построение началыуого симплекса в методах поиска при по- моши нерегулярного симплекса проводят различными способами. Один из способов состоит в выборе в качестве на 1ального регулярного симплекса Я1, координаты вершин которого вычисляют при помощи (6.1) или (6.2). Другой способ заключается 274 6. АЛГОРИТМЫ ПРЯМОГО ПОИСКА в выборе некоторой базовой шочкп жв Е К", которую принимают за вершину ж начального симплекса ом а остальные п вершин находят по формуле а ' = ж +1е„г = 1, и, (6.7) где е, — векторы стандартного базиса в К"; 1 — заданное число.
Ясно, что в этом случае начальный симплекс Я~ будет нерегулярным (например, в Кз получим равнобедренный треугольник) . С теоретической точки зрения методы поиска при помощи нерегулярного симплекса изучены недостаточно полно, однако практические вычисления указывают на их работоспособность. В задачах безусловной минимизации рекомендуют выбирать а=1, ~3=2, у=1/2 или о=2, Д=5/2, у=1/4. Вопрос выбора оптимальных параметров для каждой конкретной целевой функции может быть решен после дополнительного исследования свойств метода с помощью вычислительного эксперимента. Пример 6.2.
Используя поиск при помощи нерегулярного симплекса, найдем решение задачи минимизации из примера 6.1. В качестве базовой возьмем точку вв = ( — 2, 1), а в условии (6.5) прекращения поиска положим с = 0,01. Выберем также коэффициенты отражения а = 1, растяжения Д = 2, сжатия у = 1/2 и редукции Б = 1/2. Результаты приведены в табл. 6.2, номер варианта соответствует способу построения начального симплекса ор 1 при помощи (6.1); 2 при помощи (6.7) с выбором базовой точки жв = тц1. Графическая иллюстрация процесса поиска в обоих вариантах для каждого из трех значений параметра 1 начальной длины ребра симплекса приведена на рис.
6.10 и 6.11 соответственно. Координаты точки ж* и значение ~(х*) функции (3.40) в этой точке, приведенные в табл. 6.2, найдены при помощи формулы (6.6) и соответствуют той вершине симплекса 5А на последнем, Х-м шаге поиска, в которой значение этой функции оказалось меньше, чем в других вершинах. 6.3. Поиск при помощи порог уллряого симплокса 275 Рис. 6.10 6.3. Поиск при помощи нерегусщряого симялекса 277 Таблица б'.2 Из табл. 6.2 видно, что на точность нахождения точки щ* и значения у" (ж*), как и на необходимое число Л шагов поиска влияют и значение параметра 1, и форма начального симплекса. Наилучшим при значении 1 = 2 является вариант 2, в котором заданная точность нахождения точки х* достигнута за ДУ = 14 шагов. Этот вариант далее принят в качестве базового при установлении влияния параметров алгоритма на необходимое число дс шагов поиска при помощи нерегулярного симплекса.
Вычислительный эксперимент показывает, что изменение коэффициентов отражения еу и растяжения 13 не приводит к значительному изменению необходимого числа шагов ДУ поиска. Так, например., увеличение о от 1 до 2 изменяет Л от 14 до 16, а увеличение ~3 от 1 до 3 приводит к изменению Х от 14 до 15. Наибольший интерес представляют результаты расчетов, иллюстрирующие влияние коэффициента сжатия 7 на процесс поиска (рис.
6.12). Расчет проведен при 1 = 2, о = 1, 13 = 3 и различных значениях бс а у = 1/4 (Х = 18); б у = 1/2 (Х = 15); о у = 3/4 (ДУ = 29). Из этих результатов видно, что оптимальным по числу шагов является вариант при у = = 1/2. Выбор других значений у приводит к избыточному числу шагов поиска., причем при О < у < 1/2 процесс поиска может сопровождаться вырождением симплекса.
6.3. Поиск при помощи нерегулярного симплекса 279 Результаты расчетов позволяют сравнить эффективность алгоритмов поиска при помощи регулярного и нерегулярного симплексов. Сравнение этих алгоритмов по необходимому числу Дс шагов поиска показывает (см. табл. 6.1 и 6.2), что в случае правильного выбора параметров алгоритма метод поиска с использованием нерегулярного симплекса более эффективен, чем метод поиска при помощи регулярного симплекса. В то же время неудачный выбор параметров алгоритма может привести не только к избыточному числу шагов поиска,. но и к преждевременному окончанию процесса поиска. ф Ситуации, которые приводят к преждевременному окончанию процесса поиска, наиболее типичны в тех случаях, когда целевая функция имеет овражную структуру.
Покажем это на конкретном примере. Пример 6.3. Используя поиск при помощи нерегулярного симплекса, найдем решение задачи минимизации ~(хм хз) = 10(х1, — хз) + (х1 — 1) — ~ гп1н. График функции ~(хм ха) и топография ее линий уровня показаны на рис. 6.8. Минимальное значение функции достигается в точке х* = (1, 1). В качестве начальной выберем точку хо = ( — 1, 1), а в условии (6.5) прекращения поиска положим е = 10 '~.
Графическая иллюстрация процесса поиска при коэффициентах отражения гл = 1, растяжения ~3 = 2, сжатия у = 1/2 и редукции д = 1/2 и различных значениях параметра 1 представлена на рис. 6. 13: а -" в случае 1 = 0,5; б —. в случае 1 = 0,75. Построение исходного симплекса Я1 с начальной длиной 1 ребра было проведено по формуле (6.2).
Точка х* и значение у'(х") приближенно вычислены на последнем, Дс-м шаге поиска в соответствии с формулой (6.6). Полученные результаты показывают, что при заданном значении е = 0,01 параметра точности поиска и начальной длине 1 = 0,5 ребра симплекса алгоритм приводит к минимуму целевой функции за Ж = 22 шагов (см. рис. 6.13, а), при этом х* (0.,990, 0,978), ~(х*) 2,10 10 ~. 281 6.4.
Циклический покоордииатиый спуск Для сравнения укажем, что при 1 = 1,0 поиск с помощью нерегулярного симплекса приводит к минимуму за Ат = 25 шагов, причем х' = (0,999, 1,005), Дх*) = 5,85 10 4. В то же время при 1 = 1,75 симплекс не в состоянии изменить свою форму так, чтобы, „вытянувшись" вдоль оврага, успешно продолжить поиск точки минимума (см. рис. 6.13, 6).
Поиск заканчивается за Ат = 14 шагов в точке х44 = (0,237, — 0,017)т в которой 1'(х44) = 0,635. Аналогичная ситуация наблюдается и в случае 1 = 0,4, причем преждевременное окончание поиска после Ат = 24 шагов приводит в точку хз" = (0,645, 0,404) со значением целевой функции ~(хэ4) = 0,127, К преждевременному окончанию процесса поиска. может приводить изменение других параметров алгоритма.
Например, это происходит при е = 0,01, 1 = 1,.0, если выбрать коэффициент сжатия у = 0,25. Поиск завершается за Х = 26 шагов в точке хзв = (0,671, 0,409) со значением целевой фукнкции ~(х~а) = 0 125 6.4. Циклический покоордииатный спуск Поиск точки х*, в которой функция Дх) достигает наименьшего значения, можно описать рекуррентным соотношением х =х +аьтт, ЙЕИ, (6.8) где х --. начальная шочко; 44 — единичный вектор, определяющий направление спуска на и-м шаге; тть ) 0 — длина шага спуска, т.е. расстояние в направлении вектора 44, отделяющее точку х~ т от новой точки ха.
Различные методы отличаются друг от друга способом выбора направления спуска и значения аы Поиск точки х* обычно прекращают при выполнении одного или обоих неравенств: ~х — х ~ = Оь ( ем ~~(х ) — 71х )~ ( ез, 169) где ет и ея --- заданные тьира иетпрти тонноспт ттотшкп. 282 6. ЛЛГОРИТЫЪ| ПРЯМОГО ПОИСИЛ В одном из алгоритмов прямого тщискц базирующихся на идее методов спуска, на каждом Й-м шаге поиска проводят одномерную минимизацию целевой функции последовательно по каждой из п координат ее аргумента х Е Й".
Такой метод называют обычно лтетподом циклического покоординатного спуска. Рассмотрим алгоритм этого метода. Пусть е.;, 1 = 1, и, — стандартный базис в К". Выберем начальную точку х~. Поиск точки минимума функции в методе циклического покоординатного спуска проводят в соответствии с рскуррснтным соотношением хз'=х +оз, ЪЕИ, |=1 и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
