Назад в библиотеку

Метод поиска с запретами для оптимизационных задач

Автор: Е.С. Скаков
Источник: [Ссылка]

Аннотация

В данной статье рассматривается метод поиска с запретами и его применение для решения оптимизационных задача, приводится алгоритм вероятностного поиска с запретами в виде псевдо-кода.

Метод поиска с запретами (Tabu Search) является одним из наиболее эффективных метаэвристических методов. Он был предложен Ф. Гловером в 80-е годы [1-4]. Отличительной чертой этого метода является процесс введения и снятия некоторых искусственных ограничений задачи в процессе поиска решения [5].

Метод поиска с запретами и его вариации нашли широкое применение в решении разных оптимизационных задач NP-сложности: задач о составлении расписания [6-7], задач об упаковке [8, 5], задач о выборе оптимального маршрута [9], задач о размещении [10-17] и ряда других оптимизационных задач [18-19].

Работы [11-13] посвящены проблеме размещения базовых станций в сетях стандарта 3G.

Метод поиска с запретами дает результаты, близкие к оптимальным, за приемлемое время, что позволяет использовать его в оптимизационных задачах наряду с другими метаэвристическими методами.

Алгоритм метода локального поиска

Метод поиска с запретами – итерационный алгоритм, основанный на алгоритме поиска локального оптимума. Метод состоит в последовательном улучшении некоторого допустимого решения с целью максимизировать (минимизировать) целевую функцию.

Для оптимизации потенциального решения задачи необходимо наличие двух составляющих:

Ниже (см. алгоритм 1) представлен простейший алгоритм локального поиска для задачи максимизации. Предполагается, что вектор x – решение некоторой оптимизационной задачи. Множество всех возможных векторов обозначим X. Пусть требуется максимизировать некоторую функцию f(x) на множестве X.

Алгоритм 1. Простейший алгоритм локального поиска (задача максимизации) [5].

  1. x0 – начальное решение.
  2. Текущее решение x = x0.
  3. Построить окрестность соседних решений N(x).
  4. Найти такое решение y' ∈ N(x), что f(y') > f(y), y ∈ N(x).
  5. Положить x = y'.
  6. Если выполнены условия останова, то работа алгоритма прекращается, x – результат; иначе перейти к шагу 3.

Возможные условия останова:

  1. Текущее решение является оптимальным.
  2. Окрестность соседних решений – пустое множество.
  3. Окрестность соседних решений не содержит ни одного решения, улучшающего целевую функцию.
  4. Число итераций превысило некое заданное число.
  5. Целевая функция не улучшалась некоторое заданное число итераций подряд.

Условием останова также может быть как любой из вышеперечисленных пунктов, так и некая их логическая комбинация.

Окрестность решений N(x) для вектора x представляет собой некоторое множество решений, которые являются в некотором смысле близкими по отношению к x.

Алгоритм метода поиска с запретами

Основным недостатком метода локального поиска является его остановка при достижении локального оптимума (см. условие останова № 3). Под локально оптимальными понимаются такие решения, окрестность которых не содержит лучших по отношению к целевой функции решений, т.е. f(xopt) > f(y), y ∈ N(xopt), где xopt – локальный оптимум [5]. Нашим же искомым решением является глобальный оптимум. Очевидно, что глобальный оптимум является также и локальным, поэтому для успешного поиска решений мы должны как-то переходить от одного локального оптимума к другому.

В методе поиска с запретами с целью преодолеть вышеописанный недостаток вводится т.н. список запретов (Tabu List). Этот список хранит некоторое количество предыдущих решений, и при выборе нового решения запрещается выбирать из окрестности решения, содержащиеся в списке запретов.

Ниже (см. алгоритм 2) представлен общий алгоритм поиска с запретами для задачи максимизации. Предполагается, что вектор x(i) – решение задачи на итерации i. Список запретов обозначим как TL(i). Пусть N'(x(i), TL(i)) – множество соседних решений для x(i) за вычетом содержащихся в списке запретов.

