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

摘 要根据蚂蚁生态学提出的蚁群算法是一种新颖的用于求解复杂组合优化问题的模拟进化算法,具有典型的群体智能特征,表现出较强的学习能力和适应能力本文阐述了该算法的基本原理、算法模型和在TSP( Traveling Salesman Problem，旅行商)问题中的具体应用过程,并对算法进行了总结和展望关键词：蚁群算法，旅行商问题，外激素1 目 录 摘 要Ⅰ目 录II第一章 引言 1第二章 蚁群算法的基本原理和模型 22.1 蚁群算法的基本原理 22.2 蚁群算法的模型 3第三章 基于蚁群算法的TSP求解 53.1 TSP问题的描述 53.2 基于蚁群算法的TSP求解 53.3 蚁群算法的局限性 6第四章 蚁群算法的改进 84.1 优选参数m 84.2 参数的调整 84.3 信息素的更新 84.4 信息素链表 L 和禁忌链表 TL 的构建 9第五章 改进的算法基本流程 10第六章 结论 11参考文献 12目录不要都使用黑体 第一章 引言研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本上是自组织的，在许多场合中尽管这些合作可能很简单，但它们却可以解决许多复杂的问题蚁群算法就是利用群集智能解决组合优化问题的典型例子。

蚁群算法（Ant Colony Algorithm, ACA）是由意大利学者 M.Dorigo，V.Mzniezzo，A.Colorni 等人在20世纪90年代初首先提出来的它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等元启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法蚁群算法不仅能够智能搜索、全局优化，而且具有稳健性A、鲁棒性B、正反馈、分布式计算、易与其它算法结合等特点利用正反馈原理，可以加快进化过程；分布式计算使该算法易于并行实现，个体之间不断进行信息交流和传递，有利于找到较好的解，不容易陷入局部最优；该算法易与多种启发式算法结合，可改善算法的性能；由于鲁棒性强，故在基本蚁群算法模型的基础上进行修改，便可用于其它问题因此，蚁群算法的问世为诸多领域解决复杂优化问题提供了有力的工具TSP 问题，又称旅行商问题，就是一个销售商从 n 个城市中的某一城市出发，不重复地走完其余 n﹣1 个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条它是组合优化中研究最多的问题之一，是一个经典的 NP 难题第二章 蚁群算法的基本原理和模型2.1 蚁群算法的基本原理蚁群系统本来是生物学家为更好揭示昆虫的交互作用而提出的一种昆虫自组织模式。

尽管建立这种模式的初衷是为了帮助人们去理解这类昆虫的复杂行为，蚂蚁也不可能从这些解释中获益，但是数学及计算机方面的专家和工程师却把这种超越生物本身的模型转化成了一项有用的优化和控制算法!蚁群算法，也称蚁群系统（Ant Colony System, ACS）蚁群优化（Ant Colony Optimization, ACO）是该系统的核心内容，其原理可大致描述如下：蚂蚁属于群居昆虫，个体行为极其简单，而群体行为却相当复杂相互协作的一群蚂蚁很容易找到从蚁巢到食物源的最短路径，而单个蚂蚁则不能此外，蚂蚁还能够适应环境的变化，例如在蚁群的运动路线上突然出现障碍物时，它们能够很快地重新找到最优路径人们通过大量的研究发现，蚂蚁个体之间是通过在其所经过的路上留下一种可称之为“ 信息素”（Pheromone）的物质来进行信息传递的随后的蚂蚁遇到信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择同时，该物质随着时间的推移会逐渐挥发掉，于是路径的长短及该路径上通过的蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行动方向因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。

