基于仿真平台上的蚁群算法的研究报告

《基于仿真平台上的蚁群算法的研究报告》由会员分享，可在线阅读，更多相关《基于仿真平台上的蚁群算法的研究报告（35页珍藏版）》请在装配图网上搜索。

1、-分类号：编号：论文编号：专业代码：班级：化工大学本科毕业论文题目：基于仿真平台上的蚁群算法的研究院系：信息工程学院专业：电气工程及其自动化班级：电气1301 学生：隋雷指导教师：高淑芝论文提交日期： 2017年 6 月 20 日论文辩论日期：2017年 6 月 27 日. z.-毕业设计论文诚信承诺书本人重承诺此处所提交的学位论文是在指导教师的指导下，严格按照学校和学院系有关规定完成的。论文中引用他人的观点和参考资料均加以注释和说明。在此毕业论文中不曾剽窃或者抄袭他人的学术思想、观点和成果，不曾篡改正研究的数据，如果存在违规的行为，我愿承当所有的责任并且愿意承受学校的处分。作者签名：日期：年

2、月日关于学位论文使用授权的说明本论文的研究成果归化工大学所有，本论文的研究容不得以其它单位的名义发表。本学位论文作者和指导教师完全了解化工大学有关保存、使用学位论文的规定，即：学校有权保存并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权化工大学可以将论文的全部或局部容编入有关数据库进展检索、交流，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。的论文在解密后应遵循此规定作者签名：导师签名：日期：年月日. z.-摘要在20世纪50年代的中期出现了仿生学，人们从生物进化的机理中受到了许多启发，提出了许多用以解决复杂优化问题的新方法，如遗传算法、进化规划、进化

3、策略等等，这些算法成功地解决了一些实际问题。20世纪90年代意大利学者MDorigo，VManiezzo，AColorni等人从生物进化的机制中受到启发，通过模拟自然界中蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法 蚁群算法，是群智能理论研究领域的一种主要算法。本论文主要研究了应用蚁群算法来解决TSP问题，分析了蚁群算法的根本原理，蚁群算法的流程以及用 MATLAB 程序来进展实例的仿真。本文首先简短的回忆了蚁群算法的历史、蚁群算法的开展和蚁群算法的应用，然后详细地介绍了蚁群算法的根本原理，包括蚁群算法的行为描述和机制原理，之后从蚁群算法的主要特征出发，分析它具有自组织、分布式和正反应等特

4、征。接着引出了应用蚁群算法来解决的TSP问题，先描述了组合优化问题，然后根据TSP问题自身的定义，TSP的实用价值，以及TSP问题的理论意义等多个角度来对 TSP 问题进展详细阐述。并且重点运用 MATLAB 的实例仿真方法，实现了基于蚁群算法的实例仿真，建立求解 TSP 问题的数学模型，实现步骤，阐述了蚁群算法的优缺点以及和其它优化方法的异同。论文最后以 MATLAB 仿真实验为根底，对蚁群算法的主要参数进展了详细的讨论，并且给出了优化的参数选择，解决了算法中存在的缺乏。论文实现了基于蚁群算法对 TSP 问题的求解和仿真。关键词：蚁群算法，组合优化， TSP 问题AbstractIn the

5、 mid-1950s, bionics emerged, and many people were inspired by the mechanism of biological evolution. Many new methods for solving plex optimization problems such as genetic algorithms, evolutionary planning, evolutionary strategies, etc. The algorithm successfully solved some practical problems. In

6、the 1990s, the Italian scholar M. Dorigo, V Maniezzo, A. Colorni et al., Inspired by the mechanism of biological evolution, proposed a new type of simulated evolutionary algorithm, an ant colony algorithm, which is a major algorithm in the field of cluster intelligence theory by simulating the behav

7、ior of ant search paths in nature.In this paper, the ant colony algorithm is used to solve the TSP problem. The basic principle of the ant colony algorithm, the flow of the ant colony algorithm and the MATLAB program are used to simulate the ant colony algorithm. In this paper, we briefly review the

8、 history of ant colony algorithm, the development of ant colony algorithm and the application of ant colony algorithm. Then we introduce the basic principle of ant colony algorithm, including the behavior description and mechanism of ant colony algorithm. The main characteristics of the group algori

9、thm, it has the characteristics of self-organization, distributed and positive feedback. Then, the TSP problem is solved by using the ant colony algorithm. Firstly, the problem of binatorial optimization is described. Then, the TSP problem is elaborated according to the definition of TSP problem, th

10、e practical value of TSP and the theoretical significance of TSP problem. The The method of simulation based on ant colony algorithm is implemented, and the mathematical model of TSP problem is established. The steps of the ant colony algorithm and the similarities and differences with other optimiz

11、ation methods are expounded. Based on the MATLAB simulation experiment, the main parameters of the ant colony algorithm are discussed in detail, and the optimal parameter selection is given, which solves the shortings of the algorithm. This paper realizes the solution and simulation of TSP problem b

