OptaPlanner 中的爬山和禁忌搜索
Hill Climbing and Tabu Search in OptaPlanner
我正在使用 OptaPlanner 来解决一些规划问题。我阅读了文档，但不太确定爬山算法和禁忌搜索算法究竟是如何工作的。我不确定的是：
- 爬山选择只能选择比当前分数更好的最佳分数的动作，还是允许选择分数最高但不比当前分数差的动作？
- 如果没有移动导致与当前得分更好或相等的解决方案，禁忌搜索是否允许选择比当前得分更差的移动？
对于爬山，参见HillClimbingAcceptor#isAccepted(...)。它接受得分比最新步数高 或等于 的任何移动。并查看爬山的默认 forager 配置（在 LocalSearchPhaseConfig 中，表示 foragerConfig.setAcceptedCountLimit(1);），一旦接受 1 个移动，它就是获胜的移动。
对于 Tabu Search，它将 select 得分较差的移动，如果：
- 在每步selects的步数中（通常
acceptedCountLimit配置为1000左右），没有看到更好的步法
- 或者所有确实能带来更好分数的动作都在禁忌列表中（它们是 "taboo to use"）。对于 solutionTabu，这意味着可以保证它们不会导致新的最佳解决方案（但 solutionTabu 是无用的）。对于 entityTabu 没有这样的 100% 保证，但是如果你有超过 50 个变量（如果你有 1000+ 个变量，则更多）。 ]
PS：爬山很烂。没有充分的理由不使用延迟接受或禁忌搜索。
PPS: 使用Benchmarker，让HC, LA, TS, ...互相对抗。它会给你很多见解。
我正在使用 OptaPlanner 来解决一些规划问题。我阅读了文档，但不太确定爬山算法和禁忌搜索算法究竟是如何工作的。我不确定的是：
- 爬山选择只能选择比当前分数更好的最佳分数的动作，还是允许选择分数最高但不比当前分数差的动作？
- 如果没有移动导致与当前得分更好或相等的解决方案，禁忌搜索是否允许选择比当前得分更差的移动？
对于爬山，参见HillClimbingAcceptor#isAccepted(...)。它接受得分比最新步数高 或等于 的任何移动。并查看爬山的默认 forager 配置（在 LocalSearchPhaseConfig 中，表示 foragerConfig.setAcceptedCountLimit(1);），一旦接受 1 个移动，它就是获胜的移动。
对于 Tabu Search，它将 select 得分较差的移动，如果：
- 在每步selects的步数中（通常
acceptedCountLimit配置为1000左右），没有看到更好的步法 - 或者所有确实能带来更好分数的动作都在禁忌列表中（它们是 "taboo to use"）。对于 solutionTabu，这意味着可以保证它们不会导致新的最佳解决方案（但 solutionTabu 是无用的）。对于 entityTabu 没有这样的 100% 保证，但是如果你有超过 50 个变量（如果你有 1000+ 个变量，则更多）。 ]
PS：爬山很烂。没有充分的理由不使用延迟接受或禁忌搜索。
PPS: 使用Benchmarker，让HC, LA, TS, ...互相对抗。它会给你很多见解。