XIV Аттетков и др. Методы оптимизации (1081420), страница 39
Текст из файла (страница 39)
1. Отражение вершины л~ и+~ Е Яь осуществляют в соответствии с формулой, аналогичной 16.3): 1,п с1 2 я п,п+1 '~ ' п,1 п.,пт1 16 4) 2 —, с и 1=-1 где в~в -- точка, равноудаленная от вершин ж"", г = 1, и. Затем вычисляют значение у"1х"~1 в+1) функции у(х) в найденной точке жя 265 6.2. Использование регулярного сииплекса 2.
Редукцию симплекса Яь проводят только при выполнении неравенства у (х~ е~ о е1) > у (х" о е1) . Нри этом длину всех ребер симплекса уменьшакзт в 1 гб рвз, где б Е (О, 1) — заданный коэффициент редукции., и находят вершины нового симплекса Яа е1 по формуле Хк,1+б(ХЬ,' Хк,1) 2 11+1 сжимая симплекс в 1ггб раз к вершине хко, в которой значение целевой функции меньше, чем в других вершинах симплекса. Затем осуществляк1т переход к этапу 1 при й: = Й+ 1. если же у(хк'е'о е1) ( у(хк "е1), то редукцию симплекса Бь не пРовоДЯт и Далее РассматРивагот симплекс Яя ы с новой вершиной хье'о г1 и ц вершинами х~', 1 = 1г пг симплекса Яы переходя к этапу 1 при Й: = Й+ 1.
Эту схему алгоритма следует дополнить условием прекращения поиска, зависящим от конкретной постановки задачи минимизации. Например, поиск можно вести до тех пор, пока длина ребер регулярного симплекса не станет меньше заранее выбранного значения или же не будет выполнено заданное число шагов. Одним из возможных условий прекращения поиска является выполнение неравенства (6.5) где е > 0 --. заданное достаточно малое число. Пример 6.1.
Используя поиск при помощи регулярного симплекса, найдем решение задачи минимизации функции 1 (х1гх2) = бх, — 4х1х2+ Зх~+ 4ъ~5(х1+ 2х2) + 22, рассмотренной в примере 3.18. Выберем базовую точку хо = = ( — 2, 1) и положим с = 0,01 в условии (6.5) прекращения поиска. На рис. 6.6 дана графическая иллюстрация процесса поиска при коэффициенте редукции б = 1/2 и трех значениях начальной длины 1 ребра симплексаг укаэанных в табл. 6.1. 267 6.2. Использование регулярного сииплекса Таблица 6.1 Построение исходного симплекса с начальным значением 1 было проведено по формулам (6.1) с выбором в качестве базовой точки х" = хв.
Приближения точки х' и значения 7'(х*) функции в этой точке, указанные в табл. 6.1, соответствуют той вершине симплекса Яи на последнем., Ж-м шаге поиска, в которой значение функции оказалось меньше, чем в других вершинах, т.е. (6.6) Увеличение значения 1 в 4 раза в данном случае не повлияло на точность нахождения точки х* и значения 7(х*),но привело к заметному снижению необходимого числа Х шагов поиска. ф Некоторые возможные варианты уменьшения размера симплекса по заданному закону при втором подхода к построению алгоритма поиска в случае Жа показаны на рис.
6.7. По-прежнему считаем, что нумерация вершин симплекса Яь на каждом й-м шаге поиска является правильной. В первом варианте (рис. 6.7., а) уменьшение размеров симплскса на каждом Й-м шаге поиска осуществляют относительно найденной отражением вершины х " б Яь (в данном случае и = 2). Ее считают неподвижной, а расстояния до остальных п вершин изменяют в раз.
Изменение параметра б(й) Е б(ь) 6(я — 1) е (О, Ц можно проводить, .например, по закону б(й) = е "~Я где р > О ---- заданный коэффициент. Этот закон обычно применяют в тех случаях, когда для достижения достаточно хорошего приближения к точке наименьшего значения х* необходимо 6. АЛГОРИТМЫ ПРЯМОГО ПОИСКА .в,я .ьв Рис. 6.7 значительное число шагов поиска. Возможны и другие варианты задания закона изменения параметра* б(й). Во втором варианте (рис. 6.7, б) неподвижной считают вершину х Е Яь симплекса Яь с наименьшим значением Дх ) функции ~(х) и изменяют в раз расстояния от нее 6(Ц 6(й — Ц до остальных п вершин. В третьем варианте (рис.
6.7, в) уменьшение размеров симплекса Яь на каждом Й-м шаге поиска осуществляют относительно центра хв этого симплекса. При этом центр симплекса считают неподвижным, а в раз 6(й) 6(в — Ц изменяют расстояния от центра х до всех вершин симплекса. Подробное смс Дамбриускас А.П. или Рыков А.С. 6.3. Поиск при помощи иерегуляриого симплекса 269 6.3. Поиск при помощи нерегулярного симплекса Стандартные симплексные процедуры безусловной минимизации, в которых используются регулярные симнлексы, эффективны лишь в тех случаях, когда топография поверхностей уровня ограниченной снизу целевой функции достаточно проста.
В противном случае эффективность применения симнленсноео поиска минимума функции значительно снижается. В частности, это характерно для функции, скорость убывания которой по одному или нескольким направлениям значительно больше, чем по остальным. О графике такой функции говорят, что он имеет овражную стРуктуРу. Примером функции, график которой обладает овражной структурой, является функция ~1х, ° ) = 1о(х — х ) + (ху — 1) с минимумом в точке х* = (1, 1).
Топография линий уровня 1(ху, хз) = С этой функции приведена на рис. 6.8. Препятствием для успешного поиска минимума 1(х) является в этом случае форма симплекса: регулярный симплекс нельзя изменить так, чтобы он „вытянулся" вдоль „оврага", а это не позволяет успешно продолжить поиск минимума. Естественной в этих Рис. 6.8 270 6.
АЛГОРИТМЫ ПРЯЫОГО ПОИСКА 1+ а —. и ь-ь цв-ь1 заданный коэ44ициент отражения; х~ = центр грани симплекса с вершинами х~', 1 = 1, и. где о>0 и ,ьз г=1 условиях выглядит идея деформирования симплекса в процессе поиска, т.е. изменения его формы и размера. Существует много вычислительных конструкций прямого п,оиска с деформируемыми симплексами, различающихся по способам изменения размеров и формы симплекса. Общим для всех них является то, что в качестве основной геометрической конфигурации на каждом шаге поиска, выступает симплекс.
Информацию о значениях 1(х) в вершинах еимплекса используют д.ля принятия решения о смещении в область меньших значений функции. Рассмотрим простейшую схему алгоритма прямого поиска по деформируемому симплексу конструкцию вычислительного алгоритма Нслдера Мида. Она предусматривает возможность отражения только одной вершины симплекса на каждом шаге поиска. Пусть Я, С Б'." ..
заданный произвольный симплекс на к-м шаге поиска, имеющий правильную нумерацию вершин. Процедура отыскания вершины вновь генерируемого симплекса Яь Ы, в которой функция имеет меньшее значение, чем в вершине х "в Е яы включает несколько этапов: отражение вершины хя о ~', изменение размера и формы симплекса, полученного в результате отражения этой вершины, путем растяжения или сжатия в направлении новой вершины в зависимости от того, удачным был шаг поиска в направлении убывания функции 7'1х) или нет, и редукция синплекеа ЯЬ в случае неудачного шага поиска. 1.
Отражение вершины хь "т' е Яь осуществляют в соответствии с формулой, аналогичной 16.3): 6.Х Поиск при помощи иерегукяриого еимплекса 271 В результате получают новый симплекс Яь е1, образованный новой вершиной щк е! пг! и п вершинами щк' Е Яь, !. = 1, и. На рис. 6.9, а представлена процедура построения нового симплекса в пространстве !яв при ег = 1. Ь+1и .а+!л !с+ ! ,1ся 1с.! -е /Ь+!.с! я'„" а+! а» си '- .!се! Рие.
6.9 В новой вершине вычисляют значение ~(жь е! сс~!) функции Дсп). ЕСЛИ 7" (ХЬ Е1гп е1) < 7" (спк 1), тО Шат ПОИСКа СЧИтаЮт удаЧ- ным: получен новый симплекс Яь е! с наименьшим значением Дщь ~~" ~~) функции 7 (ж) в новой вершине ха е~ о+~. При этом переходят к этапу 2 растяжения симплекса Яье !. При выполнении неравенства ~(а!си) > 7(св~ 1о+!) > 7'(щь') далее используют полученный симплекс яье! с новой вершиной щьа! "~! и и веРшинами х"а Е Яьс ! = 1, и, и пеРехоДЯт к этапУ 1 пРи Й: = Й+ 1.
Если же 7" (св~"! " "1) > ~(св" и) > 1" (св"*1), то переходят к этапу 3 сжатия симплекса Яя е!. 2. При выполнении неравенства 7" (щ"' "' сге!) < ~(щ":!) растяжение симплекса Яь е! осушествляют в соответствии с форму- 272 6. АЛГОРИТМЫ ПРЯЫОГО ПОИСКА лой й-~-1,п-~-1 й у( й-~-1,п-/-1 й) ' й,г + р йй1,пй1 1 — /3 — ". г=1 где // ) 1 — заданный /соэ44ициентп растпяженил. Геометрически это можно интерпретировать как увеличение длины вектора х/' ~1"' ~1 †.в," в /1 раз.
После растяжения вычисляют значение Д~ж, ' ' ) функции ~(ж) в найденной точке и, й-й/,п-й/ й-~-1,п-~-1 Если Дх„+ ' " ) ( ~(жй'), то далее рассматривают симй-/-1,п-/-1 плекс Яйй/ с вершиной ш, ' и и вершинами а Е Яй, г' = 1, и, й-1-1, п+! /г,г и переходят к этапу 1 при 1с:= 9+1.
На рис. 6.9, б построен симплекс Яйй/ в 1112 с применением операции растяжения при // = 2. При ~(т„~ '"с ) ) ~(жй 1) растянутый симплекс не используют, а далее рассматривают симплекс Яй 1 с вершиной х ~ и+ и и вершинами хй" Е Яй, г = 1, и,, и переходят к этапу 1 при й:= й+1. 3. Сжатие симплекса Яйй/ проводят различными способами в зависимости от результатов сравнения значений функции 1(х) в вершинах х" и' Е Яй и х +'"~' Е Яйй/. Если дюйм/:п "") ( ~(жй" "'), тО СжатИЕ ОеущеетняяЮт В СООтВЕтствии с формулой 1-~-1,п-~-1 й + / й-' 1,п+1 й1 7 г~ и й,г й+1,п-/-1 7~ п г=1 где 7 Е (О, 1) заданный /соэф9/ициентп сжатпил. Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
