最优化方法与设计报告.DOC

1、基于 ACO 的旅行商问题研究1/10最优化方法与设计实验报告基于 ACO 的旅行商问题研究陈航航(09212688) 计算机技术Email: Tel No.: 13660371747摘要本实验参考前人的经验,把已有的改进模型整合在一起,在基本的 AS 算法上作了以下几方面的改进:添加了每次迭代最优解的全局更新(即 ACS),强化了正反馈的过程;使用了蚁恒模型计算信息素增量;对信息素进行上下界限制,以避免算法过早收敛于局部最优解.最后,还添加了基于路径信源的信息素扩散模型.本文对基于路径信源的信息素扩散模型是否有效抱有怀疑态度,于是,本实验重点比较添加与没添加基于路径信源的信息素扩散模型对实

2、验结果的影响.结果表明,没添加该模型的算法结果比添加了的要好,这个模型并不适用于本算法,其效果还有待证明.关键字蚁群算法 蚁恒模型 上下界限制 信息素扩散模型1 意义和目标对于蚁群算法的研究主要集中在两个方面问题的求解：静态组合优化问题和动态组合优化问题.静态组合优化问题包括旅行商问题(TSP) 、二次分配问题(QAP) 、车间调度问题、车辆路径问题、车辆路由问题等,它指的是在解决问题的时候,该问题的拓扑分布和转换开销不会发生变化.例如：经典的 TSP 问题,其城市的位置和城市间的距离在算法运行的时候是不会发生变化的.与此不同,在动态组合优化问题的求解过程中,该问题的拓扑分布或转换开销可能会发

3、生改变.ACO 最初的应用就是用于 TSP,而近年,ACO 在组合优化问题方面的研究及应用都有了非常大的进步,但仍处在高速发展阶段.本文选择 TSP 这一典型问题有一定的研究意义.本文将介绍蚁群算法现今的发展动态,研究现有算法的优缺点,争取在前人的基础上做出算法改进,以得到较好的结果.基于 ACO 的旅行商问题研究2/102 国内外研究现状蚁群优化(ant colony optimization,简称 ACO)算法是模拟自然界中真实蚁群的觅食行为而形成的种模拟进化算法,是 20 世纪 90 年代意大利的 M.Dorigo 等学者提出的 .受到其取得了较好的实验结果的影响,蚁群优化算法激起了其他

4、学者的研究热情,并取得了很多研究和应用成果.从当前可以查阅的文献情况来看,研究和应用蚁群算法的学者主要集中在比利时、意大利、英国、法国、德国等欧洲国家,日本和美国也较早开始启动了对蚁群算法的研究.国内于 1998 年末才开始有少量公开报道和研究成果,到现在也有了一定的研究发展.近 10 年来的研究结果已经表明:蚁群算法用于组合优化具有很强的发现较好解的能力,具有分布式计算、易于与其他方法相结合、鲁棒性强等优点.在动态环境下也表现出高度的灵活性和健壮性.然而,蚁群算法存在搜索时间过长、易于停滞的问题.为了克服这些缺点,不少学者提出了改进算法,提高了算法的性能和功效. 90 年代,Gambarde

5、lla 和 Dorigo 提出一种修正的蚁群算法,对蚁群算法提出了一些讨论,其中包括不同的蚁群初始分布对求解的影响等,还提出了精英策略,以强化精英蚂蚁(发现迄今最好路径的蚂蚁) 的影响,结果发现,对精英蚂蚁数而言有一个最优的范围:低于此范围 ,增加精英蚂蚁数可较早地发现更好的路径,高于此范围,精英蚂蚁会在搜索早期迫使寻优过程始终在次优解附近,导致性能变差 1.Dorigo 等人在基本的 ACS 基础上提出称之为 Ant-Q System2的更一般的蚁群算法,仅让每一次循环中最短路径上的信息量作更新,每次让信息量最大的路径以较大的概率被选中,以充分利用学习机制,强化最优信息的反馈.为了克服在 A

6、nt-Q 中可能出现的停滞现象 ,德国学者 Stutzle 和 Hoos 提出另一种改进的蚁群算法“最大最小蚁群系统”MMAS(Max-Min Ant System)3也是一种较好的通用优化算法 ,该算法允许各个路径上的信息量在一个限定的范围内变化,MMAS 是到目前为止解决 TSP、QAP 等问题最好的 ACO 类算法.和其他寻优算法比较起来,它仍然属于最好的解决方案之一:MMA S 限定了痕迹浓度允许值的上下限,并且采用了平滑机制.对此算法的进一步扩展是加入局部搜索,目的是一方面提高算法性能,能在搜索初期获得高质量的解,更直接地引导学习机制;另一方面,使 MMAS 为后续的局部搜索阶段构造

