用C#编写0-1背包的模拟退火算法
我正在学习模拟退火算法，并且有一些关于如何修改示例算法来解决 0-1 背包问题的问题。
我在 CP 上找到了这段很棒的代码：
http://www.codeproject.com/KB/ Recipes/simulatedAnnealingTSP.aspx
我很确定我现在了解这一切是如何工作的（除了整个玻尔兹曼条件，就我而言，这是黑魔法，尽管我了解如何逃避局部最优，显然这确实如此）正是如此）。我想重新设计它来解决 0-1 背包“ish”问题。基本上，我将 5,000 个物体中的一个放入 10 个麻袋中，并且需要优化以尽量减少未使用的空间。我分配给解决方案的实际“分数”有点复杂，但与算法无关。
这看起来很容易。这意味着 Anneal() 函数基本相同。我必须实现 GetNextArrangement() 函数才能满足我的需求。在 TSM 问题中，他只是沿着路径交换两个随机节点（即，他每次迭代都进行非常小的更改）。
对于我的问题，在第一次迭代中，我会随机选择 10 个对象并查看剩余空间。对于下一次迭代，我会只选择 10 个新的随机对象吗？或者我最好只交换一些对象，比如一半，甚至只交换其中一个？或者也许我换出的物体数量应该与温度有关？这些对我来说似乎都是可行的，我只是想知道是否有人对最佳方法有一些建议（尽管一旦我让代码工作，我可以进行改进）。
谢谢！
麦克风
I'm in the process of learning about simulated annealing algorithms and have a few questions on how I would modify an example algorithm to solve a 0-1 knapsack problem.
I found this great code on CP:
http://www.codeproject.com/KB/recipes/simulatedAnnealingTSP.aspx
I'm pretty sure I understand how it all works now (except the whole Bolzman condition, as far as I'm concerned is black magic, though I understand about escaping local optimums and apparently this does exactly that). I'd like to re-design this to solve a 0-1 knapsack-"ish" problem. Basically I'm putting one of 5,000 objects in 10 sacks and need to optimize for the least unused space. The actual "score" I assign to a solution is a bit more complex, but not related to the algorithm.
This seems easy enough. This means the Anneal() function would be basically the same. I'd have to implement the GetNextArrangement() function to fit my needs. In the TSM problem, he just swaps two random nodes along the path (ie, he makes a very small change each iteration).
For my problem, on the first iteration, I'd pick 10 random objects and look at the leftover space. For the next iteration, would I just pick 10 new random objects? Or am I best only swapping out a few of the objects, like half of them or only even one of them? Or maybe the number of objects I swap out should be relative to the temperature? Any of these seem doable to me, I'm just wondering if someone has some advice on the best approach (though I can mess around with improvements once I have the code working).
Thanks!
Mike
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
通过模拟退火，您希望使相邻态的能量尽可能接近。如果邻居有明显更大的能量，那么如果没有非常高的温度，它就永远不会跳到它们那里——温度足够高，以至于它永远不会取得进展。另一方面，如果你能想出利用低能态的启发法，那就利用它们。
对于 TSP 来说，这意味着交换相邻城市。对于您的问题，我建议使用一种条件邻居选择算法，如下所示：
也就是说，物体的概率与其大小差异成反比。您可能想在这里使用轮盘赌选择之类的东西，切片大小类似于 (1 / (size1 - size2)^2)。
With simulated annealing, you want to make neighbour states as close in energy as possible. If the neighbours have significantly greater energy, then it will just never jump to them without a very high temperature -- high enough that it will never make progress. On the other hand, if you can come up with heuristics that exploit lower-energy states, then exploit them.
For the TSP, this means swapping adjacent cities. For your problem, I'd suggest a conditional neighbour selection algorithm as follows:
That is, objects have a probability inverse to the difference in their sizes. You might want to use something like roulette selection here, with the slice size being something like (1 / (size1 - size2)^2).
啊，我想我在维基百科上找到了答案。它建议转移到“邻居”状态，这通常意味着尽可能少地改变（就像在 TSM 问题中交换两个城市）。
来自：http://en.wikipedia.org/wiki/Simulated_annealing
“一个状态的邻居是该状态的新状态以某种特定方式改变给定状态后产生的问题，例如，在旅行推销员问题中，每个状态通常被定义为要访问的城市的特定排列，某些特定排列的邻居是以下排列。例如，通过交换一对相邻的城市来改变解决方案以找到相邻的解决方案所采取的行动称为“移动”，不同的“移动”会导致不同的邻居。正如前面的例子所描述的，为了帮助算法最大限度地优化解，同时保留解中已经最优的部分，只影响次优的部分。在前面的示例中，解决方案的部分就是游览的部分。”
因此，我相信我的 GetNextArrangement 函数会想要用集合中未使用的项目替换随机项目。
Ah, I think I found my answer on Wikipedia.. It suggests moving to a "neighbor" state, which usually implies changing as little as possible (like swapping two cities in a TSM problem)..
From: http://en.wikipedia.org/wiki/Simulated_annealing
"The neighbours of a state are new states of the problem that are produced after altering the given state in some particular way. For example, in the traveling salesman problem, each state is typically defined as a particular permutation of the cities to be visited. The neighbours of some particular permutation are the permutations that are produced for example by interchanging a pair of adjacent cities. The action taken to alter the solution in order to find neighbouring solutions is called "move" and different "moves" give different neighbours. These moves usually result in minimal alterations of the solution, as the previous example depicts, in order to help an algorithm to optimize the solution to the maximum extent and also to retain the already optimum parts of the solution and affect only the suboptimum parts. In the previous example, the parts of the solution are the parts of the tour."
So I believe my GetNextArrangement function would want to swap out a random item with an item unused in the set..