蚁群优化算法NDLACO

第24卷第3期计算机应用与软件Vol. 24 ,No. 3.2007年3月Computer Applications and SoftwareMar.2007蚁群优化算法NDLACO任善全吕强钱培德杨季文(苏州大学计算机科学与技术学院江苏省计算机信息处理技术重点实验室江苏 苏州215006 )摘要ACO算法在解NP-hard问题上虽然取得了广泛应用但在解同一类型的不同问题时需要更改a β ρ等参数的值才能取得相应问题的最优解或更接近最优解的解。通过使用最近邻居选择、信息素动态更新和局部启发搜索法对MMAS算法进行优化,得出NDLACO算法。此算法运用于解CVRP问题时取得了较好的效果。在关于参数值的问题上取得了-定的成效,也有效地解决了蚁群算法的收敛过快和早熟、停滞问题。关键词蚁群算法 NDLACO CVRPAN ANT COLONY OPTIMIZATION ALGORITHM NDLACORen ShanquanLi Qiang Qian Peide Yang Jiwen( Provincial Key Laboratory for Computer Information Pocessing Technology School of Computer Science & Technology ,Soochov Univrsiy Suzhou Jiangsu 215006 China )AbstractAlthough ACO algorithm has solved many NP-hard problems scesfully ,some parameters( a β ρ )must be changed for thesake of getting optimal results or the solutions being close to when solving different problems. This paper optimizes MMAS by using the nearestneighbor node choosing dynamic pheromone updating and local searching strategies and comes into being NDLACO algorithm ,which can getgood results in solving some instances of CVRP. This article gains some significative effects in researching the parameters ,what's more NDLA-C0 algorithm also deals with the contradiction between ant's fast convergence and stagnation effectively.KeywordsAnt colony algorithm NDLACO Capacitated VRP服停滞现象等等。以上研究对算法有-定程度的改进,但在不1引言断强调提高收敛速度缩短蚂蚁的搜索时间以便运用于解决大规模优化问题时常使某些路径的信息素过度增强而导致早熟、蚁群算法ACO( Ant Colony Optimization )是近年来出现的一停滞现象使得所求解的质量降低,以致得不到最好解或最优种新型的模拟进化算法。此算法已成功运用于解决几种NP-解。可见使用所得解过度强化信息素的变化来赢得时间与所得hard的组合优化问题36]如旅行商问题(TSP)车辆调度问题解质量的提高之间存在着矛盾蚂蚁搜索时间过短会导致解的(VRP)等显示出蚁群算法在求解复杂优化问题方面的优越质量下降,而提高解的质量常需要增加蚂蚁的搜索时间。为此,性。近几年来的研究成果表明蚁群算法具有很强的发现较好我们基于VRP问题的优化应用研究了一种基于最近邻居选解的能力、具有分布式计算、易于与其他方法相结合和鲁棒性强择、信息素动态更新和局部启发搜索的蚁群算法简称NDLACO等优点。然而,蚁群算法在搜索过程中也易于出现早熟停滞算法( ACO algorithm based on the nearest neighbor node choosing ,现象。dynamic pheromone updating and local searching )。该优化算法使很多学者对此都提出了改进算法避免发生信息素更新过用最近邻节点选择来缩短蚂蚁的搜索时间;依据蚂蚁已搜索路快出现早熟停滞现象。例如,EAS( elitist ant system )算法使用径的分布状况动态更新信息素来防止出现算法的早熟停滞现取得较好解的蚂蚁进行信息素更新;RBAS( rank-based version of象使用局部启发搜索来再次优化蚂蚁的所得解以提高所得解antsystem)算法使得每个蚂蚁在更新信息素时的权重不同7];的质量。实验结果表明,本文提出的算法与其它最新的优化算BWAS( best-worst ant system )算法只使用取得最好解和最差解法相比在平衡搜索时间和解的质量这对矛盾之间和对蚁群算的蚂蚁进行信息素的更新”]文献1 ]提出了一种相遇算法主法中参数设定的研究取得了很好的成效。要思想是使用两个蚂蚁合作完成一条 路径的搜索来提高求解的中国煤化工速度文献9 ]提出的MMAS( max min ant system )算法只使用取2 ACYHCNMHG研究现状得最好解的蚂蚁进行信息素的全局更新来加速收敛控制信息素的变化范围来克服停滞现象;文献[ 10 ]提出了一种变异策CVRP问题是VRP问题的一种情况,也是VRP问题中最基略以加快局部搜索;文献11]提出了根据当前蚂蚁所走路径的分布情况动态地对信息素进行更新文献12 ]提出了一种新收稿日期2005 -03-16。任善全硕士生主研领域:计算机中文颖的动态信息素更新策略和变异策略来加速收敛速度,以期克信息处理及应用技术。160计算机应用与软件2007年本的问题。CVRP 问题属于NP-hard问题应为TSP问题属于CVRP问题的子问题,即是CVRP问题的一种特殊情况。实际4 NDLACO 算法设计模型上CVRP问题比TSP问题更难于求解。CVRP 问题包含两种子问题bin-packing问题和最短路径问题而TSP问题只属于后者4.1 最近邻居选择原则范畴。1999年Bullnbeimer等人提出了运用于解CVRP问题蚂设定每个站点i的邻居数为n/2则站点i的邻居站点表述群算法AS. ASm-CVRP)。此后2002 年Reimann 等对此算为sto[iIjIj=1 2 . n/2 ) xdistance( i i)表示站点i到站点法进行了优化称之为AS -CVRPsav[101 ,AS。n -CVRPsav算法j的距离每个站点i的邻居站点以按1/distance(ij)的升序进.优于ASk -CVRP算法。在2004年Karl F. Doererl]等人把并行排列,由此可见distance( i i)到站台j的概率则CVRP可描述载重量为Vcap的Vsum辆车( distance( cl r2 )+distance(s. c2 s. c3 )+ distance(s_ cl p3 )))子从车站出发按照-定的规则把n个分布在不同站点的重量为then执行3-opt操作断开图1波浪线部分的连接形成图2新的循w( i=1 2.. n )的乘客接到车站处并使得Vsum辆车子所走环链表。的路径短所花时间少。4.3基于均匀分 布度的选择原则3.1 蚂蚁的节点选择原则5gτn°(1)n(1)j e allowed,子在站点i选择下一站点j的依据p*( t)选择取得p*( t)吹1)= { Eel s ζgTn°(t)m&(t)(7)值最大的节点j。otherwiser%1)%1)其中ξ∈(0 ,1 )为路径( i i )的信息权重" ,当经过路径( i门)的j∈allowed,(1)= { llwmuxrn"(1)n.(t)(1 )蚂蚁的数量较多时则使5;值减小反之则增大。这样就使得通过蚂蚁较多的路径下次被选中的几率变小通过蚂蚁较少的其中llwede,表示蚂蚁k:'下-步可选择的站台的集合a表示路路径下次被选择的几率变大。P"( 1 )表示蚂蚁由站点i选择站径.上的信息量对蚂蚁选择路径所起作用的大小mj为由站点i点j的概率最终达到蚂蚁在所有的路径上处于均匀分布的目的。使用基于均匀分布的选择原则,有效地解决了蚁群算法加到站点j的希望程度通常取nη;=1/djo .速收敛和早熟、停滞的现象。3.2信息素局部更新原则(1+1)=( 1-p)r(t1)+Qrf(2)4.4信息素局部更新原则--些经典的算法在更新信息素时要么对所有的蚂蚁所经指=rQ/L。 蚂蚁h在本次循环中i和j之间(3)过的路径增加其信息量要么只增加每代中取得最优路径上的信息量其余的被蒸发,这些做法都采用固定的信息素增减比其中ρ∈(0 1 )表示信息量τ( 1 )随时间的推移而衰减的程度例没有考虑当前蚂蚁搜索中所走路径的分布情况。本算法信Q为常数Lh为蚂蚁k在本次循环中已走路径的长度。息素的更新依据当前蚂蚁所走路径的分布情况进行不同程度地3.3信息素全局更 新原则更新动中国煤化工使其不至于过分集中或在每代搜索蚂蚁中选择使用取得最好解的蚂蚁antBest 进分散导MHCNMH G行全局的信息素更新。办门- IU*0.UDrA1) 若本次迭有1/3只蚂蚁选择同一路( i j)τg"=(1-ε)ry" +eAry (i i)e antBest的解(4)Arj=1/LmBe(5)τ(1+1)={或1/5只蚂蚁选择(8)该条搜索最后一步。其中ε为全局信息素蒸发系数Lume为本代蚂蚁 中求得最好解的路径长度。(r(1)-1*0.05r61) othervise第3期任善全等蚁群优化算法NDLACO161由于蚂蚁常选择信息量较大的路径,当多只蚂蚁选中同一使用公式( 7 )基于均匀分布度的原则选择下-站点;路径后信息量会大幅度增加就容易使多只蚂蚁集中到该路径endif上。在搜索过程中希望蚂蚁处于比较均匀分布的状况如公式使用公式( 8 )进行信息索局部更新(局部更新)(8)所示如果某段路径.上的蚂蚁较多时在信息素更新时使之end while蒸发得多反之当某段路径上所经过的蚂蚁数量较少时局部更end for Vsum新时信息素的蒸发就少些。MMAS算法”1信息素的局部更新使用局部启发搜索法3-opt对所得的完整解进行优化;中只对信息素进行蒸发,而不进行蒸发后的补偿本算法信息i讯(q< =qo)(q为随机数(0