c++ - 具有实值最大化的模拟退火

Question

我正在研究模拟退火，试图解决背包问题，因此我必须最大化适应性(包中元素的值(value))。

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. 在数组中使用实数值时，我如何在执行期间告诉系统前一个解决方案接近最大边界，因为在我当前的实现中，我在第一步中连续生成随机值，重复该步骤直到系统冷却。

最后，也许我的实现中存在一些巨大的错误，如果能帮助我解决这个问题，我将不胜感激

Answer 1

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

你的第一个问题:

In step 2 when performing swapping, currently I am swapping elements of the array. Is it correct? Or should I keep track of the previous solution and swap current element (i) with previous solution element? (This is just an idea).

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

见下文presentation

z Gradual cooling of liquid …

• At high temperatures, molecules move freely
• At low temperatures, molecules are "stuck"

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

2) Perform random swapping of values in the 5D array above.

以下是您应该如何实现逐渐冷却。

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

你的第二个问题:

When using real values in the array how can I tell the system during execution that the previous solution was close to the max boundary

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