背包问题实习报告

1、背包问题 摘要：背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、嘲络信息安全等应用中具有重要的价值。从计算复杂性理论看，背包问题是一个经典NP难解问题。半个多世纪以来，该问题一直是算法与复杂性研究的热点问题之一。论文研究了背包问题的实用求解算法，提出了改进的新算法，并利用Maltab对几种算法进行了仿真实验，测试的结果显示出新算法在解决01背包问题时表现出了良好的性能。关键字：蚁群算法，背包问题，遗传算法，MATLAB引言背包问题(knapsackproblem，简称KP)是运筹学中一个典型的优化难题，在预算控制、项目选择、材料切割、货物装载等实践中有重要应用，并且还常常作为其他问

2、题的子问题加以研究。随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中也起着重要的作用。背包问题的数学模型为：Max（）式中，n为物品的编号：为资源的编号；为第j个物品的受益量；成为第i种资源的预算：为第个物品占用第i种资源的量：为o-1决策变量(当物品被选择时否贝=0)。KP的语言描述可以这样：现有（=1，2，n)个物品，每个物品将会消耗m种资源啦=（1，2，m)，如果将物品装人背包将会获益q，与此同时，要求所有装入背包的物品消耗的资源I不能超过。背包问题可以衍生出一系列与之相关的优化问题，如有限背包问题(物体可具有相同价值和重量但数量是有限的)，无限背包问题(具有相同价值和重量的

3、物体数量可以是无限的)，多背包问题(将物体装入多个容量不同的背包)等。本文中所指背包问题如无特殊说明，均指Fl的简单01背包问题。背包问题在实践中有广泛的应用背景。许多简单结构的有机组合构成了复杂结构，对简单问题的深入探索也使复杂问题的解决变得相对容易。在设计解决大量的复杂组合优化问题算法时，背包问题往往作为子问题出现。背包问题的算法改进，对复杂组合优化问题算法的改良是十分有益的。上面提到的各种类型的背包问题均属于NP难解问题类，意味着基于PNP的，无法找到多项式时间算法求得该类问题最优解。但大多数背包问题有拟多项式的时间算法，这意味着若系数规模有所界定，在可接受的时间内能够得到最优解。背包问

4、题的应用背景促使人们对该问题计算方法进行了深入研究，背包问题的特有计算性质又使其应用领域不断得到拓展。KP属于组合最优化问题。一般的，最优化问题(optimizationpmblem)由目标函数(objective function)N约束条件(constraints)两部分构成：（）将满足所有约束条件的解空间S称为可行域(feasible region)，可行域中的解称为可行解(feasible solution)；将可行域中使目标函数最小的解称为最优解(optimal solution)。对于最大化问题，可将目标函数乘以(1)，转化为最小化问题求解。当X或S为离散集合构成的解空间时，这类最

5、优化问题称为组合最优化问题(combinatorial optimization problem)。严格意义上的最优解求取非常困难，研究高速近似的算法是一个重要的发展方向。对全局优化问题，目前存在确定性和非确定性两类方法。前者以Brianin的下降轨线法、Levy的隧道法和RGe的填充函数法为代表。该类方法虽然收敛快、计算效率高，但算法复杂，求得全局极值的概率不大。非确定性方法以Monte-Carlo。随机试验法、Hartman的多始点法、Solis和Wets的结合梯度信息的搜索方法、模拟退火法(simulated annealing)等为代表。该类方法对目标函数要求低、容易实现、稳定性好，但

6、收敛速度慢、求得全局极值的概率较低。对于背包问题。已有的求解方法可分为精确算法(盘日枚举法，动态规划法，分支定界法，图论法等指数级方法)和近似算法(如贪心算法，蚂蚁算法，遗传算法等)两大类。1.背包问题的基本原理递归算法递归算法对01背包问题进行求解。这种方法本身是一种深度优先的穷举算法，所以不适合大规模问题的求解。为了提高搜索效率，算法采用了一定的优化方法对搜索树进行剪枝，避免了一定程度的盲目搜索，提高了一些效率。算法首先对物品按照单位质量的价值大小(密度)进行排序，然后从前向后进行试探。程序运行过程中保存有当前找到的最优解。下次搜索时，若当前密度小于最优解的密度则程序退出当前循环，返回上一