7、好的初始解,以便找到接近最优的解.在求解对称旅行商问题(TSP)与非对称旅行商问题(ATSP)时,MMAS 的性能与 ACS 相当, 在平均路径长度上还优于 ACS.两者的共同点是在算法的每次迭代中只允许表现最好的蚂蚁更新路径上的信息素浓度, 以加快收敛速度；其不同之处主要在于如何防止过早的停滞现象.1999 年,国内学者吴庆洪等提出了具有变异特征的蚁群算法 5,该算法为了克服蚁群算法收敛较慢的问题,采用逆转变异方式,随机地进行变异,以增大进化时所需的信息量.这种变异机制充分利用了 2-opt 方法简洁高效的特点,因而具有较快的收敛速度.经过这种变异算子作用后,这一代解的性能会有明显改善,从基

8、于 ACO 的旅行商问题研究3/10而也能改善整个群体的性能,减少计算时间.2001 年,韩国学者 Lee SG 等人提出了一种新的改进的信息素更新策略 4:其一,局部信息素修改时,挥发系数动态改变;其二,全局信息素更新时,则将蚂蚁所走路的较短的那些路径上的信息加强 ,而较差的那些路径上的信息减弱.与此同时,国内学者吴斌、史忠植首先在蚁群算法的基础上提出了基于 MMAS 的相遇算法MMMAS(Meeting Max-Min Ant System)6,提高了蚁群算法蚂蚁一次周游的质量 ,然后将相遇算法与采用并行策略的分段算法相结合, 提出一种基于蚁群算法的 TSP 问题分段求解算法实验结果表明该

9、算法有较好的有效性.后来,魏平等人通过对目标函数的自动适应来调整蚂蚁的路径搜索行为,同时通过路径选择过程中的多样性来保证得到更多的搜索空间,以快速找到函数的全局最优解,从而提出了一种求解函数优化的蚁群算法 7.朱庆保、杨志军等人基于最近邻居选择、动态信息素更新和变异策略的高速收敛算法,简称NDMACO 算法 8.该算法以最近的邻居节点选择和动态信息更新策略来加速全局收敛,以一种独特的变异策略来加快局部寻优,使收敛速度大幅度地提高.2009 年,冀俊忠等基于事例的类似思想,提出一种快速求解 TSP 的蚁群算法 PIPDMACO9 ,使收敛速度有显著的提高.此算法提出一种新的信息素增量模型,以体现

10、蚂蚁在不同路径上行走时所产生的信息量差异; 同时,以经过的路径作为信息素扩散浓度场的信源,改善了信息素扩散模型 ;最后采用较低复杂度的变异策略对迭代的结果进行优化,以加快可行解的搜索.3 算法理论分析本实验采用基本的蚁群系统 10模型,借鉴前人的经验,在基本模型上做出几方面的修改.3.1 蚁群算法求解 TSP 问题的基本模型TSP 问题的目标是极小化城市间的距离.设 n 是 TSP 规模,也就是城市数目; m 是蚁群中蚂蚁的总数目; aij 是城市 i 和城市 j 之间的路径, dij 表示相应的欧氏距离,而 是路径 aij 的启发信息,又称能见度, ijijd/1表示 t 时刻上 aij 的