12、ased on ant colony algorithm.Key Words: Ant Colony Algorithm; binatorial Optimization; TSP . z.-目录第一章引言11.1 蚁群算法研究背景11.2 蚁群算法研究现状11.3 论文的主要容1第二章蚁群算法的简介12.1 蚁群算法的原理12.2 蚁群算法的根本特征1分布式1自组织1正反应1第三章组合优化以及 TSP 问题简介13.1 组合优化简介13.1.1 引言13.1.2 组合优化问题13.1.3 NP 完全问题13.2 TSP 问题简介13.2.1 TSP 问题的定义13.2.2 TSP 的实用价值

13、13.2.3 TSP 问题的理论意义13.3 根本蚁群算法的数学模型1第四章根本蚁群算法求解TSP 14.1 根本蚁群算法求解 TSP 的实现流程14.1.1 根本蚁群算法的实现步骤14.1.2 根本蚁群算法的构造流程1第五章蚁群算法的主要参数设置15.1实验分析15.2实验设计15.3实验结果及结果分析1第六章总结和展望16.1 工作总结16.2 技术展望1参考文献1致1附录1. z.-第一章引言蚂蚁是地球上最多见、数量最为庞大的昆虫种类之一，经常成群结队地出现在人类的日常生活环境中。蚂蚁这种群居昆虫所拥有的一些智能生物特征，吸引了许多学者的密接关注。其中意大利的学者 M.Dorigo，V.

14、Maniezzo 等人在研究蚂蚁的觅食习惯时惊奇的发现，无论蚂蚁的巢穴距离食物源有多少条路径,它们总是可以找到巢穴距离食物源之间的最短路径。经过详细的研究成果说明，蚂蚁的这种群体生物之间的团结协作功能是通过一种遗留在其来来往往路径上的一种可挥发的化学性物质来进展相互协调和交流的。化学通信是蚁群之间进展根本信息交流的主要方式之一，在蚂蚁的生活习性中起着至关重要的作用。通过对整个蚁群的觅食习性的研究发现，整个蚁群就是通过这种可挥发的化学物质来进展相互交流,相互协作，并且形成了一种正反应，使多条路径上的蚂蚁最终都逐渐聚集到最短的那条路径上去。1.1 蚁群算法研究背景蚁群算法antcolonyalgr

15、othrim，ACA是由意大利学者多里戈DorigoM、马聂佐Maniezzo V等人在上个世纪九十年代初期于生物群体的进化机制中受到启发，通过模拟自然界中蚂蚁寻找食物搜索路径的行为，提出来的一种全新的模拟进化算法。该算法在蚁群搜索食物源的过程当中所表现出来的寻找最优路径的能力来解决一些复杂的系统优化问题，其算法的中心思想在于模仿蚂蚁依赖其所分泌的信息素，通过蚁群之间的正反应机制来引导每个蚂蚁的行动。蚁群算法可以被应用于解决大多数的组合优化问题或者是可以转化为优化求解的问题，目前其应用的领域更加广泛，已经扩展到数据分类、模式识别、数据聚类、多目标优化、电信QoS管理、机器人控制、信号处理、流程

16、规划以及系统辨识和仿真等方面。1.2 蚁群算法研究现状在社会科学和工程技术的开展中，需要解决问题的复杂性、约束性、非线性，建模困难等问题目渐突出。长时间以来，人们一直不断的努力寻找一种可以有效地解决这种问题的新方法。蚁群算法最初是由意大利学者MacroDorigo等人在蚂蚁觅食行为的启发下而提出的一种新型的元启发式算法，随着研究的逐步深入，MacroDorigo与其合作者于1991年设计出了第一个蚁群优化算法一蚁群系统。经过二十多年的开展，蚁群算法在实际应用上和理论当中都取得了突飞猛进。近几年来，因为蚁群算法在故障检测、数据挖掘、知识发现、路径归划等领域的广泛应用，研究的学者越来越多。蚁群算法

17、通过模拟蚂蚁在寻找食物过程当中，通过个体行为影响的累积，最后形成群体行为，从而找到适合问题的最优解。近些年来，国外学者针对蚁群算法的应用方面和模型改良方面做了大量的研究，其共同目标是在适宜的时间复杂度的情况下，尽可能提高蚁群算法在一定空间复杂度下的寻优能力，用来改善蚁群算法全局的收敛性，并且拓宽蚁群算法的应用领域。就目前发表的关于蚁群算法的学术论文来说，大约百分之六十的论文是蚁群算法在不同领域当中的关于优化的研究成果。目前，蚁群算法的应用围几乎已经关系到了各个优化的方面，但是仍然存在这许多缺乏，主要又以下的两个方面：1)从纵向上来说，蚁群算法的应用深度还不够广泛。由目前公开发表的研究成果说明，

18、大局部应用还只是停留在了仿真阶段，而且所研究的容大局部都是对实际问题约束条件或者是实验条件进展简化处理的前提下进展的。特别在动态优化问题、多目标优化问题、随机优化问题等方面的研究仍然需要进一步增加；2)从横向上来说，蚁群算法的应用领域还需要进一步地拓宽。不同的应用领域存在着许多不同的实际问题，尝试应用蚁群算法在不同的具体问题中的实际应用是今后的一项重要研究容。如何抽象地解决实际问题，使蚁群算法的求解更接近工程实际是广阔蚁群算法研究者所共同关注和需要改良的一个关键性问题。1.3 论文的主要容由于蚁群算法的多样性,并且 TSP 问题是蚁群算法众多解决问题中的经典问题,所以具有很大的随意性。虽然蚁群

