Дискретные задачи размещения Оптимизационные алгоритмы

Главная страница библиотеки  Демонстрационная версия Оптимизационные алгоритмы

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

Основоположником алгоритма поиска с запретами (Tabu search) является Ф. Гловер, который предложил принципиально новую схему локального поиска [1, 2]. Она позволяет алгоритму не останавливаться в точке локального оптимума, как это предписано в стандартном алгоритме локального спуска, а путешествовать от одного локального оптимума к другому в надежде найти среди них глобальный оптимум. Основным механизмом, позволяющим алгоритму выбираться из локального оптимума, является список запретов 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) | j Î N(i_k) \ Tabu_l (i_k)}.

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

Существует много вариантов реализации основной идеи поиска с запретами [4]. Приведем один из них, для которого удается установить асимптотические свойства. Рассмотрим рандомизированную окрестность N_p(i) Ì N(i), где каждый элемент окрестности j Î N(i) включается в множество N_p(i) с вероятностью p независимо от других элементов. С ненулевой вероятностью множество N_p(i) может совпадать с N(i), может оказаться пустым или содержать ровно один элемент. Общая схема алгоритма поиска с запретами может быть представлена следующим образом.

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

1. Выбрать начальное решение i₀ Î I и положить
f* : = f (i₀), Tabu_l (i₀) : = Æ , k : = 0.

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

   2.1. Сформировать окрестность N_p(i_k).

   2.2. Если Np(i_k) = Æ , то i_k+1 : = i_k, иначе найти i_k+1 такой, что      
          f(i_k+1) = min {f(j) | j Î N_p(i_k) \ Tabu_l (i_k)}.

   2.3. Если f ^* > f(i_k+1), то f ^* : = f(i_k+1).

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

Параметры p и l являются управляющими для данного алгоритма и выбор их значений зависит от размерности задачи и мощности окрестности. Примеры адаптации этой схемы к разным задачам комбинаторной оптимизации можно найти, например, в [3].

Литература

1. Glover F. Tabu search: part I. ORSA J. Comp. v1 (1989). pp 190–206.

2. Glover F. Tabu search: part II. ORSA J. Comp. v2 (1990). pp 4–32.

3. Glover F.(Ed.) Tabu search methods for optimization. Feature Issue of Europen J. Oper. Res. v106 (1998), N2–3.

4. Glover F., Laguna. M. Tabu search. Boston: Kluwer Acad. Publ. 1997.

Главная страница библиотеки  Демонстрационная версия Оптимизационные алгоритмы