13.6 Порівняння методів одновимірного пошуку
Найкращими критеріями порівняння методів пошуку, які були описані вище, є їх ефективність і універсальність. Під ефективністю алгоритму розуміють число обчислень функції, необхідне для досягнення необхідного звуження інтервалу невизначеності. Із табл. 13.1 видно, що найкращим в цьому відношенні є метод Фібоначчі, а найгіршим – метод загального пошуку. Конструктор не з великим задоволенням використовує метод Фібоначчі, так як при його застосуванні необхідно заздалегідь задавати число обчислень значень функції. Однак він може скористатися методом золотого перетину. Як правило, методи Фібоначчі і золотого перетину, володіють високою ефективністю, найбільш підходять для розв’язку одновимірних унімодальних задач оптимізації.
Універсальність алгоритму означає, що його можна легко застосувати для розв’язку самих різноманітних задач. В цьому відношенні метод Фібоначчі, поступається іншим, так як потребує окремого обчислення положення точок, в яких будуть визначатися значення цільової функції на кожному новому кроці. Цим приходиться розплачуватися за підвищення ефективності метода. З точки зору універсальності малоефективний метод загального пошуку має по крайній мірі одну перевагу – його можна з успіхом застосовувати і для неунімодальних функцій, якщо вони достатньо гладкі. Нерідко заздалегідь не відомо, чи є розглянута цільова функція унімодальною. В таких випадках слід використати декілька різних алгоритмів і подивитись, чи дають вони усі один і той самий оптимум. Звідси витікає важливий висновок, який слід мати на увазі, розв’язуючи задачі оптимізації: не існує універсального алгоритму, який дозволяв би розв’язувати будь-які задачі. Вирішуючи складні задачі оптимізації, слід користуватися різними методами, так як це дозволяє збільшити долю вигідних розв’язків.
Таблиця 13.1 Порівняння методів одновимірного пошуку по значенням коефіцієнта дроблення інтервалу невизначеності f
Кількість обчислень цільової функції N |
Загальний пошук |
Ділення відрізка навпіл |
Метод дихотомії |
Метод золотого перетину |
Метод Фібоначчі |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
1,0 0,667 0,500 0,400 0,333 0,286 0,250 0,222 0,200 0,182 0,167 0,154 0,143 0,133 0,125 0,118 0,111 0,105 0,100 0,095 |
1,0 - 0,500 - 0,250 - 0,125 - 0,0625 - 0,0312 - 0,0156 - 0,00781 - 0,00391 - 0,00195 - |
1,0 0,500 - 0,250 - 0,125 - 0,0625 - 0,0312 - 0,0156 - 0,00781 - 0,00391 - 0,00195 - 0,000976 |
1,0 0,618 0,382 0,236 0,146 0,090 0,056 0,345 0,0213 0,0132 0,00813 0,00502 0,00311 0,00192 0,00119 0,000733 0,000453 0,000280 0,000173 0,000107 |
1,0 0,500 0,333 0,200 0,125 0,077 0,048 0,0294 0,0182 0,0112 0,00694 0,00429 0,00265 0,00164 0,00101 0,000626 0,000387 0,000239 0,000148 0,0000913 |
Приклад 1. Одновимірна мінімізація в середовищі Mathcad
Для знаходження мінімуму одновимірної функції в середовищі Mathcad використовується функція root(f(var1, var2, ...),var1, [a, b]) – повертає змінну var1, що лежить між a і b, в якій функція, що розв’язується дорівнює нулю.
Параметри:
f – рівняння, яке потрібно розв’язати;
var1 – корінь рівняння;
[a, b] – відрізок, на якому шукається розв’язок рівняння.
Наприклад, необхідно знайти мінімум гладкої унімодальної функції у=х2+ех, використовуючи необхідну умову мінімуму.
Визначимо цільову функцію
Визначимо першу похідну цільової функції
Визначимо другу похідну цільової функції
Достатня умова унімодальності (f''(x)>0) виконана
Мінімум гладкої функції досягається в стаціонарній точці (f'(x)=0).
Розв’яжемо рівняння f'(x)=0, використовуючи функцію root; початкове наближення кореня нехай дорівнює нулю (х=0)
Точка мінімуму х=-0.351732
Значення функції в точці мінімуму
Підтвердимо результати обчислень графічно
Лекція № 14
МЕТОДИ ОПТИМІЗАЦІЇ БАГАТОВИМІРНИХ ЗАДАЧ