Табу-пошук

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

Визначення

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

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

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

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

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

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

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

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

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

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

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

Алгоритм ТП

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

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

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

    Якщо $F(x)<F_{PZ}$ , то змінюємо рекорд $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-повним завданням, евристичні наближені методи (наприклад, локальний пошук) корисні для розробки близьких до оптимальних рішень.

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

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

Джерела

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