Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Еслинеобходимонайтирешениесточностью , , покаждойизпеременных,
томыдолжныпопастьвокрестностьоптимальнойточкисобъемом .
Вероятностьпопаданиявэтуокрестностьприодномиспытанииравна .
Вероятностьнепопаданияравна . Испытаниянезависимы, поэтомувероятностьне
попаданияза 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
Привыбореоптимальногозначения , котороеминимизируетфункциювзаданном
направлении, мыполучаемстатистическийвариантметоданаискорейшегоспуска.
Существеннымпреимуществомпереддетерминированнымиалгоритмамизаключается
ввозможностипринятиярешенияонаправлениирабочегошагапри m<n. При m=n и
неслучайныхортогональныхрабочихшагах, направленныхвдольосейкоординат,
алгоритмвырождаетсявградиентныйметод.
λ
Алгоритм наилучшей пробы с направляющим гиперквадратом.
Внутридопустимойобласти строитсягиперквадрат. Вэтомгиперквадрате
случайнымобразомразбрасывается m точек , вкоторыхвычисляютсязначения
функции. Средипостроенныхточеквыбираемнаилучшую. Опираясьнаэтуточку,
строимновыйгиперквадрат. Точка, вкоторойдостигаетсяминимумфункциина k-м
этапе, беретсявкачествецентрановогогиперквадратана (k+1)-мэтапе.
m
xx ...,,
1
Координаты вершин гиперквадрата на (k+1)-м этапе определяются
соотношениями
, ,
где – наилучшаяточкавгиперквадратена k-мэтапе.
В новом гиперквадрате выполняем ту же последовательность действий,
случайнымобразомразбрасывая m точек, ит.д.
Такимобразом, на 1-мэтапекоординатыслучайныхточекудовлетворяют
неравенствам , и – точкасминимальнымзначением
целевойфункции.
В алгоритме собучением стороны гиперквадрата могут регулироваться в
соответствиисизменениемпараметра понекоторомуправилу. Вэтомслучае
координатывершингиперквадратана (k+1)-мэтапебудутопределятьсясоотношениями
, .
Хорошовыбранноеправилорегулировкистороныгиперквадратаприводитк
достаточноэффективномуалгоритмупоиска.
2
11
k
i
k
i
k
i
k
i
ab
xa
−
−=
++
2
11
k
i
k
i
k
i
k
i
ab
xb
−
+=
++
k
x
nibxa
iii
,1,
11
=≤≤
{
}
)(minarg
,1
1
j
mj
xfx
=
=
α
α
−
−=
++
2
11
k
i
k
i
k
i
k
i
ab
xa
α
−
+=
++
2
11
k
i
k
i
k
i
k
i
ab
xb
Алгоритмы глобального поиска
Случайный поиск приобретает решающее значение при оптимизации
многоэкстремальныхзадачиобъектов. Вобщемслучаерешениемногоэкстремальных
задачбезэлементаслучайностипрактическиневозможно.
Алгоритм 1.
Вдопустимойобласти D случайнымобразомвыбираютточку . Принявееза
исходную и используя некоторый детерминированный метод или алгоритм
направленногослучайногопоиска, осуществляетсяспусквточкулокальногоминимума
.
Затемвыбираетсяноваяслучайнаяточка ипотойжесхемеосуществляется
спусквточкулокальногоминимума ит.д.
D
x
∈
1
D
x
∈
∗
1
D
x
∈
2
D
x
∈
∗
2
Поискпрекращается, кактолькозаданноечислоразнеудаетсянайтиточку
локальногоэкстремумасозначениемфункции, меньшимпредыдущих.
Алгоритм 2.
Пустьполученанекотораяточкалокальногоэкстремума . Послеэтого
переходимкненаправленномуслучайномупоискудополученияточки такой, что
.
Източки спомощьюдетерминированногоалгоритмаилинаправленного
случайногопоискаполучаемточкулокальногоэкстремума , вкоторойзаведомо
выполняетсянеравенство .
Далееспомощьюслучайногопоискаопределяемновуюточку , длякоторой
справедливонеравенство , исноваспусквточкулокальногоэкстремума и
т.д.
Поискпрекращается, еслипригенерациинекоторогопредельногочислановых
случайныхточекнеудаетсянайтилучшей, чемпредыдущийлокальныйэкстремум,
которыйипринимаетсявкачестверешения.
D
x
∈
∗
1
2
x
(
)
(
)
∗
<
12
xfxf
2
x
∗
2
x
(
)
(
)
∗∗
<
12
xfxf
3
x
(
)
(
)
∗
<
23
xfxf
∗
3
x