ЛАБОРАТОРНА РОБОТА № 5. ДОСЛІДЖЕННЯ МЕТОДІВ ОДНОМІРНОГО ПОШУКУ
1 Мета роботи
Дослідження на ПЕОМ пошукових алгоритмів мінімізації функцій однієї змінної на базі методів виключення інтервалів.
2 Короткі теоретичні відомості
Більшість детермінованих алгоритмів мінімізації базуються на використанні ітераційної формули:
x(k+1) = x(k ) +λ(опk ) S (k ) |
k = 0,1,K |
(5.1) |
де S (k ) - напрям пошуку, λ(опk ) - довжина кроку у вибраному напрямку пошуку.
Постає питання, як визначити довжину кроку λ(опk ) ? Цю задачу можливо сформулювати, як задачу одномірної мінімізації виду:
min f (x(k ) +λ(k ) S (k ) ) |
(5.2) |
λ( k ) |
суть якої зводиться до пошуку такого значення λ(опk ) , при якому цільова функція f (x(k ) +λ(k ) S (k ) ) досягає свого мінімуму. В процесі вирішення задачі оптимізації того чи іншого виду результати розв’язку задачі (5.2) можуть бути використані багаторазово. Тому ефективність рішення задачі (5.2) значною мірою визначає ефективність процесу оптимізації в цілому.
32
Потрібно визначити, що у більшості випадків процес розв’язку задачі (5.2) складається з двох етапів:
- знаходження інтервалу невизначеності, тобто інтервалу [λkmin ,λkmax ], в
якому знаходиться λ(опk ) . - пошук λ(опk ) .
Хоча задачі одномірної оптимізації є найбільш простими з усіх типів екстремальних задач, однак їх наявність у багатьох більш складних алгоритмах, робіть доцільним вивчення методів їх розв’язку.
Фактично всі методи одномірного пошуку, які використовуються на практиці, засновані на припущенні, що досліджувана функція унімодальна в інтервалі пошуку. Для унімодальної функції f(x) порівняння значень функції в декількох різних точках інтервалу пошуку дозволяє визначити: у якому саме, із заданих підінтервалів, точка оптимуму відсутня. Пошук оптимуму полягає в послідовному виключенні підінтервалів і, отже,
зменшенні інтервалу пошуку. |
|
|
|
|
|||
|
|
Правило виключення інтервалів. |
|
|
|||
Нехай функція |
f (x) |
– унімодальна на замкнутому інтервалі a ≤ x ≤ b , |
|||||
а її мінімум |
досягається |
в точці x* та виконуються наступні |
умови: |
||||
значення f (x) |
в будь-якій точці інтервалу (a,b) |
менше за |
f (a) |
та f (b) . |
|||
Розглянемо точки |
x(1) і |
x(2) , розташовані |
в |
інтервалі |
таким |
чином |
|
a < x(1) < x(2) < b . |
|
|
|
|
|
|
|
Порівнюючи значення функції в точках |
x(1) і x(2) , можна зробити |
||||||
наступні висновки:
Якщо f (x(1) ) > f (x(2) ) , то точка мінімуму не лежить в інтервалі (a, x(1) ) ,
тобто x* (x(1) ,b) (рис. 5.1).
33
a |
b |
x(1) |
x(2) |
|
) |
Рисунок 5.1
Якщо f (x(1) ) < f (x(2) ) , то точка мінімуму не лежить в інтервалі (x(2) ,b) ,
тобто x* (a, x(2) ) , (рис. 5.2).
a |
b |
x(1) |
x(2) |
|
) |
Рисунок 5.2
Якщо f (x(1) ) = f (x(2) ) , то точка мінімуму не лежить в інтервалах
(a, x(1) ) і (x(2).b) і x* (x(1) , x(2) ) , (рис.5.3).
a |
b |
x(1) |
x(2) |
Рисунок 5.3
34
Методи пошуку, засновані на використанні правила виключення інтервалів, складаються з 2 етапів:
1)Знаходження інтервалу невизначеності (Лабораторна робота №6).
2)Зменшення інтервалу невизначеності до наперед встановленої величини.
Метод ділення інтервалу навпіл (метод дихотомії).
Метод дозволяє виключати половину інтервалу невизначеності на кожній ітерації. Іноді цей метод називають триточковим методом на рівних інтервалах, оскільки його реалізація заснована на виборі 3-х початкових точок, рівномірно розподілених в інтервалі пошуку.
Початковими даними є інтервал невизначеності (a,b) і похибка ε , з
якою потрібно визначити координати оптимуму. Пошук мінімуму функції f (x) методом дихотомії може бути реалізовано за допомогою наступного
алгоритму: |
|
|
|
|
|
|
|
|
|
|
1. |
Покласти |
x(m) = |
a +b |
і L = b − a . Обчислити f (x(m) ) . |
||||||
|
|
|||||||||
|
|
|
|
2 |
|
|
|
|
||
2. |
Покласти |
x(1) = a + |
|
L |
, |
x(2) = b − |
L |
. |
||
4 |
4 |
|||||||||
|
|
|
|
|
|
|
||||
Точки x(1) , x(m) і x(2) ділять інтервал (a,b) на 4 рівні частини.
Обчислити f (x(1) ), f (x(2) ) і f (x(m) ) .
3.Порівняти f (x(1) ) і f (x(m) ) .
Якщо f (x(1) ) < f (x(m) ) (рис. 5.4), виключити інтервал (x(m) ,b), поклавши b = x(m) . Середньою точкою інтервалу пошуку стає точка x(m) = x(1) . Перейти до п. 5.
35
a |
|
|
b |
||
|
|
|
|
|
|
|
|
x(1) |
x(m) |
x(2) |
|
|
|
|
|
) |
|
Рисунок 5.4
Якщо f (x(1) ) ≥ f (x(m) ) (рис. 5.5), перейти до п. 4.
|
|
a |
|
|
|
|
b |
|
|
|
|
|
|
x(1) |
x(m) |
x(2) |
|
|
|
|
|
|
Рисунок 5.5 |
|
|
|
4. Порівняти f (x(2) ) і |
f (x(m) ) . |
|
|
|
||||
Якщо |
f (x(2) ) < f (x(m) ) , |
виключити |
інтервал (a, x(m) ), поклавши |
|||||
a = xm (рис.5.6). Середньою точкою інтервалу пошуку стає точка х2, |
xm = x2 . |
|||||||
Перейти до п. 5. |
|
|
|
|
|
|||
Якщо |
f (x(2) ) ≥ f (x(m) ) |
(рис.5.), виключити інтервали (a, x(1) ) і |
(x(2) ,b), |
|||||
поклавши a = x(1) , b = x(2) , x(m) |
залишиться середньою точкою. |
|
||||||
36
a |
|
b |
x(1) |
x(m) |
x(2) |
|
|
) |
Рисунок 5.6
5. Обчислити L = b −a , якщо L ≤ε , закінчити пошук, інакше |
повернутися до п. 2.
На кожному кроці алгоритму дихотомії виключається половина інтервалу. Середня точка послідовно одержуваних інтервалів завжди співпадає з однієї з точок x(1) , x(m) , x(2) . Отже, на кожній ітерації (окрім
першої) потрібно не більше 2-х обчислень значень функції. Якщо проведено n ітерацій, то довжина одержаного інтервалу дорівнює 
довжини початкового інтервалу.
Метод Фібоначчі.
У методі Фібоначчі повинно бути заздалегідь визначено загальне число точок, в яких проводитимуться обчислення. Це число може бути визначено на підставі вимог точності.
Нехай початковий |
|
інтервал |
(a(0) ,b(0) ) |
|
після декількох |
кроків |
|||||||||
зменшився до |
(a(k ) ,b(k ) ). При цьому вибираються дві точки x1(0) і |
x2(0) , які |
|||||||||||||
визначаються наступними рівностями: |
|
|
|
|
|
||||||||||
x(0) |
= |
Fn−1−k |
(b |
− a |
) + a |
, |
x(0) |
= |
Fn−k |
(b |
−a |
) + a |
, |
k = 0(1)(n −1) |
|
|
|
|
|||||||||||||
1 |
|
Fn+1−k |
k |
k |
k |
|
2 |
|
Fn−k |
k |
k |
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
37
деFk - числа Фібоначчі, які можуть бути обчислені згідно
формулFk = Fk−1 + Fk−2 , F0 = F1 =1.
Якщо f (x1(k ) ) < f (x2(k ) ) (рис. 5.7) , то наступний інтервал невизначеності
(a(k+1) ,b(k+1) )= (a(k ) , x2(k ) ).
a(k) |
b(k) |
x(1) |
x(2) |
|
) |
Рисунок 5.7
Якщо f (x1(k ) ) > f (x2(k ) ) (рис. 5.8), то наступний інтервал невизначеності
(a(k+1) ,b(k+1) )= (x1(k ) ,b(k ) ).
a(k) |
b(k) |
x(1) |
x(2) |
Рисунок 5.8
Останні точки визначаються таким чином:
38
x1 |
= |
1 |
(b |
(n−1) |
−a |
(n−1) |
) + a |
(n−1) |
, |
x2 |
= |
|
+ξ (b |
(n−1) |
−a |
(n−1) |
) + a |
(n−1) |
, |
(n−1) |
|
|
|
|
|
(n−1) |
1 |
|
|
|
|
||||||||
|
|
2 |
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
де ξ - довільне мале позитивне число.
Одна з двох точок, в яких проводяться обчислення, завжди лежить усередині зменшеного інтервалу і служить однією з точок, в яких проводиться обчислення на наступній ітерації, таким чином, якщо не рахувати початкової ітерації, кожна ітерація вимагає тільки одну додаткову точку.
Величина останнього інтервалу дорівнює:
b(n) −a(n) = 21Fn (b(0) −a(0) ) +ξ .
Якщо узяти ξ = 0 і не додавати точки при обчисленні останнього інтервалу, то у вираз для останнього інтервалу замість 2Fn входитиме Fn+1 .
1 |
> |
1 |
для n ≥ 2 . |
|
F |
2F |
|||
|
|
|||
n+1 |
|
n |
|
Для того, щоб не вимагати попереднього визначення кількості точок, в яких буде оцінюватися функція, використовується метод "золотого перетину".
Метод "золотого перетину".
Пошук у методі "золотого перетину" базується на розподіленні інтервалу невизначеності на дві частини, яке відоме як "золотий перетин". При цьому відношення довжини всього інтервалу до більшої частини
39
дорівнює відношенню більшої частини до меншої. Тут використовуються дві дробі Фібоначчі. При k → ∞:
|
Fk−1 |
|
→ 0,382, |
|
Fk |
→ 0,618. |
|
|
|
|
F |
|
|
|
|
||||
|
|
F |
|
|
|
||||
|
k+1 |
|
|
k+1 |
|
|
|
||
Початковими даними є інтервал невизначеності (a(0) ,b(0) ) і похибка ε . |
|||||||||
Пошук мінімуму функції |
f (x) методом "золотого перетину" |
може бути |
|||||||
реалізовано наступним чином. |
|
|
|
|
|
|
|||
Обчислюються L(0) |
= a(0) −b(0) , |
x1(0) = a(0) |
+0,382L(0) , |
x2(0) = a(0) |
+0,618L(0) та |
||||
f (x1(0) ) і f (x2(0) ) , k =1. Якщо f (x1(k−1) ) ≤ f (x2(k−1) ) |
(рис. 5.9), виключити інтервал |
||||||||
(x2(k−1) ,b(k−1) ), поклавши |
|
|
|
|
|
|
|
||
a(k ) = a(k−1) ,b(k ) = x2(k−1) , L(k ) = b(k ) −a(k ) , x2(k ) = x1(k−1) , x1(k ) = a(k ) |
+0,382L(k ) . |
||||||||
a(0) |
b(0) |
x(1) |
x(2) |
|
) |
Рисунок 5.9
Якщо f (x1(k−1) ) > f (x2(k −1) ) (рис. 5.10), виключають інтервал (a(k−1) , x1(k−1) ),
поклавши
a(k ) = x(k−1) ,b(k ) = b(k−1) , L(k ) = b(k ) −a(k ) , x1(k ) = x2(k−1) , x2(k ) = a(k ) + 0,618L(k ) .
40