这就构成了蚂蚁群体行为表现出的一种信息正反馈现象蚂蚁个体之间就是通过这种信息交流达到最快捷搜索到食物源的目的图1能更具体地说明蚁群系统的原理图1 蚁群优化系统示意图图中设 A 是蚁巢，E 是食物源，H、C 为障碍物，距离为 d 由于障碍物的存在，由 A 外出觅食或由 E 返回巢穴的蚂蚁只能经由 H 或 C 到达目的地假设蚂蚁以“1单位长度/R单位时间”的速度往返于 A 和 E ，每经过一个单位时间各有30只蚂蚁离开 A 和 E 到达 B 和 D (图1 a)初始时，各有30只蚂蚁在 B 和 D 点遇到障碍物，开始选择路径由于此时路径上无信息素，蚂蚁便以相同的概率随机地走两条路中的任意一条，因而15只选往 C ，15只选往 H (图1 b)经过一个单位时间以后，路径 BCD 被30只蚂蚁爬过，而路径 BHD 上则只被15只蚂蚁爬过（ 因 BCD 距离为1而 BHD 距离为2），BCD 上的信息量是 BHD 上信息量的两倍此时，又有30只蚂蚁离开 B 和 D ，于是各20只选择往 C 方向，而另外各10只则选往 H (图1c)这样，更多的信息素量被留在更短的路径 BCD 上随着时间的推移和上述过程的重复，短路径上的信息量便以更快的速度增长，于是会有越来越多的蚂蚁选择这条短路径，以致最终完全选择这条短路径。

由上述可见，蚁群算法的核心有三条第一，选择机制：信息素越多的路径，被选中的概率越大蚂蚁群体行为表现出正反馈的过程，通过反馈机制的调整,可对系统中的较优解起到一个自增强的作用, 从而使问题的解向着全局最优的方向演变, 最终能有效地获得全局相对较优解；第二，信息素更新机制：路径越短，迹增加越快蚂蚁个体之间通过不断进行信息交流和传递有利于较好解的发现, 并在很大程度上减少了陷于局部最优的可能；第三，协作机制：个体之间通过信息素进行交流，也就是进行间接通信2.2 蚁群算法的模型设 ij t 为时刻连接节点 ij 路段上的外激素浓度, 在初始时刻, 各条路段上的外信息素浓度相等, 设 ij(0)=C (C为常数)为边 ij 启发信息, 该启发信息是由所要求解的问题给出的,t 时刻位于交叉点 i 的蚂蚁 k 选择交叉点 j 为目标点的概率取决于启发信息与蚂蚁目前所在地到目的地点路段上残留的外激素浓度, 其函数表示为 ⑴ 式（1）中，allow edk= {0，1，2 ，… n-1} 表示蚂蚁下一步允许选择的城市，表示外激素的相对重要性表示启发信息的相对重要性。

随着时间的推移, 可能会出现两种情况：⑴ 先前留下的外激素逐渐消失; ⑵ 残留的外激素过多,从而淹没了启发信息为了避免这两种情况, 在每一只蚂蚁从起点到达终点后,必须对残留的外激素进行更新用参数 来表示外激素物质的保留率,则 1- 就表示外激素的挥发率,经过 m 个时间单位后, 蚂蚁完成一次循环, 各路径上的信息量要根据以下式子作调整: ij (t+m)= ij（t）+ij(t+m) ⑵ ij = ⑶ ，若第 k 只蚂蚁在本次循环中经过 ij ⑷式中 表示在本次循环中留在路径 ij 上的信息量,ij 表示蚂蚁 k 在路段 ij上留下的残留外激素浓度式（4）中，Q是常数，Lk 表示第 k 只蚂蚁在本次循环中所走路径的长度 ij ；初始时刻，ij（0）= A，ij = 0，（ i，j = 0, 1, 2, … , n-1）第三章 基于蚁群算法的 TSP 求解放到下一页由于蚂蚁寻食的过程与旅行商问题（Traveling Salesman Problem, TSP）的求解非常相似，所以蚁群算法最早的应用就是TSP的求解。

