背包问题实习报告

背包问题摘要：背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、嘲络信息安全等应用中具有重要的价值。从计算复杂性理论看，背包问题是一个经典NP难解问题。半个多世纪以来，该问题一直是算法与复杂性研究的热点问题之一。论文研究了背包问题的实用求解算法，提出了改进的新算法，并利用Maltab对几种算法进行了仿真实验，测试的结果显示出新算法在解决0／1背包问题时表现出了良好的性能。关键字：蚁群算法，背包问题，遗传算法，MATLAB引言背包问题(knapsackproblem，简称KP)是运筹学中一个典型的优化难题，在预算控制、项目选择、材料切割、货物装载等实践中有重要应用，并且还常常作为其他问题的子问题加以研究。随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中也起着重要的作用。背包问题的数学模型为：Maxƒ（21,xx…nx）＝jjnjxc12,1j…ｎts.nj1jjijbxa2,1i…1,0jixm式中，n为物品的编号：ｍ为资源的编号；jc为第j个物品的受益量；ib成为第i种资源的预算：ija为第ｊ个物品占用第i种资源的量：jx为o-1决策变量(当物品ｊ被选择时jx＝１否贝jx=0)。KP的语言描述可以这样：现有ｊ（ｊ=1，2，⋯，n)个物品，每个物品将会消耗m种资源啦ija=（1，2，⋯，m)，如果将物品ｊ装人背包将会获益q，与此同时，要求所有装入背包的物品消耗的资源I不能超过ib。背包问题可以衍生出一系列与之相关的优化问题，如有限背包问题(物体可具有相同价值和重量但数量是有限的)，无限背包问题(具有相同价值和重量的物体数量可以是无限的)，多背包问题(将物体装入多个容量不同的背包)等。本文中所指背包问题如无特殊说明，均指Fl的简单0／1背包问题。背包问题在实践中有广泛的应用背景。许多简单结构的有机组合构成了复杂结构，对简单问题的深入探索也使复杂问题的解决变得相对容易。在设计解决大量的复杂组合优化问题算法时，背包问题往往作为子问题出现。背包问题的算法改进，对复杂组合优化问题算法的改良是十分有益的。上面提到的各种类型的背包问题均属于NP难解问题类，意味着基于P≠NP的，无法找到多项式时间算法求得该类问题最优解。但大多数背包问题有拟多项式的时间算法，这意味着若系数规模有所界定，在可接受的时间内能够得到最优解。背包问题的应用背景促使人们对该问题计算方法进行了深入研究，背包问题的特有计算性质又使其应用领域不断得到拓展。KP属于组合最优化问题。一般的，最优化问题(optimizationpmblem)由目标函数(objectivefunction)N约束条件(constraints)两部分构成：Minimizeƒ)(xƒ（21,xx…nx）XSxxxSubjecttoxn),(21将满足所有约束条件的解空间S称为可行域(feasibleregion)，可行域中的解称为可行解(feasiblesolution)；将可行域中使目标函数最小的解称为最优解(optimals01ution)。对于最大化问题，可将目标函数乘以(－1)，转化为最小化问题求解。当X或S为离散集合构成的解空间时，这类最优化问题称为组合最优化问题(combinatorialoptimizationproblem)。严格意义上的最优解求取非常困难，研究高速近似的算法是一个重要的发展方向。对全局优化问题，目前存在确定性和非确定性两类方法。前者以Brianin的下降轨线法、Levy的隧道法和R．Ge的填充函数法为代表。该类方法虽然收敛快、计算效率高，但算法复杂，求得全局极值的概率不大。非确定性方法以Monte-Carlo。随机试验法、Hartman的多始点法、Solis和Wets的结合梯度信息的搜索方法、模拟退火法(simulatedannealing)等为代表。该类方法对目标函数要求低、容易实现、稳定性好，但收敛速度慢、求得全局极值的概率较低。对于背包问题。已有的求解方法可分为精确算法(盘日枚举法，动态规划法，分支定界法，图论法等指数级方法)和近似算法(如贪心算法，蚂蚁算法，遗传算法等)两大类。1.1背包问题的基本原理递归算法作为研究的基础，这里采用普通的递归算法对0／I背包问题进行求解。这种方法本身是一种深度优先的穷举算法，所以不适合大规模问题的求解。为了提高搜索效率，算法采用了一定的优化方法对搜索树进行剪枝，避免了一定程度的盲目搜索，提高了一些效率。算法首先对物品按照单位质量的价值大小(密度)进行排序，然后从前向后进行试探。程序运行过程中保存有当前找到的最优解。下次搜索时，若当前密度小于最优解的密度则程序退出当前循环，返回上一层循环继续搜索。利用这种方法，使得程序运行速度获得很大提高。本算法由两个程序组成：knaps主程序，用来进行参数的初始化。结果的显示等。search执行递归算法，求取结果。ffunction[xmax,pmax]=knaps(cl,pl,m1)%[xmax,pmax]=knaps(c1．pl，m1)%c1plarerawvectorg%mlisthe1imit%启动定时器tic;%保存当前最优解globalxmax;xmax=zeros(size(c1));globald;[d,xi]=sort([c1./pl]d=1./d;globalc;c=c1(xi);globalP;p=pl(xi);globalpmax;pmax=O;globalm;m=ml;t=search(xmax,0);[temp,i]=sort(xi);xmax=xmax(i);%输出结果disp(['timeconsuming：'hum2str(toc)'s'7]);disp(['maximumprice：'num2str(pmax)]);disp(['totalweight：'num2sir(xmax*cl')]);disp{['indicationofgoods：'int2str(x=xmax)]);return%递归函数functiony=search(x,i)globalc;globalp;globalm;globald;globalpmax;globalxmax;%判断结果ifi0,temp=x;temp(i)=1;dc=m-temp*c';ifdc0,ifx*p'pmax,pmax=x*p';xmax=x;y=1;returnendy=1;returnelseifdc*d(i)+x+p'pmaxY=-1;return;endifi==size(C,2),x(i)=1;ifx*p'pmax,pmax=x*p';xmax=x;endY=1;returnendx(i)=1;end%新的递归forj=i+1:Size(c,2),w=search(x,j);ifw==1;breakendendy=1;return2.1蚁群优化算法求解背包问题2.1.1蚁群算法介绍蚂蚁也许是大家最看不起的一种小昆虫，他们作为一个个体是很弱小的。韩愈有诗：蚍蜉撼大树，可笑不自量。但是它们作为一个整体具有无穷的力量。“千里之堤溃于蚁穴”其实是对它们所拥有的巨大能量的准确评价。它们的这种群体团结合作的精神令人钦佩。它们在寻食、御敌、筑巢(蚂蚁的筑窝，蜜蜂建巢)上的精巧令人惊叹。现代科学技术的发展在很多方面都依赖于仿生学的成就。通过对蚂蚁的研究，若能从它们身上学习到一些什么，也会是一件获益匪浅之事。关于蜜蜂觅食，人们已经做过很彻底地了解，它们是用飞行的舞姿(兜圈圈)来传递信息，圈子的轴方向表示花蜜的方向，用飞行的圈数表示有花蜜地方的距离，别的蜜蜂得此信号，就纷拥目该方向飞去。对蚂蚁觅食方法的研究，展现了另一个世界，当蚂蚁找到食物并将它搬回来时，就会在其经过的路径上留下一种“信息索”，其他蚂蚁嗅到信息素的“味道”，就沿充满信息素的路径奋勇直前。通过这种方式不但能找到食物，而且通常还是沿着最短的路径奔食物。20世纪90年代初意大利学者Dorigo，Maniezzo等提出的“蚂蚁算法(antcolonyalgorithm)”就是依照蚂蚁觅食的基本原理设计的一个群体智能的仿生算法。下面对其思想进行简要介绍。2.1.2简单的蚂蚁算法如前文所述，蚂蚁通过使用“信息素”的方式能很快地找到通向食物的最短路径，下面我们仔细地分析一下蚂蚁是如何找到这个最短路径的。设一群蚂蚁(随机地)向四面八方去觅食，当某只蚂蚁觅到食物时，一般就沿原路回巢，同时在归途上留下信息素，信息素随着向四周散发其浓度会不断下降。如图2．1所示，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．1一个真实蚂蚁世界的例子a)蚂蚁在A与E之间的路径上行走b)一个障碍物插入路径中，蚂蚁以等概率选择两条不同的道路c)在较短的道路上留下了较多的信息素下面我们要通过对上述真实蚂蚁世界进行仿真来得到简化的蚂蚁觅食模型。首先作以下假设：·人工蚂蚁具有一定程度的记忆·人工蚂蚁有一定的观察环境的能力·人T蚂蚁世界的时间是离散的考虑图2．2a，它是图2．1b的一种简化模型。假设D与H，B与H，B—C—D的距离都等于l，C位于D与B的正中间(如图2．2a所示)现在考虑离散的时间间隔：t=0，1，2，⋯。假设在每个单位时间内有30只蚂蚁从A爬到曰，同时有30只蚂蚁从E爬到D。每只蚂蚁在每个单位时间所爬行的距离为1。当爬行时蚂蚁在t时刻留下强度为l的信息素。为使这个例子尽可能简单，假设信息素在接下来的时间问隔(t+l，t+2)内完全蒸发掉。当t=0时，路径上没有信息素。在位置B与D处分别有30只蚂蚁。它们在选择道路时是完全随机的，因此平均有15只蚂蚁分别选择C与H(图2．2)。当t=l时，又有30只蚂蚁从A爬到B。发现了通向H的道路上信息素的强度为15(这是由从B开始走这条路的蚂蚁留下的)，通向C的道路的信息素强度为30(从B出发的15只蚂蚁与从D出发沿C到B的15只蚂蚁共同留下的)。如图2．2c所示，选择道路的概率发生了倾斜。选择通向C的道路的蚂蚁平均将比选择通向H的道路的蚂蚁多l倍。它们的数量之比为20：10。对于从E到达D的蚂蚁来说也是这样的。这个过程持续进行，直到最后所有的蚂蚁都选择最近的道路。这个思想是在给定位置蚂蚁必须从不同的道路中作出选择，那些先前曾被大量蚂蚁选择过的道路(这意味着具有很高的信息素强度)会以更高的概率被选择。进一步的说高信息素强度意味着它是一条捷径。图2．2一个人T蚂蚁的例子a)标明距离的原始图形b)t=0时，路径上没有信息素，蚂蚁以等概率选择两条不同的道路c)t=l时，在较短的道路上信息索较强，蚂蚁选择较短路径的概率更高2.1.3应用蚂蚁算法求解背包问题蚂蚁算法在解决TSPI'司题时采用的是一种比较自然的仿生方案。当用它来解背包问题时需要进行一定的改进使其能适应背包问题的特点。对于0／l背包问题利用蚂蚁算法求解的步骤如下；0／1背包问题每个变量仅取0和I两个值。网此，对每个变量设置2个蚂蚁(也可多于2个)，并记：jijff目标函数差值(2．6)其中，日标函数ƒ的形式己转化为：|},0min{|11iiniiinixwVMxp(2．7)(M为一充分大的正数)，即把原约束方程作为罚函数项加入原日标中。转移概率：kkkjjijp(2.8)其中kj理解为蚂蚁j的临域吸引强度优化过程借助蚂蚁从其初始状态(O或1的位置点)开始不断移动来进行：·当j0时，蚂蚁i按概率iP从j状态移至i状态，即相应的x变为1-x；·当j≤0时，蚂蚁i维持原状态。于是，解o_l背