Альпинизм и Табу Поиск в OptaPlanner

Question

Я использую OptaPlanner для решения некоторых задач планирования. Я прочитал документацию и не совсем уверен, как именно работают алгоритмы Hill Climbing и Tabu Search. В чем я не уверен, так это:

• пики для подъема на холм движутся только с ЛУЧШИМ счетом, который ЛУЧШЕ, чем текущий, или он позволяет выбирать ходы с ЛУЧШИМ счетом, который НЕ Хуже, чем текущий?
• Позволяет ли поиск в табу выбирать ходы, у которых показатель WORSE больше, чем у текущего, если нет хода, ведущего к решению с лучшим или равным счетом к текущему?

Answer 1

Скалолазание смотрите HillClimbingAcceptor#isAccepted(...), Он принимает любой ход, у которого оценка выше или равна величине последнего шага. И глядя на конфигурацию фуражера по умолчанию для подъема на гору (в LocalSearchPhaseConfig, который говорит foragerConfig.setAcceptedCountLimit(1);), как только 1 ход принят, это выигрышный ход.

Для поиска по Табу он выберет ходы с худшим счетом, если:

• в количестве ходов, которые он выбирает за шаг (обычно acceptedCountLimit настроен на 1000 или около того), лучшего движения не видно
• ИЛИ все ходы, которые приводят к лучшему счету, находятся в списке табу (они "табу для использования"). Для SolutionTabu это означает, что есть гарантия, что они не приведут к новому лучшему решению (но SolutionTabu бесполезен). Для entityTabu такой гарантии 100% нет, но вы получите лучшие результаты примерно в 99.99999999999999999999999999999999999999999999999999999999999999999999999999999% случаев, если у вас более чем, скажем, 50+ переменных (и больше, если у вас более 1000 переменных).

PS: Скалолазание отстой. Там никогда не было веских причин, чтобы не использовать Late Acceptance или Tabu Search вместо этого.

PPS: Используйте Benchmarker, пусть HC, LA, TS, ... сражаются друг с другом. Это даст вам много понимания.