下面以求解 n 个城市的 TSP 为例来说明蚁群算法3.1 TSP 问题的描述旅行商问题中,设有 n 个城市集 C =（1，2，…，n）, 任意两个城市 i，j 之间的距离为 dij 问题是找到一条使总长度最短的闭环路线, 其中除了起点之外的每个城市都只被访问一次,即求一条经过每个城市仅一次的路径 =（（1），（2），…（n）），使得Min（（i）（i+1）+d（n）（1）） ⑸3.2 基于蚁群算法的 TSP 求解在 TSP 求解中, 参与路径搜寻的每只蚂蚁都具有下列特征：⑴在一次周游中, 蚂蚁只能游走未访问过的城市,直到本轮周游完成后,才允许蚂蚁游走已访问过的城市；⑵选择城市的概率函数由城市之间的距离和连接支路上所包含的当前外激素余量确定；⑶当完成一次周游, 每只蚂蚁都会在每条访问过的路径上留下外激素m只蚂蚁同时从某个城市出发,由公式 ⑴ 选择下一次旅行的城市,已游走过的城市放入 tabuk 集中,一次循环完成后,更新每条边上的外激素,反复重复上述过程,直到终止条件成立蚁群算法的实现步骤如下：步骤1: 首先初始化，设迭代次数为 NC，初始化 NC = 0，各 ( r, s) , Δ( r, s) 初始化，将 m 个蚂蚁置于 n 个顶点上；步骤2: 将各个蚂蚁置于当前的解集 z 中，然后对每个蚂蚁 k ( k = 1, 2, …, m )，按照概率 Pk 转移到下一个城市 S ，将 S 置于当前的解集中,如此循环,直到所有的蚂蚁访问完所有的城市；步骤3: 计算每个蚂蚁行走的总路径 Lk ，并将最优解保存；步骤4: 按信息素浓度更新公式，更新各边的信息素浓度；步骤5: 各边的 Δ( r, s) 初始化，NC = NC + 1；步骤6: 如果 NC 小于预定值并且没有稳定解，则转步骤2，否则转步骤7；步骤7: 将得到的结果蚁群及函数值记录到 R[ i，j] 及A[ i，j] 中；若性能满足则结束；否则，对 R [ 1, …, n ]，A [ 1, …, n ]进行选择，转步骤8；步骤8: 对新的 M 个子种群重新开始蚁群算法操作，转步骤1，具体流程见图2。

初始化N个子种群每个子种群独立进行蚁群算法一定次数N个结果蚁群及函数值记录到R[I, j] 及A[ I ] 中性能满足？对R [1…N, I…n ] 进行选择对新的M个子种群重新开始蚁群算法操作结束Y图2 蚁群算法流程图 实验结果表明，在TSP问题中应用蚁群算法进行最短路径求解，在城市数量不多时，结果还是挺令人满意的3.3 蚁群算法的局限性由前面对蚁群算法的介绍可知，蚁群算法在运算过程中，蚁群的转移是由各条路径上留下的信息量的强度和城市之间的距离来引导的蚁群运动的路径总是趋近于信息量最强的路径通过对蚁群以及蚁群算法的研究表明，不论是真实蚁群系统还是人工蚁群系统，通常情况下，信息量最强的路径与所需要的最优路径比较接近然而，信息量最强的路径不是所需要的最优路径的情况仍然存在，而且在人工蚁群系统中，这种现象经常出现这是由于在人工蚁群系统中，各路径上的初始信息量是相同的，蚁群创建的第一条路径所用到的信息就主要是城市之间的距离信息这时，蚁群算法等价于贪婪算法，这一次，蚁群在所经过的路径上留下的信息就不一定能反映出最优路径的方向，特别是蚁群中个体数目较少或者所计算的路径的组合较多时，就更不能保证蚁群创建的一条路径能引导蚁群走向全局最优路径。

这一次循环中，蚁群留下的信息会因正反馈作用使这条路径不是最优，而且可能是离最优解相差很远的路径上的信息得到不应有的增强，而阻碍以后的蚂蚁发现更好的全局最优解不仅是第一次循环所创建的路径可能对蚁群产生误导，任何一次循环，只要这次循环所利用的信息较平均地分布在各个方向上，这次循环所产生的路径就可能会对以后蚁群的选择产生误导蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合，这种算法在构造解的过程中，利用随机选择策略，这种选择策略使得进化速度较慢，正反馈原理旨在强化性能较好的解，却容易出现停滞现象，这是造成蚁群算法不足之处的根本原因当问题规模比较大时，由于信息量的挥发系数 1- 的存在，使那些从未被搜索到的解上信息量会减小到接近于0，降低了算法的全局搜索能力，而且 1- 过大时，当解的信息量增大时，以前搜索过的解被选择的可能性过大，也会影响到算法的全局搜索能力通过减小 1- 虽然可以提高算法的全局搜索能力，但又会使算法的收敛速度降低也就是说蚁群算法与遗传算法等模拟进化算法一样，也存在着易于陷于局部最小值的缺陷因此，蚁群所找出的解需要通过一定的方法来增强，使蚁群所留下的信息尽可能地不对以后的蚁群产生误导，而且能够克服计算时间较长的缺陷，从而提高蚁群算法的全局搜索能力，提高其搜索速度。

