蚁群算法在TSP问题上的应用研究.doc

《蚁群算法在TSP问题上的应用研究.doc》由会员分享，可在线阅读，更多相关《蚁群算法在TSP问题上的应用研究.doc（20页珍藏版）》请在三一办公上搜索。

1、中南民族大学毕业论文(设计)学院: 计算机科学学院 专业:计算机科学与技术年级:2008 题目: 蚁群算法在TSP问题上的应用研究学生姓名: 学号: 指导教师姓名: 职称: 2012年5月10日中南民族大学本科毕业论文（设计）原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。本人完全意识到本声明的法律后果由本人承担。 作者签名： 年 月 日 目录摘要1Abstract11.引言22.TSP问题简介22.1TSP问题的概述22.2TSP 问题意义23.蚁群算法简介33.1

2、蚁群算法的起源33.2蚁群算法的发展33.3蚁群算法的特点34.基本蚁群算法的原理4.4.1 蚁群行为描述44.2 基本蚁群算法的机制原理54.3 基本蚁群算法的系统学特征64.3.1 分布式64.3.2正反馈74.3.3自组织74.4 蚁群算法的数学模型74.5 基本蚁群算法求解 TSP 的实现流程94.5.1 基本蚁群算法的实现步骤94.5.2 基本蚁群算法的结构流程104.6基本蚁群算法运行结果115.关键参数设置对于路径的影响115.1关键参数介绍115.2信息挥发度的设置对结果的影响125.3启发因子的设置对结果的影响125.4蚂蚁数量的设置对结果的影响13结论14致谢15参考文献1

3、6蚁群算法在TSP问题上的应用研究摘要：随着二十一世纪的到来。计算机已经成为人们生活不可缺少的一部分，越来越多的难题问题通过计算机迎刃而解，从而也引发出一批智能算法，蚁群算法就是其中的代表之一，本文研究了基于蚁群算法解决 TSP 问题的原理，算法流程。论文首先简单回顾了蚁群算法的历史、发展以及应用，然后详细介绍了基本蚁群算法的原理，包括基本蚁群算法的行为描述和机制原理。其次从基本蚁群算法的系统学特征出发，讨论它具有分布式，自组织，正反馈等特征。接着引出了基本蚁群算法解决的 TSP 问题，从 TSP 问题的定义，实用价值，理论意义的角度对 TSP 问题进行阐述。给出了求解 TSP 问题的数学模型

4、，实现步骤，描述了蚁群算法的优缺点。本文主要运用VS2008为开发工具，以C+作为编程语言，对蚁群算法解决TSP问题进行研究，对其主要参数进行了详细的讨论，并且给出了优化的参数选择，解决了算法中存在的不足。论文实现了基于蚁群算法对 TSP 问题的求解和仿真。关键字：蚁群算法，参数，TSP 问题，自组织，正反馈。 Ant Colony Algorithm For The TSP Problem Applied ResearcAbstract：With the advent of the twenty-first century,The computer has become an indispe

5、nsable part of peoples lives,More and more the problem is solved by computer.Which also led to a number of intelligent algorithm,Ant colony algorithm is one of the representatives of,In this paper, the principle based on ant colony algorithm to solve TSP problems.Algorithm processes.Firstly, a brief

6、 review of the history of the ant colony algorithm.Development and application of,Then described in detail the basic principle of ant colony algorithm,Behavioral description of the basic ant colony algorithm and mechanisms principle.Secondly, starting from the system characteristics of the basic ant

7、 colony algorithm,Discuss it with a distributed, self-organizing positive feedback characteristics.Then leads to the basic ant colony algorithm to solve TSP problems,From the definition of the TSP,Practical value,Theoretical significance of the perspective of the TSP problems described.give The math

8、ematical model for TSP,Implementation steps,Describes the advantages and disadvantages of the ant colony algorithmIn this paper, use the VS2008 for development tools,C + + as programming language,The ant colony algorithm to solve TSP,Its main parameters are discussed in detail,And gives the optimize

9、d parameter selection,Address the deficiencies in the algorithm.Paper to achieve the TSP problem solving and simulation based on ant colony algorithmKey Word: Ant Colony Algorithm Parameter TSP problem Self-organization Positive feedback。1.引言 自然界一直是人类创造了的丰富源泉，人类认识事物的能力来源于与自然界的相互作用之中，自然界的许多的自适应优化形象不断

