Является ли Tabu Search стохастическим или детерминированным?

Я провожу сравнение двух инструментов проектирования охраняемых территорий, а именно Marxan и ConsNet, которые используют метаэвристические алгоритмы для решения версии проблемы минимального набора покрытия. Марксан использует имитацию отжига, а ConsNet - поиск по Табу. Хотя мой опыт работы в биологии, я думаю, что смог понять некоторые концепции оптимизации с помощью метаэвристики.

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

Вторая проблема, в руководстве ConsNet, следующее утверждение

Поиск является полностью детерминированным, но он может принимать решения о том, как действовать, основываясь на текущем состоянии архива решения или текущем состоянии цели

TS всегда детерминирован? Из некоторых источников я понял, что движения могут быть случайными, как в SA. Но есть и газеты, в которых говорится о "детерминированном поиске табу". Как детерминированный поиск табу узнает, какие шаги предпринять и как избежать локальной оптимизации? Иногда он должен принимать худшие решения, верно?

Спасибо заранее

Источник

1 ответ

Решение

Несколько вопросов, так что несколько ответов:)

  • Табу Поиск вылезает из местной оптимы, вот изображение, показывающее как. Он принимает худшие решения, если все улучшающие решения являются табу (и не устремлены), и либо все ходы были оценены, либо достигнут selectionLimit или acceptLimit.

  • И TS, и SA могут быть записаны как "воспроизводимые", что означает, что его повторный запуск даст одинаковые результаты. Я предполагаю, что это то, что хотел подразумевать, говоря "полностью детерминированный" (что является другим свойством). Хитрость для получения воспроизводимости проста: просто везде использовать один и тот же экземпляр Random и инициировать его с фиксированным randomSeed.

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

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

Примечание: я связан с OptaPlanner (Java, с открытым исходным кодом).

Источник
Другие вопросы по тегам