7、层循环继续搜索。利用这种方法，使得程序运行速度获得很大提高。knaps主程序，用来进行参数的初始化。结果的显示等。search执行递归算法，求取结果。functionxmax,pmax=knaps(cl,pl,m1)%xmax,pmax=knaps(c1pl，m1)%c1 pl are raw vectorg%ml is the 1imit%启动定时器tic;%保存当前最优解global xmax;xmax=zeros(size(c1);global d;d,xi=sort(c1./pld=1./d;global c;c=c1(xi);global P;p=pl(xi);global pmax

8、;pmax=O;global m;m=ml;t=search(xmax,0);temp,i=sort(xi);xmax=xmax(i);%输出结果disp(time consuming：hum2str(toc)s 7);disp(maximum price：num2str(pmax);disp(total weight： num2sir(xmax*cl);dispindication of goods：int2str(x=xmax);return%递归函数function y=search(x,i)global c;global p;global m;global d;global pmax;

9、global xmax;%判断结果if i0,temp=x;temp(i)=1;dc=m-temp*c;if dcpmax, pmax=x*p; xmax=x; y=1; return end y=1; returnelseif dc*d(i)+x+ppmax, pmax=x*p; xmax=x; end Y=1; return end x(i)=1;end%新的递归forj=i+1:Size(c,2),w=search(x,j);if w=1; break endendy=1;return2.蚁群优化算法求解背包问题2.1蚁群算法介绍蚂蚁也许是大家最看不起的一种小昆虫，他们作为一个个体是很弱

10、小的。韩愈有诗：蚍蜉撼大树，可笑不自量。但是它们作为一个整体具有无穷的力量。“千里之堤溃于蚁穴”其实是对它们所拥有的巨大能量的准确评价。它们的这种群体团结合作的精神令人钦佩。它们在寻食、御敌、筑巢(蚂蚁的筑窝，蜜蜂建巢)上的精巧令人惊叹。现代科学技术的发展在很多方面都依赖于仿生学的成就。通过对蚂蚁的研究，若能从它们身上学习到一些什么，也会是一件获益匪浅之事。关于蜜蜂觅食，人们已经做过很彻底地了解，它们是用飞行的舞姿(兜圈圈)来传递信息，圈子的轴方向表示花蜜的方向，用飞行的圈数表示有花蜜地方的距离，别的蜜蜂得此信号，就纷拥目该方向飞去。对蚂蚁觅食方法的研究，展现了另一个世界，当蚂蚁找到食物并将它

11、搬回来时，就会在其经过的路径上留下一种“信息索”，其他蚂蚁嗅到信息素的“味道”，就沿充满信息素的路径奋勇直前。通过这种方式不但能找到食物，而且通常还是沿着最短的路径奔食物。 20世纪90年代初意大利学者Dorigo，Maniezzo等提出的“蚂蚁算法(antcolony algorithm)”就是依照蚂蚁觅食的基本原理设计的一个群体智能的仿生算法。下面对其思想进行简要介绍。2.2简单的蚂蚁算法 如前文所述，蚂蚁通过使用“信息素”的方式能很快地找到通向食物的最短路径，下面我们仔细地分析一下蚂蚁是如何找到这个最短路径的。 设一群蚂蚁(随机地)向四面八方去觅食，当某只蚂蚁觅到食物时，一般就沿原路回巢

12、，同时在归途上留下信息素，信息素随着向四周散发其浓度会不断下降。如图21所示，A为蚁巢位置，E为食物源位置。若有蚂蚁找到食物，会沿原路返回。当蚁巢与食物源中出现一个障碍物时，蚂蚁在两条不同的道路中间随机选择一条。由于A-C-E比A-H-E短，所以路径A-C-E上留下的信息素会比路径A-C-E上的多。蚂蚁选择信息素多的路径的概率大于信息素少的路径的概率。因此选择路径A-C-E的蚂蚁要比选择A-H-E的蚂蚁多。这样，选择A-C-E的蚂蚁越来越多而选择A-H-E的蚂蚁越来越少。最后，所有蚂蚁都选择了A-C-E（最短路径)。 图2.2 .1 一个真实蚂蚁世界的例子 a)蚂蚁在A与E之间的路径上行走 b

13、)一个障碍物插入路径中，蚂蚁以等概率选择两条不同的道路 c)在较短的道路上留下了较多的信息素下面我们要通过对上述真实蚂蚁世界进行仿真来得到简化的蚂蚁觅食模型。首先作以下假设：人工蚂蚁具有一定程度的记忆人工蚂蚁有一定的观察环境的能力人T蚂蚁世界的时间是离散的 考虑图22.2a，它是图2.2.1b的一种简化模型。假设D与H，B与H，BCD的距离都等于l，C位于D与B的正中间(如图22a所示)现在考虑离散的时间间隔：t=0， 1，2，。假设在每个单位时间内有30只蚂蚁从A爬到曰，同时有30只蚂蚁从E爬到D。每只蚂蚁在每个单位时间所爬行的距离为1。当爬行时蚂蚁在t时刻留下强度为l的信息素。为使这个例子

14、尽可能简单，假设信息素在接下来的时间问隔(t+l，t+2)内完全蒸发掉。 当t=0时，路径上没有信息素。在位置B与D处分别有30只蚂蚁。它们在选择道路时是完全随机的，因此平均有15只蚂蚁分别选择C与H(图2.2.2)。 当t=l时，又有30只蚂蚁从A爬到B。发现了通向H的道路上信息素的强度为15(这是由从B开始走这条路的蚂蚁留下的)，通向C的道路的信息素强度为30(从B出发的15只蚂蚁与从D出发沿C到B的15只蚂蚁共同留下的)。如图2.2.2c所示，选择道路的概率发生了倾斜。选择通向C的道路的蚂蚁平均将比选择通向H的道路的蚂蚁多l倍。它们的数量之比为20：10。对于从E到达D的蚂蚁来说也是这样