11、信息素浓度,其中, i ,j(1,2,n).)(ij蚂蚁 k(1k m)在周游的过程中,将根据可选路径上的信息素浓度决定前进的方向,并把该蚂蚁已走过的路径记录在禁忌表 tabuk中.蚂蚁从城市 i 走到城市 j 按式(1)进行选择.基于 ACO 的旅行商问题研究4/10(1)otherwisJqiftj ijijabuj,)(mxg0其中, , 是可调整参数,分别表示路径 aij 上的残留信息和启发信息对蚂蚁选择的影响权重; 是初始0q设定的参数, 是一个随机采样的数, , 0,1, J 是一个随机变量,按式(2)计算得到的转移概率q0q来确定.(2)otherwistabujifttpkab

12、ul ililjjkij,0,)()(蚂蚁留在路径上的信息素会随着时间挥发,于是,要对路径上的信息素进行更新,更新可按式(3)计算.(3)1,0(,)()1(kijijij tt其中, 是信息素的挥发程序,而 表示在本次周游中蚂蚁 k 在路径 aij 上的信息素增量.这里采用蚁周kij(ant-cycle)模型来计算.(4)否 则 在 本 次 周 游 中 经 过 路 径若 蚂 蚁,0/ ijkkijLQ其中,Q 是每只蚂蚁周游一次所消耗的信息素总量 ,是个常量;L k是蚂蚁 k 在本次周游中所经过的路径长度.下面是本文实验所采用的内容.3.2 对信息素进行局部更新和全局更新每只蚂蚁走过的路径对

13、后来要走的蚂蚁有一定的影响,主要是通过信息素的更新来改变路径的权重实现的.蚁群中每只蚂蚁周游一次后,算法应该对所有蚂蚁经过的路径进行信息素的更新,这一步操作记为信息素的局部更新,也即 3.1 中所提到的更新,按式(3)计算.而在一次周游中,各蚂蚁所走的路径中必然有最优的一个,也就是路径长度最短.为了突出该最优路径的重要性,这里参考了文献1对信息素进行两次更新的方法 ,每次迭代中当所有蚂蚁都完成本次周游后,要对本次周游中的最优路径进行信息素的全局更新.(5)1,0(,ijoldijnewij这里的 表示本次迭代中最优路径上的信息素增量.ij3.3 采用蚁恒模型计算信息素增量基于 ACO 的旅行商

14、问题研究5/10本实验参考了文献9中提出的蚁恒模型来计算信息的增量 ,也就是假设每只蚂蚁在一次周游中可以消耗的能量是相等的,它将均量地转化为信息素留在走过的路径上.该模型满足能量守恒定律,能体现在一次周游中蚂蚁所消耗的能量在各段路径上的分配.当蚂蚁走过的路径长度较小时,它在该路径上留下的信息素浓度就比较大,那该路径对后面蚂蚁选路的影响权重也比较大,这就导致了短路径更容易被选中,恰恰与事实相符.蚁恒模型的计算公式如式(6).(6)否 则 在 本 次 周 游 中 经 过 路 径若 蚂 蚁,0/ ijkijkij aLQd3.4 采用基于路径信源的信息素扩散模型文献11提出信息素会扩散的想法,蚂蚁留

15、下的信息素不仅仅影响它所走过路径上的城市 ,还会影响邻近的城市,从而提出了基于城市信源的信息素扩散模型.而文献9又在此基础上提出了基于路径信源的信息素扩散模型.虽然信息素会扩散这一想法并未得到验证,但也有一定的道理.本实验将比较添加与没添加该模型的结果.该模型根据判断一个城市 l 是否在路径 aij 的扩散区域内来决定城市 l 的信息素增量.具体可分为三个区域,每个区域有不同的信息素增量计算公式,更详细的描述就不在这里介绍了,下面只简单列出三个区域的计算公式.有兴趣的读者可以阅读参考文献9.1)当 ,且 时,02cos21ijlllid 02cos2ijjlljld(7)otherwisrfL

16、QDlilikijkil,0),1(2)当 而 时 ,0cos1cs2(8)otherwisrdifLQdDjijkijkjl,0),1(3)当 而 时,0cos2cs1(9)otherwisrdifLQdDkijkjlil,0),1(其中, 1、 2分别是 ail、a lj与 aij的夹角.基于 ACO 的旅行商问题研究6/103.5 对信息素进行上下界的限制文献3提出对信息素进行上下界限制的 MMAS,将各条路径上可能的信息素限制在一定的范围内,这样可以避免算法过早收敛于局部最优解.本实验采用了该算法的思想,对信息素进行上下界的限制(MM,max-min),把信息素浓度限制在0.00001

17、,20内 .4 算法的技术路线本实验的算法实现步骤如下:1) 初始化初始化地图,各路径上初始信息素浓度 (C 为常数), 信息素增量 ;把 m 只蚂蚁随机Cij)0( 0kij放到 n 个城市上,并把各蚂蚁始点加到它的禁忌表 tabuk 中;为参数 、 、 、 、 、Q 设初始值.2) 蚁群的一次周游WHILE NOT 终止条件 DOFOR i=1 TO m /所有蚂蚁周游一次FOR j=1 TO n /遍历所有城市 ,并回到出发点根据式(1)(2)选择下一个城市 j,并把 j 加到禁忌表中所有蚂蚁回到出发点,并计算各自路径长度ENDEND3) 本次迭代的信息素局部更新FOR 每条边 aijL

