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

Табу-поиск - это метаэвристический метод поиска, использующий методы локального поиска, используемые для математической оптимизации . Он был создан Фредом В. Гловером в 1986 году и оформлен в 1989 году.

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

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

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

Задний план

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

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

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

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

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

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

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

Типы памяти

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

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

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


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

Псевдокод

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

sBest ← s0
bestCandidate ← s0
tabuList ← []
tabuList.push(s0)
while (not stoppingCondition())
    sNeighborhood ← getNeighbors(bestCandidate)
    bestCandidate ← sNeighborhood[0]
    for (sCandidate in sNeighborhood)
        if ( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) )
            bestCandidate ← sCandidate
        end
    end
    if (fitness(bestCandidate) > fitness(sBest))
        sBest ← bestCandidate
    end
    tabuList.push(bestCandidate)
    if (tabuList.size > maxTabuSize)
        tabuList.removeFirst()
    end
end
return sBest

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

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

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

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

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

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

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

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

Рекомендации

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