Моделювання процесу в шару каталiзатора. 4 страница

6. Аналогічно п.3 будується новий симплекс S₁₁, S₂₀, S₃₁, тобто

виключається вершина S₃₀, що мала найбільше значення цільової функції і т.д.

У результаті застосування розглянутої процедури виключення вершин симплексів з найбільшим значенням цільової функції процес пошуку сходиться до мінімального значення R(U₁,U₂). При виникненні зациклення в околицях крапки екстремуму необхідно зменшувати розміри симплекса.

Критерієм закінчення пошуку можуть служити розміри симплекса. Наприклад, якщо всі ребра симплекса стануть менше δ, те пошук можна припиняти.

Розглянемо алгоритм симплексного методу для задач довільної розмірності.

Нехай вершинам вихідного симплекса S_i (i=1,2,...,n+1) відповідають координати

U⁽ⁱ⁾ =(U⁽ⁱ⁾₁,U⁽ⁱ⁾₂ ,..., U⁽ⁱ⁾_n), (i=1,2,...,n+1). І нехай найбільше значення цільової функції відповідає вершині S_j. Визначимо координати вершини Ŝ_j нового симплекса.

Вершина Ŝ_j розташовується симетрично вершині S_j щодо середини грані, що знаходиться проти вершини S_j. Координати центра цієї грані U⁽ⁱ⁾ визначаються по формулі: (5.62) причому підсумовування ведеться тільки по тим векторам U⁽ⁱ⁾, що відповідають вершинам S_i, що утворюють цю грань. Вектор, що характеризує відстань від вершини S_j до центра грані, яка розташована проти цієї вершини, буде:

(5.63)

Координати вершини S_j визначаються по формулі

(5.64)

Підставивши в (5.64) вираження для U з (5.62), одержимо:

(5.65)

Формула (5.65) визначає координати вершини S_j нового симплекса.

При необхідності зменшити розміри симплекса (у випадку зациклення в околиці крапки оптимуму) замість формули (5.63) можна користатися наступним вираженням:

(5.66)

Найбільше ефективно симплексний метод сходиться при використанні правильних симплексів - рівностороннього чи трикутника тетраедра, утвореного рівносторонніми трикутниками. У цьому випадку напрямок пошуку збігається з напрямком градієнта (якщо симплекс досить малий).

Симплексний метод володіє ще одним важливим достоїнством - при збільшенні розмірності задачі обчислювальні витрати зростають незначно, тому що на кожнім кроці вважається тільки одне значення цільової функції.

5.7.8. Метод Нелдера-Мида

Метод Нелдера-Мида є розвитком симплексного методу Спендли, Хекста і Химсворта. Ідея методу складається в порівнянні значень функції в n+1 вершинах симплекса і переміщенні симплекса в напрямку оптимальної крапки за допомогою ітераційної процедури.

У даному методі симплекс переміщається за допомогою трьох операцій: відображення, розтягання і стиски. Зміст цих операцій стане зрозумілим при розгляді кроків процедури.

А. Знайдемо значення функції у вершинах симплекса.

f₁ = f(x₁); f₂=f(x₂);.....f_n+1=f(x_n+1)

Б. Серед обчислених значень знайдемо найбільше значення функції f_max, що випливає за найбільшим значенням функції f_cp, найменше значення функції f_min і відповідні їм крапки X_max, X_cp, і X_min.

В. Знайдемо центр ваги всіх крапок, за винятком крапки X_max (тобто середину грані, яка розташована проти крапки X_max).

Обчислимо f(X_O)=f.

Г. Зручніше за все почати переміщення від крапки Х_max. Відбивши крапку Х_max щодо крапки Х_о, одержимо крапку Х_r і знайдемо f(Х_r) = f. Якщо α - коефіцієнт відображення, то положення крапки X_r визначається в такий спосіб:

Х_r - Х_о = α.(Х_о - Х_max)

чи

Х_r = (1 + α) Х_о - α.Х_max,

де α = │ Х_r - Х_о│∕│ Х_о - Х_max│

Д. Порівняємо значення функцій f і f_min.

