背包问题的模拟退火算法

下面来介绍一下非常经典的背包问题及其用模拟退火算法实现的程序：

基本的背包向题,更复杂一些的比如:物品允许部分带走或者每类物品有多个等情况，在这个背包的例子中,假设有12件物品,质量分别为2磅、4磅、11磅、13磅、8磅、5磅、10磅、4磅、7磅、17磅、9磅、6磅,价值分别为8元、12元、3元、14元、9元、5元、6元、10元、7元、16元、17元、11元,包的最大允许质量是46磅。求解的方法如下：

1、在MATLAB的主界面编辑器中写入下列代码：

a = 0.85
k = [8;12;3;14;9;5;6;10;7;16;17;11];
k = -k;	% 模拟退火算法是求解最小值，故取负数
d = [2;4;11;13;8;5;10;4;7;17;9;6];
restriction = 46;
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;

while t>=tf
	for r=1:100
		%产生随机扰动
		tmp=ceil(rand.*num);
		sol_new(1,tmp)=~sol_new(1,tmp);
		
		%检查是否满足约束
		while 1
			q=(sol_new*d <= restriction);
			if ~q
                p=~p;	%实现交错着逆转头尾的第一个1
                tmp=find(sol_new==1);
                if p
                    sol_new(1,tmp)=0;
                else
                    sol_new(1,tmp(end))=0;
                end
            else
                break
			end
		end
		
		% 计算背包中的物品价值
		E_new=sol_new*k;
		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;
end

disp('最优解为：')
sol_best
disp('物品总价值等于：')
val=-E_best;
disp(val)
disp('背包中物品重量是：')
disp(sol_best * d)

2、命名保存至自定义路径下，点击运行，结果如下：

背包问题的模拟退火算法

此时，我们看到，最优解为

sol_best =

1 1 0 1 1 0 0 1 0 0 1 1

其中1表示放入，0表示不放入，而背包物品的总价值为81，总重量为46磅，基本解决了问题，请大家继续关注！！！

背包问题的模拟退火算法

相关推荐