Табу-поиск

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

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

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

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

Предыстория

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

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

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

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

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

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

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

Виды памяти

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

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

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

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

Псевдокод

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

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

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

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

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

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

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

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

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

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

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

• Визуализация алгоритма поиска Табу (Applet)
• Международная метаэвристическая конференция (MIC 2011) – Удине
• Сообщество реактивного поиска. Архивировано 2 июня 2010 г. на Wayback Machine.
• Конференция LION по методам обучения и интеллектуальной оптимизации. Архивировано 8 ноября 2010 г. в Wayback Machine.