第四章 蚁群算法的改进为了克服算法收敛速度慢，易陷于局部最优解的缺陷，算法可从如下几个方面进行改进4.1 优选参数m用蚁群算法求解问题，都存在算法有关参数的设定问题，较好的参数组合将会使算法具有全局的搜索能力和较快的收敛速度在其他参数不变的情况下，当蚂蚁数量太少,在能导致最优路径的那些边(优选边) 走过的次数较少, 难以留下较多的信息素, 不利于算法迅速向最优解收敛,而且当优选边在数代之内不能被再次选择时,其信息素将会挥发殆尽, 从而造成之前数代蚂蚁的优选结果浪费；而当 m 值太大,一方面会增加计算量,另一方面因为在最初的几代因为选择路径随机性比较大,最初的最优值因为蚂蚁多以至于得到强化的速度太快, 容易造成局部最优解蚁群算法中蚂蚁数目 m ，信息素残留系数,参数和 β 4个参数之间是相互耦合的,具有复杂的关系,所以算法中的4个参数应当综合考虑4.2 参数的调整 是表示信息素的残留程度, 该参数受城市 n 的影响较大,当城市 n 太大时,若挥发系数 1- 太大,算法的全局搜索能力会降低；若 1- 太小,算法的全局搜索能力会随之提高,但收敛速度会变慢,因此可以对采取自适应控制策略,即的初始值可取大些,随着循环次数的不断增加,可根据下列函数做调整: ⑹式子中的 Tc 表示禁忌表[ tabu ] k 中的元素, 禁忌表[ tabu ] k 用来记录蚂蚁 k 当前已经走过的城市, μ 为挥发约束系数， ⑺4.3 信息素的更新在进行路径寻优过程中,为了避免算法停滞和扩散,可以将残留信息素数量限制在[min , max ] , min 可以有效地避免算法的停滞,而 max 可以避免某条路径上的信息素远大于其他路径,使得所有的蚂蚁都集中到同一条路径上来,从而限制了算法的扩散，因此可以采用如下方式来对信息素进行更新。

⑻4.4 信息素链表 L 和禁忌链表 TL 的构建在蚁群算法中构建一个链表 L ,当算法运行 h 次后,将各条边上的信息素存放在链表 L 中,同时为了加快收敛速度,把信息素含量特少的一定数量的边加入到 TL ( Tabulist )中, TL 中的路径将被排除在选取的范围外,即忘记“不好”的路径禁忌表[ tabu ] k ( k = 1，2，…，m ) 用来记录蚂蚁 k 当前走过的城市,[ tabu ]k中的元素将随着进化过程做动态的调整蚂蚁在运动的过程中，根据链表中各条路径上的信息素以及路径的启发信息来计算转移概率 Pkij ( t ) , ⑼ 第五章 改进的算法基本流程初始化各参数 α, β,, m,min,max, n, η 每只蚂蚁从起点城市开始周游城市，利用禁忌表来判断蚂蚁的一次周游是否完成；若没有完成,则根据式子(8) 计算出来的转移概率来决定选择下一个城市,并更改禁忌表；对每只蚂蚁经过的路径执行局部更新规则(根据(6)式调整参数;根据(7) 式对信息素进行更新),得到新的最优解,并对最优解进行更新；若尚未达到指定的周游次数,转到步骤(2)输出最优解。