10、的给人以启示：生物体和自然生态系统成千上万年的不断进化，不但向人民展示出大自然的无限创造力和无穷的智慧，而且人类通过对生物的生理结构和行为规律的研究，为许多在人类看来高度复杂的问题提供很好解决办法。近些年来一些与经典数学规划原理截然不同的，试图通过模拟自然生态系统机制以求解复杂优化问题的仿生学算法相继出现，而蚁群算法就是其中的代表之一，生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智商不高，看起来没有集中指挥，但他们却能依靠群体能力完成协同工作，集中食物，建立蚁穴等一系列复杂的群体协同工作。蚁群算法作为一种新发展的模拟昆虫中蚂蚁智能行为的仿生学算法，它的诞生源于一个著名的数学问题TSP问题（

11、旅行商问题），TSP问题是一个局部最优的最优化问题，人们为了解决这问题想了许多方法，渐渐的人们发现在解决这个问题时，计算机具有人脑是不具备的优势，并发展出许多算法，蚁群算法具有较强的鲁棒性，优良的分布式计算机制，易于与其他算法结合的有点，从而使这种新兴的算法展现出勃勃生机和广阔的发展前景2.TSP问题简介2.1TSP问题的概述 旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。简单来说它是：假设有一个旅行商人要拜访N个城市，必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路

12、程为所有路径之中的最小值。 TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。1948年由美国RAND公司引入TSP问题，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题。 2.2TSP 问题意义TSP问题广泛的存在于许多领域，而且问题规模（城市的数目）都很大。比如说，电路板钻孔问题，X射线结晶学问题，VLSL（超大规模集成电路）制造问题等等。总之，凡是可以抽象成为遍历全部城市一次且仅一次，求代价最小的路径的问题，都可以当作TSP问题来解决.同实用价值相比，TSP问题的理

13、论意义更加重大。事实上，该问题是作为所有组合优化问题的范例而存在的11。它己经成为并将继续成为测试新算法的标准问题。这是因为，TSP问题展示了组合优化的所有方面。它从概念上来讲非常简单，但是其求解的难度是很大的。如果针对TSP问题提出的某种算法能够取得比较好的实算效果，那么对其进行修改，就可以应用于其它类型的组合优化问题并取得良好的效果。基于上述原因，该问题吸引了许多不同领域的研究者。3.蚁群算法简介3.1蚁群算法的起源蚂蚁:大自然中一种渺小却又让人敬畏的生物，它们个体很小，头脑也很简单但却依靠群体生活在残酷的大自然中获得极大的成功，成为世界上数量最多的生物也是最成功的物种之一，它们没有一个领

14、导者指挥，却行动一致，井然有序，在寻找食物等方面表现出极高的效率，和令人惊叹的能力。从而吸引许多科学家对其的兴趣。Marco Dorigo在长时间通过对蚂蚁的个体和群体行为进行长时间的观察和研究后，于1992年在他的博士论文中提出蚁群算法(ant colony optimization, ACO)。 3.2蚁群算法的发展蚁群算法又称蚂蚁算法，蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值蚁群优化算法最初用于解决TSP

15、问题，经过多年的发展，已经陆续渗透到其他领域中，如，图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域己获得成功的应用，其中最成功的是在组合优化问题中的应用。在网络路由处理中，网络的流量分布不断变化，网络链路或结点也会随机地失效或重新加入。蚁群的 自身催化与正向反馈机制正好符合了这类问题的求解特点，因而，蚁群算法在网络领域得到一定应用。蚁群觅食行为所呈现出的并行与分布特性使得算法特别适合于 并行化处理。因而，实现算法的并行化执行对于大量复杂的实际应用问题的求解来说是极具潜力的。 在某群体中若存在众多无智能的个体，它们通过相互之间的简单合作所

16、表现出来的智能行为即称为集群智能(Swarm Intelligence)。互联网上的交流，不过是更多的神经元连接(人脑)通过互联网相互作用的结果，光缆和路由器不过是轴突和突触的延伸。从自组织 现象的角度上看，人脑的智能和蚁群也没有本质上的区别，单个神经元没有智能可言，单个蚂蚁也没有，但是通过连接形成的体系，是一个智能体。3.3蚁群算法的特点蚁群算法是一种自组织的算法，在系统论中，自组织和它组织是组织的两个基本分类，其区别在于组织力或组织指令是来自于系统的内部还是来 自于系统的外部，来自于系统内部的是自组织，来自于系统外部的是他组织。如果系统在获得空间的、时间的或者功能结构的过程中，没有外界的特

