Поиск табу
Алгоритм локального поиска

Поиск с запретами (TS) — это метаэвристический метод поиска, использующий методы локального поиска , используемые для математической оптимизации . Он был создан Фредом В. Гловером в 1986 году [1] и формализован в 1989 году. [2] [3]

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

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

Реализация поиска с запретами использует структуры памяти, которые описывают посещенные решения или предоставленные пользователем наборы правил. [2] Если потенциальное решение уже посещалось в течение определенного краткосрочного периода или если оно нарушило правило, оно помечается как « табу » (запрещено), чтобы алгоритм не рассматривал эту возможность повторно.

Фон

Слово «табу» происходит от тонганского слова, обозначающего вещи, к которым нельзя прикасаться, поскольку они священны. [4]

Поиск с запретами — это метаэвристический алгоритм, который можно использовать для решения задач комбинаторной оптимизации (задач, где требуется оптимальный порядок и выбор вариантов).

Текущие приложения TS охватывают области планирования ресурсов , телекоммуникаций, проектирования СБИС , финансового анализа, планирования, планирования пространства, распределения энергии, молекулярной инженерии, логистики, классификации шаблонов , гибкого производства, управления отходами, разведки полезных ископаемых, биомедицинского анализа, охраны окружающей среды и множества других. В последние годы журналы в самых разных областях опубликовали учебные статьи и вычислительные исследования, документирующие успехи поиска с запретами в расширении границ проблем, которые могут быть решены эффективно — приводя к решениям, качество которых часто значительно превосходит то, что было получено с помощью ранее применявшихся методов. Полный список приложений, включая краткие описания достижений, достигнутых в результате практических реализаций, можно найти в [5]

Основное описание

Поиск с запретами использует локальную или соседнюю процедуру поиска для итеративного перехода от одного потенциального решения к улучшенному решению в окрестности , пока не будет удовлетворен некоторый критерий остановки (обычно это ограничение попыток или пороговое значение баллов). Процедуры локального поиска часто застревают в областях с низкими баллами или областях, где баллы выходят на плато. Чтобы избежать этих ловушек и исследовать области пространства поиска , которые остались бы неисследованными другими локальными процедурами поиска, поиск с запретами тщательно исследует окрестности каждого решения по мере продвижения поиска. Решения, допускаемые в новую окрестность, , определяются с помощью структур памяти. Используя эти структуры памяти, поиск продвигается путем итеративного перехода от текущего решения к улучшенному решению в . х {\displaystyle x} х ′ {\displaystyle x'} х {\displaystyle x} Н ∗ ( х ) {\displaystyle N^{*}(x)} х {\displaystyle x} х ′ {\displaystyle x'} Н ∗ ( х ) {\displaystyle N^{*}(x)}

Поиск табу имеет несколько сходств с имитацией отжига , поскольку оба предполагают возможные движения вниз. Фактически, имитацию отжига можно рассматривать как особую форму TS, в которой мы используем «градуированное владение», то есть движение становится табу с указанной вероятностью.

Эти структуры памяти формируют то, что известно как список табу, набор правил и запрещенных решений, используемых для фильтрации решений, которые будут допущены к соседству для исследования поиском. В своей простейшей форме список табу представляет собой краткосрочный набор решений, которые были посещены в недавнем прошлом (менее итераций назад, где — количество предыдущих решений, которые должны быть сохранены — также называется сроком действия табу). Чаще всего список табу состоит из решений, которые изменились в процессе перехода от одного решения к другому. Для простоты описания удобно понимать, что «решение» кодируется и представляется такими атрибутами. Н ∗ ( х ) {\displaystyle N^{*}(x)} н {\displaystyle n} н {\displaystyle n}

Типы памяти

Структуры памяти, используемые при табу-поиске, можно условно разделить на три категории: [6]

  • Краткосрочный: Список недавно рассмотренных решений. Если потенциальное решение появляется в списке табу, к нему нельзя вернуться, пока не истечет срок его действия.
  • В среднесрочной перспективе: правила интенсификации, направленные на смещение поиска в сторону перспективных областей поискового пространства.
  • В долгосрочной перспективе: правила диверсификации, направляющие поиск в новые регионы (например, в отношении сбросов, когда поиск застревает на плато или в неоптимальном тупике).

