Табу пошук

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Історія створення[ред.ред. код]

Табу пошук, створений Фредом У. Гловером в 1986[1]. році і формалізований в 1989[2]. році, є методом локального пошуку для математичної оптимізації.

Визначення[ред.ред. код]

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

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

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

    min{F(x)|x∈D}

вдалося знайти деяке допустиме рішення x0. Розглянемо околиці N(x0)⊂ D точки x0 і знайдемо рішення задачі

    min{F(x)|x∈N(x0)U}

Позначимо його через x1. Розглянемо тепер околиці N(x1), знайдемо точку x2 і т. д. до тих пір, поки xk≠xk+1. Якщо xk=xk+1, то точка xk є локальним оптимумом.

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

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

  min{F(x)|x∈N(xk)| \cup_{i=0}^k {x_i}}

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

Алгоритм ТП[ред.ред. код]

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

    а)z ∈ N'(x);
    б)F(z)=min{F(y)|y∈N'(x)};
    в)перехід x→z не є забороненим або F(z)<FПЗ.

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

    Якщо F(x) < FПЗ, то змінюємо рекорд FПЗ:=F(x).

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

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

Псевдокод[ред.ред. код]

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

    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. Открытая задача маршрутизации транспортного средства с временными сроками: методы решения и применения. (перевод Александрова О. А.)