用C#编写0-1背包的模拟退火算法

我正在学习模拟退火算法，并且有一些关于如何修改示例算法来解决 0-1 背包问题的问题。

我在CP上发现了这段很棒的代码：

http://www.codeproject.com/KB/recipes/simulatedAnnealingTSP.aspx http://www.codeproject.com/KB/recipes/simulatedAnnealingTSP.aspx

我很确定我现在了解这一切是如何运作的（除了整个玻尔兹曼条件，就我而言，这是黑魔法，尽管我了解如何逃避局部最优，显然这正是这样做的）。我想重新设计它来解决 0-1 背包“ish”问题。基本上，我将 5,000 个物体中的一个放入 10 个麻袋中，并且需要优化以尽量减少未使用的空间。我分配给解决方案的实际“分数”有点复杂，但与算法无关。

这看起来很容易。这意味着 Anneal() 函数基本相同。我必须实现 GetNextArrangement() 函数才能满足我的需求。在 TSM 问题中，他只是沿着路径交换两个随机节点（即，他每次迭代都进行非常小的更改）。

对于我的问题，在第一次迭代中，我会随机选择 10 个对象并查看剩余空间。对于下一次迭代，我会选择 10 个新的随机对象吗？或者我最好只交换一些对象，比如一半，甚至只交换其中一个？或者也许我换出的物体数量应该与温度有关？这些对我来说似乎都是可行的，我只是想知道是否有人对最佳方法有一些建议（尽管一旦我让代码工作，我可以进行改进）。

Thanks!

Mike

通过模拟退火，您希望使相邻态的能量尽可能接近。如果邻居有明显更大的能量，那么如果没有非常高的温度，它就永远不会跳到它们那里——温度足够高，以至于它永远不会取得进展。另一方面，如果你能想出利用低能态的启发法，那就利用它们。

对于 TSP 来说，这意味着交换相邻城市。对于您的问题，我建议使用以下条件邻居选择算法：

1. 如果有适合空白空间的物体，那么它总是将最大的物体放入其中。
2. 如果空白处没有适合的对象，则选择一个对象进行交换 - 但更喜欢交换大小相似的对象。

也就是说，物体的概率与其大小差异成反比。您可能想在这里使用轮盘赌选择之类的东西，切片大小类似于 (1 / (size1 - size2)^2)。