Краткосрочная, среднесрочная и долгосрочная память могут пересекаться на практике. В рамках этих категорий память может быть дополнительно дифференцирована по таким показателям, как частота и влияние внесенных изменений. Одним из примеров структуры среднесрочной памяти является та, которая запрещает или поощряет решения, содержащие определенные атрибуты (например, решения, которые включают нежелательные или желательные значения для определенных переменных) или структура памяти, которая предотвращает или побуждает определенные ходы (например, основанная на частоте памяти, применяемой к решениям, разделяющим общие черты с непривлекательными или привлекательными решениями, найденными в прошлом). В краткосрочной памяти выбранные атрибуты в недавно посещенных решениях помечаются как «активные с запретом». Решения, содержащие активные с запретом элементы, запрещены. Критерии стремления используются для отмены состояния табу решения, тем самым включая в противном случае исключенное решение в разрешенный набор (при условии, что решение «достаточно хорошее» в соответствии с мерой качества или разнообразия). Простой и часто используемый критерий стремления — разрешить решения, которые лучше, чем известное в настоящее время лучшее решение.

Кратковременной памяти может быть достаточно для достижения решений, превосходящих те, которые найдены обычными методами локального поиска, но для решения более сложных задач часто необходимы промежуточные и долгосрочные структуры. [7] Поиск с запретами часто сравнивают с другими метаэвристическими методами, такими как имитация отжига , генетические алгоритмы , алгоритмы оптимизации муравьиной колонии , оптимизация реактивного поиска, управляемый локальный поиск или жадный рандомизированный адаптивный поиск . Кроме того, поиск с запретами иногда сочетают с другими метаэвристиками для создания гибридных методов. Наиболее распространенный гибрид поиска с запретами возникает путем объединения TS с поиском рассеяния, [8] [9] классом процедур на основе популяции, который имеет общие корни с поиском с запретами и часто применяется при решении больших нелинейных задач оптимизации.

Псевдокод

Следующий псевдокод представляет собой упрощенную версию алгоритма поиска табу, описанного выше. Эта реализация имеет элементарную кратковременную память, но не содержит промежуточных или долговременных структур памяти. Термин «пригодность» относится к оценке решения-кандидата, воплощенной в целевой функции для математической оптимизации.

sBest ← s0  лучшийКандидат ← s0  tabuList ← []  tabuList . push ( s0 )пока ( не останавливаетCondition ())   sNeighborhood ← getNeighbors ( bestCandidate )   bestCandidateFitness ← - ∞   для ( sКандидата в sСоседстве )    если ( ( не tabuList . содержит ( sCandidate ))     и ( фитнес ( sКандидат ) > bestCandidateFitness ) )     bestCandidate ← sCandidate   bestCandidateFitness ← фитнес ( bestCandidate )   конец конец если ( bestCandidateFitness равен - ∞ )    перерыв ; конец если ( bestCandidateFitness > fitness ( sBest ))    sBest ← лучшийКандидат   конец tabuList . push ( лучший кандидат ) если ( tabuList . size > maxTabuSize )    tabuList . removeFirst () конецконецвернуться sBest

Строки 1–4 представляют некоторую начальную настройку, соответственно, создание начального решения (возможно, выбранного случайным образом), установка этого начального решения как лучшего из увиденных на сегодняшний день и инициализация списка табу с этим начальным решением. В этом примере список табу — это просто структура кратковременной памяти, которая будет содержать запись элементов посещенных состояний.

Основной алгоритмический цикл начинается в строке 5. Этот цикл будет продолжать поиск оптимального решения до тех пор, пока не будет выполнено указанное пользователем условие остановки (два примера таких условий — простое ограничение по времени или пороговое значение оценки пригодности). Соседние решения проверяются на наличие элементов табу в строке 9. Кроме того, алгоритм отслеживает лучшее решение в окрестности, которое не является табу.

Функция пригодности, как правило, является математической функцией, которая возвращает оценку или удовлетворяет критериям стремления — например, критерий стремления может рассматриваться как новое пространство поиска, найденное. [4] Если лучший локальный кандидат имеет более высокое значение приспособленности, чем текущий лучший (строка 18), он устанавливается как новый лучший (строка 19). Лучший локальный кандидат всегда добавляется в список табу (строка 21), и если список табу заполнен (строка 22), некоторым элементам будет разрешено истечь (строка 23). Как правило, элементы исчезают из списка в том же порядке, в котором они были добавлены. Процедура выберет лучшего локального кандидата (даже если у него худшая приспособленность, чем у текущего лучшего), чтобы избежать локального оптимума.

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

