蚁群优化算法在解决tsp问题中的应用

摘要根据蚂蚁生态学提出的蚁群算法是一种新颖的用于求解复杂组合优化问题的模拟进化算法,具有典型的群体智能特征,表现出较强的学习能力和适应能力。本文阐述了该算法的基本原理、算法模型和在TSPTRAVELINGSALESMANPROBLEM，旅行商问题中的具体应用过程,并对算法进行了总结和展望。关键词蚁群算法，旅行商问题，外激素COMMENT微微微微1目录不要都使用黑体目录摘要目录II第一章引言1第二章蚁群算法的基本原理和模型221蚁群算法的基本原理222蚁群算法的模型3第三章基于蚁群算法的TSP求解531TSP问题的描述532基于蚁群算法的TSP求解533蚁群算法的局限性6第四章蚁群算法的改进841优选参数M842参数的调整843信息素的更新844信息素链表L和禁忌链表TL的构建9第五章改进的算法基本流程10第六章结论11参考文献12第一章引言研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本上是自组织的，在许多场合中尽管这些合作可能很简单，但它们却可以解决许多复杂的问题。蚁群算法就是利用群集智能解决组合优化问题的典型例子。蚁群算法（ANTCOLONYALGORITHM,ACA）是由意大利学者MDORIGO，VMZNIEZZO，ACOLORNI等人在20世纪90年代初首先提出来的。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等元启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。蚁群算法不仅能够智能搜索、全局优化，而且具有稳健性A、鲁棒性B、正反馈、分布式计算、易与其它算法结合等特点。利用正反馈原理，可以加快进化过程；分布式计算使该算法易于并行实现，个体之间不断进行信息交流和传递，有利于找到较好的解，不容易陷入局部最优；该算法易与多种启发式算法结合，可改善算法的性能；由于鲁棒性强，故在基本蚁群算法模型的基础上进行修改，便可用于其它问题。因此，蚁群算法的问世为诸多领域解决复杂优化问题提供了有力的工具。TSP问题，又称旅行商问题，就是一个销售商从N个城市中的某一城市出发，不重复地走完其余N1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。它是组合优化中研究最多的问题之一，是一个经典的NP难题。第二章蚁群算法的基本原理和模型21蚁群算法的基本原理蚁群系统本来是生物学家为更好揭示昆虫的交互作用而提出的一种昆虫自组织模式。尽管建立这种模式的初衷是为了帮助人们去理解这类昆虫的复杂行为，蚂蚁也不可能从这些解释中获益，但是数学及计算机方面的专家和工程师却把这种超越生物本身的模型转化成了一项有用的优化和控制算法蚁群算法，也称蚁群系统（ANTCOLONYSYSTEM,ACS）。蚁群优化（ANTCOLONYOPTIMIZATION,ACO）是该系统的核心内容，其原理可大致描述如下蚂蚁属于群居昆虫，个体行为极其简单，而群体行为却相当复杂。相互协作的一群蚂蚁很容易找到从蚁巢到食物源的最短路径，而单个蚂蚁则不能。此外，蚂蚁还能够适应环境的变化，例如在蚁群的运动路线上突然出现障碍物时，它们能够很快地重新找到最优路径。人们通过大量的研究发现，蚂蚁个体之间是通过在其所经过的路上留下一种可称之为“信息素”（PHEROMONE）的物质来进行信息传递的。随后的蚂蚁遇到信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。同时，该物质随着时间的推移会逐渐挥发掉，于是路径的长短及该路径上通过的蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行动方向。因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂蚁群体行为表现出的一种信息正反馈现象。蚂蚁个体之间就是通过这种信息交流达到最快捷搜索到食物源的目的。图1能更具体地说明蚁群系统的原理。图1蚁群优化系统示意图图中设A是蚁巢，E是食物源，H、C为障碍物，距离为D。由于障碍物的存在，由A外出觅食或由E返回巢穴的蚂蚁只能经由H或C到达目的地。假设蚂蚁以“1单位长度/R单位时间”的速度往返于A和E，每经过一个单位时间各有30只蚂蚁离开A和E到达B和D图1A。初始时，各有30只蚂蚁在B和D点遇到障碍物，开始选择路径。由于此时路径上无信息素，蚂蚁便以相同的概率随机地走两条路中的任意一条，因而15只选往C，15只选往H图1B。经过一个单位时间以后，路径BCD被30只蚂蚁爬过，而路径BHD上则只被15只蚂蚁爬过（因BCD距离为1而BHD距离为2），BCD上的信息量是BHD上信息量的两倍。此时，又有30只蚂蚁离开B和D，于是各20只选择往C方向，而另外各10只则选往H图1C。这样，更多的信息素量被留在更短的路径BCD上。随着时间的推移和上述过程的重复，短路径上的信息量便以更快的速度增长，于是会有越来越多的蚂蚁选择这条短路径，以致最终完全选择这条短路径。由上述可见，蚁群算法的核心有三条。第一，选择机制信息素越多的路径，被选中的概率越大。蚂蚁群体行为表现出正反馈的过程，通过反馈机制的调整,可对系统中的较优解起到一个自增强的作用,从而使问题的解向着全局最优的方向演变,最终能有效地获得全局相对较优解；第二，信息素更新机制路径越短，迹增加越快。蚂蚁个体之间通过不断进行信息交流和传递有利于较好解的发现,并在很大程度上减少了陷于局部最优的可能；第三，协作机制个体之间通过信息素进行交流，也就是进行间接通信。22蚁群算法的模型设IJT为时刻连接节点IJ路段上的外激素浓度,在初始时刻,各条路段上的外信息素浓度相等,设IJ0CC为常数。为边IJ启发信息,该启发信息是由所要求解的问题给出的,。T时刻位于交叉点I的蚂蚁K选择交叉点J为目标点的概率取决于启发信息与蚂蚁目前所在地到目的地点路段上残留的外激素浓度,其函数表示为,0,IJIJTKKALOWEDKIJALOWEDKPTS式（1）中，ALLOWEDK0，1，2，N1表示蚂蚁下一步允许选择的城市，表示外激素的相对重要性表示启发信息的相对重要性。0入0入随着时间的推移,可能会出现两种情况先前留下的外激素逐渐消失残留的外激素过多,从而淹没了启发信息。为了避免这两种情况,在每一只蚂蚁从起点到达终点后,必须对残留的外激素进行更新。用参数来表示外激素入01物质的保留率,则1就表示外激素的挥发率,经过M个时间单位后,蚂蚁完成一次循环,各路径上的信息量要根据以下式子作调整IJTMIJ（T）IJTMIJMKIJ1，若第K只蚂蚁在本次循环中经过IJ0,KIJQTLKELS式中表示在本次循环中留在路径IJ上的信息量,IJ表示蚂蚁K在路段IJKIJ上留下的残留外激素浓度。式（4）中，Q是常数，LK表示第K只蚂蚁在本次循环中所走路径的长度IJ；初始时刻，IJ（0）A，IJ0，（I，J0,1,2,N1）。COMMENT微微微微2放到下一页第三章基于蚁群算法的TSP求解由于蚂蚁寻食的过程与旅行商问题（TRAVELINGSALESMANPROBLEM,TSP）的求解非常相似，所以蚁群算法最早的应用就是TSP的求解。下面以求解N个城市的TSP为例来说明蚁群算法。31TSP问题的描述旅行商问题中,设有N个城市集C（1，2，N）,任意两个城市I，J之间的距离为DIJ。问题是找到一条使总长度最短的闭环路线,其中除了起点之外的每个城市都只被访问一次,即求一条经过每个城市仅一次的路径（1），（2），（N），使得MIN（I）（I1）D（N）（1）1I32基于蚁群算法的TSP求解在TSP求解中,参与路径搜寻的每只蚂蚁都具有下列特征在一次周游中,蚂蚁只能游走未访问过的城市,直到本轮周游完成后,才允许蚂蚁游走已访问过的城市；选择城市的概率函数由城市之间的距离和连接支路上所包含的当前外激素余量确定；当完成一次周游,每只蚂蚁都会在每条访问过的路径上留下外激素。M只蚂蚁同时从某个城市出发,由公式选择下一次旅行的城市,已游走过的城市放入TABUK集中,一次循环完成后,更新每条边上的外激素,反复重复上述过程,直到终止条件成立。蚁群算法的实现步骤如下步骤1首先初始化，设迭代次数为NC，初始化NC0，各R,S,R,S初始化，将M个蚂蚁置于N个顶点上；步骤2将各个蚂蚁置于当前的解集Z中，然后对每个蚂蚁KK1,2,M，按照概率PK转移到下一个城市S，将S置于当前的解集中,如此循环,直到所有的蚂蚁访问完所有的城市；步骤3计算每个蚂蚁行走的总路径LK，并将最优解保存；步骤4按信息素浓度更新公式，更新各边的信息素浓度；步骤5各边的R,S初始化，NCNC1；步骤6如果NC小于预定值并且没有稳定解，则转步骤2，否则转步骤7；步骤7将得到的结果蚁群及函数值记录到RI，J及AI，J中；若性能满足则结束；否则，对R1,N，A1,N进行选择，转步骤8；步骤8对新的M个子种群重新开始蚁群算法操作，转步骤1，具体流程见图2。图2初始化N个子种群每个子种群独立进行蚁群算法一定次数N个结果蚁群及函数值记录到RI,J及AI中性能满足对R1N,IN进行选择对新的M个子种群重新开始蚁群算法操作结束Y蚁群算法流程图实验结果表明，在TSP问题中应用蚁群算法进行最短路径求解，在城市数量不多时，结果还是挺令人满意的。33蚁群算法的局限性由前面对蚁群算法的介绍可知，蚁群算法在运算过程中，蚁群的转移是由各条路径上留下的信息量的强度和城市之间的距离来引导的。蚁群运动的路径总是趋近于信息量最强的路径。通过对蚁群以及蚁群算法的研究表明，不论是真实蚁群系统还是人工蚁群系统，通常情况下，信息量最强的路径与所需要的最优路径比较接近。然而，信息量最强的路径不是所需要的最优路径的情况仍然存在，而且在人工蚁群系统中，这种现象经常出现。这是由于在人工蚁群系统中，各路径上的初始信息量是相同的，蚁群创建的第一条路径所用到的信息就主要是城市之间的距离信息。这时，蚁群算法等价于贪婪算法，这一次，蚁群在所经过的路径上留下的信息就不一定能反映出最优路径的方向，特别是蚁群中个体数目较少或者所计算的路径的组合较多时，就更不能保证蚁群创建的一条路径能引导蚁群走向全局最优路径。这一次循环中，蚁群留下的信息会因正反馈作用使这条路径不是最优，而且可能是离最优解相差很远的路径上的信息得到不应有的增强，而阻碍以后的蚂蚁发现更好的全局最优解。不仅是第一次循环所创建的路径可能对蚁群产生误导，任何一次循环，只要这次循环所利用的信息较平均地分布在各个方向上，这次循环所产生的路径就可能会对以后蚁群的选择产生误导。蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合，这种算法在构造解的过程中，利用随机选择策略，这种选择策略使得进化速度较慢，正反馈原理旨在强化性能较好的解，却容易出现停滞现象，这是造成蚁群算法不足之处的根本原因。当问题规模比较大时，由于信息量的挥发系数1的存在，使那些从未被搜索到的解上信息量会减小到接近于0，降低了算法的全局搜索能力，而且1过大时，当解的信息量增大时，以前搜索过的解被选择的可能性过大，也会影响到算法的全局搜索能力。通过减小1虽然可以提高算法的全局搜索能力，但又会使算法的收敛速度降低。也就是说蚁群算法与遗传算法等模拟进化算法一样，也存在着易于陷于局部最小值的缺陷。因此，蚁群所找出的解需要通过一定的方法来增强，使蚁群所留下的信息尽可能地不对以后的蚁群产生误导，而且能够克服计算时间较长的缺陷，从而提高蚁群算法的全局搜索能力，提高其搜索速度。第四章蚁群算法的改进为了克服算法收敛速度慢，易陷于局部最优解的缺陷，算法可从如下几个方面进行改进。41优选参数M用蚁群算法求解问题，都存在算法有关参数的设定问题，较好的参数组合将会使算法具有全局的搜索能力和较快的收敛速度。在其他参数不变的情况下，当蚂蚁数量太少,在能导致最优路径的那些边优选边走过的次数较少,难以留下较多的信息素,不利于算法迅速向最优解收敛,而且当优选边在数代之内不能被再次选择时,其信息素将会挥发殆尽,从而造成之前数代蚂蚁的优选结果浪费；而当M值太大,一方面会增加计算量,另一方面因为在最初的几代因为选择路径随机性比较大,最初的最优值因为蚂蚁多以至于得到强化的速度太快,容易造成局部最优解。蚁群算法中蚂蚁数目M，信息素残留系数,参数和4个参数之间是相互耦合的,具有复杂的关系,所以算法中的4个参数应当综合考虑。42参数的调整是表示信息素的残留程度,该参数受城市N的影响较大,当城市N太大时,若挥发系数1太大,算法的全局搜索能力会降低；若1太小,算法的全局搜索能力会随之提高,但收敛速度会变慢,因此可以对采取自适应控制策略,即的初始值可取大些,随着循环次数的不断增加,可根据下列函数做调整CMINC01/2TNNI入入T式子中的TC表示禁忌表TABUK中的元素,禁忌表TABUK用来记录蚂蚁K当前已经走过的城市,为挥发约束系数，MAXIN入1/243信息素的更新在进行路径寻优过程中,为了避免算法停滞和扩散,可以将残留信息素数量限制在MIN,MAX,MIN可以有效地避免算法的停滞,而MAX可以避免某条路径上的信息素远大于其他路径,使得所有的蚂蚁都集中到同一条路径上来,从而限制了算法的扩散，因此可以采用如下方式来对信息素进行更新。MINMINAXAX,AXIJIJIJIJJTTNT入44信息素链表L和禁忌链表TL的构建在蚁群算法中构建一个链表L,当算法运行H次后,将各条边上的信息素存放在链表L中,同时为了加快收敛速度,把信息素含量特少的一定数量的边加入到TLTABULIST中,TL中的路径将被排除在选取的范围外,即忘记“不好”的路径。禁忌表TABUKK1，2，M用来记录蚂蚁K当前走过的城市,TABUK中的元素将随着进化过程做动态的调整。蚂蚁在运动的过程中，根据链表中各条路径上的信息素以及路径的启发信息来计算转移概率PKIJT,0,IJKKIJKIJTJALOWEDJTLTALOWEDTS第五章改进的算法基本流程初始化各参数,M,MIN,MAX,N,每只蚂蚁从起点城市开始周游城市，利用禁忌表来判断蚂蚁的一次周游是否完成；若没有完成,则根据式子8计算出来的转移概率来决定选择下一个城市,并更改禁忌表；对每只蚂蚁经过的路径执行局部更新规则根据6式调整参数根据7式对信息素进行更新,得到新的最优解,并对最优解进行更新；若尚未达到指定的周游次数,转到步骤2输出最优解。COMMENT微微微微3放到下一页第六章结论本文通过对蚁群优化算法的基本原理和模型进行分析来解决TSP问题并且提出了一种改进的蚁群算法，该方法通过改变信息素和挥发系数的更新方式、构造信息素链表和禁忌链表等方法来加快算法的收敛速度,扩大子解的搜索空间,有效地缓解了基本蚁群算法容易出现的早熟、停滞现象。实验表明改进后的算法有效地提高了蚁群的收敛速度,并且表现出良好的稳定性。蚁群算法是一种原理相对简单的新兴仿生进化算法,在众多领域中已展现出它的特点和魅力。但蚁群算法理论与遗传算法、禁忌搜索算法等理论相比还远不成熟，实际应用也远未挖掘出其真正潜力，还有很多富有挑战性的课题亟待解决。主要体现在以下几个方面加强蚁群算法的基础理论研究，进一步发展新的数学分析和建模工具，尤其对算法的基础理论研究非常重要,包括对解决不同优化问题时收敛性和收敛速度的估计、避免陷入局部最优值、鲁棒性分析以及A,B,F,Q等参数的设计理论。目前尚未发现有关合理选择蚂蚁数量以及算法运行时间数学分析的论述。因此，该算法的数学基础理论研究将成为今后研究的一个重要课题。可将蚁群算法与其他类型方法综合使用以开发混合优化方法，进而发展思想更先进、功能更强大、解决更复杂系统的智能行为。将蚁群算法与神经网络、模糊控制、遗传算法、模拟退火算法等相融合，必将成为今后蚁群算法领域内新的研究热点。新的理论必须通过实践进行检验，在实践过程中，可以发现新问题，从而促进理论向前发展。近年来，蚁群算法虽在众多领域得到了推广应用，但其中大多仅仅是对蚁群算法在该领域应用的一个简单仿真。因此，今后应充分挖掘蚁群算法在实际应用中的潜力，在对现有应用领域进行深化研究的同时，进一步扩大其应用范围。此外，蚁群算法的硬件实现也将成为研究的热点方向之一。对上述问题的深入研究必将大大促进蚁群算法理论和应用的发展，蚁群算法也必将在智能计算领域中展现出更加光明的前景。COMMENT微微微微4居中，放到下一页参考文献1吴桂芳，武宏华求解TSP问题的蚁群算法研究N广西民族大学学报，2007512（1）2谢宏蚁群算