如何在模拟退火中找到邻近的解决方案？
How to find neighboring solutions in simulated annealing?
我正在研究优化问题并尝试使用模拟退火作为启发式方法。我的目标是在给定成本函数的情况下优化 k 个对象的放置。解决方案采用一组 k 个有序对的形式，表示 M*N 网格中的点。在给定当前解决方案的情况下，我不确定如何最好地找到相邻的解决方案。我考虑过在随机方向上将每个点移动 1 或 0 个单位。给定当前点集，找到相邻解决方案的好方法是什么？
由于我也在尝试了解更多关于 SA 的信息，什么是好的邻居查找算法以及邻居应该与当前解决方案有多接近？此外，如果涉及随机性，为什么选择 "neighbor" 比生成随机解决方案更好？
我会将你的问题分成几个更小的问题：
- 此外，如果涉及随机性，为什么选择 "neighbor" 比生成随机解决方案更好？
通常，您从一个社区中选择 多个 个点，然后您可以探索所有这些点。例如，您随机生成 10 个点并选择最好的一个。通过这样做，您可以有效地探索更多可能的解决方案。
为什么它比随机猜测更好？好的解决方案往往有很多共同点（例如，它们在搜索中彼此接近 space）。因此，通过引入小的增量更改，您将能够找到一个好的解决方案，而随机猜测可能会将您带到完全不同的搜索部分 space，并且您将永远找不到合适的解决方案。而且由于 curse of dimensionality 随机跳跃并不比蛮力好 - 会有太多地方需要跳跃。
- 在给定当前点集的情况下，找到相邻解决方案的好方法是什么？
很遗憾的告诉你，这个问题一般情况下好像是无解的。 :( 它是艺术与科学的混合体。选择正确的方式来探索搜索 space 太具体了。即使是在不同约束下解决放置问题，不同的启发式方法也可能导致完全不同的结果。
您可以尝试以下操作：
- 按固定步数 (1,2...) 随机移动。这就是你的方法
- 交换两点
- 你可以记住一段时间不好的动作（类似于tabu search），所以接下来的 100 步你将只使用 'good' 个
- 使用贪婪方法生成次优布局，然后使用上述方法对其进行改进。
- 尝试随机重启。在某个阶段，放弃到目前为止的所有进展（目前最好的解决方案除外），提高温度并从随机初始点重新开始。您可以每 10000 步或类似的步骤执行此操作
- 修复一些问题。将一个物体放在点(x,y) 并且完全不要移动它，尝试在此约束下搜索最佳可能的解决方案。
- 禁止对象的某些组合，例如"distance between p1 and p2 must be larger than D".
- 以不同方式混合上述所有步骤
- 尝试了解您的问题的所有细节。您可以从您的问题描述中得出一些有用的 information/constraints/insights 。假设您 不能 解决一般的放置问题，因此请尝试将其简化为更具体的（== 更简单，== 使用更小的搜索 space）问题。
我会说最后一个项目符号是最重要的。仔细观察您的问题，仅考虑其 实用 方面。例如，你的问题的规模可能允许你列举一些东西，或者，也许，有些位置对你来说是不可能的，等等。 SA没有办法自己推导出这种领域特定的知识，所以帮助它！
如何理解你的启发式是好的？只能通过实际评价。准备一组具有 obvious/well-known 答案的体面测试，并尝试不同的方法。有的话就用知名的benchmark。
希望对您有所帮助。 :)
我正在研究优化问题并尝试使用模拟退火作为启发式方法。我的目标是在给定成本函数的情况下优化 k 个对象的放置。解决方案采用一组 k 个有序对的形式，表示 M*N 网格中的点。在给定当前解决方案的情况下，我不确定如何最好地找到相邻的解决方案。我考虑过在随机方向上将每个点移动 1 或 0 个单位。给定当前点集，找到相邻解决方案的好方法是什么？
由于我也在尝试了解更多关于 SA 的信息，什么是好的邻居查找算法以及邻居应该与当前解决方案有多接近？此外，如果涉及随机性，为什么选择 "neighbor" 比生成随机解决方案更好？
我会将你的问题分成几个更小的问题：
- 此外，如果涉及随机性，为什么选择 "neighbor" 比生成随机解决方案更好？
通常，您从一个社区中选择 多个 个点，然后您可以探索所有这些点。例如，您随机生成 10 个点并选择最好的一个。通过这样做，您可以有效地探索更多可能的解决方案。
为什么它比随机猜测更好？好的解决方案往往有很多共同点（例如，它们在搜索中彼此接近 space）。因此，通过引入小的增量更改，您将能够找到一个好的解决方案，而随机猜测可能会将您带到完全不同的搜索部分 space，并且您将永远找不到合适的解决方案。而且由于 curse of dimensionality 随机跳跃并不比蛮力好 - 会有太多地方需要跳跃。
- 在给定当前点集的情况下，找到相邻解决方案的好方法是什么？
很遗憾的告诉你，这个问题一般情况下好像是无解的。 :( 它是艺术与科学的混合体。选择正确的方式来探索搜索 space 太具体了。即使是在不同约束下解决放置问题，不同的启发式方法也可能导致完全不同的结果。
您可以尝试以下操作：
- 按固定步数 (1,2...) 随机移动。这就是你的方法
- 交换两点
- 你可以记住一段时间不好的动作（类似于tabu search），所以接下来的 100 步你将只使用 'good' 个
- 使用贪婪方法生成次优布局，然后使用上述方法对其进行改进。
- 尝试随机重启。在某个阶段，放弃到目前为止的所有进展（目前最好的解决方案除外），提高温度并从随机初始点重新开始。您可以每 10000 步或类似的步骤执行此操作
- 修复一些问题。将一个物体放在点(x,y) 并且完全不要移动它，尝试在此约束下搜索最佳可能的解决方案。
- 禁止对象的某些组合，例如"distance between p1 and p2 must be larger than D".
- 以不同方式混合上述所有步骤
- 尝试了解您的问题的所有细节。您可以从您的问题描述中得出一些有用的 information/constraints/insights 。假设您 不能 解决一般的放置问题，因此请尝试将其简化为更具体的（== 更简单，== 使用更小的搜索 space）问题。
我会说最后一个项目符号是最重要的。仔细观察您的问题，仅考虑其 实用 方面。例如，你的问题的规模可能允许你列举一些东西，或者，也许，有些位置对你来说是不可能的，等等。 SA没有办法自己推导出这种领域特定的知识，所以帮助它！
如何理解你的启发式是好的？只能通过实际评价。准备一组具有 obvious/well-known 答案的体面测试，并尝试不同的方法。有的话就用知名的benchmark。
希望对您有所帮助。 :)