资源描述：
《基于交换策略的蚁群算法求解多维0_1背包问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、计算机与现代化2008年第3期JISUANJIYUXIANDAIHUA总第151期文章编号:10062475(2008)03008303基于交换策略的蚁群算法求解多维01背包问题潘夏福,倪子伟(厦门大学信息科学与技术学院,福建厦门361005)摘要:在项目决策与规划、资源分配、货物装载等工作中,提出了多维01背包问题,对这一问题,国内外学者提出了许多算法。本文推广了文献[7]中求解单维01背包问题的蚁群算法,并从结合2opt等局部优化的蚁群算法求解旅行商问题中得到启示:通过交换策略可以加快算法的收敛速度和获取更
2、高质量的解,因此提出了基于交换策略的蚁群算法。再[8]把这种算法与AIAACA算法进行比较,实验结果显示该算法与AIAACA算法效果相当,用时更少,是求解多维01背包问题的有效算法。关键词:多维01背包问题;蚁群算法;交换中图分类号:TP301文献标识码:AAntColonyAlgorithmforSolvingMultidimensional01KnapsackProblemBasedonExchangeStrategyPANXiafu,NIZiwei(CollegeofInformationScienc
3、eandTechnology,XiamenUniversity,Xiamen361005,China)Abstract:Multidimensional01knapsackproblemoftenappearsindecisionmakingandprogramming,resourcedistribution,loading,andsoon.Forsolvingthisproblem,manyalgorithmshavebeenproposedbyscholars.Thispaperextendstheantcolony
4、[7]algorithmwhichisusedforsolving01knapsackprobleminreference,andgetsenlightenmentfromtheantcolonyalgorithmwith2optlocaloptimizationforsolvingtravelingsalesmanproblems:Exchangestrategycanmakethealgorithmhavefasterconvergencerateandgetbetterqualitysolution.Sothisp
5、aperpresentstheantcolonyalgorithmbasedonexchangestragegy.ComparedwithAIAACAalgorithm,experimentresultsdemonstratethatthealgorithmproposedinthispaperhasthesameresultbuttheruntimeisshorter.Sothisalgoritmisratherefficientforsolvingmultidimensional01knapsackproblem.Ke
6、ywords:multidimensional01knapsackproblem;antcolonyalgorithm;exchange值为vj(j=1,2,,n)的物品,m个容积大小为ci(i0引言=1,2,,m)的容器,第j个物品占用第i个容器的容积大小为bij。现在问题是:选择哪些物品装入这m多维01背包问题是一类经典组合优化NP完全问题[1]。如货物装载、资源分配等许多有实用价值个容器使得装入总价值最大。其严格数学描述为:n的问题,都可以转化为背包问题。求解多维01背包maxf(x1,x2,,xn)=
7、vj!xjj=1问题有许多种传统方法,如隐枚举法、分支定界法等,n在求解较大规模问题时大多存在计算量大、迭代时间s..tbij!xjci(i=1,2,,m)(1)j=1长的弱点。本文提出一种基于交换策略的蚁群算法,xi∀{0,1}(i=1,2,,n)能够有效解决多维01背包问题,并具有较好性能。式中f(x1,x2,,xn)为目标函数;n为物品数量;m1问题描述为容器数量;vj为第j个物品的价值;ci为第i个容器的容积;bij为第j个物品占用第i个容器的容积大小;xj为对一个m维01背包问题可描述为:已知几个价0
8、1变量,当物品j被选择装入时xj=1,否则xj=0。收稿日期:20070403作者简介:潘夏福(1981),男,海南文昌人,厦门大学信息科学与技术学院硕士研究生,研究方向:智能算法;倪子伟(1954),男,福建泉州人,副教授,硕士,研究方向:智能算法。84计算机