Алгоритм 2. Общий алгоритм поиска с запретами [5].

  1. x0 – начальное решение.
  2. Лучшее решение x* = x0.
  3. Список запретов TL – пустое множество.
  4. Добавить x* в TL.
  5. i = 0 – номер итерации.
  6. Построить окрестность соседних решений N'(x(i), TL(i)).
  7. Найти такое решение y' ∈ N'(x(i), TL(i)), что f(y') имеет максимальное значение среди всех элементов окрестности.
  8. x(i) = y'.
  9. Обновить список TL.
  10. Если f(x(i)) > f(x*), то x* = x(i).
  11. i++.
  12. Если выполнены условия останова, то работа алгоритма прекращается, x* – результат; иначе перейти к шагу 6.

Окрестность решения

Одним из главных понятий в методах локального поиска и поиска с запретами является окрестность соседних решений N(x) для решения x. Но с практической точки зрения лучше определить не все множество соседних решений N(x), а множество изменений, которым мы можем подвергнуть наше решение [20].

Окрестность решений N(x) может быть описана как множество решений, которые мы можем получить, применив изменение m к решению x (m принадлежит к некоему множеству возможных изменений M). Применение изменения m к решению x обозначим как x ⊕ m. Тогда N(x) = {x'|= x ⊕ m, m ⊕ M}.

Вероятностный поиск с запретами

Алгоритм 2 описывает некий общий абстрактный алгоритм поиска с запретами. Он подразумевает, что для каждого решения мы исследуем всю его окрестность. Однако в реальных задачах это часто бывает невозможно, например, когда решения представлены вещественными числами, и/или окрестность имеет экспоненциальную мощность.

Для таких случаев был разработан вероятностный поиск с запретами. В нем мы исследуем не окрестность N'(x(i), TL(i)), а вероятностную окрестность N'p(x(i), TL(i), p). Каждая точка N'(x(i), TL(i)) с вероятностью p включается в N'p(x(i), TL(i), p) независимо от других точек. Новая окрестность, в принципе, может оказаться пустой, или, например, содержать всего одну точку.

Самым простым способом формирования вероятностной окрестности является генерация случайным образом некоего заранее определенного числа соседних решений (см. алгоритм 3).

Алгоритм 3. Общий алгоритм вероятностного поиска с запретами 

        1: l ← длина списка запретов 
        2: n ← число элементов окрестности 
        3: S ← начальное потенциальное решение 
        4: Best ← S – лучшее решение 
        5: L ← ∅ – список запретов макс. длины l (реализуется в виде очереди) 
        6: Добавить S в список запретов TL
        7: repeat 
        8:    if Длина(TL) > l then 
        9:        Удалить из списка запретов самый «старый» элемент 
        10:   end if 
        11:   R ← S 
        12:   quality_tmp ← -∞ – переменная, хранящая качество лучшего на данный момент решения окрестности 
        13:   for n раз do 
        14:       Tmp ← Neighbour(R) 
        15:       if Tmp ← L и Качество(Tmp) > quality_tmp then 
        16:           S ← Tmp
        17:         quality_tmp ← Качество(Tmp)
        18:       end if 
        19:   end for 
        20:   if Качество(S) > Качество(Best) then 
        21:      Best ← S 
        22:      Добавить S в список запретов 
        23:   end if 
        24: until не закончилось время поиска 
        25: return Best

Neighbour(R) – функция, которая случайным образом генерирует одно решение из окрестности некоторого решения R>.

Алгоритмы 1, 2 и 3 отражают ход решения задачи безусловной оптимизации, либо подразумевают, что проверка решений на соответствие ограничениям осуществляется на стадии формирования окрестности. В задачах условной оптимизации добавляется условие допустимости решения.

Список запретов

Длина списка запретов определяется параметром l ≥ 0 и показывает максимальное количество элементов, которое может содержаться в списке. При добавлении нового элемента в список запретов в случае, когда его длина становится больше заданной, из него удаляется элемент, добавленный раньше всех. При l = 0 список запретов пуст и алгоритм превращается в стандартный алгоритм локального спуска, который совершает шаги, только улучшающие целевую функцию, и останавливается в локальном оптимуме.

Выбор длины списка запретов зависит от размерности решаемой задачи и мощности окрестности. При коротком списке запретов алгоритм может зациклиться. При длинном списке может оказаться так, что большая часть окрестности будет запрещена, что также не приведет к хорошим результатам [8].

Список использованной литературы

  1. Glover F. Tabu search – part I // ORSA Journal on computing. – 1989. – Т. 1, № 3. – Р. 190-206.
  2. Glover F. Tabu search – part II // ORSA Journal on computing. – 1990. – Т. 2, № 1. – Р. 4-32.
  3. Glover F., Taillard E. A user's guide to tabu search // Annals of operations research. – 1993. – Т. 41, № 1. – Р. 1-28.
  4. Glover F. Tabu search: A tutorial // Interfaces. – 1990. – Т. 20, № 4. – С. 74-94.
  5. Усманова А.Р. Метод поиска с запретами для задач упаковки в контейнеры: дисс. … канд. физико-математических наук. – Уфа. 2002. – 101 с.
  6. Боровых Н.И., Красоткина О.В. Применение алгоритма поиска с запретами в задаче автоматизированного составления оптимального штатного расписания // Известия ТулГУ. Технические науки. – 2013. – Вып. 6. Ч. 2. – С. 218-227.
  7. Lü Z., Hao J. K. Adaptive tabu search for course timetabling // European Journal of Operational Research. – 2010. – Т. 200, № 1. – Р. 235-244.
  8. Руднев А.С. Вероятностный поиск с запретами для задачи упаковки кругов и прямоугольников в полосу // Дискретный анализ и исследование операций. – 2009. – Т. 16, № 4. – Р. 61-86.
  9. Vogt L., Poojari C.A., Beasley J.E. A tabu search algorithm for the single vehicle routing allocation problem // Journal of the Operational Research Society. – 2007. – Т. 58, № 4. – Р. 467-480.
  10. Crainic T.G., Toulouse M., Gendreau M. Parallel asynchronous tabu search for multicommodity location-allocation with balancing requirements // Annals of Operations Research. – 1996. – Т. 63, № 2. – Р. 277-299.
  11. Amaldi E., Capone A., Malucelli F. Planning UMTS base station location: Optimization models with power control and algorithms // Wireless Communications, IEEE Transactions on. – 2003. – Т. 2, № 5. – Р. 939-952.
  12. Amaldi E. et al. Optimizing base station location and configuration in UMTS networks // Annals of Operations Research. – 2006. – Т. 146, № 1. – Р. 135-151.
  13. Amaldi E., Capone A., Malucelli F. Radio planning and coverage optimization of 3G cellular networks // Wireless Networks. – 2008. – Т. 14, № 4. – Р. 435-447.
  14. Sun M. Solving the uncapacitated facility location problem using tabu search // Computers & Operations Research. – 2006. – Т. 33, № 9. – Р. 2563-2589.
  15. Sun M. A tabu search heuristic procedure for the capacitated facility location problem // Journal of Heuristics. – 2012. – Т. 18, № 1. – Р. 91-118.
  16. Al-Sultan K. S., Al-Fawzan M. A. A tabu search approach to the uncapacitated facility location problem // Annals of Operations Research. – 1999. – Т. 86. – Р. 91-103.
  17. Michel L., Van Hentenryck P. A simple tabu search for warehouse location // European Journal of Operational Research. – 2004. – Т. 157, № 3. – Р. 576-591.
  18. van der Gaast J. P. et al. A Tabu Search Algorithm for Application Placement in Computer Clustering // Computers & Operations Research. – 2014. – Т. 50, № 1. – Р. 38-46.
  19. Xhafa F. et al. A Tabu Search Algorithm for Ground Station Scheduling Problem // Advanced Information Networking and Applications (AINA), 2014 IEEE 28th International Conference on. – IEEE, 2014. – Р. 1033-1040.
  20. Dreo J., Petrowski A., Taillard E. Metaheuristics for Hard Optimization. – Springer, 2006. – 382 р.