XIV Аттетков и др. Методы оптимизации (1081420), страница 38
Текст из файла (страница 38)
Эффективность этого алгоритма можно повысить за счет использования информации о ранее вычисленных значениях функции, что позволяет уменьшить число рассматриваемых точек путем отбрасывания тех точек, в которых значения функции не существенны для выбора следующей базовой точки. Геометрически это соответствует процедуре построения вокруг базовой точки в качестве шаблона не и-мерного куба,. а конфигурации с меньшим количеством вершин, в которых вычисляют значения функции.
Реализация этой идеи привела к разработке методов симплексноео поиска, получивших к началу 1970-х годов широкое распространение. Симплекс (от латинского слова яш1р1ех .— простой) — это простейший выпуклый многогранник в 1я~ с и+ 1 вершинами (в К треугольник, в 2' тетраэдр). Каждую вершину этого многогранника называют вер1аикой сямплекса. Идея построения алгоритма симплексного поиска состоит в следующем: в вершинах симплскса вычисляют значения минимизируемой функции, наихудшую из вершин ..
ту, в которой значение функции наибольшее, — заменяют по определенному правилу новой вершиной, образуя тем самым новый симплекс. Затем эту процедуру повторяют. В одном из первых разработанных вариантов симплексного поиска был использован рееулярный симплекс., у которого все вершины равноудалены друг от друга (в К вЂ” равносторонний треугольник, в Ф " правильный тетраэдр). Дж. Нелдер и Р. Мид* в 1965 году впервые рассмотрели произвольный (нерегулярный) симплекс и предложили способ изменения скорости его движения путем расширения или сжатия симплекса в зависимости от того, удачно ли был выбран 1ааг поиска в направлении убывания функции или нет.
Позднее в исходные Смв Базара М., Швтта К. 259 6.2. Использование регулярного симялекса варианты методов симплексного поиска были введены различные способы изменения размеров и формы симплекса. Это привело к разработке метода управляемого прямого поиска, под которым понимают выбор по определенному правилу направления смещения центра используемой конфигурации и величины этого смещения, приводящего к убыванию значений функции в вершинах или центре симплекса. Метод, в котором в процессе поиска осуществляют управление изменением формы симплекса, обычно называют методом деформируемых конфигураций'. Изменение формы симплекса позволяет улу ппить процесс адаптации используемой конфигурации к рельефу графика минимизируемой функции.
6.2. Использование регулярного симплекса Сначала рассмотрим простейший алгоритм еимплексного поиска минимума ограниченной снизу целевой функции Дх), х б 1св, с использованием регулярного самплекса постоянных размеров. На первом шаге поиска строим регулярный симплекс с вериринами х1', 1 = 1, г1+1, который обозначаем я1. Построение симплекса можно провести различными способами. 1. Если хгд Е 51 заданная базовая точка, то координаты х,.л (1 = 2, и+1, 1 = 1, п) остальных и вершин х1л 6 Я1 регулярного симплекса Яь имеющего ребра длиной 1, можно вычислить по формулам*' ~/и+ 1 — 1 1 х' +, 1=2+ (6.1) 1,1 Ч7~-~-1+и — 1 з:' + пи2 где х, ', 1 =1, и.
координаты вершины х 1 Е Ь'1. Например, если в 22 выбрана базовая точка х11 = (О, 0), то при 1 = 2 *Сьс: Рмяоа А.С. Смс Реклейглис Г., Рейвиндран А., Рзесдел К. 260 6. АЛГОРИТМЫ ПРЯЪ|ОГО ПОИСКА остальные две вершины х и ж ' имеют координаты и,' цг = 1,932, яз' — — 0,518 и и1" — — 0,518, я2' — — 1,932. На рис. 6.2,а приведен построенный симплекс. Рис. 6.2 2. Если же е Н" заданная базовая точка, определяемая как центр регулярного симплекса Ям имекнцего ребра длиной 1, то координаты яс ' (и = 1, в+1, у = 1, и) всех вершин ж1з Е Я1 находят по формулам* у (г — 1; у =г — 1; (6.2) )/ 2Н+ Ц т, — 1, у ) г — 1, ~ г 21Н -~- Ц где хе, у = 1, п, координаты точки ж .
Например, если в йг2 задана точка же = (О, О) и 1 = 2, то вершинами правильного симплскса будут точки ж"' = ( — 1,000, — 0,578), ж'2 = = (1,000, — 0,578)., ж1з = (0,000, 1,.156). На рис. 6.2, б приведен построенный симплекс. Сми Даибриааииа А.П.
261 6.2. Использование регулярного сииплекса После построения симплекса Я1 на первом шаге поиска в вершинах х1" б Я1, 1 = 1, и+1г вычисляют значения минимизируемой функции. По результатам вычислений выбирают вершину, в которой значение функции является наиболыпим (пусть для определенности это будет вершина х1" е1; если таких вершин несколько, то может быть взята любая из них), и по формуле 2от1 2Х1 1пт1 '~ 1г 1о11 (6.3) и г.—.-1 НаХОдят тОЧКу Хя "+1г СИММЕтрИЧНуЮ ВЕРШИНЕ Х1"" ~ ОТНОСИ- тельно гиперплоскости, в которой лежат остальные вершины симплекса Я1.
Точка х,'. равноудалена от вершин х", 1 = 1, и, т.е. является центром регулярного симплекса с и вершинами, или, иначе говоря, центром масс системы материальных точек, расположенных в вершинах симплекса и имеющих одинаковую массу. Нахождение точки х~ в+~ нвзыва- оь, .з ют отпрахсением вергиины. В ре- х" зультате получают новый регуляр- 1 ный симплекс Язг образованный новой вершиной хя "+' и и вершинами Х ' 1 = 1г П ПРИНаДЛЕжаВШИМИ СИМплексу 51. На рис. 6.3 представлена процедура построения нового регу- Рис. 6.3 лярного симплекса в случае К .
На втором шаге поиска в новой вершине хял'+~ Е Я2 симплекса яз вычисляют значение 1(хант'), и если 1(х~ "~') < < ~(Х1 гг+1)г тО ОПИСаННуЮ ВЫШЕ ПрОцЕдуру ПОВтОряЮт. Прн построении алгоритма удобно на каждом 1с-м шаге поиска отражаемой вершине симплекса Яа присваивать номер и+ 1г т.е. обозначать ее халве~ Е Яь. НУмсРацию веРшин симплекса Яь назовем правильной, если выполнены неравенства ~(х ') « ... Дх ') « ...
у(х '*"''). 262 6. АЛГОРИТМЫ ПРЯМОГО ПОИСКА Если на й-м шаге после отражения вершины х" "Ы Е Яь в точку х~"'~'"~1 и вычисления значения ~(х~ "~ "+~) окажется, что у(хььь"+') > дх~"+'), то следует вернуться к симплексу Яы считая отражение вершины хь"+1 неудачным. После этого, предполагая нумерацию вершин симплекса Яь правильной, проводят отражение вершины хь'я Е я~, получают точку хь 1" и сравнивают значения ~(хь+1") и ~(х"'"+'). Если 1 (х ~ ") > ~(х "'~ ), то отражение и этой вершины считают неудачным и проводят отражение вершины х '" Е Яь и т.д. При фиксированной длине ребра симплекса поиск прекращают на шаге с номером Л, если отражения всех вершин симплекса ок оказались неудачными.
Тогда в ка тестве оценки искомого наименьшего значения у'„минимизируемой функции Дх) можно принять наименьшее из вычисленных значений 1(хк '), хК" Е ок, г' = 1, и+1. Полученной в процессе поиска конечной последовательности 1оь)к построенных симплексов Яы Й = 1, Х, соответствует невозрастающая конечная последовательность (~(х ))к минимизируемой функции. исследование свойств последовательности (дх~д ) ) к весьма затруднено.
Поэтому на практике вместо нее изучают свойства последовательности 1 Я значений ~ь = ~(х ) минимизируемой функции, каждое из которых вычислено в центре х симплекса Ягз к = 1, К. Процедуру поиска точки х* Е Ж", в которой функция 1(х) достигает наименьшего значения, в этом случае проводят в соответствии с рекуррентным соотношением хь ' = хь + оьрь, й = 1, К, где р — единичный и-мерный вектор, определяющий направление смещения центра симплекса на к-м шаге; оь > 0 смещение центра симплекса в направлении вектора р~ при переходе от х~ к х~+~. Геометрическая иллюстрация процедуры такого поиска в случае 1к представлена на рис.
6.4. Рассмотрим некоторые подходы к построению алгоритмов, позволяющих повысить эффективность процесса поиска при 6.2. Использование регулярного гииплекса Рис. 6.5 Рис. 6.4 помощи регулярного симплекса*. В общем случае управление процессом поиска можно осуществлять, выбирая как направление смещения центра симплекса, так и значение оы При этом выбор вектора р" из множества возможных направлений должен быть связан с определенным правилом, допускающим отражение сразу нескольких вершин симплекса, а изменение оь при выбранном векторе р" предполагает изменение длины ребра регулярного симплекса, при сохранении его формы.
На рис. 6.5 приведен пример построения регулярного симплекса в пространстве К по правилу., допускающему отражение всех тех вершин правильного треугольника, в которых значения минимизируемой функции больше, чем в центре треугольника. Если значения этой функции во всех вершинах симплекса превышалот ее значение в центре, то процесс поиска прекращают.
Иной путь построения эффективных алгоритмов связан с идеей изменения размера регулярного симплекса в процессе поиска. Введение правил такого изменения является одним из существенных элементов построения алгоритмов дправляельоео Сил Даиорярскис А.П., а также: Рьтое А.С. 264 6. ДЛГОРИтьтЫ ПРНМОГО ПОИСКЛ прямого поиски Это особенно важно в тех случаях, когда наименьшее значение функции 1(х) необходимо найти с высокой точностью. Действительно, чем меньше размер симплекса, тем точнее можно локализовать точку ж*, в которой эта функция достигает наименыпего значения.
При этом, однако, малый размер симплекса приводит к его замедленному смещению в направлении точки ж*, т.е. к росту числа шагов поиска, связанному с увеличением вычислительных затрат. Большой размер симплекса, наоборот, позволяет за каждый шаг поиска осуществлять большое смещение центра симплекса, но обеспечивает лишь грубую локализацик1 точки х". Поэтому возможность изменения размера симплекса наделяет алгоритм поиска высокими адаптивными свойствами. Выделим два основных подхода к построению алгоритма, предусматрива1ощего изменение размера симплекса в процессе поиска.
В первом из них это изменение происходит лишь при выполнении определенного условия, проверяемого на каждом шаге поиска, а во втором на каждом шаге поиска по заранее заданному закону. Простейшая схема алгоритма, построенного на основе первого подхода, такова. Пусть Яь С К" регулярный симплекс на к-м шаге поиска, имеющий правильную нумерацию вершин.
Процедура отыскания вершины х Е Яьь1 нового симплекса Яя+1, в Я.-'с!,п-1-1 которой функция у (х) имеет меньшее значение, чем в вершине х 'и+', включает два этапа отражение вершины х 'и+ Е яя и уменьшение размера симплекса Яя при сохранении его формы, называемое редукцией симп алекса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