19、算法的选择性很多，但是所有的算法都是基于最根本的蚁群算法，并且根本蚁群算法也可以很好的解决 TSP 问题，以及说明参数选择问题。所以本文以根本蚁群算法为根底，通过 MATLAB 仿真这个平台，重点讨论了根本蚁群算法如何解决 TSP 问题。第一章主要介绍了蚁群算法的历史、开展、应用，对蚁群算法原理的核心信息素作了简单的描述。第二章对根本蚁群算法的原理进展了介绍，包括根本蚁群算法的行为描述，机制原理。同时探讨了根本蚁群算法的系统学特征。第三章对组合优化以及 TSP 问题的定义，实用价值，理论意义进展了描述。并且介绍了根本蚁群算法求解 TSP 问题的数学模型。第四章首先介绍了利用根本蚁群算法的参数仿

20、真平台，及实现步骤和构造流程。并给出了用 MATLAB 实现的仿真结果。第五章主要讨论了蚁群算法中主要参数对于蚁群算法的全局搜索能力以及收敛性的影响，并做了相应仿真实验加以验证。第六章对蚁群算法的开展进展了展望，同时对本文进展了总结。. z.-第二章蚁群算法的简介2.1 蚁群算法的原理根据仿生学者的长期研究说明：蚂蚁这种群居生物虽然没有视觉，但运动时会通过在其经过的路径上释放出一种特别的分泌物信息素来搜索路径。当它们遇见一个全新的路口的时，就会随机的挑选其中的一条路径前行，同时开场释放与路径长度相关的信息素。蚂蚁所经过的路径越长，其释放的信息量浓度越小。当后来的蚂蚁再一次经过这个路口的时，将会

21、大概率地选择信息素浓度较高的路径，这样就形成了一种正反应的机制。最终该条路径上的信息素浓度将变得越来越大，相反随着时间的继续，其它路径上走过的蚂蚁越来越少，信息素浓度也变得越来越小，最终整个蚁群将会找出蚁穴距离食物源的最正确路径。同时蚁群还可以适应环境的变化，当蚁群在不断的运动过程中突然遇见障碍物时，蚂蚁也能很快地进展调整，重新找出一条最正确的路径。由此可知，在整个蚁群寻找路径的过程中，虽然每一只蚂蚁的行为能力和选择能力有限，但是整个蚁群却可以通过信息素的作用相互协调合作很快地找出最优的路径。下列图2.1用蚂蚁觅食的原理图来描述蚁群搜索最优路径的根本原理。图2.1 蚂蚁觅食原理图所有的蚂蚁从A

22、点出发，食物在D点，每只蚂蚁的移动速度一样，可随机选择的路线分别有ABD和ACD。如果初始时刻每条分配路线分别分配一只蚂蚁，每经过单位时间后蚂蚁行走一步，该图为经过了9个单位时间时的情况：当经过ABD的蚂蚁到达终点时，而经过ACD的蚂蚁此时刚好走到C点，为路程的一半。1假设蚂蚁每经过图中的每一点留下的信息素为一个单位，当经过36个时间单位时，一起出发的每一只蚂蚁都经过不同的路径从D点获得了食物，此时：ABD路线上的蚂蚁往返了2次，图中每个点遗留的的信息素为4个单位； ACD的路线上的蚂蚁往返了1次，每个点遗留的的信息素为2个单位；浓度比值为2：1。2如果寻找食物的过程仍在进展，那么按照信息素的

23、指导，蚁群在ABD路线上增加一只蚂蚁共2只，而ACD路线上依旧为一只蚂蚁。继续经过36个单位时间，两条线路上蚁群遗留的信息素含量积累分别为12单位和4个单位，比值变成了3：1。3寻找食物的过程继续进展，那么根据信息素的指引，最终所有的蚂蚁都会选择走ABD路线而放弃ACD线路。这也就是上文中所提及到的正反应机制。2.2 蚁群算法的根本特征蚁群算法在系统学上表现以下三个特征：分布式，自组织，正反应。三者表现出一个整体，相辅相成。2.2.1分布式大自然中的真实蚁群的行为表现出了分布式。每当蚁群需要完成某一项工作时，其中的绝大多数蚂蚁都为共同的一个目标进展着一样的工作，而不会因为单个个体的失误使最终的

24、结果受到影响。蚁群算法作为一种对蚁群觅食行为的抽象表达，也表达出了群体行为的分布式特征。每一只人工蚂蚁在问题空间中的多个点同时开场互不干扰地构造问题解，而整个问题的求解却不会因为某一只人工蚂蚁找不到最优解而受到影响。蚁群算法所具有的分布式特征对于许多的优化问题有的重要的意义，尤其是对于应用到不同的组合优化问题而言效果更为显著。因为几乎所有的仿生类的优化算法全都可以看做是这样的一个问题，该种算法是根据一定的规律在问题解的空间来搜索最优解的，所以针对一个这样的问题，初始时搜索点的选取将变得至关重要，这将直接地关系到该种算法的寻优效率和该算法求解结果时的优劣。这样根本蚁群算法就可以直接看成是一个具有

