Источник: [Ссылка]
В данной статье рассматривается метод поиска с запретами и его применение для решения оптимизационных задача, приводится алгоритм вероятностного поиска с запретами в виде псевдо-кода.
Метод поиска с запретами (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.
Возможные условия останова:
Условием останова также может быть как любой из вышеперечисленных пунктов, так и некая их логическая комбинация.
Окрестность решений 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) за вычетом содержащихся в списке запретов.
Одним из главных понятий в методах локального поиска и поиска с запретами является окрестность соседних решений 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).
Neighbour(R) – функция, которая случайным образом генерирует одно решение из окрестности некоторого решения R>.
Алгоритмы 1, 2 и 3 отражают ход решения задачи безусловной оптимизации, либо подразумевают, что проверка решений на соответствие ограничениям осуществляется на стадии формирования окрестности. В задачах условной оптимизации добавляется условие допустимости решения.
Длина списка запретов определяется параметром l ≥ 0 и показывает максимальное количество элементов, которое может содержаться в списке. При добавлении нового элемента в список запретов в случае, когда его длина становится больше заданной, из него удаляется элемент, добавленный раньше всех. При l = 0 список запретов пуст и алгоритм превращается в стандартный алгоритм локального спуска, который совершает шаги, только улучшающие целевую функцию, и останавливается в локальном оптимуме.
Выбор длины списка запретов зависит от размерности решаемой задачи и мощности окрестности. При коротком списке запретов алгоритм может зациклиться. При длинном списке может оказаться так, что большая часть окрестности будет запрещена, что также не приведет к хорошим результатам [8].