Табу-пошук

Табу-пошук (ТП) — метод локального пошуку для математичної оптимізації. Створений Фредом У. Гловером в 1986 році і формалізований в 1989.

Визначення

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

Фред У. Гловер запропонував наступну схему локального пошуку:

нехай для задачі дискретної оптимізації

 ${\displaystyle \min\{F(x)|x\in D\}}$ 

вдалося знайти деяке допустиме рішення ${\displaystyle x_{0}}$. Розглянемо окіл ${\displaystyle N(x_{0})\subset D}$ точки ${\displaystyle x_{0}}$ і знайдемо рішення задачі

 ${\displaystyle \min\{F(x)|x\in N(x_{0})U\}}$ 

Позначимо його через ${\displaystyle x_{1}}$. Розглянемо тепер окіл ${\displaystyle N(x_{1})}$, знайдемо точку ${\displaystyle x_{2}}$ і т. д. до тих пір, поки ${\displaystyle x_{k}\neq x_{k+1}}$. Якщо ${\displaystyle x_{k}=x_{k+1}}$, то точка ${\displaystyle x_{k}}$ є локальним оптимумом.

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

На ${\displaystyle k}$-му кроці алгоритму точка ${\displaystyle x_{k+1}}$ знаходиться з рішення задачі

 ${\displaystyle \min\{F(x)|x\in N(x_{k})|\bigcup _{i=0}^{k}{x_{i}}\}}$ 

Множина ${\displaystyle \bigcup _{i=0}^{k}{x_{i}}}$ виступає як список заборон, що і послужило приводом для назви алгоритму. Цей список поповнюється на кожному кроці новою точкою. Очевидно, що якщо стара інформація не буде видалятися зі списку, то працездатність алгоритму буде падати з ростом числа ітерацій. Тому довжина списку обмежується зверху деякою константою ${\displaystyle l}$, і список заборон містить тільки останні ${\displaystyle l}$ точок. Перевірка і поповнення списку може виявитися досить трудомісткою операцією. Тому, іноді доцільно зберігати не самі рішення ${\displaystyle x_{i}}$, ${\displaystyle i=k-l+1,\dotsi ,k}$, а або функції від них (наприклад, значення цільової функції), або номера змінюваних координат, атрибути переходу від ${\displaystyle x_{k}}$ до ${\displaystyle x_{k+1}}$. Позначимо через ${\displaystyle N'(x)}$ частину околу ${\displaystyle N(x)}$, взяту випадковим чином. Тоді алгоритм пошуку із заборонами можна представити в наступному вигляді.

Алгоритм ТП

1. Обираємо початкове рішення ${\displaystyle x}$, вважаємо ${\displaystyle F_{PZ}:=F(x)}$ . Формуємо порожній список заборон.
2. Знаходимо нове рішення ${\displaystyle z}$ таке, що

 а) ${\displaystyle z\in N'(x)}$ б) ${\displaystyle F(z)=\min\{F(y)|y\in N'(x)\}}$; в) перехід ${\displaystyle x\to z}$ не є забороненим або ${\displaystyle F(z)<F_{PZ}}$ . 

3. Переходимо в нову точку ${\displaystyle x:=z}$.
Змінюємо список заборон.

 Якщо ${\displaystyle F(x)<F_{PZ}}$ , то змінюємо рекорд ${\displaystyle F_{PZ}:=F(x)}$ . 

4. Якщо виконаний критерій зупинки, то STOP, інакше йти на п.2.

Як критерій зупинки використовується або зупинка по числу ітерацій, або необхідна точність по відношенню до заданої нижньої межі. Початкове рішення вибирається за допомогою якогось простого алгоритму. Змінюючи довжину списку заборон, можна керувати процесом пошуку. При зменшенні довжини, інтенсифікується пошук в поточній області, збільшення довжини сприяє переходу до іншої області. Як околиці можна розглядати безліч всіх рішень, які виходять з поточного рішення зміною однією з координат. У 1992 році Файгл і Керн запропонували імовірнісну версію методу TS, який при кількості ітерацій прагнучих до нескінченності, сходиться до глобального оптимуму, що, втім, властива більшості імовірнісних алгоритмів. Так рандомізація околиці скорочує трудомісткість алгоритму на кроці 2 і вносить елемент випадковості при виборі напрямку спуску. Якщо рандомізована околиця становить від 1 до 10 відсотків від початкової, то алгоритм не зациклюється навіть без списку заборон. Алгоритм TS застосовувався до широкого кола завдань дискретної оптимізації, показав високу працездатність і на сьогодні є однією з найпопулярніших імовірнісних евристик. Одне з можливих застосувань методу «Пошук з заборонами» для вирішення задач нерегулярного розкрою — упаковки (Р-У) запропоновано в роботі польськими авторами Блазевічем, Хаврулюком і Валковяком.

Псевдокод

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

 Input: Output: ConstructInitialSolution() TabuList While ( StopCondition()) CandidateList For ( ) If ( ContainsAnyFeatures(, TabuList)) CandidateList End End LocateBestCandidate(CandidateList) If (Cost() Cost()) TabuList FeatureDifferences(, ) While (TabuList > ) DeleteFeature(TabuList) End End End Return () 

Приклад

Задача комівояжера

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

Зада́ча комівояже́ра (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP; нім. Problem des Handlungsreisenden) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів.

Наприклад, якщо місто A і місто B розташовані поруч одне з одним, в той час як місто C розташоване далі, загальна пройдена відстань, буде коротшою, якщо міста А і Б відвідали одне за одним перед приїздом до міста С. Оскільки знаходження оптимального рішення до задачі комівояжера є NP-повним завданням, евристичні наближені методи (наприклад, локальний пошук) корисні для розробки близьких до оптимальних рішень.

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

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

Посилання

1. F. Glover and C. McMillan (1986). «The general employee scheduling problem: an integration of MS and AI». Computers and Operations Research.
2. Fred Glover (1989). «Tabu Search». ORSA Journal on Computing 1 (2).
3. Faigle U., Kern W. Some convergence results for probabilistic tabu search. ORSA Journal on Computing 4(1), pp.32-37,1992.
4. Glover F., Laguna M. Tabu search in modern heuristic techniques for combinatorial problems, Blackwell Publishing, 1992.
5. Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem. — Annals of OR, 41(1-4), pp.313-325, 1993.

Джерела

Zeynep Özyurt, Deniz Aksen, Necati Aras. Открытая задача маршрутизации транспортного средства с временными сроками: методы решения и применения. (перевод Александрова О. А.)