1

我正在比较两个保护区设计工具，即Marxan和ConsNet，它们都使用元启发式算法来解决最小集覆盖问题的一个版本。Marxan 使用模拟退火，ConsNet 使用禁忌搜索。虽然我的背景是生物学，但我认为我能够通过元启发式掌握一些优化的概念。

但是，关于禁忌搜索，我还没有弄清楚两件事。首先是它如何逃避局部最优。我知道它不能逆转它的动作，这会阻止它循环，但我不知道是什么让它在找到它后留下局部最优值。我可以理解模拟退火是如何做到的——它有一定的概率接受一个更糟糕的解决方案，随着时间的推移它会减少，直到它不再接受一个更糟糕的解决方案——但我不知道 TS 是如何做到的。

第二个问题是，在ConsNet手册中，找到如下语句

搜索是完全确定性的，但它可以根据解决方案存档的当前状态或目标的当前状态来决定如何进行

TS 总是确定性的吗？通过阅读一些资料，我了解到移动可能是随机的，就像在 SA 中一样。但是后来有一些论文谈论“确定性禁忌搜索”。确定性禁忌搜索如何知道采取哪些行动以及如何摆脱局部最优？它有时必须接受更糟糕的解决方案，对吧？

提前谢谢了

4

1 回答 1

2

多个问题，所以多个答案:)

  • 禁忌搜索摆脱了局部最优，这里有一张图片展示了如何。如果所有改进的解决方案都是禁忌（而不是渴望），并且所有移动都已评估或已达到 selectionLimit 或 AcceptedLimit，它会接受更差的解决方案。

  • TS 和 SA 都可以写成“可重现的”，这意味着运行两次将产生相同的结果。我认为这就是说“完全确定性”（这是一个不同的属性）想要暗示的意思。获得可重复性的技巧很简单：只需在任何地方重用相同的 Random 实例并使用固定的 randomSeed 启动它。

  • TS 在向外扩展时，将无法在合理大小的数据集上评估每一步的所有可能移动。所以它也需要求助于随机选择。

  • TS、SA（以及就此而言的延迟接受）具有竞争力。这取决于性能最好的用例（这几乎是不可能提前预测的）。因此，所需的约束可能会影响性能最好的，但实际数据集的影响要小得多。

注意：我隶属于OptaPlanner（java，开源）。

于 2013-11-13T07:22:04.653 回答