资源描述：
《基于蚁群算法求解01背包问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、大庆石油学院学报第29卷第3期2005年6月JOURNALOFDAQINGPETROLEUMINSTITUTEVol.29No.3Jun.2005基于蚁群算法求解0/1背包问题刘华蓥,林玉娥,刘金月(大庆石油学院计算机与信息技术学院,黑龙江大庆163318)摘要:阐述了蚁群算法的基本原理,根据求解TSP问题的蚁群系统模型及转移概率公式,修改了蚁群算法模型,给出了适用于0/1背包问题的模型.通过实验测试改进的算法,结果表明,改进算法的收敛速度得到提高.关键词:蚁群算法;信息素;背包问题;禁忌表;标识表中图分类号:TP301.6文献标识码:A文章编号:10001891(20
2、05)03005904n0/1背包问题是典型的组合优化问题,直接的枚举搜索可能遍历问题的所有2个解,因此其计算复n杂度为O(2).背包问题在生产管理中有重要的应用,如资源分配、投资决策、装载等均可建模为背包问题.蚁群算法是由意大利学者DorigoM和Maniez-zoV提出的一种新型的模拟进化算法,称之为蚁群系[1]统.蚁群算法已成功地应用于求解旅行商、二次指派、排序等问题.笔者对蚁群算法模型做适当的修改,使之成为适于0/1背包问题的模型,仿真实验证实了该算法的有效性.1蚁群算法的基本原理蚁群算法是模仿真实的蚁群行为而提出的一种模拟进化算法.蚂蚁之间是通过一种称为信息素
3、(Pheromone)的物质传递信息的,蚂蚁在运动过程中能够在经过的路径上留下该种物质,而且能够感知这种物质的存在及其强度,并以此指导自己的运动方向.因此,由大量蚂蚁组成的集体行为便表现出一种信息正反馈现象:某一条路径上走过的蚂蚁越多,该路径上留下的信息素就越多,则后来者选择该路径的概[2]率就越大.蚂蚁个体之间就是通过这种信息素的交流,搜索到一条从蚁巢到食物源的最短路径.2蚁群系统模型蚁群算法已成功地解决了TSP问题,以求解平面上n个城市的TSP问题为例说明蚁群系统模型.TSP问题就是寻找通过n个城市各一次且最后回到出发点的最短封闭路径.TSP问题的目标函数为n-1m
4、inDtotal=6d(i,i+1)+d(n,1),(1)i=1式中:d(i,j)(i,j=1,2,⋯,n)表示城市i和城市j之间的距离.求解TSP问题的蚁群系统模型为:设m为蚂蚁数量,n为城市数量,t时刻i城市与j城市间的路径ij上的信息素密度为τij(t),其初值为很小的正数C.在t时刻每只蚂蚁将根据转移概率公式移动到下一个城市,时间将变为t+1,经过n次这样的移动,时间变为t+n.当每只蚂蚁都完成一次循环,所有蚂蚁走过的封闭路径中最短的一条路径将被记录下来.其转移概率公式为αβτij(t)ηij(t),j
5、tabu(k),αβpi,j(k)=6τis(t)ηis(
6、t)(2)s
7、tabu(k)0,j∈tabu(k),式中:ηij(t)为路径长度的倒数,表示由城市i转移到城市j的期望程度;τij(t)ηij(t)为该路径单位长度的收稿日期:20041029;审稿人:吴雅娟;编辑:陆雅玲作者简介:刘华蓥(1969-),女,硕士,副教授,主要从事人工智能及应用方面的研究.·59·©1994-2006ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net大庆石油学院学报第29卷2005年信息素;α,β分别表示第k只蚂蚁在运动过程
8、中积累的信息及启发式因子在蚂蚁选择路径中所起的不同作用;tabu(k)(k=1,2,⋯,m)是一个禁忌表,其长度为n,用以记录蚂蚁k所走过的城市,并随时间做动态调整.蚂蚁k将根据式(2)计算下一步所有可选择城市的概率pi,j(k),概率最大的城市即为下一步选择的城市,并把该城市j置入tabu(k)中.当所有的城市都被放入tabu(k)中,则蚂蚁k的一次循环结束.当所有的蚂蚁完成一次循环,则各城市之间路径上的信息素密度按下式更新:mτij(t+n)=ρτij(t)+6Δτij(k),(3)k=1式中:ρ表示路径上信息素的保留程度;Δτij(k)表示第k只蚂蚁在本次循环中留
9、在路径ij上的信息素增量,计算式为Q/Lk,第k只蚂蚁在本次循环中经过了ij路径,Δτij(k)=(4)0,第k只蚂蚁在本次循环中未经过ij路径,式中:Q是常数;Lk是第k只蚂蚁的旅行距离.蚂蚁将按式(2)选择城市,最终形成一条封闭路径.当所有的蚂蚁完成闭合路径选择后,则一次迭代结束,利用全局信息素更新规则更新路径的信息量,再开始下一次的迭代,直至收敛或达到最大迭代次数.3背包问题的数学描述背包问题在数学中实际上是一个0-1规划问题.假设有n个物品,其质量及价值分别为wi和ci(wi>0,ci>0,i=1,2,⋯,n),背包的容量假设为v