第六章 结论放到下一页本文通过对蚁群优化算法的基本原理和模型进行分析来解决 TSP 问题并且提出了一种改进的蚁群算法，该方法通过改变信息素和挥发系数的更新方式、构造信息素链表和禁忌链表等方法来加快算法的收敛速度,扩大子解的搜索空间,有效地缓解了基本蚁群算法容易出现的早熟、停滞现象实验表明改进后的算法有效地提高了蚁群的收敛速度,并且表现出良好的稳定性蚁群算法是一种原理相对简单的新兴仿生进化算法,在众多领域中已展现出它的特点和魅力但蚁群算法理论与遗传算法、禁忌搜索算法等理论相比还远不成熟，实际应用也远未挖掘出其真正潜力，还有很多富有挑战性的课题亟待解决主要体现在以下几个方面:　　⑴ 加强蚁群算法的基础理论研究，进一步发展新的数学分析和建模工具，尤其对算法的基础理论研究非常重要,包括对解决不同优化问题时收敛性和收敛速度的估计、避免陷入局部最优值、鲁棒性分析以及 A, B, F, Q 等参数的设计理论目前尚未发现有关合理选择蚂蚁数量以及算法运行时间数学分析的论述因此，该算法的数学基础理论研究将成为今后研究的一个重要课题　　⑵ 可将蚁群算法与其他类型方法综合使用以开发混合优化方法，进而发展思想更先进、功能更强大、解决更复杂系统的智能行为。

将蚁群算法与神经网络、模糊控制、遗传算法、模拟退火算法等相融合，必将成为今后蚁群算法领域内新的研究热点　　⑶ 新的理论必须通过实践进行检验，在实践过程中，可以发现新问题，从而促进理论向前发展近年来，蚁群算法虽在众多领域得到了推广应用，但其中大多仅仅是对蚁群算法在该领域应用的一个简单仿真因此，今后应充分挖掘蚁群算法在实际应用中的潜力，在对现有应用领域进行深化研究的同时，进一步扩大其应用范围此外，蚁群算法的硬件实现也将成为研究的热点方向之一对上述问题的深入研究必将大大促进蚁群算法理论和应用的发展，蚁群算法也必将在智能计算领域中展现出更加光明的前景参考文献:居中，放到下一页 [1] 吴桂芳，武宏华.求解TSP问题的蚁群算法研究[N].广西民族大学学报，2007-5-12（1）.[2] 谢宏.蚁群算法解决TSP问题的研究[J].农业网络信息，2007,13（3）：22-24.[3] 段海滨，王道波，朱家强，等.蚁群算法理论及应用研究的进展[J].控制与决策，2004，19（12）：1321-1325.[4] 赵文彬，孙志毅，李红.一种求解TSP问题的相遇蚁群算法[J].计算机工程，2004，30（12）：136-138.[5] 吴义虎，李宁，杨秋实.一种改进的蚁群算法及其在TSP问题中的应用[N].长沙交通学院学报，2007-6-23(2).[6] 胡小兵，黄席樾.蚁群优化算法及其应用[J].计算机仿真，2004，21（5）：81-85.[7] 王芳.蚁群算法的原理及其应用[N].潍坊教育学院学报，2005-6（1）.[8] 陈敏，徐东平.基于蚁群优化算法的TSP问题研究[J].福建电脑，2007,3: 117-128.[9] MIN Ke-xue，GE Hong-wei，ZHANG Yi，LIANG Yan-chun. Solving Traveling Salesman Problems by an ACO-and-PSO-Based Hybrid Algorith[J]. Journal of Jilin University Information Science Editio, July 2006, 24(4): 2378-2383.[10] James Kennedy and Russell Eberhart. Particle Swarm Optimization [J]. Purdue School of Engineering and Technology Indianapolis, 2002, 36: 1942-1948.致 谢在此感谢山东理工大学的各位专业老师的指导和帮助。

在毕业论文写作过程中，得到了贵校和山西大同大学老师的大力支持，给予了我很大的帮助在此向指导老师表示衷心的谢意同时还要感谢函授站在对我的精心指导和严格要求，使我获得了丰富的理论知识，极大地提高了实践能力，并对当前电子领域的研究状况和发展方向有了一定的了解。