25、分布式特征的多智能化的系统，它在问题解空间的多个点同时互不干扰地进展最优解的搜索，不但加大了算法的可靠性，而且使算法拥有更强的全局搜索的能力。2.2.2自组织根本蚁群算法所拥有的另外一个重要的特征就是自组织。自组织的定义是跟随系统科学的进步而产生的。通常情况下可以把系统理论当中的组织行为分为自组织和他组织两大类。它们的根本区别在于组织的指令或者组织力是来源于系统的部还是系统的外部，如果来源于组织的部称之为自组织，相应地来源于外部称之为他组织。如果系统在获得结果过程当中，不曾遭到外界的特定干预，那么系统可以称之为是自组织的。从某种抽象的意义上来说，自组织就是系统在没有外界的作用下从无序进化到有序

26、的过程。根本蚁群算法为了实现了这一过程，以蚁群优化为样例，在算法开场的前期，单只人工蚂蚁不断地在无序地寻找解，当经过一段时间之后的算法演化后，人工蚁群越来越靠近最优解，直至找到最优解，这恰好表达出了人工蚁群从无序开展到有序的自组织进化过程。自组织还大大的增强了算法的鲁棒性在这里可以理解为算法的抗干扰能力,就是指当不针对某一具体的问题算法时也可以同样求解,极大的表现出了蚁群算法的抗干扰性，传统的优化算法通常都是针对了某一具体问题的而设计的，这就需要对该问题必须有全面的认知和理解能力，一般情况下很难适应到其他的优化问题。而由于蚁群算法所具有的自组织特性，所以使用蚁群算法解决实际问题时一般不必对求解

27、的问题的所有方面都做很深的理解，表达了蚁群算法的优越性。2.2.3正反应反应又可称为回馈，是控制理论当中的至关重要定义之一，它表示被控制的过程对控制机构的反作用。在系统学中可以这样理解，系统目前的行为对系统未来的行为产生了影响，而原因就是因为反应。反应又分为负反应和正反应两种状态，前者使输出信号起到与输入信号相反的作用，使系统的输出与系统目标之间的误差减小，系统逐渐趋于稳定；后者使输出信号起到与输入信号相近的作用，使系统的偏差不断增大，使系统振荡，可以起到放大控制的作用。根据自然界中真实蚂蚁的觅食习性可以知道，最终蚂蚁之所以能够找到蚁穴和食物源之间的最短路径，是因为最短路径上的信息素的积累，而

28、信息素的积累属于一个正反应的过程，对于蚁群算法而言，在初始时刻，系统中存在着完全一样的信息量，如果给系统一个轻微的干扰，这样系统中各个位置的信息量大小将变得不再一样，蚂蚁构造的解就产生了优劣。蚁群算法中所采取的反应方式就是：蚁群在经过较优解的路径上留下了越来越多的信息素，而大量的的信息素又吸引来了越来越多的蚂蚁，系统通过正反应的调节，使初始值不断地扩大，与此同时通过信息素的指引，整个系统逐步趋于最优解的方向进化。在线形系统当中，单一的负反应或者正反应是不具有系统的自我组织能力的。自组织系统通过负反应和正反应机制，应用概率搜索技术，通过该技术使生成解的随机性大大增加。一方面，由于随机性的影响，生

29、成解在一定程度上存在着的退化。在另一方面，在一定时间又使得搜索围能够保持的足够大。这样通过正反应缩小搜索围，使算法朝着最优解的方向进化；而负反应通过保持搜索围，防止了算法因为过早收敛而产生不好的结果。正是由于在负反应和正反应共同作用影响条件下，根本蚁群算法能够得以自组织地进化，从而获得问题在一定程度上的最优解。. z.-第三章组合优化以及 TSP 问题简介3.1 组合优化简介3.1.1 引言随着计算机技术的高速开展，计算机正在逐渐成为人们解决问题的必不可少的重要工具。但是在实际的生产生活中遇见了这样一类问题：在多项式时间，采用了准确的算法却仍然找不到问题的最优解，这类问题我们称之为组合优化问题

30、。这类问题当中常常随着求解问题的空间呈现组合爆炸空间、问题规模的扩大等特征，求解问题的时间、空间复杂程度将呈指数形式增长，在现有的条件下使用常规的方法求解是没有方法实现的，这类问题属于NP完全问题，旅行商问题就是它们当中最经典问题之一。所以根据仿生进化算法，在短时间以，获得问题的满意解，就成为研究的关键。3.1.2 组合优化问题组合优化问题的目的是在组合问题的诸多可行解中找到最优解。在实际的生产生活中我们可以遇见许多组合优化问题，它们当中的许多问题比方旅行商问题、分配问题、图着色问题、布线问题、调度问题及路由的选择问题等等，截止到目前仍然找不到特别有效的多项式算法，这些问题都己经被证明是NP完

