optaplanner - OptaPlanner 中的爬山和禁忌搜索

Question

我正在使用 OptaPlanner 来解决一些规划问题。我阅读了文档，但我不太确定爬山和禁忌搜索算法究竟是如何工作的。我不确定的是：

• 爬山选择是否只移动具有比当前更好的最佳分数的移动，或者它是否允许选择具有不比当前更差的最佳分数的移动？
• 禁忌搜索是否允许选择得分比当前得分更差的动作，如果没有动作导致解决方案的得分高于或等于当前得分？

Answer 1

对于爬山，请参阅HillClimbingAcceptor#isAccepted(...)。它接受任何得分高于或等于最后一步得分的移动。并查看爬山的默认觅食配置（在 中LocalSearchPhaseConfig，其中表示foragerConfig.setAcceptedCountLimit(1);），一旦接受 1 步，即是获胜步。

对于禁忌搜索，如果出现以下情况，它将选择得分较低的动作：

• 在每步选择的移动次数中（通常acceptedCountLimit配置为1000左右），没有看到更好的移动
• 或者所有确实导致更好分数的动作都在禁忌列表中（它们是“禁忌使用”）。对于 solutionTabu，这意味着可以保证它们不会导致新的最佳解决方案（但 solutionTabu 是无用的）。对于 entityTabu，没有这样的 100% 保证，但是如果您有超过 50 个变量（如果您有 1000 个以上变量），您将在大约 99.9999999999999999999999999999999999999999999999999999% 的情况下获得更好的结果。

PS：爬山很烂。没有理由不使用延迟接受或禁忌搜索。

PPS：使用 Benchmarker，让 HC、LA、TS、... 互相对抗。它会给你很多洞察力。