Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Обсудимэтотметод. Минимизируетсяфункциянезависимыхпеременныхс
использованием (n+1) вершинмногогранника. Вершина, вкоторойзначениецелевой
функциинаибольшее, проектируетсячерезцентртяжести остальныхвершин.
Улучшенныезначенияцелевойфункциинаходятсяпоследовательнойзаменойточки
снаибольшимзначениемнаболее "хорошие" точки, поканебудетнайденминимум.
Приэтоммногогранникможетвытягиватьсяилисжиматьсяповыбранному
направлению.
Пусть , является i-йвершинойнанекотором (k- м)
этапепоиска. Пустьтакже
т.е., вточке X
h
целеваяфункцияпринимаетнаибольшее, авточке X
l
наименьшеезначениесредиточекмногогранника.
Таккакмногогранниксостоитиз (n+1) точек, тоцентртяжестивсехвершин,
кроме X
h
, обозначимчерез X
n+2
. Координатыцентратяжестиопределяютсяпо
формуле:
,j=1,…,n.
1,...,1,),...,,(
21
+==
Τ
nixxxX
i
n
iii
{
}
,)(),...,(),(max)(
121
+
=
nh
XfXfXfXf
{
}
,)(),...,(),(min)(
121
+
=
nl
XfXfXfXf
−
=
∑
+
=
+ h
j
n
j
i
j
n
j
xx
n
x
1
1
1
1
Начальныймногогранниквыбираетсяобычноввидерегулярногосимплекса (но
этонеобязательно) сточкой№1вкачественачалакоординат. Началокоординат
можетбытьтакжепомещеновцентретяжестимногогранника.
Опишемоперации, изкоторыхсостоиталгоритм.
1. Отражение - проектирование X
h
черезцентртяжестиоставшихсявершинв
соответствииссоотношением
X
n+3
=X
n+2
+ α⋅(X
n+2
-X
h
),
где α≥1-коэффициентотражения.
2. Растяжение.
Если f(X
n+3
) ≤ f(X
l
), товектор (X
n+3
-X
n+2
) растягиваетсявсоответствиис
соотношением
X
n+4
=X
n+2
+ γ⋅(X
n+3
-X
n+2
),
где γ >1-коэффициентрастяжения.
Если f(X
n+4
)<f(X
l
), то X
h
заменяетсяна X
n+1
ипроцедурапродолжаетсясновас
операции 1.
Впротивномслучае X
h
заменяетсяна X
n+3
итакжеосуществляетсяпереходк
операции 1.
3. Сжатие.
Если
f(X
n+3
)
>
f(X
i
)
для
всех
i
≠
h,
то
вектор
(X
h
-
X
n+2
)
сжимается
в
4. Редукция.
Если f(X
n+3
)>f(X
h
), товсевекторы (X
i
-X
l
)уменьшаютсявдваразасотсчетом
от X
l
всоответствиисформулой
X
i
=X
l
+0,5⋅(X
i
-X
l
),i=1,...,n+1.
Затем - возвраткоперации 1 дляпродолженияпоисканаследующемшаге.
Еслиниоднаизопераций (растяжение, сжатие, редукция) невыполняется, то
происходитследующееотражение.
Критерийостанова (окончанияпоиска), предложенныйНелдеромиМидом,
следующий:
где ε - произвольноемалоечисло,X
n+2
- центртяжестимногогранниканаданном
шаге.
Деформируемый многогранник в противоположность жесткому симплексу
адаптируется
к
топографии
целевой
функции,
вытягиваясь
вдоль
длинных
наклонных
[ ]
,)()(
1
1
2
1
1
1
2
2
ε≤
−
+
∑
+
=
+
n
i
ni
XfXf
n
Обсудимвыборкоэффициентов α, β, γ. Послетого, какдеформируемый
многогранник подходящим образом промасштабирован, его размеры должны
поддерживатьсянеизменными, покаизменениявтопологиизадачинетребуют
применениямногогранникадругойформы. Этоможнореализоватьтолькопри α=1.
Былопоказано, чтопри α<1 требуетсябольшееколичествовычислений целевой
функции. Если α>>1, тоэтозатрудняетадаптациюмногогранникаприизменениях
направленияпоискаизамедляетсходимостьвокрестностиминимума (мешает
уменьшать размеры многогранника). Таким образом, α=1 выбирается как
компромисс.
Чтобывыяснить, какоевлияниенапоискимеетвыбор β и γ, былипроведены
решениятестовыхзадач. Оказалось, чтовлияние β наэффективностьпоискаболее
заметно, чемвлияние γ. При 0<β<0,4 существуетвозможность, чтоиз-засжатия
многогранникабудетиметьместопреждевременноеокончаниепроцесса. При β>0,6
можетпотребоватьсяизбыточноечислошаговибольшемашинноговременидля
достиженияокончательногозначения. Дляпрактическихнуждбылирекомендованы
следующиезначениякоэффициентов:
α =1,
0,4 ≤β≤0,6,
2,8 ≤γ≤3,0.
Подчеркнем чисто рекомендательный характер этих значений.
Какиувсякогодругогометода, получившегоширокоепризнание, уметода
Нелдера-Мидаимеетсямногомодификаций. Наиболеесущественнойявляется
модификация, прикоторойпосленормальнойостановкиалгоритмавыполняется
попыткапостроитьновыйстартовыйсимплекс. Дляэтойцеливыполняются
маленькиепробныешагивкаждомнаправленииосейкоординат. Еслихотябыодин
изэтихшаговоказываетсяуспешным, топоисквыполняетсяснова, носимплекс
имеетсторонызначительноменьшейдлины. Этотрестартрекомендуетсясамой
процедуройпоиска, т.к.(вособенностидлябольшогочислапеременных) симплекс
обычноимееттенденциютерятьобъем (размерностьсимплексастановитсяменьше
размерностипространства), т.е. симплексстягиваетсявточкубездостижения
реальногоминимума.
Другоймодификациейявляетсярекомендацияподстраиватькоэффициенты
растяженияисжатиявзависимостиоттого, имеллиместоуспехпривыполнении
этойоперацииилибыланеудача.
Для задач с небольшим числом переменных метод деформируемого
многогранникаизвестенкакнадежныйиробастныйметод, который, однако,
являетсяиотносительнодорогостоящим. Дляработыалгоритманеобходимохранить
n+1 векторов, аоперацияотображениятребуетпорядка n
2
операций. НелдериМид
эмпирическиобосновалиутверждение, чтосростомразмерности n количество
обращенийкцелевойфункциирастетпримернокак n
2.11
, однакоэтообоснование
проведенонаразмерностименьшедесятииврядлибудетвсиледлямногобольшего
числа
переменных
.
Методы прямого случайного поиска (СП)
Прямойслучайныйпоиск
Послетого, какзадананачальнаяточка, строитсяслучайнаятраекториядля
последовательностишагов, каждыйизкоторыхпроводитсявнаправленииот
некоторойточки, гдефункцияминимальнанаданномэтапе, доследующейточки,
соответствующейещеболеенизкомузначениюфункции.
Начинаяиз X0, следующаяслучайнаяточкаполучаетсяпоправилу:
,
где:
λ
k
- величинашага (скаляр), которыйувеличиваетсяпослеуспешногошагаи
уменьшаетсяпосленеудачного,
Z
k
- вектор "предыстории", указывающийсреднеенаправлениепоискана
предыдущихшагах:Z
k+1
= γ⋅Z
k
+(1- γ)⋅(X
k+1
-X
k
)⋅S,
β-коэффициентпредыстории (0<β<1), заменяемыйвпроцессепоиска,
R
k
- единичный случайный вектор, компоненты которого распределены
нормально, реализуемыйдатчикомпсевдослучайныхчисел,
γ
-
постоянный
весовой
множитель,
−++=
+ k
k
k
kkk
R
Z
Z
XX )1(
1
ββλ
Вектор X
k+1
будетпринятилиотвергнутвзависимостиоттого, выполняетсяили
нетсоотношение f(X
k+1
)<f(X
k
). Послетогокак X
k+1
принят (отвергнут), λ
k
увеличивают (илиуменьшают) спомощьюмножителя, зависящегооттого, былли
поисктруднымилилегким.
ТестированиеалгоритмапрямогоСПпоказывает, чтовобщемслучаеонменее
эффективен, чемрегулярныеалгоритмы.
Случайныйпоискнагиперсферe
Начальнаяточка X
0
выбираетсявкачествецентра n-мернойгиперсферы. Наэтой
гиперсфереслучайнымобразомвыбираютсянесколькоточек, вычисляетсязначение
функциивнихиотмечаетсялучшаясрединих . Затемпроводитсярегулярный
одномерныйпоисквдольпрямой, соединяющей X
0
и , иопределяетсяточкас
минимальнымзначениемфункции.
Послеэтогопроцедураповторяетсяизновогоцентрагиперсферы - точки X
1
.
Радиусгиперсферыможноизменять. Поискможетбытьускорен, еслиточкина
гиперсферевыбираютсяслучайно, носограничением, чтобыонинеотклонялись
более, чемнанекоторыйвыбранный уголдруготдругаиотпредыдущего
направленияпоиска. Другаямодификация - использованиеэллипсоидавместосферы.
Существует множество алгоритмов СП, отличающихся друг от друга
соотношением
случайности
и
регулярности,
способом
выбора
случайного
)
×
0
)
×
0
Завершая раздел, посвященный методам прямого поиска, подчеркнем их
достоинстваинедостатки.
Достоинства: простотапрограммирования, простотаподготовительногоэтапа,
универсальность, устойчивостькошибкамсчета.
Недостатки: весьмасомнительныеилиотсутствующиегарантиисходимостик
решению, большоеколичествотребующихнастройкипараметров, откоторыхзависит
успехрешения, экспоненциальный (обычно) ростобъемавычисленийвзависимости
отразмерности.
Общая рекомендация об использовании прямого поиска, выработанная
многолетнимопытом, можетбытьсформулированаследующимобразом: используйте
прямойпоисктольковкрайнемслучае, когдатвердоубедитесь, чтоникакойдругой
методнеможетбытьприменен, иначевампридетсядорогозаплатитьзавашуошибку
ввыбореметода, таккакэтоприведеткчрезмернымзатратамприотсутствиикаких-
либогарантий, чтобудетнайденодействительноерешение.
Оправданиемсуществованиюиприменениюметодовпрямогопоискаслужиттот
факт, чтоприрешенииреальныхзадачслишкомчастоникакойдругойметодине
может
быть
применен
.
Метод сопряженных направлений Пауэлла (метод переменной метрики)
В 1962 годуК.Смитпредложил, аМ.Пауэллв1965 г. усовершенствовал
процедурупоисковойоптимизации, использующуютакназываемыесопряженные
направления [4].
Определение 1.6. Система n линейнонезависимыхнаправлений 1, 2,…, n
называетсясопряженнойпоотношениюкположительноопределеннойматрице Q,
если i
T
⋅Q⋅ j =0, ∀ i ≠ j.
Понятиесопряженностианалогичнопонятиюортогональности. Чтобыпонять
это, надовыбрать Q = E (единичнаяматрица). Тогдадлясопряженныхнаправлений
получим i
T
⋅ j =0,i≠j.
Сопряженностьобычноинтерпретируюткакортогональностьвпространствес
преобразованнымикоординатами, гдевкачественовыхкоординатныхнаправлений
выбранысобственныевекторыматрицы Q.
Вметодахоптимизациивкачестве Q выбираютгессиан - матрицувторых
производных, котораяположительноопределена, еслифункцияцеливыпуклая. В
такомслучаепереходксопряженнымнаправлениямгеометрическиозначаетвыбор
новыхнаправленийкоординат, которыебольшесоответствуюттопологииповерхности
функции
(направления
поиска
вытягиваются
вдоль
главных
осей
квадратичной
S
S
S
S
S
S
S
АлгоритмПауэлла, приведенныйвэтомпараграфе, можетбытьотнесенк
методамнулевогопорядка, т.к. неиспользуетпроизводныхвявномвиде, ноонже
можетбытьотнесеникградиентнымалгоритмам, т.к. неявноформируетоценку
матрицыГессеииспользуетинформациюоповедениипроизводных. Болеетого, как
методквадратичнойаппроксимациицелевойфункции, онможетдажерассматриваться
какметодНьютоновскоготипа. Такоепромежуточноеположениеметодасопряженных
направленийипобудилоизложитьеговотдельномпараграфе, неотносяметодник
прямомупоиску, никградиентнымалгоритмам.
Утверждение 1.1. Еслииспользуютсясопряженныенаправления, толюбая
квадратичная функция n переменных, имеющая минимум, может быть
минимизированаза n шагов, поодномувкаждомизсопряженныхнаправлений.
Порядокиспользованиясопряженныхнаправленийнеимеетзначения.
Таккакметодыпрямогопоисканеиспользуютпроизводные, томатрицаГессене
известна и нужно другое правило определения подходящих сопряженных
направлений.
Теорема 1.2. Еслиприначальнойточке X
0
поискавнаправлении минимум f(X)
находитсявнекоторойточке X
a
иеслиприначальнойточкепоиска X
1
≠ X
0
втомже
самомнаправлении минимум f(x) находитсявточке X
b
, топри f(X
b
)<f(X
a
)
направление X
b
-X
a
сопряженоснаправлением поотношениюкматрицеГессе
функции f.
S
S
S