31、全问题。优化问题具备三个根本的要素:变量、约束以及目标函数。在求解的过程当中所选择的根本的参数称之为变量，对所选取的变量取值的限制称之为约束，将衡量可行方案标准的函数称之为目标函数。所谓的组合优化问题就是在给定的约束前提情况下，求目标函数的最优值问题。下面用一个对偶S，f来表示组合优化问题，其中解空间 S 可表示为可行解目标函数f的一个映射，因此可以定义为:f : SR求解目标函数的最小值问题称之为最小化问题，记作：min f (i),iS求解目标函数的最大值问题称之为最大值问题，记作：max f (i),iS很明显，假设目标函数的符号发生改变，最大化问题和最小化问题之间将可以进展等价转换，我

32、们将目标函数的最优值的解称之为最优解整体最优解。设S，f是组合优化问题当中的一个例子，iaptS，如果f (iapt) f (i)对所有的iS成立,那么称iapt为最小化问题 min f (i),iS的最优解。优化问题在实际的生产工程中有着极为广泛的应用，所涉及到的问题是在一组限制的前提下求解问题的最优(或最好)解的问题。一般情况下可以把最优化问题分成两种:一种是离散变量的问题，另一种是连续变量的问题。拿离散变量的问题来说，一般情况下是寻找离散变量问题的最优编排，筛选，次序或者分组等等。很显然这些问题的求解的个数都是有限的，一般把这类问题称之为组合最优化问题，而把应用数学的方法用来求解这类问题

33、的过程就被称之为组合最优化。3.1.3 NP 完全问题根据求解复杂性理论问题的难易程度，可以把问题分为：P类、NP类以及NP完全类。定义一:对于一个判定问题 D，存在这样的一个多项式 Pt，使得每一次对其输入规模为 n 的实例，都可以在P(n)时间求解出最优解，此类问题称之为P(Polynomial)问题。其它问题那么称为NP(Non一Polynomial)问题。假设一个问题是P问题，我们一般认为它是简单的，而 NP 问题，一般可以认为它是复杂的。NP问题是指在多项式时间里验证一个解的问题，到目前为止都没有找到多项式时间的算法。定义二：如果问题LNP，所有 NP 问题都可以通过多项式计算时间来

34、转化为 L，那么可以将L称之为NP完全问题。假设 NP 完全类问题当中存在一个问题可以用多项式确定性的算法求解，那么其余的所有 NP 完全类问题都可以用多项式确定性算法来求解，许多问题被已经被证明为 NP 完全问题，例如 TSP 问题，NP 完全问题也是检验仿生算法有效性和可靠性的有效平台。3.2 TSP 问题简介3.2.1 TSP 问题的定义 TSP问题的英文名traveling salesman problem,中文译为旅行商问题。问题的定义非常简单，即为一个旅行商打算要走访全国的N个城市，其中每一座城市都必须经过，而且每一座城市都只能经过一次，最终再回到出发的城市完成了一次旅行，问怎么样

35、才能找到一条最短的路径。3.2.2 TSP 的实用价值 TSP问题的应用十分广泛，而且问题的规模城市的数目都很大。例如，X射线结晶学问题，电路板的钻孔问题以及超大规模集成电路制造问题VLSL等等。总之，所有的可以抽象成为遍历全部的城市一次且只有一次，求代价最小的路径的问题，都可以当成TSP问题来解决。3.2.3 TSP 问题的理论意义与实用价值相比拟，TSP问题的理论意义显得更加重要。实际上，该问题是可以作为所有的组合优化问题的例而存在的。它己经成为并将继续成为测试新算法的标准问题。这是由于，TSP问题展示出了组合优化问题的所有方面。虽然它在定义方面来讲十分简单，但是其求解的难度还是很大的。假

36、设针对TSP问题提出的某种算法可以取得比拟重大的实际运算效果，如果对其加以修改，就可以应用到其它类型的组合优化问题并将产生良好的实际成果。基于上述的原因，该问题吸引了大量不同领域的研究学者。3.3 根本蚁群算法的数学模型蚂蚁k(k=1,2,.,m)在运动过程中，运动转移的方向由各条路径上的信息量浓度决定。为方便记录可用tabuk(k=1,2,.,m)来记录第k只蚂蚁当前已走过的所有节点，这里可以称存放节点的表为禁忌表；这个存放节点的集合会随着蚂蚁的运动动态的调整。在算法的搜索过程中，蚂蚁会智能地选择下一步所要走的路径。设m表示蚂蚁的总数量，用dij(i,j=0,1,.,n-1)来表示节点i与节

37、点j 之间的距离，ij(t)表示当t时刻时ij连线上的信息素浓度。在初始时刻，m只蚂蚁将被随机地放置，各路径上的初始信息素浓度是一样的。在t时刻，蚂蚁k从节点i转移到节点j的状态转移概率为其中，allowedk=c-tabuk表示蚂蚁k下一步可以选择的所有节点，C为全部节点集合；为信息启发式因子，在算法中代表轨迹相对重要程度，反映路径上的信息量对蚂蚁选择路径所起的影响程度，该值越大，蚂蚁间的协作性就越强；可称为期望启发式因子，在算法中代表能见度的相对重要性。ij是启发函数，在算法中表示由节点i转移到节点j的期望程度，通常可取ij=1/dij。在算法运行时每只蚂蚁将按照状态转移概率公式进展搜索前

