一种改进蚁群算法在TSP中的应用

一种改进蚁群算法在TSP中的应用摘要:以TSP问题为例，针对蚁群算法在运算时出现的收敛速度慢、易陷入局部最优解等问题，提出了一种改进信息素更新方式的策略,有效地提高了算法的收敛速度，抑制了早熟现象的出现。最后通过实例证明了改进后算法的有效性。关键词:旅行商问题；蚁群算法；路径优化；中图分类号:TP301.6；文献标识码:A20世纪90年代初，DorigoM等人提出一种仿真进化蚁群算法]1[，该算法首先应用于解决TSP问题（旅行商问题）并获得了良好的效果。而随着人们在应用蚁群算法求解规模更大的问题之时，发现其存在着收敛速度慢，解的质量差等缺陷。针对这些问题，许多学者对其展开了深入的研究并提出了一些改进策略。比如BullnheimerB等人提出的基于排序的蚂蚁系统（rankAS）、StutzleT和HoosH提出的最大—最小蚂蚁系统]2[（MMAS）等。这些算法成功应用于工程领域中且相对于基本蚁群算法具有更高的运算效率。经过研究发现，MMAS算法相对于其他寻优方法在解决TSP等问题上具有更好的效果，但仍存在搜索速度慢的问题。本文通过对基本蚁群算法以及MMAS算法中存在的问题进行研究，在此基础上提出了一种改进蚁群算法，有效地提高了算法的性能。1蚁群算法1.1蚁群算法基本原理基本蚁群算法中的蚂蚁以“信息素”]4,3[作为蚁群之间的联系方式是其最大的特点。当蚁群离开蚁穴外出觅食的时候，它们会随时在经过的路径上释放一种特殊的化学物质（称之为“信息素”）。这种物质会作为一种信号并对后面蚂蚁的行动产生一定影响。当一条路径上通过的蚂蚁数量越多，该路径上的信息素浓度越高，之后的蚂蚁选择该条路径的概率越大。当某条路径上信息素浓度越来越大，而其他路径上的信息素会随着时间的流逝以及信息素的挥发变得越来越少，最终蚁群会发现一条最短路径。1.2蚁群算法在TSP问题中的实现在求解n个城市TSP问题的时候，需作如下假设：将m只蚂蚁随机放到n个城市。为了防止蚂蚁在一次循环中重复经过同一个城市，每只蚂蚁都保存了一个禁忌表，如ktabu表示用于记录第k只蚂蚁已访问过的城市，每只蚂蚁的禁忌表中第一个元素为其出发的城市，t时刻位于城市i的蚂蚁k选择城市j作为其下一个目标城市的概率为：otherwiseallowedjtttkallowedsisisijijkijkP，0,][)]([][)]([)(（1）其中)(tij表示t时刻边),(ji上的信息素浓度，边),(ji表示连接城市i与城市j的路径；ij表示城市i与城市j之间的距离长短因子，在TSP问题中，一般令ijijd/1，ijd表示城市i到城市j之间的距离；,为启发因子，分别表示)(tij与ij的相对重要性]6,5[；kallowed表示未访问过的城市；t为迭代计数器。当某只蚂蚁经过一个城市时，我们对该蚂蚁的禁忌表做相应的记录，然后蚂蚁依照(1)式继续选择其下一个拜访的城市。当所有蚂蚁的禁忌表记录完n个城市时，说明所有蚂蚁已完成一次周游，此时计算每只蚂蚁在此次周游中经过的距离L并对每条路径上的信息素按照以下方式进行更新：)()()1()1(1tttmkkijijij（2）otherwisetRjitLQtkkkij0)(),()()(（3）其中表示信息素的挥发系数]7[，通常取值范围是1~0；Q表示每只蚂蚁携带的信息量，为一常数；)(tLk表示第k只蚂蚁在第t次迭代中所走的路程；)(tRk表示蚂蚁k在第t次迭代中所走的路径。保存该次循环的最优路径，清空所有禁忌表，一直重复上述过程，当循环次数达到迭代次数上限或者所有蚂蚁的路线保持一致（即算法进入停滞状态），算法停止。比较每次迭代中保存的最优路径，最终得出全局最优路径。1.3蚁群算法的缺陷随着问题规模的扩大，通过蚁群算法得到的最优解和运行时间都无法让人满意，性能明显不如一些其他启发式算法，造成这种结果的原因为：①.通过蚁群算法得到的是一个局部最优解，而非全局最优解。当算法运行到一定的迭代次数后，所有蚂蚁搜索到的是同一条路径，因此无法进行下一步的搜索。②.蚂蚁依照概率公式选择移动到下一个目的地，这种移动的随机性很强，当问题规模较大时，算法无法在很短的时间内找到一条较好的路径。2改进蚁群算法2.1全局信息素更新策略在一些改进蚁群算法中，MMAS算法算是一种具有较强全局搜索能力的算法，在求解一些NP-hard问题的过程中确实能得到比较满意的解。但该算法每次迭代完成后只对最优路径上的信息素进行更新，而每条路径初始信息素量均为max，从而导致多数路径上的信息素量在多次迭代后仍是相同的，影响了搜索最优解的速度。综合分析两种算法的优缺点，在基本蚁群算法的基础上作出如下改进：信息素更新策略上采取全局更新的策略。考虑到每次迭代产生的较差解对搜索全局最优解的帮助不大，此时若增加较差解路径上的信息素反而会影响搜索最优解的速度。因此，在每次迭代结束后适当减少这些解路径上的信息素，相应地增加较优解路径上的信息素，这里将(3)式改成如下形式：otherwisetRjiLLLLtkLLbestworstkavekijkave0)(),(5)()sgn(（4）其中kL表示第k只蚂蚁在本次迭代中所走路径的总长度，worstbestLL、分别表示本次迭代中得出的最短路径与最长路径。aveL表示所有蚂蚁在本次迭代中所走路径的平均长度。2.2信息素挥发机制的改进由于每次迭代结束后要对路径上的信息素进行更新，因此迭代前期的较差解所在路径上的信息素量相对较少，加上挥发系数的存在，导致这些路径上的信息素量在一定的迭代次数后会接近甚至等于min，从而降低了算法的搜索能力。因此，对每次迭代后信息素的挥发策略加以改进：mkkijijtijttt1)()()()1()1(（5）1)(25)(maxmaxtNCNCt（6）其中maxNC为最大迭代次数。这样，在迭代前期，信息素的保留率相对于之前得到了提高，较差解所在路径被搜索的概率得到了提升，从而扩大了算法的搜索空间。之后随着迭代的进行，通过不断增大)(t的值以使得算法在搜索时更倾向于搜索到较优路径，在迭代中后期加快了算法的搜索速度。此外，为防止部分路径上的信息素量过大或过小甚至消失，每次更新后对各条路径上的信息素量进行限制：minminmaxminmaxmax)1(,)1(),1()1(,)1(tttttijijijijij（7）2.3算法的实现步骤：Step1参数初始化。每条路径上的信息素浓度cij)0(,c为常数。0NC，MAXNCmax(最大迭代次数)。Step2将m只蚂蚁随机放到n个城市中，为每只蚂蚁建立禁忌表ktabu并把它们当前所在的第一个城市记录在禁忌表中。Step3蚂蚁从其所在的第一个城市出发，依照(1)式在kallowed中选择其下一个城市并记录在禁忌表ktabu中。Step4重复步骤3，直至访问完所有城市。所有蚂蚁回到起点，这样就形成了m条闭合的回路。计算每只蚂蚁走过的路程，得出worstbestLL、aveL、的值并将其中的最小值bestL保存。Step5按照式(4)~(7)对每条路径上的信息素进行更新，清空所有禁忌表。Step61NCNC,1tt，重复步骤2,3,4,5，当MAXNC时，算法停止。比较每次迭代产生的最短路程，输出其中的最优解及其所对应的路径。3仿真实验实验环境是在WindowsXPMATLABR2012b上运行。为了检验改进蚁群算法的具体性能，这里采用27个城市的TSP问题来进行试验，具体坐标如表1所示：表1城市的坐标城市坐标(X,Y)城市坐标(X,Y)城市坐标(X,Y)1(14.5,17.5)10(0.5,4.5)19(15.5,3.5)2(14.5,6.2)11(6.0,16.0)20(6.0,6.0)3(12.0,14.0)12(16.0,14.0)21(20.0,15.5)4(10.0,18.0)13(17.8,4.0)22(12.5,19.0)5(1.5,11.5)14(9.0,12.0)23(12.5,11.0)6(18.0,11.5)15(8.0,8.0)24(15.5,10.0)7(4.0,10.0)16(4.0,18.0)25(10.5,11.0)8(18.0,18.0)17(12.5,3.0)26(9.0,15.0)9(9.7,10.0)18(13.5,15.0)27(15.5,12.0)实验的各参数设置为:1.0,5,1,100Q，01.0,10minmax，基本蚁群算法与本文算法中各条路径上的信息素量初始值1)0(ij，蚂蚁的数量20m,每种算法运行20次，每次运行迭代250次，运行得到的结果分别如表2、图1及图2所示，其中平均解为20次运行所得的解的平均值；最优解为20次运行所得的解的最小值；平均耗时为各次运行得到最优解的时间的平均值；表2算法性能的比较算法平均解最优解平均耗时本文算法92.215691.22861.42基本蚁群算法95.568094.39292.83sMMAS算法92.578591.22862.12s图1本文算法与MMAS算法的最优路径图2基本蚁群算法的最优路径通过表2可以看出本文算法相对于基本蚁群算法以及MMAS算法在求解最优解时更具有优势，具体表现在全局搜索能力与收敛速度两个方面。继续应用本文算法解决oliver30城市问题，参数设置：蚂蚁的数目30m，每次运行迭代200次，其他参数的设置与上例相同。算法在运行到第三次得到了最优解423.7476，得到的解进化曲线与最短路径分别如图3及图4所示：图3解进化曲线图4oliver30的最优路径4结束语本文通过对基本蚁群算法进行分析，在此基础上提出了一种新的启发式算法，具体体现在对信息素的更新规则以及挥发策略上加以改进,增强了系统的适应性及鲁棒性。最后的算例实验表明，改进后的算法在收敛速度以及搜索最优解的能力上都要优于基本蚁群算法和MMAS算法。然而,本文在参数的选取上没有严格的理论依据，算法在对其他一些NP问题的求解是否仍有改进的空间，这些都有待进一步的研究。参考文献：[1]DORIGOM,MANIEZZOV,COLORNIA.Antsystem:optimizationbyacolonyofcooperatingagents[J].IEEEtransactionsonsystems,man,andcybernetics.PartB,Cybernetics1996,26(1):29-41.[2]STÜTZLET,HOOSH.MAX-MINantsystemandlocalsearchforthetravelingsalesmanproblem[C]//EvolutionaryComputation,1997.,IEEEInternationalConferenceon.IEEE,1997:309-314.[3]DORIGOM,BONABEAUE,THERAULAZG.Antalgorithmsandstigmergy[J].FutureGenerationComputerSystems,2000,16(8):851-871.[4]PARPINELLIRS,LOPESHS,FREITASAA.Dataminingwithanantcolonyoptimizationalgorithm[J].IEEETransactionsonEvolutionaryComputation,2002,6(4):321-332.[5]黄度樾.现代智能算法及应用[M].北京,科学出版社，2005:283-383[6]李金汉，杜德生.一种改进蚁群算法的仿真研究[J].自动化技术与应用,2008,27(2):58-60.[7]龚本灿，李腊元，蒋廷耀，等.基于局部优化策略求解TSP的蚁群算法[J