18、 1L 2L m按式(6)计算对所经过的路径产生的信息素增量 /*蚁恒模型*/FOR k=1 TO n /查找在扩散区域内的城市 /*基于路径信源的信息素扩散模型 */按式(7)(8)(9) 计算对路径扩散区域内的路径产生的信息素增量END按式(3)对信息素进行局部更新 对信息素进行上下界的限制 /*上下界限制*/END4) 查找本次迭代的最优解FOR j=1 TO m基于 ACO 的旅行商问题研究7/10比较当前最短路径长度与各蚂蚁的路径长度,找到最短路径 besttourEND5) 本次迭代的信息素全局更新FOR 每条边 aijbesttour按式(6)计算对所经过的路径产生的信息素增量F

19、OR k=1 TO n /查找在扩散区域内的城市按式(7)(8)(9) 计算对路径扩散区域内的路径产生的信息素增量END按式(5)对信息素进行全局更新对信息素进行上下界的限制END迭代数加 1END其中,基于路径信源的信息素扩散模型不一定是个好的选择,后面的实验将会比较,使用了该模型与没使用,哪个更优.5 数据实验及结果本实验对新添加模块的算法性能进行测试,并将测试结果与 ACS 算法、改进的 ACS 算法（包含 2-opt 优化）进行了比较.实验中所使用的多个 TSP 问题的数据来源于 TSPLIB 标准数据库（http:/elib.zib.de/pub/mp-testdata/tsp/ts

20、plib/tsplib.html）.实验的运行环境为:操作系统 Windows XP,CPU为 Pentium(R) Dual 2.00GHz,内存为 2GB,算法用 Visual C+语言编程实验,实验的参数均通过实验确定.如第 3 节所说的,本实验在基本的 AS 算法上加了每次迭代最优解的全局更新、蚁恒模型计算信息素增量以及信息素的上下界限制.另外,还添加了基于路径信源的信息素扩散模型.本实验重点比较添加与没添加基于路径信源的信息素扩散模型对实验数据的影响.这里,把没添加基于路径信源的信息素扩散模型的算法记为 ACS+MM+CON,把加了基于路径信源的信息素扩散模型的算法记为 ACS+MM

21、+CON+PATH.为了验证、比较算法效果，本实验把算法用于计算下面三个 TSP 问题数据：Oliver30、eil51、st70.实验结果的比较如表 1.表 1 一些 TSP 问题上不同算法的结果比较Public Data Sets ACS ACS+2opt ACS+MM+CON ACS+MM+CON+PATHInstance of TSPOptimum ValuesBest ResultNum. of cyclesBest ResultNum. of cyclesBest ResultNum. of cyclesBest ResultNum. of cycles基于 ACO 的旅行商问题研

22、究8/10Oliver30 423.741 423.74 830 423.74 210 417.785 1686 418.589 1801eil51 426 441 2100 431 900 449.318 1758 477.724 154st70 675 690 3900 681 2200 713.661 3525 767.697 745表 2 是本实验在不同 TSP 范例上获得表 1 结果时所使用的参数配置 ,另外,实验时,设置 m=n,即蚂蚁数与城市数相等;而信息素扩散模型的圆锥体锥面与中心轴的夹角设为 .6/表 2 本实验在一些 TSP 问题上的参数设置Instance of TSP

23、QOliver30 1 5 0.3 0.4 1 100eil51 1 5 0.5 0.4 1 100st70 1 5 0.3 0.4 1 100其中, 的大小反映了蚁群在路径搜索中随机性因素作用的强度, 越大,蚂蚁在选路时选择以前走过的路的可能性会越大,随机性越小.而 的大小反映了蚁群在路径搜索中的先验性和确定性因素作用的强度, 越大,蚂蚁在某个局部点上选择局部最优路径的可能性越大.一般二者组合的取值可以是(1,1),(1,2),(1,5),(0.5,5).经过实验, 最终本文确定了(1,5)的组合 .而信息素总量 Q 的取值对实验的结果影响不大 , 、 、 的取值是参考了文献9 的参数设置而

24、确定的.6 分析与总结本实验在基本的 AS 算法上作了四方面的改进:1) 添加了每次迭代最优解的全局更新(即 ACS),在原有的局部更新中再加大最优路径的权重,强化了正反馈的过程,能使解的质量得到提高.另外,这里局部更新采用的是延迟更新,即全部蚂蚁周游一次才更新.2) 使用蚁恒模型计算信息素增量, 该模型满足能量守恒定律,能体现在一次周游中蚂蚁所消耗的能量在各段路径上的分配.3) 对信息素进行上下界限制,使各条路径上可能的信息素限制在一定的范围内,这样可以避免算法过早收敛于局部最优解.4) 添加了基于路径信源的信息素扩散模型,这个模型是由文献9提出的,意思是蚂蚁留下的信息素不仅仅影响它所走过路