38、进。在蚂蚁运动的过程中，为了防止在路径上残留过多的信息素而导致启发信息被淹没，在每只蚂蚁遍历完成后，要对残留的信息进展更新处理。因此，在t+n时刻,路径(i,j)上信息调整如下在式中，常数0,1表示信息素挥发因子,表示路径上信息量的损耗程度,的大小关系到算法的全局搜索能力和收敛速度，那么可用1-代表信息素残留因子,ijk表示一次寻找完毕后路径(i,j)的信息素增量。在初始时刻ij0=0，ijkt表示第k只蚂蚁在本次遍历完毕后路径(i,j)的信息素。由于信息素更新策略有所不同，学者DorigoM研究发现了三种不同的根本蚁群算法模型，分别记为蚁周系统(Ant-Cycle)模型、蚁量系统(Ant-Q

39、uantity)模型及蚁密系统(Ant-Density)模型，三种模型求解ijkt方式存在不同。蚁周系统(Ant-Cycle)模型蚁量系统(Ant-Quantity)模型蚁密系统(Ant-Density)模型从上边各公式可以看出三种模型的主要区别是：蚁量系统和蚁密系统中，信息素是在蚂蚁完成一步后更新的，即采用的是局部信息；而在蚁周系统中路径息素是在蚂蚁完成一个循环后更新的，即应用的是整体信息。在一系列标准测试问题上运行的实验说明，蚁周系统算法的性能优于其他两种算法。因此，对蚂蚁系统的研究正朝着更好地了解蚁周系统特征的方向开展。. z.-第四章根本蚁群算法求解TSP本章首先利用了 MATLAB

40、平台做出一个参数设置平台，是为后一章做参数讨论做铺垫，主要是运用 MATLAB 中 GUIDE 设计工具。然后描述了根本蚁群算法求解 TSP 的实现流程，并且做了相应的仿真，得出了仿真结果。并在下一章中进展了蚁群算法的主要参数设置的分析。4.1 根本蚁群算法求解 TSP 的实现流程4.1.1 根本蚁群算法的实现步骤以 TSP 为例，根本蚁群算法的具体实现步骤如下：1参数初始化。令时间 t=0 和循环次数Nc=0，设置最大循环次数Ncmax ，将 m只蚂蚁置于n个城市上，令每条边i,j的初始化信息量ij(t) = const，其中 const 表示常数，且初始时刻ij(0) = 0 。2循环次数

41、 Nc=Nc+13蚂蚁的禁忌表索引号 k=14蚂蚁数目k = k + 1。5蚂蚁个体根据状态转移概率公式计算的概率选择城市 j。6修改禁忌表指针，即选择好之后将蚂蚁移动到新的城市，并把该城市移动到该蚂蚁个体的禁忌表中。7假设集合 C 中的城市未遍历完，即 km,那么跳转到到第4步，否那么继续往下一步执行。8更新每条路径上的信息量。9假设满足完毕条件，即循环次数NCNCmax，那么循环完毕并输出程序计算结果，否那么清空禁忌表并跳转到第2步。4.1.2 根本蚁群算法的构造流程以 TSP 为例，根本蚁群算法的构造流程如图 4.1 所示。开场初始化NC=NC+1蚂蚁K=1蚂蚁K=K+1根据状态概率公式

42、选择下一个城市修改禁忌表k蚂蚁总数m进展信息素的更新满足完毕条件？算出程序计算结果完毕图 4.1 蚁群算法的程序构造流程. z.-第五章蚁群算法的主要参数设置TSP问题虽然是蚁群算法所研究的热门方向和主流方向之一，但是因为蚁群算法的搜索时间长及容易陷于局部最优解等缺点，想要克制这些困难，除了可以选择当下比拟先进的算法进展研究之外，还可以针对对应的TSP问题，去改变算法里面的参数的设置值，依次来到达优化解的效果。本文就是通过研究蚁群的基数变化对求解TSP问题的影响，以此来推断出求解该TSP问题的最正确蚁群基数。5.1实验分析蚁群算法求解TSP问题：在保持其他条件因素不变的情况下，假设改变蚁群的基

43、数，会对求解和时间和解的准确性发生变化，并且变化遵循以下规那么：(1)当蚁群的基数增大时，求得的最优解的准确性增大，但求解的时间也会增加；(2)当蚁群的基数减小时，求得的求得的最优解的准确性减小，但求解的时间也会减少；5.2实验设计本实验的TSP问题的节点设置n=30个，蚁群基数初始值m0=10，增量k=10，最大值mmax=80，其他因素的初始值如下表5-1所示：表5-1 蚁群算法各因素对照表参数名对照蚁群算法中的因素初始值alpha1beta5rho0.1Q常系数1Eta路径长度-1除了以上那些可以影响求解结果的参数以外，还包括一些记录的参数和常规的参数。表5-2 其余参数对照表参数名参数

44、含义参数取值D路径总距离zeros(n,n)Tau信息素矩阵ones(n,n)Table路径记录表zeros(m,n)iter/iter_max迭代初始值/迭代最大值1/200Route_best各代最正确路径zeros(iter_max,n)Length_best各代最正确路径的长度zeros(iter_max,1)Length_ave各代平均路径的长度zeros(iter_max,1)对每个m值运行十次，得到十个最短路径d和时间t，记录数据，对这些数据进展处理：对d和t分别求平均，并指出当前基数下的最优路径。最后将十个平均值绘成图，通过分析得到求解该TSP问题的最正确蚁群数量。5.3实验结

