01背包问题的模拟退火算法
话说王二狗家里着火了，现在他要把家里头值钱的东西一次性搬出去。但是他体力有限，最多只能扛得动36千克的东西。现在他家里的物品价值如下14;27;42;18;33;24;55;36;28;46;87;29。其中每件物品对应的重量如下3;6;8;4;7;5;12;8;5;7;17;5。
有的物品很有价值但是太笨重，有的物品很轻但是价值不是那么大。下面问题来了，二狗怎样做才能尽可能多的将自己家的东西抢救出去呢？
这就是经典的01背包问题，下面我们用模拟退火算法优化，得到最优的选择。模拟退火算法来源于固体退火的原理，学过物理的都知道。当一个高温物体温度逐渐降低时。固体内部的粒子由无序状态逐渐变成有序状态。粒子的能量也越来越低。跳动的能力也越来越弱。
下面是优化的效果图
在实际的优化算法中，存在局部最优解和全局最优解，局部最优解不一定是全局最优解，但是搜索算法往往容易陷入局部最优解。
在全局寻优中，我们需要粒子（解）的活动范围尽可能大，而不需要其在某个局部最优解附近精确搜索，避免陷入局部最优。而在到达全局最优解以后，我们需要在这个解附近精确搜索，得到更优的值。这就需要粒子的跳动能力弱，以免跳出全局最优解。
通过模拟退火，可以将这两者精确地结合到一起。
模拟退火的两个核心问题就是目标函数和产生新解。
a = 0.9;
value = [14;27;42;18;33;24;55;36;28;46;87;29];
value = -value;
weight = [3;6;8;4;7;5;12;8;5;7;17;5];
limit = 36;
num = 12;先将物品的价值和重量储存在变量中。我们用1表示带走这件东西，0表示不带走这件东西。sol_new为初始化的解。limit表示最多能带走36千克物品。E_current和E_best都设置为无限大（为了方便后面的优化）。
sol_new = ones(1,num);
E_current = inf;E_best = inf;
% E_current是当前解对应的目标函数值
% E_new是新解的目标函数值；
% E_best是最优解的
sol_current = sol_new;
sol_best = sol_new;
t0=97; tf=3; t=t0;
p=1;
y=zeros(1,10000);
j=1接下来，我们在一个while循环中进行模拟退火运算。在程序刚开始时，t比较高。sol非常容易跳出局部最优解。这样可以尽可能避免陷入局部最优解而无法跳出来。另一方面，随着退火的进行，温度t越来越低，exp(-(E_new-E_current)./t)就越来越小，程序跳出这个搜索范围的可能性就越小。有利于精确搜索。轮盘赌就是实现精确搜索与粗略大范围搜索的关键。
while t>=tf
for r=1:5
%产生新解,随机选择两个数反转。
new=randperm(num,2);
sol_new(new(1))=~sol_new(new(1));
sol_new(new(2))=~sol_new(new(2));
%检查是否能搬出去，如果不能，修改到能反转为止
while 1
q=(sol_new*weight <= limit);%检查是否能搬出去
if ~q
new=randperm(num,2);
sol_new(1,new(1))=~sol_new(1,new(1));
sol_new(1,new(2))=~sol_new(1,new(2));
else
break
end
end
% 计算背包中的物品价值
E_new=sol_new*value;
if E_new<E_current
E_current=E_new;
sol_current=sol_new;
if E_new<E_best
% 把冷却过程中最好的解保存下来
E_best=E_new;
sol_best=sol_new;
end
else
if rand<exp(-(E_new-E_current)./t)
E_current=E_new;
sol_current=sol_new;
else
sol_new=sol_current;
end
end
end
t=t.*a;
y(j)=-E_best;
j=j+1;
end为了产生新解，我们在物品中随机选择两个进行反转，如果新解的重量超过了36kg。我们再进行随机反转。直到符合要求为止。
然后计算这些物品的价值（利用了矩阵）。与先前的解比较，如果现在的解更优，就用现在的解代替原来的最优解。否者用轮盘赌的方式决定是否接受这个解。
完整的代码如下
a = 0.9;
value = [14;27;42;18;33;24;55;36;28;46;87;29];
value = -value;
weight = [3;6;8;4;7;5;12;8;5;7;17;5];
limit = 36;
num = 12;
sol_new = ones(1,num);
E_current = inf;E_best = inf;
% E_current是当前解对应的目标函数值
% E_new是新解的目标函数值；
% E_best是最优解的
sol_current = sol_new;
sol_best = sol_new;
t0=97; tf=3; t=t0;
p=1;
y=zeros(1,10000);
j=1
while t>=tf
for r=1:5
%产生新解,随机选择两个数反转。
new=randperm(num,2);
sol_new(new(1))=~sol_new(new(1));
sol_new(new(2))=~sol_new(new(2));
%检查是否能搬出去，如果不能，修改到能反转为止
while 1
q=(sol_new*weight <= limit);%检查是否能搬出去
if ~q
new=randperm(num,2);
sol_new(1,new(1))=~sol_new(1,new(1));
sol_new(1,new(2))=~sol_new(1,new(2));
else
break
end
end
% 计算背包中的物品价值
E_new=sol_new*value;
if E_new<E_current
E_current=E_new;
sol_current=sol_new;
if E_new<E_best
% 把冷却过程中最好的解保存下来
E_best=E_new;
sol_best=sol_new;
end
else
if rand<exp(-(E_new-E_current)./t)
E_current=E_new;
sol_current=sol_new;
else
sol_new=sol_current;
end
end
end
t=t.*a;
y(j)=-E_best;
j=j+1;
end
j=j-1;
disp('最优解为：')
sol_best
disp('物品总价值等于：')
val=-E_best;
disp(val)
disp('物品重量是：')
disp(sol_best * weight)
x=1:j;
y=y(1:j);
plot(x,y)本文作者：南海一号