25、径上的城市,还会影响邻近的城市.本文对基于路径信源的信息素扩散模型是否有效抱有怀疑态度,于是,本实验重点比较添加与没添加基于路径信源的信息素扩散模型对实验结果的影响.由第 5 节的结果可以看到,添加了基于路径信源的信息素扩散模型的算法(ACS+MM+CON+PATH)比不上没有加该模型的算法(ACS+MM+CON)结果.在本实验中该并不适用,其效果还有待证明.基于 ACO 的旅行商问题研究9/10由表 1 我们也可以看到,本文的算法并达不到所有问题的最优解,如在 eil51 和 st70 数据集上的计算结果,还远达不到现有的最优解,但在 Oliver30 这个数据集上却有一定的提高.在 Oli

26、ver30 上, ACS+MM+CON 比 ACS+MM+CON+PATH 的结果提高得更多,相比现有最优解,提高了 1.405%.相信这个数据是具有一定意义的 ,只可惜它在别的数据集上结果并不理想.由结果上看,似乎本文算法适用于维度较小的问题计算,这一点还需验证,是否可以把低维度上的提高扩展到较高维度上,还需进一步研究.本文是对 ACO 一个初步的学习与研究,推理过程有欠慎密,实验过程还需完善,结果也并不理想,但在整个研究过程中,作者确实学到了很多东西,无论是算法理论上的知识、学习与研究的方法,还是编程能力的锻炼.个人觉得这是一个个人能力提升的过程,对自己日后的学习、工作都会和很有帮助的.学

27、习的方法是最重要的,学会如何学习,足以让一个人终生受益.而在这个实验中,我还有很多做得不够的地方,比如一开始急功近利,理论没搞明白就开始做实验,后面才发现那是无法进行下去的.只有把基础打扎实了,把整体框架弄明白了才可以往前走.而整个实验,我都是边学习边摸索完成的,很多细节都是后面一点点弄明白的,我觉得这是一个理论与实践的结合的过程,为了实现算法,不知道回头看了多少次前面模糊的地方,一次次尝试,一点点理解才把它实现了出来.相信这个经历对我日后的学习会很有启发的.7 参考文献1 Gambardena L M, Dorigo M. Solving symmetric and asymmetric T

28、SPs by ant colonic, Proc of the IEEE Conference on Evolutionary Computation, 1996: 622-627.2 Gambardena L M, Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem, Proceedings of ML-95, the 12th International Conference on Machine Learning. Morgan Kaufmann. IEEE Press,

29、 1995: 252-260.3 Stutzle T, Hoos HH. MAX-MIN ant xystem and local search for the traveling salesman problem, IEEE Intl Conf. on Evolutionary Computation, 1997: 309314.4 Lee SG, Jung TU, Chung TC. An effective dynamic weighted rule for ant colony system optimization. Proc.of the 2001 Congress on Evol

30、utionary Computation, Vol 2.IEEE Press, 2001.5 吴庆洪, 张纪会, 徐心和. 具有变异特征的蚁群算法, 计算机研究与发展, 1999, 36(10): 1240-1245.6 吴斌, 史忠植. 一种基于蚁群算法的 TSP 问题分段求解算法, 计算机学报, 2001, 24(12): 1328-13337 魏平, 熊伟清. 一种求解函数优化的蚁群算法, 计算机科学 , 2002, 29(9): 227-229.8 朱庆保, 杨志军. 基于变异和动态信息素更新的蚁群优化算法 , 软件学报, 2004, 15(2): 185-192.基于 ACO 的旅行

31、商问题研究10/109 冀俊忠, 黄振, 刘椿年. 一种快速求解旅行商问题的蚁群算法, 计算机研究与发展, 2009, 46(6): 968-978. 10 Dorigo M, Maniezzo V, Colorni A. The ant system: Optimization by a colony of cooperating agents, IEEE Trans on Systems, Man, and Cybernetics, 1996, 26(1): 29-41.11 Huang Guorui, Cao Xianbin, Wang Xifa. An ant colony optimization algorithm based on pheromone diffusion, Acta Electronica Sinica, 2004, 32(5): 865-868.