Вопрос 31: Поиск с запретами

Основоположником алгоритма поиска с запретами (Tabu search) является Ф. Гловер, который предложил принципиально новую схему локального поиска. Она позволяет алгоритму не останавливаться в точке локального оптимума, как это предписано в стандартном алгоритме локального спуска, а путешествовать от одного локального оптимума к другому в надежде найти среди них глобальный оптимум. Основным механизмом, позволяющим алгоритму выбираться из локального оптимума, является список запретов $Tabu(i_k)$. Он строится по предыстории поиска, то есть по нескольким предшествующим решениям $i_k, i_k-1,..., i_k-l+1$, и запрещает часть окрестности текущего решения $N(i_k)$. Точнее на каждом шаге алгоритма очередная точка $i_{k+1}$ является оптимальным решением подзадачи

$f_{i_{k+1}} = min( f(j) \mid j \in N(i_k) \setminus Tabu_{l}(i_k) )$

Список запретов $Tabu_l(i_k) \in N(i_k)$ учитывает специфику задачи и, как правило, запрещает использование тех "фрагментов" решения (ребер графа, координат вектора, цвета вершин), которые менялись на последних $l$ шагах алгоритма. Константа $l$ задает длину списка запретов. При $l = 0$ получаем стандартный локальный спуск.

Существует много вариантов реализации основной идеи поиска с запретами. Приведем один из них, для которого удается установить асимптотические свойства. Рассмотрим рандомизированную окрестность $N_p(i) \in N(i)$, где каждый элемент окрестности $j \in N(i)$ включается в множество $N_{p}(i)$ с вероятностью $p$ независимо от других элементов. С ненулевой вероятностью множество $N_{p}(i)$ может совпадать с $N(i)$, может оказаться пустым или содержать ровно один элемент. Общая схема алгоритма поиска с запретами может быть представлена следующим образом.

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

1. Выбрать начальное решение $i_0 \in I$ и положить

$f^* := f(i_0), Tabu_l(i_0) := AE, k := 0$

1. Пока не выполнен критерий остановки делать следующее.

   2.1. Сформировать окрестность $N_{p}(i_k)$

   2.2. Если $N_{p}(i_k) = AE$, то $i_{k+1} := i_k$, иначе найти $i_{k+1}$ такой, что

$f(i_{k+1}) = min( f(j) \mid j \in N_{p}(i_k) \setminus Tabu_l(i_k))$

2.3. Если {% math %} f^* > f(i_{k+1}) {% endmath %}, то {% math %} f^*:= f(i_{k+1}) {% endmath %}.

2.4. Положить $k := k+1$ и обновить список запретов $Tabu_{l}(i_k)$.

Параметры $p$ и $l$ являются управляющими для данного алгоритма и выбор их значений зависит от размерности задачи и мощности окрестности.