资源描述：
《蚁群算法求解多维0_1背包问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、CN43-1258/TP计算机工程与科学2006年第28卷第10期ISSN1007-130XCOMPUTERENGINEERING&SCIENCEVol128,No110,2006文章编号:1007-130X(2006)010-0078-02*蚁群算法求解多维0/1背包问题TheAntColonyAlgorithmforSolvingtheMultidimensional0/1KnapsackProblem熊伟清,魏平,王小权XIONGWe-iqing,WEIPing,WANGXiao-quan(宁波大学计算机科学与
2、技术研究所,浙江宁波315211)(InstituteofComputerScienceandTechnology,NingboUniversity,Ningbo315211,China)摘要:0/1背包问题是一类典型的组合优化问题,并且是NP-完全的问题,研究它具有很重要的意义。本文针对多维0/1背包问题的特点,设计了二进制编码的有向图,使得蚁群算法可以应用到背包问题上。仿真结果表明,该蚁群算法在求解多维0/1背包问题上的是相当出色的。Abstract:The0/1KnapsackProblemisofaclass
3、oftypicalcombinatorialoptimizationproblemsandisNP-complete.Ithasimportantmeaningstostudyit.Aimingatthecharacteristicsofthemultidimensional0/1knapsackproblem,abinarycodingdirectedgraphisdesigned,whichmakestheantcolonyalgorithmsuitablefortheKnapsackProblem.Thesim
4、ulationresultsshowthattheAntColonyAlgorithmisveryexcellentinsolvingthemultidimensional0/1knapsackproblem.关键词:蚁群算法;NP-完全问题;整数规划;背包问题Keywords:antcolonyalgorithm;NP-complete;integerprogramming;knapsackproblem中图分类号:TP311文献标识码:A1引言2多维背包问题的数学模型背包问题(KnapsackProblem)是典
5、型的组合优化问多维背包问题是带有一组约束的背包问题,其描述如题,它极大地吸引了理论研究人员和实际工作者的注意力。下:存在重量分别为W[1],W[2],,,W[n]和价值相应为理论方面研究兴趣来自于该问题简单的结构,这种特点既V[1],V[2],,,V[n]的n个物品以及负重为C[1],C[2],可以深入探索许多组合特性,又可以通过解决一系列背包,,C[m]的m个背包。要将尽量多的物品放入背包,在确子问题来最终求解更为复杂的优化问题。从实践的角度来保每个背包中物品不超出承重的前提下满足最大化背包中看,这些问题可以表述许
6、多工业场合的应用,最典型的应用物品的总价值。这里设X[i][j]为二进制变量。如果物品[1]如资金预算、货物装载、存储分配和密码加密等。i被放入背包j则X[i][j]=1,否则X[i][j]=0。则多维蚁群优化算法是20世纪90年代才提出的一种新型的背包问题的数学描述如下:[2,3]模拟进化算法,它是由意大利学者M.Dorigo等人首mn先提出的,称为蚁群系统(AntColonySystem),并应用该max=EEV[i]X[i][j]j=1i=1算法求解TSP问题、分配问题、Job-shop调度问题,取得了mmEX
7、[i][j][1,EW[i]X[i][j][C[j],X[i][j]I{0,1},i较好的结果。受其影响,蚁群系统模型逐渐引起研究者的j=1i=1注意,并用该方法求解一些实际问题。近几年,在欧、美召=1,2,,,n,j=1,2,,,m。因此,背包问题是一个特殊的开的有关会议上,蚁群优化算法已成为研究的热点之一。整数规划问题,也是一个NP难题。对于多维的背包问题,对此,我们在文中针对多维0/1背包问题的特点设计了基在确定一个物品最多只能放入一个背包条件满足下,它的mn于二进制编码的有向图遍历的蚂蚁算法。时间复杂度为O(
8、2)。在现实生活中,使用背包理论解决*收稿日期:2005-01-20;修订日期:2006-06-02基金项目:国家自然科学基金资助项目(60472099)作者简介:熊伟清(1966),男,浙江丽水人,副教授,研究方向为进化计算和软件工程。通讯地址:315211浙江省宁波市宁波大学计算机科学与技术研究所;Tel:(0574)87605806;E-