17、定干预，我们便 说系统是自组织的。在抽象意义上讲，自组织就是在没有外界作用下使得系统墒增加的过程(即是系统从无序到有序的变化过程)。蚁群算法充分休现了这个过程， 以蚂蚁群体优化为例子说明。当算法开始的初期，单个的人工蚂蚁无序的寻找解，算法经过一段时间的演化，人工蚂蚁间通过信息激素的作用，自发的越来越趋向于 寻找到接近最优解的一些解，这就是一个无序到有序的过程。 蚁群算法是一种本质上并行的算法每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多agent系统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力

18、。 蚁群算法是一种正反馈的算法从真实蚂蚁的觅食过程中我们不难看出，蚂蚁能够最终找到最短 路径，直接依赖于最短路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程。对蚁群算法来说，初始时刻在环境中存在完全相同的信息激素，给予系统 一个微小扰动，使得各个边上的轨迹浓度不相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素，而更多的信息激 素又吸引了更多的蚂蚁，这个正反馈的过程使得初始的不同得到不断的扩大，同时又引导整个系统向最优解的方向进化。因此，正反馈是蚂蚁算法的重要特征，它使得算法演化过程得以进行。 蚁群算法具有较强的鲁棒性相对于其它算法，蚁群算法对

19、初始路线要求不高，即蚁群算法的求解结果不依赖子初始路线的选择，而且在搜索过程中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其它组合优化问题的求解。4.基本蚁群算法的原理.4.1 蚁群行为描述根据仿生学家的长期研究发现：蚂蚁虽然没有视觉，但运动时会通过在路径上释放出一种特殊的分泌物信息素来寻找路径。当它们碰到一个还没有走过的路口的时，就随机的挑选一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口的时候，选择信息量较大路径的概率相对较大，这样便形成了一个正反馈机制。最优路径上的信息量越来越大，而其他路

20、径上的信息量却会随着时间的流逝而逐渐消减，最终整个蚁群会找出最优路径。同时蚁群还能够适应环境的变化，当蚁群的运动路径上突然出现障碍物时，蚂蚁也能很快的重新找到最优路径。可见，在整个寻径过程中，虽然单只蚂蚁的选择能力有限，但是通过信息素的作用使整个蚁群行为找出最优路径。这里用人工蚂蚁觅食图来描述蚁群搜索原理。 如图a设 A 点是蚁巢，D 点是食物源，EF 之间区域是障碍物。由于障碍物的存在蚂蚁只能经由 A 经 E 或 F 到达 D，或由 D 到达 A，各点之间的距离如图 所示。假设每个时间单位有 30 只蚂蚁由 A 到达 D 点，有 30 只蚂蚁由 D 到达 A 点，蚂蚁过后留下的信息量为 1。

21、为了方便起见，设该物质停留时间为 1。在初始时刻，由于路径 BF、FC、BE、EC 上均无信息存在，位于 A 和 D 的蚂蚁可以随机选择路径，从统计学的角度可以认为蚂蚁以相同的概率选择 BE、FC、BE、EC，如图 b所示。经过一个时间单位后，在路径BFC 上的信息量是路径 BEC 上的信息量的 2 倍。又经过一段时间，将有 20 只蚂蚁由 B、F 和 C 点到达D，如图c 所示。随着时间的推移，蚂蚁将会以越来越大的概率选择路径 BFC，最终将会完全选择 BFC，从而找到由蚁巢到食物源的最短路径。4.2 基本蚁群算法的机制原理模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入，该算法

22、基于以下基本假设：1.蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对其周围的局部环境产生影响。2.蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的适应性表现，即蚂蚁是反应型适应性主体。3在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该路径越容易被选择；时间越长，信息量会越小；在协

