Запретный поиск

запретный поиск

Табу-поиск был предложен Фредом Гловером в 1986 году (диаграммы для которого вы найдете в раскрытии алгоритма). Метод использует память (или несколько памяти), которая обновляется и используется во время поиска.

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

запретный список

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

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

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

Поток алгоритма

запретный поиск

запретный поиск

 с  с0
Лучший  с
tabuList  []
пока (нет остановкаСостояние())
   список кандидатов  []
   лучший кандидат  нулевой
   за (sКандидат в sОкрестности)
      если ( (нет tabuList.содержит(sКандидат)) 
      а также (фитнес(sКандидат) > фитнес(лучший кандидат)) )
         лучший кандидат  sКандидат
      конец, если
   конец для
   с  лучший кандидат
   если (фитнес(лучший кандидат) > фитнес(Лучший))
      Лучший  лучший кандидат
   конец, если
   tabuList.толкать(лучший кандидат);
   если (tabuList.размер > maxTabuSize)
      tabuList.removeFirst()
   конец, если
еИ пока
возвращаться сБес

Пример приложения

Возьмем пример коммивояжера (TSP). Учитывая набор городов, мы знаем расстояние между всеми парами городов. Цель состоит в том, чтобы посетить каждый город, один за другим, пока не вернетесь в первый город, при этом сводя к минимуму общее пройденное расстояние.

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

Район построен движением. Движение состоит из удаления двух дуг, чтобы «пересечь» их. Например, пара дуг <(а,в), (д,б)> СТАНОВИТСЯ <(а,д), (в,б)>. Таким образом, гамильтонов цикл сохраняется. Затем мы «убрали» дуги и «добавили» дуги.

Чтобы не повторять одно и то же движение, вводим два табу-списка: В содержащие удаленные дуги (а, в) и (д, б); ВНЕ содержащие добавленные дуги (а, д) и (в, б). К каждой итерации запрещенные движения: ввести дугу В и снимите бант с ВНЕ. Здесь запрет бесконечен.

Табу-поиск TSP

Делиться
ru_RURU
%d такие блоггеры, как: