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

Question

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

我在CP上找到了这个很棒的代码：

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

我相信我现在已经理解了所有的工作原理（除了Bolzman条件，就我而言，这是黑魔法，但我明白如何避免局部最优解，而这正是它所做的）。我想重新设计它来解决0-1背包问题。基本上，我要把5000个物品放入10个袋子中，并需要优化未使用空间最少的情况。实际的“分数”我分配给一个解决方案有点更复杂，但与算法无关。

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

对于我的问题，在第一次迭代中，我会选择10个随机对象并查看剩余空间。那么在下一个迭代中，我应该只选择10个新的随机对象吗？还是最好只交换其中几个对象，例如其中的一半或仅一个对象？或者交换的对象数量应该与温度有关？我认为这些都是可行的，但我想知道是否有人能提供一些关于最佳方法的建议（尽管一旦代码能够运作起来，我可以进行改进）。

谢谢！

迈克

- Mike Christensen

---

如果你每次把一个物体放进一个袋子里，那么你只需要找到可以装下10个最大物体的袋子。我不认为这就是你想要的。你能否让这更清晰些？ - Svante

这里，看一下我的通用SA实现（部分代码）。它是用Java编写的，但概念应该是可转移的。https://dev59.com/PnPYa4cB1Zd3GeqPmLAN#18657788 - mike

@mike - 谢谢，但我几年前就完成了这个项目。如果你对这个项目的用途感兴趣，请查看我的网站上的“我能做什么？”部分（http://www.kitchenpc.com）。 - Mike Christensen

我看到了日期，不过还是觉得你可能会感兴趣 :) ……有趣的应用。你优化的函数是什么，以便“适合最小溢出”的餐点？ - mike

@mike - 基本上，我正在尝试找到一种配方组合，可以使用购物车中的食材制作，需要最少的新食材，并尽可能多地使用现有的食材而不超过限额。此外，我想倾向于评分较高的食谱。这是一种修改过的SA实现，具有非常定制化的得分函数，可以沿着滑动比例工作。 - Mike Christensen

Answer 1

啊，我在维基百科上找到了答案。它建议移动到“邻居”状态，这通常意味着尽可能少地更改（例如，在TSM问题中交换两个城市）。

来源：http://en.wikipedia.org/wiki/Simulated_annealing “状态的邻居是通过某种特定方式改变给定状态而产生的问题的新状态。例如，在旅行商问题中，每个状态通常定义为要访问的城市的特定排列。某些特定排列的邻居是通过交换相邻城市对而产生的排列。为了找到相邻解决方案所采取的操作称为“移动”，不同的“移动”会产生不同的邻居。这些移动通常会导致解决方案的最小改变，如前面的例子所示，以帮助算法最大程度地优化解决方案，并保留已经最优的部分，并仅影响次优部分。在前面的例子中，解决方案的部分是旅游的部分。”

因此，我认为我的GetNextArrangement函数将希望用未使用的项目交换随机项目。

- Mike Christensen

Answer 2

使用模拟退火算法，您需要使相邻状态的能量尽可能接近。如果相邻状态的能量显著较大，则在没有非常高的温度下它将永远不会跳转到它们 -- 这将永远无法取得进展。另一方面，如果您可以想出利用低能态的启发式算法，然后就可以利用它们。

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

1.如果有适合放入空白空间的对象，则始终将最大的对象放入其中。

2.如果没有对象适合放在空白空间中，则选择要交换的对象 -- 但是更喜欢交换大小相似的对象。

也就是说，对象具有与其大小差异成反比的概率。您可能希望在此处使用类似于轮盘选择的东西，其中切片大小为（1 /（size1-size2）^ 2）。

- Michael Melanson