23、作阶段，候选解之间通过信息交流，以期望产生性能更好的解。蚁群算法实际上是一类智能多主体系统，其自组织机制使得蚁群算法不需要对所求的问题的每一方面都有详尽的认识。自组织本质上体现了从无序到有序的动态演化，其逻辑结构如下图所示。 基本蚁群算法的逻辑结构由上图 可见，先将具体的组合优化问题表述成规范的格式，然后利用蚁群算法在“探索”和“利用”之间根据信息素这一反馈载体确定决策点，同时按照相应的信息素更新规则对每只蚂蚁个体的信息素进行增量构建，随后从整体角度规划出蚁群活动的行为方向，周而复始，即可求出组合优化的最优解。4.3 基本蚁群算法的系统学特征基本蚁群算法在系统学上表现以下三个特征：分布式，自组

24、织，正反馈。三者表现出一个整体，相辅相成。4.3.1 分布式自然界中的真实蚁群行为也出现了分布式。当蚁群需要完成某项工作时，其中的许多蚂蚁都为共同目的进行着同样的工作，而最终任务的完成不会由于某些个体的的缺陷而受到影响。蚁群算法作为对蚁群觅食行为的抽象，也体现了群体行为的分布式特征。每只人工蚂蚁从抽象意义上讲，自组织就是在没有外界作用下使得系统从无序到有序的进化过程。基本蚁群算法体现了这一过程，以蚁群优化为例，当算法开始的初期，单只人工蚂蚁无序地寻找解，经过一段时间的算法演化，人工蚂蚁越来越趋向于寻找到接近最优解的一些解，这恰恰体现了从无序到有序的自组织进化。自组织大大增强了算法的鲁棒性5（在

25、这里可以理解为算法抗干扰性,就是指不是针对具体问题算法也同样可以求解,极大的体现了蚁群算法的抗干扰能力），传统的算法都是针对某一具体问题而设计的，这往往建立在对该问题有了全面清晰认识的基础上，通常很难适应其他问题。而自组织的蚁群算法不需要对待求解问题的所有问题的所有方面都有所认识，因而较容易应用到一类问题中。4.3.2正反馈反馈是控制论中的重要概念，它代表信息输入对输出的反作用。在系统学上认为，反馈就是把系统现在的行为作为影响系统未来行为的原因。反馈分正反馈和负反馈两种，前者指的是以现在的行为去加强未来的行为，而后者则是以现在的行为去削弱未来的行为。由自然界中真实蚂蚁的觅食行为可见，蚂蚁能够最

26、终找到最短路径，直接依赖于最短路在问题空间的多个点同时开始相互独立地构造问题解，而整个问题的求解不会因为某只人工蚂蚁无法成功获得解而受到影响。具体到不同的优化问题而言，蚁群算法体现出的分布式特征就具有了更加现实的意义。因为所有的仿生优化算法均可看做按照一定规则的问题解空间搜索最优解的过程，所以搜索点的初始选取就直接关系到算法求解结果的优劣和算法寻优效率。当求解许多复杂问题时，从一点出发的搜索受到局部特征的限制，可得不到所求问题的满意解；而基本蚁群算法则可看做是一个分布式的多智能系统，它在问题空间的多点同时独立地进行解搜索，不仅使得算法具有较强的全局搜索能力，也增加了算法的可靠性。4.3.3自组

27、织基本蚁群算法的另一个重要特征是自组织。自组织的概念是随着系统科学的发展而建立起来的。通常把系统论中的组织行为分为自组织和他组织两大类。其根本区别在于组织力或组织指令是来自于系统内部还是来自于系统外部，前者称为自组织，而后者即为他组织。如果系统在获得时间的、空间的或者功能的结果过程中，没有外界的特定干预，则称为系统是自组织的。径上信息素的堆积，而信息素的堆积却是一个正反馈的过程，对于基本蚁群算法而言，初始时在环境中存在完全相同的信息量，给系统一个微小的扰动，使得各个边上的信息量大小不同，蚂蚁构造的解就存在了优劣。算法采用的反馈方式是在较优解经过的路径留下更多的信息素，更多的信息素又吸引了更多的