Пример: задача коммивояжера

Задача коммивояжера (TSP) иногда используется для демонстрации функциональности поиска с запретами. [7] Эта задача ставит простой вопрос: учитывая список городов, каков кратчайший маршрут, который посещает каждый город? Например, если город A и город B находятся рядом друг с другом, а город C находится дальше, общее пройденное расстояние будет короче, если города A и B будут посещены один за другим до посещения города C. Поскольку поиск оптимального решения является NP-трудным , методы аппроксимации на основе эвристики (такие как локальный поиск) полезны для разработки решений, близких к оптимальным. Чтобы получить хорошие решения TSP, необходимо использовать структуру графа. Ценность использования структуры задачи является повторяющейся темой в метаэвристических методах, и поиск с запретами хорошо подходит для этого. Класс стратегий, связанных с поиском с запретами, называемых методами цепочек выталкивания, позволил эффективно получать высококачественные решения TSP [10]

С другой стороны, простой поиск с запретами может быть использован для поиска удовлетворительного решения для задачи коммивояжера (то есть решения, которое удовлетворяет критерию адекватности, хотя и не с высоким качеством, полученным при использовании структуры графа). Поиск начинается с начального решения, которое может быть сгенерировано случайным образом или в соответствии с каким-либо алгоритмом ближайшего соседа . Для создания новых решений порядок посещения двух городов в потенциальном решении меняется местами. Общее расстояние путешествия между всеми городами используется для оценки того, насколько идеально одно решение по сравнению с другим. Чтобы предотвратить циклы, т. е. повторное посещение определенного набора решений, и чтобы не застрять в локальных оптимумах , решение добавляется в список запретов, если оно принято в окрестности решения, . Н ∗ ( х ) {\displaystyle N^{*}(x)}

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

Ссылки

  1. ^ Фред Гловер (1986). «Будущие пути целочисленного программирования и связи с искусственным интеллектом». Компьютеры и исследования операций . 13 (5): 533–549. doi :10.1016/0305-0548(86)90048-1.
  2. ^ ab Фред Гловер (1989). «Поиск с запретом – Часть 1». Журнал ORSA по вычислениям . 1 (2): 190–206. doi :10.1287/ijoc.1.3.190.
  3. ^ Фред Гловер (1990). «Поиск с запретами – Часть 2». Журнал ORSA по вычислениям . 2 (1): 4–32. doi :10.1287/ijoc.2.1.4.
  4. ^ ab "Курсы" (PDF) .
  5. ^ Ф. Гловер; М. Лагуна (1997). Tabu Search . Kluwer Academic Publishers. ISBN 978-1-4613-7987-4.
  6. ^ Фред Гловер (1990). "Tabu Search: A Tutorial". Интерфейсы .
  7. ^ ab M. Malek; M. Huruswamy; H. Owens; M. Pandya (1989). «Последовательные и параллельные методы поиска для задачи коммивояжера». Annals of OR: Linkages with Artificial Intelligence .
  8. ^ Ф. Гловер, М. Лагуна и Р. Марти (2000). «Основы поиска рассеяния и перераспределения путей». Управление и кибернетика . 29 (3): 653–684.
  9. ^ М. Лагуна и Р. Марти (2003). Scatter Search: Методология и реализация в C. Kluwer Academic Publishers. ISBN 9781402073762.
  10. ^ D. Gamboa, C. Rego & F. Glover (2005). «Структуры данных и цепочки выброса для решения крупномасштабных задач коммивояжера». European Journal of Operational Research . 160 (1): 154–171. CiteSeerX 10.1.1.417.9789 . doi :10.1016/j.ejor.2004.04.023. 
  • Визуализация алгоритма поиска Табу (Апплет)
  • Международная метаэвристическая конференция (MIC 2011) – Удине
  • Сообщество реактивного поиска Архивировано 2010-06-02 на Wayback Machine
  • Конференция LION по методам обучения и интеллектуальной оптимизации. Архивировано 08.11.2010 на Wayback Machine.
Получено с "https://en.wikipedia.org/w/index.php?title=Tabu_search&oldid=1236255373"