Метаевристика
Метаеври́стика — досить невдала назва для опису великого підрозділу, в дійсності основного, в стохастичній оптимізації (stochastic optimization). Стохастична оптимізація є великим класом алгоритмів і методів, які так чи інакше використовують випадковість для пошуку оптимального (або досяжного оптимального) рішення складних завдань. Метаевристики — найзагальніші алгоритми з цього класу і застосовуються для вирішення широкого спектра завдань.
Тип задач метаевристики
Які завдання розглядаються? У справі Якобелліс проти штату Огайо (Jacobellis v. Ohio) (1964 р., справа про фільм нецензурного змісту) суддя Верховного суду США Поттер Стюарт написав свій знаменитий вислів: «Сьогодні я не буду більше намагатися дати визначення тих матеріалів, які я розумію, і які потрібно втиснути в коротке визначення. Цілком можливо, що в мене ніколи не вийде зробити це виразно. Але я впізнаю їх, коли побачу, і фільм, що розглядається в справі, до них не відноситься.»
Метаевристики застосовуються до завдань типу «я впізнаю їх, коли побачу». Це алгоритми, які використовуються для пошуку рішення на завдання, в яких доступно дуже мало допоміжної інформації: ви не знаєте, на що схоже оптимальне рішення, невідомо, яким способом необхідно шукати це рішення, наявної евристичної інформації явно недостатньо, а послідовний перебір не підходить, тому що простір пошуку дуже великий. Але якщо є потенційне рішення, то його можна перевірити і встановити, наскільки воно добре. Тобто можна дізнатися якість рішення, коли воно доступно.
Припустимо, наприклад, що необхідно знайти оптимальний набір дій для робота, який грає у футбол. Є симулятор дій робота і можна протестувати будь-який набір дій і присвоїти цьому набору оцінку (хороший набір дій можна побачити). Також є загальне визначення для набору дій, тобто можна уявити, що він із себе представляє. Однак немає жодної ідеї про те, яким повинен бути оптимальний набір, і про те, як до нього прийти.
Найпростіший варіант розв'язання задачі в подібній ситуації — випадковий пошук (Random Search): будемо просто генерувати випадкові набори поводжень, поки не закінчиться відведений на пошук час, і повернемо найкращий знайдений набір. Але перш ніж впасти у відчай і взятися за випадковий пошук, розглянемо альтернативу, таку як локальний пошук (Hill-Climbing). Почнемо працювати з випадковим набором дій. Потім застосуємо до нього невелику випадкову зміну і протестуємо отриману нову версію. Якщо вона виявиться краще, то попередню версію відкинемо. В іншому випадку, відкидається нова версія. Після зробимо ще одне невелику випадкову зміну поточної версії набору (тобто тієї, яка не була відкинута). Якщо нова версія краща, то відкидаємо поточну, інакше не приймаємо нову. Повторюємо процес наскільки це можливо.
Локальний пошук — це простий метаевристичний алгоритм. Він використовує евристичне припущення про властивість простору пошуку, яке зазвичай актуально для багатьох завдань: схожі рішення часто поводять себе подібним чином (і часто мають близьку якість), тому невеликі модифікації рішень зазвичай тягнуть невеликі і зрозумілі зміни в їхній якості, що дозволяє підніматися на «вершину гори якості» для отримання хороших рішень. Таке евристичне припущення є однією з ключових особливостей метаевристичних методів. І дійсно, практично всі метаевристики об'єднують локальний пошук з випадковим.
Алгоритми
Локальний пошук
Випадковий пошук
Best ← деяке початкове значення
'repeat
S ← випадковий потенційний розв'язок
if (якість)S >(якість)Best then
Best ← S
end if
until в Best записано ідеальний розв'язок, або скінчився час пошуку
return Best
Алгоритм імітації відпалу
Пошук із забороною
Алгоритм пошуку з забороною (Табу пошук), розроблений Фредом Гловером (Fred Glover), використовує оригінальний підхід до дослідження простору пошуку: у ньому зберігається інформація про недавні згенеровані потенційні рішення (так званий «список заборон», табу список), повернення до яких на подальших етапах неможливий поки не скінчиться тимчасове обмеження. Таким чином, якщо алгоритм «підіймається» по пагорбу, то у нього немає іншого вибору, як перейти на іншу сторону, оскільки залишитися на вершині не можна.
Найпростішим способом реалізації пошуку з забороною є підтримка списку заборон L з максимальною довжиною I, включає вже знайдені потенційні рішення. Кожен раз, коли створюється нове рішення, воно записується в список заборон. Якщо список стає занадто великим, то з нього виключається саме «старе» рішення, яке перестає бути забороненим. Пошук із забороною зазвичай нагадує варіант найшвидшого підйому з заміщенням.
Ітеративний локальний пошук
Ітеративний локальний пошук (ІЛП) (Iterated Local Search (ILS)) намагається працювати більш інтелектуально: він виконує стохастичний локальний пошук в просторі локальних оптимумів. Тобто ІЛП знаходить локальний оптимум, а потім здійснює пошук іншого локального оптимуму в околиці і можливо робить його поточним, потім шукає новий локальний оптимум в околиці нового і т. д. Тут використовується евристика, що завжди можна знайти більш «хороший» локальний оптимум поруч з поточним, і подібні переміщення мають бути ефективнішими, ніж абсолютно випадкові перезапуски.
Джерела інформації
Sean Luke, 2009, Essentials of Metaheuristics, First Edition