4

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

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

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

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

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

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

谢谢！

麦克风

4

2 回答 2

3

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

来自：http ://en.wikipedia.org/wiki/Simulated_annealing

“一个州的邻居是在以某种特定方式改变给定状态后产生的问题的新状态。例如，在旅行商问题中，每个州通常被定义为要访问的城市的特定排列。某些特定排列的邻居是例如通过交换一对相邻城市而产生的排列。为找到相邻解决方案而改变解决方案所采取的行动称为“移动”，不同的“移动”会产生不同的邻居。这些移动通常会导致解决方案的最小变化，正如前面的例子所描述的，为了帮助算法最大限度地优化解决方案，同时保留解决方案中已经最优的部分，只影响次优部分。在前面的示例中，解决方案的部分是游览的部分。”

所以我相信我的 GetNextArrangement 函数想要用集合中未使用的项目交换随机项目..

于 2010-08-02T11:36:49.447 回答
3

通过模拟退火，您希望使相邻状态的能量尽可能接近。如果邻居有更大的能量，那么它就永远不会在没有非常高的温度的情况下跳到他们身边——高到它永远不会取得进展。另一方面，如果你能想出利用低能量状态的启发式方法，那么就利用它们。

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

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

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

于 2010-08-19T16:07:38.193 回答