28、蚂蚁，这个正反馈的过程使得初始值不断地扩大，同时又引导整个系统向着最优解的方向进化。单一的正反馈或者负反馈存在于线形系统之中，是无法实现系统的自我组织的。自组织系统通过正反馈和负反馈机制，它体现于蚁群算法在构造问题解的过程中用到了概率搜索技术，通过该技术增加了生成解的随机性。随机性的影响就在于接受了解在一定程度上的退化，另一方面又使得搜索范围得以在一段时间内保持足够大。这样正反馈缩小搜索范围，保证算法朝着最优解的方向进行；而负反馈保持搜索范围，避免算法过早收敛于不好的结果。恰恰是在正反馈和负反馈共同作用影响下，基本蚁群算法得以自组织地进化，从而得到问题在一.定程度上的满意解。4.4 蚁群算法的

29、数学模型设ij(t) 为 t 时刻路径（i,j）上的信息量，n 表示 TSP 规模，m 为蚁群中蚂蚁的总数目。在初始时刻各条路径上的信息量相等，并设ij(0) = const 。蚂蚁k（k=1,2,m）在运动过程中，根据各条路径上的信息量决定其转移方向，这里用禁忌表tabuk(k=1,2,m)来记录蚂蚁k当前所走过的城市，集合随着 tabuk进化过程作动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。 pijk(t) 表示在t蚂蚁k由城市i转移到城市j的状态转移概率 （公式一） 式中，allowedk表示蚂蚁k下一步允许选择的城市； 为信息启发式因子，表示轨

30、迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时的所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强； 为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态转移概率越接近于贪心规则；ij(t ) 为启发函数，其表达式如下 ij(t )=1/dij （公式二） 式中， dij表示相邻两个城市之间的距离。对蚂蚁 k 而言， dij越小，则ij(t) 越大， pijk(t) 也就越大。显然，该启发函数表示蚂蚁从城市 i 转移到城市 j 的期望程度。为了避免残留信息素过多引起残留信息淹没启

31、发信息，在每只蚂蚁走完一步或者完成对所有 n 个城市遍历（也即一个循环结束）后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存入大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。由此，t+n 时刻在路径（i,j）上的信息量可按如下规则进行调整 (公式三) ，(公式四)式中， 表示信息素挥发系数，则1-表示信息素残留因子，为了防止信息的无限积累，的取值范围为： 0,1) ；ij(t ) 表示本次循环中路径（ i,j）上的信息素增量，初始时刻ij(0) = 0 ，ijk(t) 表示第 k 只蚂蚁在本次循环中留在路径（i,j）上的信息量。根据信息素更新

32、策略的不同，Dorigo M 提出了三种不同的基本蚁群算法模型，分别称之为 Ant-Cycle 模型、Ant-Quantity 模型及 Ant-Density 模型，其差别在于ijk(t) 求法的不同。在 Ant-Cycle 模型中 （ 公式五）式中，Q 表示信息素强度，它在一定程度上影响算法的收敛程度； Lk表示第 k 只蚂蚁在本次循环中所走过路径的总长度。在 Ant-Quantity 模型中 （公式六）在 Ant-Density 模型中（公式七）公式（公式六）和（公式七）中利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素；而公式（ 公式一）中利用的是整体信息，即蚂蚁完成一次循环后更新所

33、有路径上的信息素，在求解 TSP 时性能较好，因此通常采用公式（ 公式五）作为蚁群算法的基本模型。4.5 基本蚁群算法求解 TSP 的实现流程4.5.1 基本蚁群算法的实现步骤以 TSP 为例，基本蚁群算法的具体实现步骤如下：（1）参数初始化。令时间 t=0 和循环次数 Nc=0，设置最大循环次数 Ncmax，将 m 只蚂蚁置于 n 个城市上，令每条边（i,j）的初始化信息量ij(t) = const ，其中 const 表示常数，且初始时刻 ij(0) = 0 。（2）循环次数NC NC + 1（3）蚂蚁的禁忌表索引号 k=1（4）蚂蚁数目 k k + 1。（5）蚂蚁个体根据状态转移概率公式

34、（公式一）计算的概率选择城市 j。（6）修改禁忌表指针，即选择好之后将蚂蚁移动到新的城市，并把该城市移动到该蚂蚁个体的禁忌表中。（7）若集合 C 中的城市未遍历完，即 km,则跳转到到第（4）步，否则继续往下一步执行。（8）根据公式（公式三）和（公式四）更新每条路径上的信息量。（9）若满足结束条件，即循环次数 NC NcMAX，则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第（2）步。4.5.2 基本蚁群算法的结构流程以 TSP 为例，基本蚁群算法的结构流程如下图所示。 蚁群算法基本流程结构图4.6基本蚁群算法运行结果 程序采用的是国际通用的eil51.tsp城市坐标数据（城市名是151

