Безградiєнтні методи рішення задач оптимiзації

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

Безградiєнтні методи засновані на використанні у процесі пошуку інформації, що одержується від порівняльної оцінки значень цільової функції внаслідок виконання чергового кроку.

З використанням безградiєнтних методів може бути реалізований як одномірний пошук для випадку, коли цільова функція залежить від однієї незалежної перемінної, так і многомірний пошук. При одномірному пошуку використовуються слідуючи методи: одномірного сканiрованія, локалiзації екстремуму функції, " золотого перетину " та ін.

Методи многомірного пошуку - покоордiнатного спуска, многомірного сканiрованiя, Хука-Джiвса, сiмплексний можуть використовувати методи одномірного пошуку як допоміжні.

Спершу розглянемо методи одномірного пошуку. Для всіх методів постановка завдання наступна - визначити стан екстремуму на iнтервалі [Umin, Umax ].

 

Метод сканiрованiя

 

Алгоритм методу слідуючи й. Iнтервал пошуку [Umin, Umax] розбивається на N рівних дільниць, кожний з яких равен кроку пошуку h. Далі послідовно визначається R(U_j) значення цільової функції у всіх точках розбивки, включаючи граничні точки та запам’ятається максимальне чи мінімальне значення цільової функції (рис.5.23).

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

Рис. 5. 23

 

Метод локалiзації екстремума

Iнтервал пошуку [Umin, Umax] розбивається на 4 рівні частини та у точках розбивки та на кордонах інтервалу вираховуються значення цільової функції - у точках 0, 1, 2, 3 та 4 (рис. 5.24). Неважко помітити, що розбивка інтервалу на 4 - найбільш зручний варіант, так як на кожному наступному кроці необхідно обчислювати тільки 2 нових значення цільової функції. У наданому випадкуу точках 5 та 6.

 

Рис 5.24

 

Локалiзація екстремуму продовжується до отих пор, доки не буде досягнута задана точність. Абсолютна помилка у знаходженні стану екстремуму визначається по формулі:

 

Δ=(U_max-U_min)*2^-(S-1)/2 (5.51)

 

де S - кількість обчислювань значень цільової функції завжди непарне число.

Так, наприклад, при S=21 відносна помилка у знаходженні стану екстремуму складе:

 

Δ=(U_max-U_min)*2^-10 ≈ 0.001

 

5.7.3. Метод "золотого перетину"

 

Результати пошуку можуть бути краще, якщо ділення iнтервала [Umin, Umax], у якому знаходиться екстремум, виробляти не на ціле число, а у певному ірраціональному відношенні.

(a / b) = (b / c) або a*c = b ² (5.52)

 

В основі цього методу лежить закон геометричного відношення чи "золотого перетину". Нехай даний відтинок a, що поділений на дві нерівні частини b та c так, що виконується. Відповідно до цього закону визначаються точки досліджуваного інтервалу, у яких необхідно виробляти обчислення цільової функції.

Оскільки c = a – b, отой підставив вираз для с в (5.52) та запровадивши нову перемінну k = b / a, після перетворень одержимо:

 

K² + K – 1 = 0 (5.53)

 

Вирішив (5.53), одержимо близьке значення K ~ 0. 62.

Порядок пошуку екстремуму методом "золотого перетину" наступний. На досліджуваним iнтервалі визначаються дві точки Umin та Umах:

 

U₁=U_min+(1-K).a

U₂=U_min+K.a (5.54)

 

де а - довжина інтервалу Umin – Umax.

 

У точках U₁ і U₂ розраховується цільова функція. За знайденим значенням R(U₁і U₂) з обліком R(U_min і U_max) визначається подінтервал, у якому локалізований екстремум. У даному випадку це [U_min,U₂ ] (рис. 5.25).

Далі усередині великого подінтервалу [U_min,U₁ ] знаходиться крапка, що відстоїть від загального кінця подінтервалу на відстані

(1–К)Wb= K².b,

де b - довжина подінтервалу [U_min,U₂ ], у якому локалізований екстремум, причому b = K.a. Тоді:

 

U3=Umin+K^2.b =Umin+K^2.(K.a)=Umin+K^3.a

(5.55)

 

Неважко показати, що в інтервалі [U_min,U₂ ] також дотримується "золотий перетин". Далі обчислюється значення цільової функції R(U₃) і порівнюються значення R(U₂), R(U₁), R(U₃). Знаходиться мінімальне значення (у даному випадку R(U₃)) і процедура продовжується - визначається аналогічно крапка R(U₄) і т.д., поки не буде знайдений екстремум із заданою точністю. Абсолютна помилка у визначенні положення екстремуму після S обчислень складе

(5.56)

При S=21 відносна помилка: Δ/(U_max -U_min)= 0,5*0.62¹⁸ ≈ 0.9*10^-4 Отже, точність розрахунку по методу "золотого перетину" практично на порядок перевершує точність розрахунку по методу локалізації екстремуму при тому самому кількості обчислень.

Розглянемо тепер деякі з методів багатомірного пошуку.