Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Покоординатный спуск
Простейшимметодомпрямогопоискаявляетсяметодпокоординатногоспуска.
Изначальнойточки A производитсяпоискминимумавдольнаправленияоси x
1
и
определяетсяточка B, вкоторойкасательнаяклинииуровняпараллельнаоси x
1
.
Затемпроизводитсяпоискминимумаизточки B внаправленииоси x
2
иопределяется
точка C. Продолжаяспусквдольосей x
3
,x
4
,...,x
n
,затемсновавдоль x
1
,x
2
,...,x
n
,
приходимвточкуминимума. Дляпоискавдольнаправления x
i
, i =1,...,n,может
бытьиспользованлюбойизодномерныхметодов, рассмотренныхвпредыдущем
разделе.
Теоретическиметодпокоординатногоспускаэффективендляунимодальной
функции, нонапрактикеоноказываетсяслишкоммедленным. Методхорошоработает
нагладкихсепарабельныхфункцияхиособеннонаквадратичных, линииуровня
которыхпохожинаконцентрическиекруги, тоестьвслучаеэллипсоидовонидолжны
иметьглавныеосипримерноравнымиподлине. Методпритягателенсвоейпростотой
ибылисделанымногочисленныепопыткиулучшитьегосходимостьвобщемслучае,
которыенепривеликбольшимуспехам. Поэтомубылиразработаныболеесложные
методы, использующиебольшеинформациинаоснованииужеполученныхзначений
функции. Однойизтакихмодификацийпокоординатногоспускаявляетсяпоискпо
образцу, разрешающийшагиподиагоналикоординатнойплоскости.
Метод Хука-Дживса (поиск по образцу)
Этотметодвпервыепредложенв1960 г., ноивнастоящеевремяшироко
используетсянапрактике. ХукиДживспредложилилогическипростуюстратегию
поиска, использующуюаприорныесведенияивтожевремяотвергающуюустаревшую
информациюотносительнохарактераповеденияцелевойфункции. Поисксостоитиз
последовательности шагов исследующего поиска вокруг базисной точки, после
которого, вслучаеуспеха, следуетпоискпообразцу.
АлгоритмХука-Дживса
ШагА.Выбратьначальнуюбазиснуюточку B
1
ишагдлиной h
j
длякаждой
переменной x
j
,j=1,...,n.
ШагБ.Вычислить f(x) вбазиснойточке B
1
сцельюполучениясведенийо
локальномповедениифункции. Этисведениябудутиспользованыдлянахождения
подходящегонаправленияпоискапообразцу, спомощьюкоторогоможнонадеяться
достичьбольшегоубываниязначенийфункции. Информацияолокальномповедении
f(x) находитсяследующимобразом:
1. Вычисляетсязначениефункции f(x) вбазиснойточке B
1
.
2. Каждаяпеременнаяпоочередиизменяетсяприбавлениемдлинышага.
Вычисляются значения функции , где -единичный вектор в
направленииоси x
j
. Еслиэтоприводиткуменьшениюзначенияфункции, то B
1
заменяетсяна . Впротивномслучаевычисляетсязначение , если
значениефункцииуменьшилось, то B
1
заменяетсяна . Еслиниодиниз
проделанныхшаговнеприводиткуменьшениюзначенияфункции, тоточка B
1
остается
f
B
h
e
j j
(
)
1
+
e
j
B
h
e
j j1
+
f
B
h
e
j j
(
)
1
−
B
h
e
j j1
−
3. Если B
2
=B
1
, то есть уменьшение функции не было достигнуто, то
исследованиеповторяетсявокругтойжебазиснойточки B
1
, носуменьшенной
длинойшага (обычношагуменьшаетсявдесятьраз).
4. Если B
2
≠B
1
, топроизводитсяпоискпообразцу.
Шаг В. Припоискепообразцуиспользуетсяинформация, полученнаяв
процессе исследования, и минимизация функции совершается поиском в
направлении, заданномобразцом:
1. Разумнодвигатьсяизбазиснойточки B
2
внаправлении B
2
-B
1
, поскольку
поисквэтомнаправленииужепривелкуменьшениюзначенияфункции. Поэтому
вычислимфункциювточке P=B
1
+2⋅(B
2
-B
1
).
2. Провестиисследующийпоисквокругточки P.
3. Еслинаименьшеезначениенашаге B-2 меньшезначениявбазиснойточке B
2
,
тополучаютновуюбазиснуюточку B
3
ипереходяткшагу B-1. Впротивномслучае
непроводятпоискпообразцуизточки B
2
, апроводятисследующийпоисквточке
B
2
.
ШагГ.Завершитьэтотпроцесс, когдадлинышаговбудутуменьшеныдо
заданногозначения (точностьопределенияточкиминимума).
Достоинствомалгоритмаявляетсято, чтоегооперацииоченьпростыидажев
случаенепредвиденныхобстоятельствнеприводяткзапрещеннымарифметическим
операциям (типаделениянаноль). Ещеоднимдостоинствомявляетсято, что
алгоритмтребуеточеньмало (порядка n) памятикомпьютера. Поискпообразцу
ускоряетпродвижениеалгоритмаподнуоврага, ашагиисследующегопоиска
позволяютприблизительноопределитьнаправлениеградиента.
Недостаткомалгоритмаявляетсяограничениеисследующегопоискатолько
направлениямиосейкоординат, чтоможетпривестикпреждевременнойостановке
алгоритмаскольугоднодалекоотточкиминимума, еслинаправлениеоврага
окажетсянепараллельнымосямкоординат. Ещеодиннедостаток - большоечисло
вычисленийцелевойфункции.
Былиразработанымногиемодификацииметодапоискапообразцу, новсеони
неявляютсястольпопулярными, какоригинальныйалгоритм.
Метод вращающихся координат Розенброка
ИдеяРозенброка - устранитьограниченияпокоординатногопоискаи
методаХука-Дживсанавозможныеизмененияпеременных, которыевэтих
методахмоглиизменятьсятольковнаправлениях, параллельныхосям
координат. ВметодеРозенброкашагипоискамогутпроизводитьсявдоль
направленийкоординатныхосей, которыемогутвращатьсявпространстве.
Однаизосейустанавливаетсявнаправлении, котороепредставляется
наиболее удачным. Для этой цели накапливается опыт успешных и
неудачныхперемещенийвпроцессеоптимизациипримернотакже, какив
методеХука-Дживса. Остальныеосивыбираютсяортогональнопервой.
Первоначальноосивыбираютсясовпадающимисосямикоординат
пространстваоптимизации. Затемвдолькаждойизосейделаетсяшаг
определеннойдлины. Еслишагбылуспешен, тодлинашагаувеличивается
ипопыткаповторяетсядотехпор, поканепоследуетнеудача. Если
первоначальныйшагбылнеудачен, тодлинашагауменьшаетсяипопытка
повторятсядотехпор, поканебудетполученоулучшениефункции. Затем
координатные оси поворачиваются с помощью процедуры
ортогонализации. Такойпроцессповторяетсядотехпор, поканебудет
выполненоусловиеостанова. Например, улучшениезначенияфункции
станет малым или перемещение на нескольких шагах подряд будет
невелико.
Так же, как и поиск по образцу, метод Розенброка не требует
информацииопроизводных, новпроцессевращенияосейкоординат
отслеживаетположениеградиентафункции. Этопозволяетемудвигаться
вдольднаоврагаипреодолеватьповороты. Методтакженеиспользует
одномернуюоптимизациювдольвыбранныхосей. Этоделаетпроцедуру
весьмаустойчивой (робастной).
Однако имеется дополнительный недостаток - процедура
ортогонализацииоченьдорогостоитивсмыслеколичестваопераций,
производимыхссистемойкоординат, ивсмысленеобходимойпамяти,
которойтребуетсяужепорядка n
2
, ане n, каквметодеХука-Дживса. Это
значит, чтодажевслучаеотносительно “дешевой” целевойфункции
вычислительныезатратынаортогонализациюоказываютсязначительными
всравнениисобщимизатратами. Крометого, размерностьрешаемыхзадач
ограничиваетсятребуемымобъемомпамяти.
СуществуетнесколькомодификацийалгоритмаРозенброка, главнаяиз
которыхсостоитвотказеотпостояннойдлинышагаизамененапроцедуру
масштабированиядлинышагавзависимостиотуспешностипоискав
данномнаправлении.
Метод ортогонализации Дэвиса, Свана и Кампея
ДанныйметодпредставляетсобойкомбинациюидеиРозенброкао
вращающихсякоординатахиодномерныхметодовоптимизации.
Начиная из некоторой стартовой точки, выполняется одномерная
оптимизацияпоочередновнаправлениях, совпадающихсосямикоординат.
Послеэтоговыполняетсяодномернаяоптимизациявдольнаправления
суммарного перемещения на всех шагах. Затем выполняется
ортогонализация.
Еслихотябыодинизодномерныхпоисковбылнеудачным, тоновое
множествонаправленийнебудетболееотражатьполноепространство
оптимизации (системакоординатныхосейстановитсялинейно-зависимой).
Поэтомувпроцессортогонализациивключаютсятолькотеизстарых
направлений, перемещение по которым было больше некоторого
установленногоминимума. Остальныекоординатныевектораостаются
неизменными. Еслисуммарноеперемещениенаоднойитерацииоказалось
меньше,
чем
длина
шага
одномерного
поиска,
этот
шаг
уменьшается
в
10
После ортогонализации одно из новых направлений (первое)
совпадаетснаправлениемсуммарногоперемещениянаданнойитерации.
Этоинтерпретируетсякакпервыйодномерныйпоискнановойитерации.
Остаетсясделатьеще n-1 шаговвдольоставшихсякоординатныхосейи
одно вдоль направления суммарного перемещения. Итерации
продолжаютсядотехпор, покадлинавекторасуммарногоперемещенияна
однойитерациинеокажетсяменьше, чемзаранееопределенныйминимум.
Численныеэкспериментыпоказали, чтоданныйметодпревосходит
методыРозенброкаиХука-Дживсавслучае, когдацелеваяфункция
достаточногладкаяиимеетнеоченьмногопеременных. Вслучае, когда
числопеременныхвелико, дорогостоящиепроцессыортогонализациии
одномернойоптимизациисводятнанетвсепреимуществаалгоритма.
Отмеченытакжеслучаизигзагообразнойтраекторииалгоритмаподну
оврага, что, естественно, существенноснижаетуверенностьвтом, что
алгоритмработоспособенвовражныхситуациях.
Метод деформируемого многогранника Нелдера-Мида
В 1962 годуСпендли, ХекстиХимсвортпредложилиметодпоискапо
регулярному многограннику, разработанный ими в связи со статистическим
планированиемэксперимента. Этотметодполучилназваниесимплексного, т.к.
используеттакназываемые симплексы припостроениитраекториипоиска. Несмотря
насовпадениявназваниях, этотметоднеимеетникакогоотношенияксимплекс-
методулинейногопрограммирования. Обсудимосновныеидеиэтогометода.
Определение 1.5. Регулярным многогранником (симплексом) в n-мерном
пространственазываетсямножествоиз (n+1) равноудаленнойточки. Наплоскости
симплексомявляетсяравностороннийтреугольник, впространстве - правильный
тетраэдр.
Изаналитическойгеометрииизвестно, чтокоординатывершинрегулярного
симплексаопределяютсяследующейматрицейразмерности n×(n+1):
Здесьстолбцыестькоординатывершин, астрокидаютномеракоординат,t-
расстояниемеждувершинами.
При
n=
2
и
t=
1
получим
треугольник
с
координатами
:
=
1222
2212
2221
...0
......
...0
...0
dddd
dddd
dddd
D
)11(
2
)11(
2
2
1
−+=
−++=
n
n
t
d
nn
n
t
d
.
956,0259,00
259,0956,00
=D
Приоптимизацииэтимметодомцелеваяфункциявычисляетсявкаждойиз
вершинрегулярногосимплекса. Извершины, гдецелеваяфункциямаксимальна,
проводитсяпроектирующаяпрямаячерезцентртяжестисимплекса, затемвершинас
максимальнымзначениемфункцииотбрасываетсяистроитсяновыйотраженный
симплексизоставшихсяпрежнихточекиоднойновойточки, расположеннойна
проектирующейпрямойнанадлежащемрасстоянииотцентратяжести.
Продолжениеэтойпроцедуры, вкоторойкаждыйразотбрасываетсяточкас
максимальным значением целевой функции, а также использование правил
уменьшения размера многогранника позволяют осуществить поиск, в котором
величинашаганалюбомшагефиксирована, анаправлениепоискаможноменять
(производнаянеиспользуется).
Определенныетрудности, встречающиесяприиспользованииэтогометода, а
именноотсутствиеускоренияпоискав"хорошем" направленииитрудностипри
поискенаискривленных "оврагах" и "хребтах", привеликнеобходимостиулучшений.
В 1964 годуНелдериМидпредложилимодификацию, вкоторойсимплексможет
изменятьсвоюформу. Таккаквэтомслучаесимплекснебудетужерегулярным, метод
назвалипоискомподеформируемомумногограннику.