15、的。 这个思想是在给定位置蚂蚁必须从不同的道路中作出选择，那些先前曾被大量蚂蚁选择过的道路(这意味着具有很高的信息素强度)会以更高的概率被选择。进一步的说高信息素强度意味着它是一条捷径。 图2.2.2 一个人T蚂蚁的例子a)标明距离的原始图形b)t=0时，路径上没有信息素，蚂蚁以等概率选择两条不同的道路 c)t=l时，在较短的道路上信息索较强，蚂蚁选择较短路径的概率更高2.3应用蚂蚁算法求解背包问题 蚂蚁算法在解决TSPI司题时采用的是一种比较自然的仿生方案。当用它来解背包问题时需要进行一定的改进使其能适应背包问题的特点。对于0l背包问题利用蚂蚁算法求解的步骤如下； 01背包问题每个变量仅取0

16、和I两个值。网此，对每个变量设置2个蚂蚁(也可多于2个)，并记： 目标函数差值 (1)其中，日标函数的形式己转化为： (2)(M为一充分大的正数)，即把原约束方程作为罚函数项加入原日标中。转移概率： (3)其中理解为蚂蚁j的临域吸引强度优化过程借助蚂蚁从其初始状态(O或1的位置点)开始不断移动来进行：当0时，蚂蚁i按概率从j状态移至i状态，即相应的x变为1-x；当0时，蚂蚁i维持原状态。于是，解0-1背包问题的蚂蚁算法过程可归纳为：Begin nc=0;(nc为迭代次数)初始化：While nci预定的迭代次数 将备蚂蚁置于相应变量的0，1位置点； 按转移概率(式3)移动各蚂蚁；记录当前的最佳

17、蚂蚁位置；end数值实验表明，蚂蚁优化算法在解决01背包问题上表现出了很好的性能。在计算中将每个变量处设两个以上的蚂蚁后，计算结果没有明显改善。这与蚂蚁算法在TSP等组合优化问题上的表现截然不同。需要作进一步的研究以使蚂蚁算法在解决背包问题上发挥更大的作用。 图23 蚂蚁算法适应值增长曲线在0，1上随机生成100个物体的重量、价值数据，V=5；运行10次取平均值，采用不同参数的蚂蚁算法适应值增长如图23所示。两条曲线是分别将每个变量处设1个与2个蚂蚁后得到的。例：基于蚁群算法的0-1背包问题（1）运行结果如下图所示（程序见附录）。 需要注意，最优方案并不唯一，但最优结果为81（最大价值）。（2

18、）500只蚂蚁（m=500）分别迭代100、200、300、400、500次的结果如下表所示：（3）100、200、300、400、500只蚂蚁分别迭代100次的结果如上图所示：（4）程序如下：V=20;15;18;14;8;4;10;%各物体对应的价值矩阵Q=5;5;2;6;12;2;4;%各物体对应的质量矩阵n=size(V,1)%n表示问题的规模（物体的个数）Alpha=1;Beta=5;Rho=0.1;H=100;%各参数值D=zeros(n,n);%D表示完全图的赋权邻接矩阵for i=1:n for j=1:n if i=j D(i,j)=V(i,1)/Q(j,1); else D

19、(i,j)=eps; %i=j时不计算，应该为0，但后面的启发因子要取倒数， 故用eps（浮点相对精度）表示 end D(j,i)=D(i,j); %对称矩阵 endendm=500;%蚂蚁的数量Eta=1./D;%Eta为启发因子，这里设为倒数Tau=ones(n,n); %Tau为信息素矩阵Tabu=zeros(m,n); %存储并记录价值比的生成Delta_Tau=zeros(n,n);NC=1; NC_max=100;%迭代计数器，记录迭代次数，次数从1开始while NC=rand); %若计算的概率大于原来的概率，则选择这个过程，find找的是坐标 to_visit=J(Selec

20、t(1); %可能找到多个，选第一个 Tabu(i,j)=to_visit; %下一步选择哪个物体，将其放入禁忌 end end %第四步，信息素更新 z=zeros(1,m); KK=; for i=1:m k=1; while(k25) KK=KK,k; k=8; else k=k+1; end end end W=zeros(m,7); KK=KK-1; for i=1:m W(i,1:KK(i)=Tabu(i,1:KK(i); end V1=zeros(1,m); for i=1:m for k1=1:KK(i) V1(i)=V1(i)+V(Tabu(1,k1); end end %第五步，确定最大价值 V2=max(V1); %最大价值 zy=find(V1=V2); zy1=zy(1); for k3=1:KK(zy1)-1 Delta_Tau(Tabu(zy1,k3),Tabu(zy1,k3+1)=Delta_Tau(Tabu(zy1,k3),Tabu(zy1,k3+1)+H; end Tau(Tabu(zy1,k3),Tabu(zy1,k3+1)=(1-Rho).*Tau(Tabu(zy1,k3),Tabu(zy1,k3+1)+Delta_Tau(Tabu(zy1,k3),Tabu(zy1,k3+1); %考虑到信