35、），其最短路径长度为426，对信息启发式因子 ，期望启发式因子 ，蚂蚁数目 m，挥发系数 ，蚂蚁信息素强度Q进行设置 =1， =2， =0.5，m=51，Q=100，运行结果为：第一次：第二次： 由于蚂蚁所选路径是不确定的有的选择的路径可能较短，而其他的则可能较长，因此运算的时间，和结果也不尽相同。5.关键参数设置对于路径的影响5.1关键参数介绍群算法中 . 等参数对算法性能有很大的影响。值的大小表明留在每个结点上的信息量受重视的程度，值越大，蚂蚁选择以前经过的路线的可能性越大，但过大会使搜索过早陷于局部最小解； 的大小表明启发式信息受重视的程度， 值越大，蚂蚁选择离它近的城市的可能性越大；表

36、示信息素的保留率，如果它的值取的不恰当，得到的结果会很不理想。5.2信息挥发度的设置对结果的影响在蚁群算法中，人工蚂蚁是具有人类记忆功能的，随着时间的推移，以前留下的信息将要逐渐消逝。在算法模型中用参数 表示信息消逝程度（或称信息素挥发度），而1 就是信息素保留系数。蚁群算法存在着收敛速度慢、易于陷入局部最优等缺陷。而信息素挥发度 的大小直接关系到蚁群算法的全局搜索能力及其收敛速度：由于信息素 的存在，当要处理的问题规模比较大时，会使那些从来未被搜索到的路径（可行解）上的信息量减小到接近于0，因而降低了算法的全局搜索能力，而且当 过大时以前搜索过的路径被再次选择的可能性过大，也会影响到算法的随

37、机性能和全局搜索能力；反之，通过减小信息素挥发度 虽然可以提高算法的随机性能和全局搜索能力，但又会使算法的收敛速度降低。不同挥发度下的最优解值（迭代次数2000，蚂蚁数量30）挥发度第一次第二次第三次第四次第五次平均值0.14454444404474504450.24484374444374394410.34354394394374374370.44524484504474444480.54414364364494484420.64404474444484404430.74464454384414454430.84444364384394424390.9444444446443445444 由

38、以上结果可知=0.3时效果最佳，当挥发度较小时残留激素对蚂蚁影响较大，导致容易形成局部最优解，而从0.5到0.9平均值几乎一样，同样说明当挥发度过大时，算法需要更多的迭代次数来获取最优解，这是由于挥发度过大，导致随机性增强，全局搜索能力增强，导致需要更大 的运算量。5.3启发因子的设置对结果的影响信息启发式因子 反映蚂蚁在运动过程中所积累的信息量(即残留信息量ij(t ) )在指导蚁群搜索中的相对重要程度，期望值启发式因子 反映蚂蚁在运动过程中启发信息(即期望值ij)在指导蚁群搜索中的相对重要程度。期望值启发式因子 的大小反映了蚁群在路径搜索中先验性、确定性。 因素作用的强度，其值越大，蚂蚁在

39、某个局部点上选择局部最短路径的可能性越大，虽然搜索的收敛速度得以加快，但蚁群在最优路径的搜索过程中随机性减弱，易于陷入局部最优;而信息启发式因子 的大小则反映了蚁群在路径搜索中随机性因素作用的强度，其值越大，蚂蚁选择以前走过的路径的可能性越大，搜索的随机性减弱，当 值过大也会使蚁群的搜索过早陷于局部最优。蚁群算法的全局寻优性能，首先要求蚁群的搜索过程必须有很强的随机性;而蚁群算法的快速收敛性能，又要求蚁群的搜索过程必须要有较高的确定性。因此，两者对蚁群算法性能的影响和作用是相互配合、密切相关的。 不同启发因子下最优解值（迭代次数2000，蚂蚁数量30，挥发度0.3）启动因子第一次第二次第三次第