45、果及结果分析将不同蚁群基数运行程序后得到的最短路径图列出如下：(a)m=10(b)m=20(c)m=30(d)m=40(e)m=50(f)m=60(g)m=70(h)m=80图5-1 蚁群基数与其对应最短路径图将分析完后的各组数据进展处理，得到以下结果：表5-3 蚁群基数及其对应的TSP问题解m10203040平均路径11027.7510907.6310815.0610818.59平均时间5.64210.95616.29520.138最优路径10659.6510735.3110475.6910321.33m50607080平均路径10785.7310800.3710838.5010793.58

46、平均时间26.02531.08635.89541.121最优路径10435.359950.88610267.589608.484由上表可知，虽然随着蚁群基数的增大，最短路径也会呈减短的趋势，但是平均路径并未得到大幅度的减小，最优解具有更大的偶然性，所以无法确定所求的最优解是否有效，因此求解的最短路径不能作为求解TSP问题时考量最正确蚁群基数的一个指标。将最短路径之外的两个结果在MATLAB工具箱中绘制出来，由于两个结果的数量级相差较大，为方便观察，将两个结果分别绘图如下：(a)m-t (b)m-d 图5-2 蚁群基数与最优路径和搜索时间关系图分析图5-2：随着蚁群数量从10到80有规律地递增，

47、算法的搜索时间也几乎呈线性增长；而在寻优方面，在蚁群数量从10递增到30的过程中，所寻的平均最优路径的质量有着明显的提高，但是当蚁群数量继续增加时(30-80)，所寻的平均最优路径根本保持在一定围上下波动，无明显变化。虽然在m=50和m=80两处的平均最优路径较m=30处的平均最优路径有所改善，但变化不大，且所用搜索时间更长，因此，对于该TSP问题而言，最正确蚁群基数是m=30。据此可以得出：对于一个特定TSP问题，蚁群基数与求解该TSP问题所需时间呈线性相关的关系，即当蚁群基数增大时，求解TSP问题所需时长也会出现类似线性的增加，反之亦然。当蚁群基数m所要研究的TSP问题的结点个数n时，求解

48、能力与蚁群基数呈负线性相关的关系路径随着m的增大而减小；当蚁群基数超过了TSP问题的节点数之后，这种线性相关的关系将立即消失，并且此时的求解能力将在一定的围上下起伏，但逼近于nm=时所得出的结果。因此，要想使一个TSP问题得到稳定有效的求解结果，必须满足：蚁群基数必须不小于所求的TSP问题的结点数；要想快速的求出稳定有效的解，可以使蚁群基数与TSP问题的节点数相等或相近。. z.-第六章总结和展望6.1 工作总结蚁群算法解决 TSP 问题只是解决了众多组合优化问题的一种，但就是围绕着 TSP 问题的解决才有了蚁群算法的开展和创新。它涉及了仿生学，程序设计学，计算机科学仿真技术多个学科，是信息处

49、理领域的一项前沿技术。本文的前期工作是介绍了根本蚁群算法的原理和蚁群算法的机制原那么，其中也详细介绍了组合优化问题。本文的重点是利用蚁群算法解决 TSP 问题，并利用 MATLAB 成功进展了仿真。其中重点讨论了如何通过选择合理的参数配置使蚁群算法性能得到提高，并用大量的仿真实验结果予以证明。总的来说，本文有两个难点，根本蚁群算法原理的理解，与利用 MATLAB 进展仿真实验解决 TSP 问题。6.2 技术展望蚁群算法开展至今，人们已经针对不同的具体问题提出了许多不同类型的改良蚁群算法模型，但这些改良的蚁群算法模型往往普适性不强，同时根本蚁群算法模型也不能直接应用于解决所有的优化问题。另外，自

50、然界中的真实蚁群还有许多其他的智能行为，用逆向思维和发散思维开发不同的蚂群算法模型是一条新的开展思路。基于此，今后可以从以下几个方面对其模型进展改良。 1、设计一种通用的蚁群算法普适性模型。 2、进一步研究自然蚁群行为，提出更加智能化的蚁群混合行为模型。 3、摆脱传统模型框架，开发新的蚁群算法模型。因此，关于蚁群算法理论及其应用的研究必将是一个长期的研究课题。相信随着人们对仿生智能系统理论及应用研究的不断深入，蚁群算法这一新兴的仿生优化算法必将展现出更加广阔、更加引人注目的开展前景。. z.-参考文献1段海滨.蚁群算法原理及其应用M.：科学.2005：15-21.2海.王洪国.徐卫志.蚁群算法

