Реактивний пошук

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

Машинне самовдосконалення засноване на методах пошукової евристики (від грец. «знаходити» — знання, надбане по мірі накопичення людиною досвіду у певній діяльності, тобто при вирішенні практичних завдань певного класу. Більш строго — це стратегія вибіркового пошуку у просторі станів. Тобто теоретично не обґрунтоване правило, що дозволяє скоротити кількість переборів у просторі рішень. Евристичні методи на відміну від алгоритмічних не потребують вичерпної вихідної інформації, але не завжди гарантують успіху. Евристики використовуються у експертних системах та в евристичному програмуванні) для того аби дозволити алгоритму самостійно налаштувати усі операційні параметри під час пошуку. Таким чином, підбір параметрів, який зазвичай демонструє машина в автономному режимі, стає невід'ємною частиною пошукового алгоритму і гарантує гнучкість методу без втручання людини. «Навчальний» елемент реалізується як схема певних реакцій заснована на історії попередніх пошуків завдяки чому підвищується результативність та ефективність методу.

Проблеми оптимізації

Реактивний пошук як і всі методи локального пошуку, застосовується для вирішення проблеми знаходження оптимальної конфігурації системи. Ця конфігурація зазвичай складається з окремих або неперервних параметрів, і число цих параметрів буде змінюється в залежності від кожної окремої конфігурації. В більшості випадків, оптимізаційна задача перетворюється на знаходження глобального мінімуму функції, аргументами якої є параметри оптимізації, представлені як вільні змінні в просторі цієї функції. Розглянемо наприклад функцію, графік якої представлений вище. Знаходження глобального мінімуму функції на цьому графіку не здається складною задачею, оскільки мі можемо бачити і аналізувати «загальний» вид графічного представлення цієї функції. Але комп'ютерна програма може обчислювати та аналізувати лише одну точку простору в один момент часу. «Глобальне» бачення, від самого початку, не доступне нікому, але воно розвивається і вдосконалюється під час виконання достатньої кількості обчислень. (наприклад, маленька дитина, що тільки вчиться рахувати, не в змозі одразу назвати кількість намальованих по кутках аркушу паперу крапочок. Дитина має порахувати кожну окремо: один, два, три, чотири. Тоді як дорослій людині буде досить лише на мить поглянути на аркуш і вона одразу скаже правильну відповідь. Згадайте лише колоду гральних карт.)

Методи локального пошуку

