Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Алгоритм 3. Пусть - некотораяисходнаяточкапоискавобласти D, изкоторой
осуществляетсяспусквточкулокальногоэкстремума созначением . Далееиз
точки двигаемсялибовслучайномнаправлении, либовнаправлении дотех
пор, покафункцияснованестанетубывать (выходимизобластипритяжения ).
Полученнаяточка принимаетсязаначалоследующегоспуска. Врезультатенаходим
новыйлокальныйэкстремум изначениефункции .
Если , точка забываетсяиееместозанимаетточка . Если
, товозвращаемсявточку идвижемсяизнеевновомслучайном
направлении.
0
1
x
∗
1
x
(
)
∗
1
xf
∗
1
x
0
1
1
x
x
−
∗
∗
1
x
0
2
x
∗
2
x
(
)
∗
2
xf
(
)
(
)
∗∗
<
12
xfxf
∗
1
x
∗
2
x
(
)
(
)
∗∗
≥
12
xfxf
∗
1
x
Процесспрекращается, еслинеудаетсянайтилучшийлокальныйминимумпосле
заданногочислапопытокили “случайного” направления, вкоторомфункцияснова
начинаетубывать.
Этотметодпозволяетнайтиглобальныйэкстремумвслучаемногосвязных
допустимыхобластей.
Алгоритм 4.
Вдопустимойобласти D разбрасываем m случайныхточекивыбираемизних
наилучшую, тоестьту, вкоторойзначениефункцииминимально. Извыбраннойточки
осуществляемлокальныйспуск. Адалеевокругтраекторииспускаобразуемзапретную
область. Воставшейсяобластислучайнымобразомразбрасываемновуюсовокупность
случайныхточек, иизлучшейточкиосуществляемспусквточкулокального
экстремума. Вокругновойтраекториитакжестроимзапретнуюобластьит.д.
Замечание: Комбинация случайного поиска с детерминированными методами
применяетсянетолькодлярешениямногоэкстремальныхзадач. Частоктакой
комбинацииприбегаютвситуациях, когдадетерминированныеметодысталкиваютсяс
темиилиинымитрудностями (застреваютнаднеузкогооврага, вседловойточкеит.д.).
Шагвслучайномнаправлениипоройпозволяетпреодолетьтакуютупиковуюситуацию
длядетерминированногоалгоритма.
Статистические методы поиска
Статистическиеметоды или методыслучайногопоиска получилидостаточно
широкое распространение при построении оптимальных решений в различных
приложениях. Этообъясняетсявпервуюочередьтем, чтосростомразмерностизадач
резкоснижаетсяэффективностьрегулярныхметодовпоиска (детерминиoрованных), так
называемое “проклятие размерности”. Во-вторых, зачастую информация об
оптимизируемомобъектеслишкоммаладлятого, чтобыможнобылоприменить
детерминированныеметоды. Статистическиеалгоритмычастоиспользуютприпоиске
оптимальногорешениявсистемахуправления, когдаоткликможнополучитьтолько
призаданииуправляющихвоздействий навходахсистемы. Втакихситуациях
статистические алгоритмы могут оказаться значительно эффективнее
детерминированных.
x
Статистическиеметодынаиболееэффективныприрешениизадачбольшой
размерностиилиприпоискеглобальногоэкстремума.
Подслучайнымиилистатистическимиметодамипоискабудемпониматьметоды,
использующиеэлементслучайностилибоосбореинформацииоцелевойфункциипри
пробныхшагах, либодляулучшениязначенийфункцииприрабочемшаге. Случайным
образомможетвыбиратьсянаправлениеспуска, длинашага, величинаштрафапри
нарушенииограничения.
Статистическиеалгоритмыобладаютрядомдостоинств:
• простотареализациииотладкипрограмм;
• надежностьипомехоустойчивость;
• универсальность;
• возможностьвведенияоперацийобучения;
• возможностьвведенияоперацийпрогнозированияоптимальнойточки.
Основными недостатками являются большое количество вычислений
минимизируемойфункции, медленнаясходимостьврайонеэкстремума.
Принятосчитать, чтопреимуществостатистическихметодовпроявляетсяс
ростомразмерностизадач, таккаквычислительныезатратывдетерминированных
методах поиска с ростом размерности растут быстрее, чем в статистических
алгоритмах.
Простой случайный поиск
Пустьнамнеобходиморешитьзадачуминимизациифункции приусловии, что
. Вэтойобластипоравномерномузаконувыбираемслучайнуюточку ивычисляемв
нейзначениефункции . Затемвыбираемтакимжеобразомслучайнуюточку и
вычисляем . Запоминаемминимальноеизэтихзначенийиточку, вкоторой
значение функции минимально. Далее генерируем новую точку. Делаем N
экспериментов, послечеголучшуюточкуберемвкачестверешениязадачи (вкоторой
функцияимеетминимальноезначение) средивсехслучайносгенерированных.
(
)
xf
[
]
BAx ,∈
1
x
(
)
1
1
xfy
=
2
x
(
)
2
2
xfy
=
Пусть n - размерностьвекторапеременных. Объем n-мерногопрямоугольника, в
которомведетсяпоискминимума, .
( )
∏
=
−=
n
i
ii
ABV
1
Еслинеобходимонайтирешениесточностью , , покаждойизпеременных,
томыдолжныпопастьвокрестностьоптимальнойточкисобъемом .
i
ε
ni ,1
=
∏
=
ε
ε=
n
i
i
V
1
Еслинеобходимонайтирешениесточностью , , покаждойизпеременных,
томыдолжныпопастьвокрестностьоптимальнойточкисобъемом .
Вероятностьпопаданиявэтуокрестностьприодномиспытанииравна .
Вероятностьнепопаданияравна . Испытаниянезависимы, поэтомувероятностьне
попаданияза N экспериментовравна . Вероятностьтого, чтомынайдемрешение
за N испытаний: . Нетруднополучитьоценкудлянеобходимогочислаиспытаний
N дляопределенияминимумастребуемойточностью:
Опираясьназаданнуюточность , , величину V , можноопределить и,
задаваясь вероятностью P, посмотреть, как меняется требуемое количество
экспериментов N взависимостиот и P (см. табл.).
i
ε
ni ,1
=
∏
=
ε
ε=
n
i
i
V
1
V
V
P
ε
ε
=
ε
−
P1
(
)
N
P
ε
−1
(
)
N
PP
ε
−−= 11
(
)
( )
ε
−
−
≥
P
P
N
1ln
1ln
i
ε
ni ,1
=
ε
P
ε
P
0.8 0.9 0.95 0.99 0.999
0.1 16 22 29 444 66
0.025 64 91 119 182 273
0.01 161 230 299 459 688
0.005 322 460 598 919 1379
0.001 1609 2302 2995 4603 6905
P
ε
P
Прирешенииэкстремальныхзадачнаобластяхсосложнойгеометриейобычно
этуобластьвписываютвn-мерныйпараллелепипед, вкоторомгенерируютслучайные
точкипоравномерномузакону, оставляятолькоте, которыепопадаютвдопустимую
область.
Различаютнаправленныйиненаправленныйслучайныйпоиск:
1. Ненаправленныйслучайныйпоиск. Всепоследующиеиспытанияпроводят
совершеннонезависимоотрезультатовпредыдущих. Сходимостьтакогопоискаочень
мала, ноимеетсяважноепреимущество: возможностьрешатьмногоэкстремальные
задачи (искатьглобальныйэкстремум). Примеромявляетсярассмотренныйпростой
случайныйпоиск.
2. Направленныйслучайныйпоиск. Вэтомслучаеотдельныеиспытаниясвязаны
междусобой. Результатыпроведенныхиспытанийиспользуютсядляформирования
последующих. Сходимостьтакихметодов, какправило, выше, носамиметодыобычно
приводятклокальнымэкстремумам.
Простейшие алгоритмы направленного случайного поиска
Алгоритмпарнойпробы.
Вданномалгоритмечеткоразделеныпробныйирабочийшаги. Пусть –
найденноена k-мшагенаименьшеезначениеминимизируемойфункции . По
равномерномузаконугенерируетсяслучайныйединичныйвектор ипообестороныот
исходнойточки делаютсядвепробы: проводимвычислениефункциивточках
, где g-величинапробногошага. Рабочийшагделаетсявнаправлении
наименьшего значения целевой функции. Очередное приближение определяется
соотношением .
k
x
(
)
xf
ξ
k
x
ξ⋅±= gxx
kk
2,1
(
)
)()(sign
1
ξ+−ξ−⋅ξ⋅+=∆+=
+
gxfgxfaxxxx
kkkkkk
Особенностью данного алгоритма является его повышенная тенденция к
“блужданию”. Даженайдяэкстремум, алгоритмуводитсистемувсторону.
Алгоритмнаилучшейпробы.
На k-мшагемыимеемточку .
Генерируется m случайныхединичныхвекторов . Делаютсяпробные
шагивнаправлениях ивточках вычисляются
значенияфункции. Выбираетсятотшаг, которыйприводиткнаибольшемууменьшению
функции: .
Ивданномнаправленииделаетсяшаг . Параметрможетопределяться
какрезультатминимизациипоопределенномунаправлениюиливыбираетсяпо
определенному закону. С увеличением числа проб выбранное направление
приближаетсякнаправлению .
Еслифункция близкаклинейной, тоестьвозможностьускоритьпоиск,
выбираявместеснаилучшейинаихудшуюпробу. Тогдарабочийшагможноделатьили
внаправлениинаилучшей, иливнаправлениипротивоположномнаихудшейпробе.
k
x
m
ξ
ξ
,...,
1
m
gg
ξ
⋅
ξ
⋅
...,,
1
m
kk
gxgx ξ⋅+ξ⋅+ ...,,
1
(
)
i
k
mi
gxf ξ⋅+=ξ
= ,1
*
minarg
∗
ξ⋅λ=∆
k
x
λ
(
)
xf
∇
−
(
)
xf
(
)
i
k
mi
gxf ξ⋅+=ξ
= ,1
*
minarg
Изисходногосостояния делается m независимыхпроб ивычисляются
соответствующиезначенияминимизируемойфункциивэтихточках. Длякаждойпробы
запоминаемприращенияфункции
Послеэтогоформируемвекторнуюсумму . Впределепри она
совпадаетснаправлениемградиентацелевойфункции.
При конечном m вектор представляет собой статистическую оценку
направления градиента. Рабочий шаг делается в направлении . Очередное
приближениеопределяетсясоотношением
.
k
x
m
gg
ξ
⋅
ξ
⋅
...,,
1
∑
=
∆⋅ξ=∆
m
j
jj
ff
1
∞
→
m
f
∆
f
∆
Метод статистического градиента.
(
)
(
)
k
j
k
j
xfgxff −ξ⋅+=∆
f
f
xx
kk
∆
∆
⋅λ−=
+1