Метод Кулакова (Метод Хука-Джівса)
(англ. Hooke - Jeeves) служить для пошуку безумовного локального екстремуму функції і відноситься до прямих методів, тобто спирається безпосередньо на значення функції. Алгоритм ділиться на дві фази: пошук і пошук за зразком.
Метод Хука-Джівса – це комбінація досліджувального пошуку за напрямками та пошуку за зразком.
Досліджуючий пошук: задається величина кроку, яка може бути різною для різних координатних напрямків та змінюватись у процесі пошуку. Якщо значення цільової функції в пробній точці не перевищує значення у вихідній, крок пошуку розглядається як успішний. В іншому випадку необхідно повернутися в попередню точку і зробити крок у протилежному напрямку. Після перебору всіх координат N досліджуючий пошук закінчується. Отримана точка називається базовою.
Пошук за зразком: полягає у реалізації єдиного кроку з отриманої базової точки вздовж прямої, що з'єднує її з попередньою базовою точкою.
Нова точка будується за такою формулою:
x(k) – поточна базова точка;
x(k-1) - попередня базова точка;
xp(k+1) - точка, побудована під час руху за зразком;
x(k+1) – нова базова точка.
Якщо рух за зразком не призводить до зменшення цільової функції, то точка xp(k+1) фіксується як часова базова точка і знову проводиться досліджуючий пошук з цієї точки. Якщо в результаті виходить точка зі значенням функції меншим, ніж x(k), то вона розглядається як нова базова точка x(k+1).
Якщо досліджуючий пошук невдалий, потрібно повернутися в x(k) і провести пошук у протилежному напрямі. Якщо він також не призводить до успіху, потрібно зменшити величину кроку і відновити досліджуючий пошук. Пошук завершується, коли величина кроку стає достатньоюмалій.
12. Методи штрафних функций. Належить до чисельних методів вирішення завдань умовної оптимізації. У разі вихідна завдання умовної оптимізації перетворюється на послідовність завдань безумовної оптимізації шляхом запровадження штрафних функцій. Розглянемо завдання умовної мінімізації виду:
Методи штрафних функцій поділяються на методи внутрішньої точки та методи зовнішньої точки. p align="justify"> Метод штрафних функцій називається методом внутрішньої точки (зовнішньої точки), якщо всі точки послідовності x [t], t = o, 1,2. є допустимими (неприпустимими). Вид методу (внутрішньої чи зовнішньої точки) визначає вид штрафної функції і правило, яким здійснюється перерахунок штрафного параметра після рішення? чергове завдання безумовної мінімізації.
У дещо більш загальної постановки Штрафних функцій метод полягає у зведенні задачі мінімізації функції j(х) на множині Х до задачі мінімізації деякої параметричної функції М (х, a) на множині більш простої структури з точки зору ефективності застосування чисельних методів мінімізації, ніж вихідна множина X.
Усі методи цієї групи, незважаючи на різні схеми та варіанти, мають одну загальну особливість: у них здійснюється перехід від завдання умовної оптимізації до еквівалентної задачі чи послідовності задач безумовної оптимізації. Методи штрафних функцій можна розділитина два класи : параметричні та непараметричні.
Параметричні методи характеризуються наявністю одного або кількох належним чином вибраних параметрів, що входять до структури штрафної функції як вагові коефіцієнти.
До параметричних методів відносяться: метод послідовної безумовної оптимізації (МПБО), запропонований Фіакко та Маккорміком, метод Зангвілла та ін.
УНепараметричні методи цільова функція розглядається як функція, що задає додаткове штучне обмеження, що поступово ущільнюється в міру отримання нової інформації про хід вирішення завдання.
Параметричні методи поділяються на: 1) методи внутрішньої точки; 2) методи зовнішньої точки; 3) комбіновані методи.
При використанні методів внутрішньої точки поточна точка постійно знаходиться в допустимій області за допомогою штрафної функції, яка в цьому випадку називається бар'єрною. Методи зовнішньої точки, навпаки, генерують послідовність точок, які за межі допустимої області, але у межі дають допустиме рішення. Зрештою, у комбінованих методах, які необхідно використовувати при обмеженнях-рівностях, у процесі оптимізації одні з обмежень задовольняються, а інші – ні. Однак при досягненні шуканого рішення усі умови в межах заданого допуску виконуються.
13. Критерій оптимальності (критерій оптимізації) - характерний показник вирішення задачі, за значенням якого оцінюється оптимальність знайденого рішення, тобто максимальне задоволення поставленим вимогам. В одному завданні може бути встановлено декілька критеріїв оптимальності.
Критерії оптимальності
Правильний вибір критеріїв відіграє важливу роль у виборі оптимального рішення. Теоретично прийняття рішень не знайдено загального методу вибору критеріїв оптимальності. В основному керуються досвідом чи рекомендаціями. Найбільш вивчене питання для фінансово-економічних завдань, у яких найчастіше застосовується єдиний критерій - максимум показника ефективності, прибутку, або максимум рентабельності, або мінімум терміну окупності тощо. Застосування для технічних завдань лише одного критерію (наприклад,максимум рівня безпеки, мінімум споживання енергії, мінімум екологічних збитків) часто призводить до абсурдних результатів, що виходять за область допустимих рішень, тому зазвичай поєднується з економічними критеріями (наприклад, мінімум вартості або максимум доходу).
Великі складності викликають «незліченні» критерії оптимальності, які стосуються, наприклад, гуманітарних питань, художнього враження, зміни ландшафту тощо (наприклад, максимум зручності, краси). Для обліку таких критеріїв можуть застосовуватись експертні оцінки.
Найбільш розроблені методи однокритеріальної оптимізації, що у більшості випадків дозволяють отримати однозначне рішення. У задачах багатокритеріальної оптимізації абсолютно краще рішення вибрати неможливо (за винятком окремих випадків), оскільки при переході від одного варіанту до іншого, як правило, покращуються значення одних критеріїв, але погіршуються значення інших. Склад таких критеріїв називається суперечливим, і остаточно обране рішення буде компромісним. Компроміс дозволяється запровадженням тих чи інших додаткових обмежень чи суб'єктивних припущень. Тому неможливо говорити про об'єктивне єдине рішення такого завдання.
Часто багатокритеріальну задачу зводять до однокритеріального застосування «згортки» критеріїв в один комплексний, що називається цільовою функцією (або функція корисності). Іноді загальним методом для багатокритеріальних завдань називають оптимальність щодо Парето, яке дозволяє знайти ряд «непокращуваних» рішень, проте цей метод не гарантує глобальної оптимальності рішень. Менш відома «оптимальність за Слейтером».
Нормування критеріїв
Для зручності та однозначності сприйняття критерію Ki (де i = 1,…, m; m – число критеріїв)нормують, тобто зазвичай приводять до такого вигляду:
критерії Ki зменшуються з поліпшенням рішення, зі зростанням якості об'єкта, що проектується (зустрічається і зворотна вимога).
Наприклад, мінімальна ціна, втрати енергії (рівні 1- ККД);
переважно критерії приводити до безрозмірного вигляду.
наприклад, відносна ціна (стосовно ціни найдорожчого варіанту);
як наслідок, найкраще значення критерію дорівнює нулю. Рішення, у якого всі нульові критерії (Ki = 0), відповідає ідеальному кінцевому результату (ІКР), коли об'єкта немає, але його функція виконується.