51、的应用研究与开展J.科学和技术信息学报 2007年第28期：5-7.3志硕.申金升.柴跃廷一种求解车辆路径问题的混合多蚁群算法J.系统仿真学报 2007 年第19卷15期：2-6.4劳眷.TSP 问题中的蚁群优化算法研究D.:大学,2007年5宗永.静.谭家华.蚁群算法的改良及其应用J.交通大学学报 2002 年第36卷第11期：19-25.6骏.基于蚁群优化算法的 TSP 问题研究D.:理工大学,2005 年7乃文.方爱.蚁群算法用于 TSP 的并行策略及模型J. 2007年第24卷第12期：7-12.8晓峰.基于 MATLAB 的混合型蚁群算法求解旅行商问题J.铁路计算机应用学报 2005

52、 年第14卷第9期：25-31.9胡小兵.袁锐.黄席.易继军.蚁群算法原理的仿真与研究J. 2004年第21卷第8期：14-23.10宏达.全第.基于蚁群算法的 TSP 的仿真和研究J. 2005年第35卷第4期11勇,胡上序等.蚁群算法求解连续空间优化问题J.控制与决策2003,18(5):573-576.12 王凌.智能优化化算法及其应用M.：清华大学，2001. 13邢文讯，金星.现代优化计算方法M.：清华大学，2001.14正军，康力山，毓屏.演化计算M.：清华大学XX科学技术，1998.7.15王正志，薄涛.进化计算.：国防科技大学，2000.16D.CostaandA.Hertz.

53、AntscancolorgraphsJ.JournaloftheOperationalResearchSociety,48:295-305,1997.17W.J.Gutjahr.ACOalgorithmswithguaranteedconvergencetotheoptimalsolutionJ.Info.ProcessingLett.,vol.82,no3,pp.145-153,2002.18E.Lawler,A.Lenstra,R.Kan,andD.Shmoys.Thetravelingsalesmanproblem.JohnWiley&Sons,1985.19M.Dorigo.Optim

54、ization,LearningandNaturalAlgorithma(inItalian)D.Ph.D.t-Hesis,DipartimentodiElettronica,PoliteicodiMilano,IT,1992.20L.M.GambardellaandM.Dorigo.Ant-Q:AreinforcementlearningapproachtothetravelingsalesmanproblemC.InA.PrieditisandS.Russell,editors,Proceedi-ngsoftheTwelfthInternationalConferenceonMachine

55、Learning(ML-95),pages252-260.MorganKaufmannPublishers,PaloAlto,CA,1995.21R.MichelandM.Middendorf.AnACOalgorithmfortheshortestsupersequenceproblemM.InD.Corne,M.Dorigo,andF.Glover,editors,NewIdealsinOptimizat-ion,pages51-61.McGrawHill,London,UK,1999.22J.LevineandF.Ducatelle.Antcolonyoptimizationandloc

56、alsearchforbinpackingandcuttingstockproblems.JournaloftheOperationalResearchSociety,toappear,2003.23M.Dorigo.Parallelantsystem:Anexperimentalstudy.Unpublishedmanuscript1993.24J.P.Cohoon,S.U.Hegde,W.N.Martine,andD.Richards.PunctuatedEquilibria:AParellelGeneticAlgorithm.InSecondInternationalConference

57、onGeneticAlgorithms,pp.148-154,1987.25R.MichelandM.Middendorf.AnislandmodelbasedAntSystemwithlookaheadfortheshortestsupersequenceproblemC.InA.E.Eiben,T.Bck,M.Schoenauer,andH.-P.Schwefel,editors,ProceedingsofPRSN-V,FifthInternationalConferenceonParallelProblemSolvingfromNature,volume1498ofLectureNote

58、sinputerScience,pages692-701.SpringerVerlag,Berlin,Germany,1998.26 Dorigo M.Ant algorithms and atigmergy.Future Generation puter Systems.2000,16(8),873871 27 Dorigo M.Gambardella L M.Ant colony system:cooperative learning approach to the traveling salesman problemJ.IEEE Transactions on Evolutionary

59、putation.1997,1(1),536628 Dorigo M.Luca M.The ant colony alogrithm applied to the nuclear reload problem.Annals of Nuclear Energy.2002,29(12),14551470 29Dorigo M.Ant colony system: optimization by a colony of cooperating agents.IEEE Transactions on System,Man and Cybernetics-Part B.1996,26(1),2941 3

60、0M.DorigoandG.Di.Caro.TheAntColonyOptimizationmeta-heuristic.InD.Corne,M.Dorigo,andF.Glover,editors,NewIdeasinOptimizationM,pages11-32.McgrawHill,London,UK,1999.致本文是在高淑芝教师的耐心指导下完成的。在课题的研究过程中，她每周都对我的毕业设计进展悉心指导和帮助。在我遇到困难时，她也屡次给我鼓励和鞭策。谭教师在科学上的执着追求、严谨的治学态度、学者的先锋精神，严以律己、宽厚待人和亦师亦友的高尚品德，给我树立了典范，使我在今后的工作和生活中受益匪浅。经过这段时间的毕业设计，我感觉到掌握扎实的根底知识和学会使用必要工具的重要性，深刻体会到网络资源的巨大作用，在遇到难以解决的问题时，可以在因特网这个无穷的空间中寻找所需的资料，到相关的论坛上去求得帮助；学会灵活运用Internet这个现代工具是我们必备的素质。同时毕业设计对我的英语水平也提出了较高的要求，通过阅读英文资料、翻译英文材料切实提高