40、四次第五次平均值0.16306356266226230.549949850748848114384404454434361.546745246244844524684654584694595495474487508493 当较小时，蚂蚁完全依赖期望因子进行引导，城市距离将成为蚂蚁选择路径的重要因素，当较大时，蚂蚁将主要依靠信息素进行引导，其他蚂蚁走过的路径将成为下一只蚂蚁的首选。不同期望启发因子最优解（迭代次数2000，蚂蚁数量30，挥发度0.3）期望启发因子第一次第二次第三次第四次第五次平均值0.552354056053652014464704664664712436443440444444

41、44364444454444468450449443455452当较小时，蚂蚁主要依靠其他蚂蚁的残留激素进行选择，当过大时城市距离将成为蚂蚁的首选要素，当都较小时蚂蚁将陷入无限随机循环中，当都偏大是路径将过早决定，此时结果往往是局部最优解，所以=1，=2为佳。5.4蚂蚁数量的设置对结果的影响蚁群算法是一种随机搜索算法，通过多个候选解(可行解的一个子集)组成的群体的进化过程来寻求最优解，在该过程中既需要每个个体的自适应能力，更需要群体的相互协作。蚁群在搜索过程中之所以表现出复杂而有序的行为，个体之间的信息交流与相互协作起着至关重要的作用。对于 TSP 问题，单个蚂蚁在一次循环中所经过的路径，表现

42、为问题可行解集中的一个解，m只蚂蚁在一次循环中所经过的路径，则表现为问题解集中的一个子集。显然;子集越大(即蚁群数量多)可以提高蚁群算法的全局搜索能力以及算法的稳定性;但蚂蚁数目增大后，会使大量的曾被搜索过的解(路径)上的信息量的变化比较平均，信息正反馈的作用不明显，搜索的随机性虽然得到了加强，但收敛速度减慢;反之，子集较小(即蚁群数量少)，特别是当要处理的问题规模比较大时，会使那些从来未被搜索到的解(路径)上的信息量减小到接近于 0，搜索的随机性减弱，虽然收敛速度加快，但会使算法的全局性能降低，算法的稳定性差，容易出现过早停滞现象。 在不同蚂蚁数量下运行5次的值及其平均值迭代次数设置为200

43、0次（表三） 蚂蚁数量 第一次 第二次第三次第四次第五次平均值104384524504374444441544844443744743644220445440437447436441254414474404444424423045045143643143444035440439443437448441404364374394424494404544644144544444544450438444443442436440从上表结果，发现当蚂蚁数量越大，其值之间的波幅越小说明结果其算法稳定性高，除此之外还有个有趣的现象，从理论上来说当蚂蚁数量越大，去其最优解应该越小，但是我们发现结果不是这样，从3

44、050 开始除了45的444其他几组平均值几乎一样，说明当蚂蚁数量越多是需要更多的迭代次数才能求出最优解，而几组数据一样说明2000次迭代已经不能满足运算需求了。 结论在基本蚁群算法中，蚂蚁数量，启发因子，期望启发因子，及挥发度的参数的设定直接决定了算法的结果的优化程度。所以良好的参数设定能使蚁群算法更好运算出最优解。在当今强调人工智能化的时代趋势下，蚁群算法洽洽拥有这个优势，它的自动更新信息素浓度机制正是人工智能的体现，它能使人们减少许多不必要的工作量，因而在现在的发展中越来越受到人们的重视，蚁群算法在解决TSP问题是有着独特的优势，同时也存在着较早陷入局部最优解等缺点，运用基本蚁群算法并不

45、是解决TSP问题的最好选择，在长时间的实践中人们发现，在与其他算法相结合后，能更好的解决TSP问题，随着对蚁群算法的研究越来越深入，蚁群算法也开始应用于其他领域并获得巨大的成功 致谢 由于课题比较有学术性，因而在完成毕业设计的过程中会遇到许多问题问题，在此感谢周凌云老师对我的帮助和指导，在她的指导下我才能顺利的完成这篇论文，同时也感谢的我的同学对我帮助，他们的让我更好的完成了论文，并为我解决了许多麻烦的问题。毕业设计是大学生们走出校门前的最后的一次作业，是凝聚了大学四年的所学，也是对自己四年的最好的一个总结，告别大学我们将走入社会，从此我们将告别一个陪伴了我们十几年的学生身份，正式的成为这个社会的一员，毕业设计也是对我们独自工作能力的一个检验，运用一切可以运用的到资源来完成毕业设计，是对我的一次锻炼，运用在图书馆，因特网寻找帮助，查找资料，解