1. Якщо f < f_min, то в знайденій крапці одержали найменше значення функції. Напрямок із крапки Х_о в крапку Х_r найбільше доцільно для переміщення. Тому, ми робимо розтягання в цьому напрямку і знаходимо крапку Х_e і значення функції f = f(X_e). Коефіцієнт розтягання γ > 1 можна знайти з наступних співвідношень:

X_e - X_o = γ (X_r - X_o),

тобто

X_e = γ. X_r + (1 - γ) X_o,

де γ = │X_e - X_o│ / │X_r - X_o│.

а) Якщо f < f_min, те заміняємо крапку X_max на крапку X_E і перевіряємо (n + 1)- ую крапку симплекса на збіжність до мінімуму (див. крок 3). Якщо збіжність досягнута, то процес зупиняється; у противному випадку повертаємося на крок Б.

б) Якщо f > f_min, те відкидаємо крапку X_E. Очевидно, ми перемістилися занадто далеко від крапки X_o до крапки X_r. Тому варто замінити крапку X_max на крапку X_r, у якій було отримане поліпшення (крок Д, 1), перевірити збіжність і, якщо вона не досягнута, повернутися на крок В.

2. Якщо f > f_min, але f ≤ f_cp, те X_r є кращою крапкою в порівнянні з іншими двома крапками симплекса і ми заміняємо крапку X_max на крапку X_r і, якщо збіжність не досягнута, повертаємося на крок Б.

3. Якщо f > f_min, і f > f_cp, то перейдемо на крок Е.

Е. Порівняємо значення функцій f і f_max.

1. Якщо f > f_max, то переходимо безпосередньо до кроку стиску Е,2.

Якщо f < f_max, то заміняємо крапку X_max на крапку X_r і значення функції f_max на значення функції f. Запам'ятовуємо значення

f > f_cp із кроку Д.2, приведеного вище. Потім переходимо на крок Е, 2.

2. Так як у цьому випадку f > f_max, тому ясно, що ми перемістилися занадто далеко від крапки X_max до крапки X_o. Спробуємо виправити це, знайшовши крапку X_c ( а потім f) c допомогою кроку стиску.

Якщо f > f_max, то відразу переходимо до кроку стиску і знаходимо крапку X_c зі співвідношення

X_c - X_o = β (X_max - X_o),

де (0 < β < 1) - коефіцієнт стиску.

Тоді

X_c = β. X_max + (1 - β) X_o.

Якщо f < f_max, то спочатку замінимо крапку X_max на крапку X_r, потім

зробимо стиск. Тоді крапку X_c знайдемо зі співвідношення

X_c - X_o = β (X_r - X_o),

тобто

X_c = β X_r + (1 - β) X_o (Рис. 4).

Ж. Порівняємо значення функцій f і f_max.

1.Якщо f < f_max, то заміняємо крапку X_max на X_c, і якщо збіжність не досягнута, то повертаємося на крок Б.

2.Якщо f > f_max, то очевидно, що всі наші спроби знайти значення менше f_max закінчилися невдачею, тому ми переходимо на крок З.

З. На цьому кроці ми зменшуємо розмірність симплекса розподілом навпіл відстані від кожної крапки симплекса до X_min - крапки визначальної найменше значення функції.

Таким чином, крапка X_i заміняється на крапку X_i + 1/2(X_i-X_min),

тобто заміняємо крапку X_i крапкою 1/2(X_i-X_min).

Потім обчислюємо f_i для i = 1,2,..., (n + 1), перевіряємо збіжність і, якщо вона не досягнута, повертаємося на крок В.

И. Перевірка збіжності заснована на тім, щоб стандартне відхилення (n + 1) -го значення функції було менше деякого заданого малого значення ε. У цьому випадку обчислюється

де .

Якщо σ < ε, те всі значення функції дуже близький друг до друга

і тому вони, можливо, лежать поблизу крапки мінімуму функції X_min. Тому такий критерій збіжності є розумним.

Коефіцієнти α, β і γ є відповідно коефіцієнтами відображення, стиски і розтягання. Автори рекомендують брати α=1; β = 0.5; γ = 2. Початковий симплекс вибирається довільно.

Дата добавления: 2014-11-29