Для того аби знайти мінімум, машина використовує метод «швидкого спуску», при цьому методі генерується довільна конфігурація яка рухається в напрямку до менших значень функції (див. зображення справа, на якому зображена та сама функція, що й раніше, але вже не вид згори, а вид збоку), пошук зупиняється коли не залишається шляхів до вдосконалення. Конфігурації що розглядаються представлені червоною крапкою що рухається вздовж ліній. Цей метод дослідження гарантовано зупиниться в локальному мінімумі функції (де не залишиться жодних варіантів для подальших досліджень). На жаль не можна заздалегідь сказати коли саме пошук завершиться. Цей метод схожий на наступну реальну дію: ви кладете м'ячика на похилу площину і чекаєте доки він скотиться вниз. Але функції які реально потребують досліджень в наш час, на жаль набагато складніші, аніж та, що ми розглядали раніше. Вони можуть мати кілька локальних мінімумів, а послідовне «закидання м'ячика» може зайняти багато часу перш ніж рішення буде знайдене. Витонченіший приклад: пошук заснований на забороні. Більш «реальні» проблеми, тим не менш мають певні «структури», такі, що локальні мінімуми зібрані у певній області довкола глобального мінімуму, таким чином, метод який продовжує пошук після того як знайдено локальний мінімум, може дати кращі результати. Для вирішення таких задач можливе використання сукупності методів, що базуються на забороні («табу»-пошук). Це означає, не зупиняти пошук, навіть коли не спостерігається ніяких покращень (тобто дозволити нашому м'ячику рухатись вгору), це потрібно для того аби здолати бар'єри (гірки) між мінімумами, аби попередити скочування системою по вже пройденому шляху. Це означає, що коли перший крок зроблено наступний крок не може залишитися незакінченим. Таким чином, основною метою «табу»-пошуку є уникання повторного проходження однієї і тієї ж самої ділянки пошуку.

Реактивний пошук Але кількість ітерацій застосованих у пошуку не може нескінченною, інакше система вичерпає всі свої ресурси а рішення так і не буде знайдене. Необхідно правильно встановити критерій зупинки процесу пошуку. І обрати цей параметр правильно це і є одним із найкритичніших параметрів даного методу. Через різні, невірно вибрані умови продовження, можуть виникнути різні непередбачувані помилки. Звичайний спосіб знаходження вірного параметра — «запуск-до-помилки» в кілька повторюваних етапів: дослідник повторно запускає пошук на машині, встановлюючи різні параметри зупинки роботи, таким чином відкидаючи невірні, і обираючи самий багатообіцяючий.

Техніка Реактивного пошуку автоматизує усі параметри пошуку спираючись на впорядкування історії минулих пошуків (тобто свого роду використання попереднього досвіду, навчання). Наприклад, якщо дослідження певної конфігурації повторюється занадто часто, це, можливо, означає необхідність прискорити момент припинення операції на цьому проміжку пошуку. Схема відгуку яка змінює параметри пошуку в залежності від результатів називається реакцією і є ядром техніки реактивного пошуку. Іншою перевагою системи заснованої на запам'ятовуванні історії є можливість розпізнавання «безнадійних» ситуацій, в яких система не знаходить покращення протягом тривалого часу; може бути застосований механізм втечі, який перезавантажить систему з довільної точки за певних обставин.

«Табу-пошук» — це тільки один із прикладів технік що мають перевагу над звичайними механізмами реагування. Всі алгоритми що критично залежать від певних параметрів, таких як алгоритм модельного «загартування» (покращення моделі), генетичні алгоритми, та інші можуть мати переваги над цією евристикою.

Використання історії (попереднього досвіду)

Реактивний пошук використовує широкий спектр евристичних алгоритмів задля дискретної оптимізації, в якій локальний пошук доповнюється і підтримується схемами відгуку (реакції), саме вони використовують історію минулих пошуків, аби підвищити якість та дієвість методу. У реактивному пошуку історія минулих пошуків використовується задля:

• Налаштування параметрів, заснованих на схемі відгуку. Цей алгоритм підтримує максимальну гнучкість для вирішення багатьох можливих проблем, але налаштування цілком автоматизоване і виконується доти доки виконується алгоритм, також налаштування враховує попередню історію.
• Автоматизований баланс розширення меж та посилення на проміжку. Дилема «Дослідження проти дослідження» зустрічається в багатьох евристиках: Чи краще посилити пошук у перспективних регіонах, чи розсунути межі пошуку на незадіяні території. Можна здобути автоматизований евристичний баланс за допомогою механізмів відгуку, наприклад, почати із зосередження ресурсів на проміжку, а потім, коли це виправдано, поступово розширювати окіл пошуку.

Головні стадії реактивного пошуку

Перейдемо до визначення трьох головних стадій реактивного пошуку, заснованого на схемах заборонах (табу пошук):

• Період самоналаштовуючої заборони. У реактивному пошуку заборона «Т» визначається через схеми відгуку (реакції) під час пошуку. На початку операції «Т» прирівнюється до одиниці (), значення «Т» зростає лише тоді коли є підстава для того щоб розширити поле пошуку, та зменшується коли такі підстави зникають. Зрозуміти що настав час розширювати поле пошуку дуже просто, — машина починає занадто часто сигналізувати про повторне проходження тієї самої ділянки пошуку.

На прикладі графіка, зображеного вище ми можемо бачити поведінку параметра «Т» під час певного пошуку. Тут параметр «Т» збільшується експоненціально коли зустрічаються повторні проходження ділянок, і поступово зменшується коли повторні проходження зникають

• Механізм виходу (втечі)

Основного «табу»-механізму заснованого на заборонах, недостатньо для того щоб уникнути довгих повторюваних циклів. До того ж, навіть коли вдалося уникнути «лімітних циклів» (нескінченні циклічні повторення на одному і тому ж проміжку), реагуючий механізм необов'язково гарантує що траєкторія пошуку не замкнеться на певній ділянці пошукового простору. Хаотичне «замикання» траєкторії пошуку на обмеженій ділянці пошукового простору можливе завжди (задля аналогії можна привести динамічні системи із хаотичним притяганням, де траєкторія обмежена у певному проміжку області пошуку, хоча лімітний цикл відсутній). Тому механізм виходу (втечі із циклу) необхідний з двох причин: перша — підвищити працездатність алгоритму, друга — розширити коло пошуку. Фаза виходу запускається багатьма факторами та повторюється занадто часто. Проста схема «втечі» складається з набору довільних кроків що виконуються на поточному проміжку (інколи ці кроки обираються із врахуванням того аби швидше покинути поточну область пошуку).

• Швидкі алгоритми із використанням історії пошуку.

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

Використані матеріали

• https://web.archive.org/web/20100602130211/http://www.reactive-search.org/