Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Привыбореоптимальногозначения , котороеминимизируетфункциювзаданном
направлении, мыполучаемстатистическийвариантметоданаискорейшегоспуска.
Существеннымпреимуществомпереддетерминированнымиалгоритмамизаключается
ввозможностипринятиярешенияонаправлениирабочегошагапри 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
Алгоритм 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 случайныхточекивыбираемизних
наилучшую, тоестьту, вкоторойзначениефункцииминимально. Извыбраннойточки
осуществляемлокальныйспуск. Адалеевокругтраекторииспускаобразуемзапретную
область. Воставшейсяобластислучайнымобразомразбрасываемновуюсовокупность
случайныхточек, иизлучшейточкиосуществляемспусквточкулокального
экстремума. Вокругновойтраекториитакжестроимзапретнуюобластьит.д.
Замечание: Комбинация случайного поиска с детерминированными методами
применяетсянетолькодлярешениямногоэкстремальныхзадач. Частоктакой
комбинацииприбегаютвситуациях, когдадетерминированныеметодысталкиваютсяс
темиилиинымитрудностями (застреваютнаднеузкогооврага, вседловойточкеит.д.).
Шагвслучайномнаправлениипоройпозволяетпреодолетьтакуютупиковуюситуацию
длядетерминированногоалгоритма.
РассмотримусловияКуна-Такеравнесколькодругомвиде.
Пустьимеемзадачуоптимизациисограничениямиввидеравенств:
z = f(x
1
, x
2
,…, x
n
) → min
приусловиях:
g
1
(x
1
, x
2
,...,x
n
)=0,
g
2
(x
1
, x
2
,...,x
n
)=0,
. . . .
g
n
(x
1
, x
2
,...,x
n
)=0.
Точкаусловногоминимумафункции f совпадаетсседловойточкойфункции
Лагранжа:
приэтомседловаяточкадолжнаобеспечиватьминимумпосвоимпеременным x
i
и
максимумпопеременным λj.
Необходимые условия стационарной точки - равенство нулю частных
производныхпервогопорядкаповсемпеременным:
,)()(),(
1
∑
=
+=
m
j
jj
XgXfXF λλ
.,1j ,0)(
),(
,,1 ,0
),(
1
mXg
XF
ni
x
g
x
f
x
XF
j
j
m
j
i
j
j
ii
===
==+=
Λ
∑
=
∂λ
λ∂
∂
∂
λ
∂
∂
∂
∂
Рассмотрим общую задачуматематическогопрограммирования:
Z=f(X) → min,
приусловиях:
g
i
(X) ≤ b
i
,(i=1,…,m).
Ограниченияввиденеравенствмогутбытьпреобразованывограниченияввиде
равенствдобавлениемккаждомуизних ослабляющих переменных
СформируемфункциюЛагранжа:
Тогданеобходимыеусловияминимумапринимаютвид:
)0(
22
≥
ii
uu
.0)( )(
22
=−+⇒=+
iiiiii
buXgbuXg
∑
=
−++=Λ
m
i
iiii
buXgXfUXF
1
2
).)(()(),,( λ
,,1 ,0)(
,,1 ,0
2
1
mibuXg
nj
x
g
x
f
iii
m
i
i
i
i
j
==−+
==+
∑
=
∂
∂
λ
∂
∂
.,1 ,02 miu
i
i
==⋅λ
Можнопоказать, что
,
где - коэффициентЛагранжавточкеминимума, f*-оптимальноезначение
функции.
Очевидно, чтопривозрастании b
i
допустимаяобластьрасширяется, аэтозначит,
чтоминимальноезначениеможеттолькоуменьшаться, тоестьпроизводнаядолжна
бытьотрицательной (неположительной). Следовательно, λ
i
≥ 0 вточкеусловного
минимума.
Окончательнополучаемнеобходимыеусловиядляусловного минимума:
Выражения
во
второй
строке
гарантируют,
что
оптимальная
точка
будет
*
*
i
i
b
f
λ
∂
∂
−=
*
i
λ
.m1,=i ,0
,,1 ,0))((
.,1 ,)(
,,1,0
1
≥
==−
=≤
==+
∑
=
i
iii
ii
m
i
i
i
i
j
mibXg
mibXg
nj
x
g
x
f
λ
λ
∂
∂
λ
∂
∂