模拟退火算法中如何找到相邻解？

Question

模拟退火算法中如何找到相邻解？

algorithmoptimizationsimulated-annealing

4

我正在研究一项优化问题，并尝试使用模拟退火作为启发式方法。我的目标是通过某个成本函数来优化放置k个物体的位置。解决方案采用k个有序对表示M*N网格中的点。我不确定如何在给定当前解的情况下最好地找到相邻的解。我考虑过将每个点随机向一个方向移动1或0个单位。在给定一组当前点的情况下，找到相邻的解的好方法是什么？

由于我也想了解更多关于SA的知识，那么什么样的邻居查找算法比较好？相邻解与当前解的距离应该有多远？此外，如果涉及到随机性，为什么选择“邻居”比生成随机解更好呢？

- Joel Abraham

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- CaptainTrunky · Accepted Answer

我会将你的问题分成几个小问题：

此外，如果涉及到随机性，为什么选择“邻居”比生成随机解更好呢？

通常，您从邻域中选择多个点，并且可以探索它们所有。例如，您随机生成10个点并选择最佳点。通过这样做，您可以有效地探索更多可能的解决方案。

为什么它比随机猜测更好？良好的解决方案往往有许多共同之处（例如，在搜索空间中它们彼此靠近）。因此，通过引入小的增量变化，您将能够找到一个好的解决方案，而随机猜测可能会将您发送到完全不同的搜索空间的另一部分，并且您永远找不到适当的解决方案。由于维度诅咒的存在，随机跳跃并不比暴力搜索更好-要跳跃的位置太多了。

在给定当前点集的情况下，可能是找到相邻解决方案的好方法是什么？

很抱歉告诉你，这个问题似乎总体上是无法解决的。 :( 这是艺术和科学的结合体。选择正确的方式来探索搜索空间太过特定于问题。即使在处理不同约束条件下的放置问题时，不同的启发式方法也可能导致完全不同的结果。

您可以尝试以下方法：

随机移动一定步数（1，2...）。这是您的方法
交换两个点
可以记忆一段时间内的不良移动（类似于禁忌搜索），因此您将在接下来的100个步骤中仅使用“好”的移动
使用贪婪方法生成次优放置，然后使用上述方法进行改进。
尝试随机重启。在某个阶段，放弃迄今为止所有进展（除了迄今为止最佳解决方案），提高温度并从随机初始点重新开始。您可以每10000个步骤或类似的方式执行此操作
固定某些点。将对象放置在点（x，y）处，完全不移动它，尝试在此约束条件下搜索最佳解决方案。
禁止某些对象组合，例如“p1和p2之间的距离必须大于D”。
以不同的方式混合以上所有步骤
尝试在最微小的细节中理解问题。您可以从问题描述中推导出一些有用的信息/约束/见解。假设您无法普遍解决放置问题，因此尝试将其缩小到更具体（==更简单，==搜索空间更小）的问题。

我认为最后一点是最重要的。仔细观察您的问题，只考虑其实际方面。例如，您的问题规模可能允许您枚举某些内容，或者某些位置对您来说不可行等等。SA无法自己推导出这样的领域特定知识，所以请帮助它！

如何理解您的启发式方法是否有效？只有通过实际评估。准备一个合理的测试集，其中包含明显/已知的答案，并尝试不同的方法。如果有任何著名的基准，请使用它们。

希望这对您有所帮助。 :)