多维背包问题的一个蚁群优化算法.doc

PAGE PAGE 2 多维背包问题的一个蚁群优化算法 摘 要 蚁群优化(ACO)是一种通用的启发式方法,已被用来求解很多离散优化问题.近年来,已提出几个ACO算法求解多维背包问题(MKP).这些算法虽然能获得较好的解但也耗用太多的CPU时间.为了降低用ACO求解MKP的复杂性,本文基于一种已提出但未实现过的MKP的信息素表示定义了新的选择概率的规则和相应的基于背包项的一种序的启发式信息,从而提出了一种计算复杂性较低、求解性能较好的改进型蚁群算法.试验结果表明,无论串行执行还是虚拟并行执行,在计算相同任务时,新算法耗用时间少且解的价值更高.不仅如此,在试验中,本文的新算法获得了ORLIB中测试算例5.250-22的两个“新”解. 1 引 言 多维背包问题(MKP)[1]是一类NP难的组合优化问题.给定待选项的集合,MKP可以叙述如下:从集合中选出一组满足所有问题约束的项,使其价值之和最大.MKP的数学公式如下: MACROBUTTON AuroraSupport.EditInitialCounterValues ADDIN MACROBUTTON AuroraSupport.NoMacro ADDIN MACROBUTTON AuroraSupport.PasteReferenceOrEditStyle ( IF 0 = SEQ EqChapter \c \* arabic 0 SEQ EqChapter \c \* arabic 0. IF 0 = SEQ EqSection \c \* arabic 0 SEQ EqSection \c \* arabic 0. SEQ Eq \* arabic 1) ADDIN 满足于 式中: —项数,; —项的价值,; —对应项的变量,项被选中对应,否则,; —项耗用资源的量; —资源的总量; —约束数,. 一个定义完整的MKP应该满足: 并且. 近年来,蚂蚁、蜜蜂等群居昆虫的集体行为引起了人们的广泛关注.每个昆虫的能力虽然十分有限,但昆虫群体的能力却远远超过所有个体能力的总和.比如,蚂蚁群可以快速建立起巢穴与食物源之间的最短路径.令人惊奇的是,每只蚂蚁并不直接比较每条路径,而仅仅只是遵守信息素迹释放/跟随规则就能找到最佳路径.蚂蚁群的这种能力很自然地引起了计算机科学家的兴趣.人工智能发展中的最大困难是``组合爆炸问题,其实质是组合优化问题.如果能定义某种计算能力有限的“人工昆虫”,使其组成的群体具有解决某类组合优化难题的能力,则整个人工智能甚至整个计算技术都会有一个里程碑式的发展. Dorigo等人沿着这个方向迈出了第一步:他们根据蚁群的觅食行为定义了求解旅行商问题(TSP)的蚁群(AS[2])算法,并取得了令人鼓舞的结果. 蚁群优化 (ACO)[3]是由AS算法演变而成的一种难解问题的通用启发式解法.现已广泛用于求解包括TSP在内的各种组合优化问题.应用ACO求解MKP是一项颇具挑战性的研究工作.近年来,国内外的研究者对此作了一些尝试性的应用研究. Leguizamon等人分析了应用ACO求解TSP和MKP之间的区别,并将AS算法应用于MKP[4]. Fidanova提出增强当前未被蚂蚁访问过的项的迹浓度,以增加这些项被蚂蚁选中的概率[5]. Parra-Hernandez等人将ACS[6]的迹全局更新策略更改为满足一定条件的新解发现时才进行,并引入迹的局部存储,由此实现了ACS求解MKP的并行计算[7].Alaya等人将信息素迹放在被选择项的所有序对组合上,在此基础上提出了求解MKP的Ant-knapsack算法[8].国内与此相关的文献[9—11]大多是将国外文献中的算法用于求解背包问题,对ACO算法求解背包问题的性能并没有多少改进.仔细分析文献中的求解MKP的ACO算法会发现它们的复杂性偏高.然而,应用ACO算法求解MKP的算法复杂性还可以进一步降低. 本文在文献[12]背包问题表示的基础上提出了一种新的构造解的规则,并为背包问题设计了一种适合该规则的新的启发式信息.改进后的ACO求解MKP的空间复杂性为,构造每个解的时间复杂性为.试验表明,无论在串行执行还是在虚拟并行执行,在计算目标函数次数相同的条件下,本文的ACO算法不仅耗用时间少,而且求得最优解的能力也提高了.在后面的叙述中,称本文实现的ACO算法为NAntKp. 本文的其余部分组织如下:节2简要描述了现有文献中求解MKP的ACO算法的关键内容并分析了它们的复杂性;节3详细定义NAntKp算法;节4应用NAntKp算法求解MKP的标准测试实例,讨论算法性能并与其它ACO算法比较;节5简单总结了全文并指出了将来的研究方