Табу поиск - Tabu search

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

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

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

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

Задний план

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

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

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

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

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

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

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

Типы памяти

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

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

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


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

Псевдокод

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

 1 sBest ← s0 2 лучший кандидат ← s0 3 tabuList ← [] 4 tabuList.От себя(s0) 5 в то время как (не stopCondition()) 6     Соседство ← getNeighbours(лучший кандидат) 7     лучший кандидат ← Соседство[0] 8     для (кандидат в Соседство) 9         если ( (не tabuList.содержит(кандидат)) и (фитнес(кандидат) > фитнес(лучший кандидат)) )10             лучший кандидат ← кандидат11         конец12     конец13     если (фитнес(лучший кандидат) > фитнес(sBest))14         sBest ← лучший кандидат15     конец16     tabuList.От себя(лучший кандидат)17     если (tabuList.размер > maxTabuSize)18         tabuList.removeFirst()19     конец20 конец21 вернуть sBest

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

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

Функция пригодности, как правило, представляет собой математическую функцию, которая возвращает балл или критерии стремления удовлетворены - например, критерий стремления может быть рассмотрен при обнаружении нового пространства поиска.[4]). Если лучший местный кандидат имеет более высокое значение пригодности, чем текущий лучший (строка 12), он устанавливается как новый лучший (строка 13). Местный лучший кандидат всегда добавляется в список запретов (строка 15), и если список запретов заполнен (строка 16), некоторым элементам будет разрешено истечь (строка 17). Как правило, элементы удаляются из списка в том же порядке, в котором они добавляются. Процедура выберет лучшего местного кандидата (хотя он имеет худшую пригодность, чем sBest), чтобы избежать локального оптимума.

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

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

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

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

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

использованная литература

  1. ^ Фред Гловер (1986). «Пути будущего для целочисленного программирования и связи с искусственным интеллектом». Компьютеры и исследования операций. 13 (5): 533–549. Дои:10.1016/0305-0548(86)90048-1.
  2. ^ а б Фред Гловер (1989). «Табу-поиск - Часть 1». Журнал ORSA по вычислительной технике. 1 (2): 190–206. Дои:10.1287 / ijoc.1.3.190.
  3. ^ Фред Гловер (1990). «Табу-поиск - Часть 2». Журнал ORSA по вычислительной технике. 2 (1): 4–32. Дои:10.1287 / ijoc.2.1.4.
  4. ^ а б "Курсы" (PDF).
  5. ^ Ф. Гловер; М. Лагуна (1997). Табу Поиск. Kluwer Academic Publishers. ISBN  978-1-4613-7987-4.
  6. ^ Фред Гловер (1990). «Поиск табу: Учебное пособие». Интерфейсы.
  7. ^ а б М. Малек; М. Хурусвами; Х. Оуэнс; М. Пандья (1989). «Методы последовательного и параллельного поиска для задачи коммивояжера». Annals of OR: Связь с искусственным интеллектом.
  8. ^ Ф. Гловер, М. Лагуна и Р. Марти (2000). «Основы точечного поиска и перенаправления путей». Управление и кибернетика. 29 (3): 653–684.
  9. ^ М. Лагуна и Р. Марти (2003). Scatter Search: методология и реализация на C. Kluwer Academic Publishers. ISBN  9781402073762.
  10. ^ Д. Гамбоа, К. Рего и Ф. Гловер (2005). «Структуры данных и цепочки выброса для решения крупномасштабных задач коммивояжера». Европейский журнал операционных исследований. 160 (1): 154–171. CiteSeerX  10.1.1.417.9789. Дои:10.1016 / j.ejor.2004.04.023.

внешние ссылки