0

我正在研究模拟退火，试图解决背包问题，我必须最大化适应度（包中物品的价值）。

float weight[5]={2, 3, 5, 4, 3}; // weight
float value[5]={10, 20, 15, 25, 5}; // value of corresponding item
float bagSize = 11.0;

通过硬计算，我们知道最好的解决方案是{1,1,0.4,1,0}。但是我没有得到这个解决方案。

我将用伪代码解释我的 c++ 代码，以避免这里的所有长代码。

While (temperate > 1){
  1) Generate random values between (0,1) to fill the 5 sized array for each item
  2) Perform random swapping of values in the 5D array above.
  3) Calculate the fitness and new weight
  4) Save the best solution. 
}

基本上这是我的代码。我的问题

  1. 在执行交换的第 2 步中，目前我正在交换数组的元素。这是对的吗？还是我应该跟踪以前的解决方案并将当前元素 (i) 与以前的解决方案元素交换？（这只是一个想法）。
  2. 当在数组中使用实际值时，我如何在执行期间告诉系统先前的解决方案接近最大边界，因为在我当前的实现中，我在第一步中连续生成随机值，该随机值重复直到系统冷却。

最后，也许我的实现中有一些巨大的错误，如果我能在这个问题上得到帮助，我真的很感激

4

1 回答 1

2

您的伪代码不是模拟退火。您在没有任何目标的情况下随机跳跃搜索空间。

你的第一个问题：

在执行交换的第 2 步中，目前我正在交换数组的元素。这是对的吗？还是我应该跟踪以前的解决方案并将当前元素 (i) 与以前的解决方案元素交换？（这只是一个想法）。

您应该实现一个名为 perturb 的函数。这个扰动应该交换你的数组值。模拟退火，顾名思义使用退火的概念。这意味着你开始很热。你的扰动函数会剧烈地改变值。然后你的解决方案开始冷却，这意味着你的扰动函数只会改变一点值。

请参阅以下演示文稿

z 液体逐渐冷却……

  • 在高温下，分子自由移动
  • 在低温下，分子被“卡住”

根据您的解决方案，您可以在下一行中获得随机性。

2) 对上面的 5D 数组中的值进行随机交换。

这是您应该如何实施逐渐冷却的方法。

  • 2a) int MaxRandomValueToAddToArrayValues = 20;
  • 2b）我是如何找到 20 的，它是领域知识。根据您的价值观和最佳解决方案，20 似乎很有价值。
  • 2c) 使用此边界执行上述 5D 数组中的值的随机交换
  • 2d) 逐渐减少 MaxRandomValueToAddToArrayValues。例如，对于每 10 次迭代，您可以将其减少 0.1。

你的第二个问题：

在数组中使用实际值时，如何在执行期间告诉系统先前的解决方案接近最大边界

您无法知道您的解决方案是否接近最大边界。您只能知道您的解决方案比以前的解决方案更好。如果我们能知道最大边界，为什么要实施 SA 或任何其他启发式方法。知道最佳解决方案是不可能或非常昂贵的（用你的话最大边界），因此我们使用启发式解决方案。

于 2013-11-05T08:37:59.537 回答