《毕业设计论文基于蚁群算法的TSP问题研究.doc》由会员分享，可在线阅读，更多相关《毕业设计论文基于蚁群算法的TSP问题研究.doc（41页珍藏版）》请在三一办公上搜索。
1、编号200502122005021237 南京航空航天大学金城学院毕 业 设 计 题 目基于蚁群算法的 TSP 问题研究学生姓名学 号系 部专 业班 级指导教师信息工程系信息工程二九年六月南京航空航天大学金城学院本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：基于蚁群算法的TSP问题研究）是本人在导师的指导下独立进行研究所取得的成果。尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。作者签名：（学号）：20050212372009 年6 月 6 日毕业设计（论文）报告纸基于蚁群算法的 TS
2、P 问题研究摘 要本文研究了基于蚁群算法解决 TSP 问题的原理，算法流程以及用 MATLAB 程序的仿真。论文首先简单回顾了蚁群算法的历史、发展以及应用，然后详细介绍了基本蚁群算法的原理，包括基本蚁群算法的行为描述和机制原理。其次从基本蚁群算法的系统学特征出发，讨论它具有分布式，自组织，正反馈等特征。接着引出了基本蚁群算法解决的 TSP 问题，先讨论了组合优化问题，然后从 TSP 问题的定义，实用价值，理论意义的角度对 TSP 问题进行阐述。并且重点运用 MATLAB 的仿真方法，实现了基于蚁群算法的仿真，给出了求解 TSP 问题的数学模型，实现步骤，描述了蚁群算法的优缺点。论文最后以 MA
3、TLAB 仿真实验为基础，对蚁群算法的主要参数进行了详细的讨论，并且给出了优化的参数选择，解决了算法中存在的不足。论文实现了基于蚁群算法对 TSP 问题的求解和仿真。关键字：蚁群算法，组合优化，信息素，TSP 问题i毕业设计（论文）报告纸TSP research based on ant colony algorithm AbstractThis paper researched the principle based on ant colony algorithm to solve TSP problem,the algorithm processes and procedures usin
4、g MATLAB simulation.Paper first briefly reviewed thehistory of ant colony algorithm ,development and application,and then described in detail the basicprinciple of ant colony algorithm,including the conduct of the basic ant colony algorithm and themechanism descried in principle.Second,the basic ant
5、 colony algorithm from the characteristics ofthe system starting to discuss it with the distributed,self-organdization,characteristics of positivefeedback. Then leads to the basic ant colony algorithm to solve the TSP problem, first discuss thecombinatorial optimization problems, and then from the d
6、efinition of TSP problem, practical value,the theoretical significance of the point of view on the issue of the TSP. Focus on the use ofMATLAB and the simulation method, ant colony algorithm based on the realization of thesimulation, are given for solving the mathematical model of the TSP problem, t
7、he realization ofthese steps, describing the advantages and disadvantages of the ant colony algorithm. Finallysimulation results in MATLAB based on the main parameters of ant colony algorithm are discussedin detail, and optimized parameters are given options to solve the shortcomings of existingalgo
8、rithms. Paper achieved on optimization and simulation based on Ant colony algorithm to solvethe problem. Key Words:ant colony algorithm;combinatorial optimization;pheromone;TSP ii目 录毕业设计（论文）报告纸摘 要 .iAbstract. ii第一章 绪 论 . - 1 - 1.1 蚁群算法概况. - 1 -1.2 论文的主要内容. - 2 -第二章 基本蚁群算法简介 . - 3 - 2.1 基本蚁群算法的原理. -
9、3 -2.1.1 蚁群行为描述 . - 3 -2.1.2 基本蚁群算法的机制原理 . - 5 -2.2 基本蚁群算法的系统学特征. - 6 -2.2.1 分布式 . - 6 -2.2.2 自组织 . - 7 -2.2.3 正反馈 . - 7 -第三章 组合优化以及TSP问题简介. - 9 - 3.1 组合优化简介. - 9 -3.1.1 引言 . - 9 -3.1.2 组合优化问题 . - 9 -3.1.3NP完全问题 . - 10 -3.2TSP问题简介 . - 10 -3.2.1TSP问题的定义. - 10 -3.2.2TSP的实用价值. - 11 -3.2.3TSP问题的理论意义. -
10、11 -3.3 基本蚁群算法的数学模型. - 11 -第四章 基本蚁群算法求解TSP . - 14 - 4.1 参数设置平台 . - 14 -iii毕业设计（论文）报告纸4.2 基本蚁群算法求解TSP的实现流程 . - 15 -4.2.1 基本蚁群算法的实现步骤 . - 15 -4.2.2 基本蚁群算法的结构流程 . - 15 -4.3 基本蚁群算法的仿真结果 . - 17 -第五章 蚁群算法的主要参数设置 . - 19 - 5.1 关键参数介绍. - 19 -5.2 不同参数设置的试验. - 21 -5.2.1 信息素挥发度的设置 . - 21 -5.2.2 蚁群数量的设置 . - 21 -
11、5.2.3 启发式因子的设置 . - 22 -5.3 不同参数设置的实验结果和结论. - 22 -5.3.1 信息素挥发度的选择设置 . - 22 -5.3.2 蚁群数量的选择设置 . - 24 -5.3.3 启发式因子的选择设置 . - 25 -第六章 总结和展望 . - 27 - 6.1 工作总结. - 27 -6.2 技术展望. - 27 -参考文献 . - 28 - 致 谢 . - 29 - 附 录 . - 30 - 附录 1: 基于基本蚁群算法的TSP问题源码 . - 30 -iv第一章 绪 论毕业设计（论文）报告纸蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现在人类
12、的日常生活环境中。这些昆虫的群体生物智能特征，引起了一些学者的注意。意大利学者 M.Dorigo，V.Maniezzo 等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素（Pheromone）的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。1.1 蚁群算法概况M.Dorigo等人于 1991 年首先
13、提出了蚁群算法。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征1，以及该过程与旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优解答。同时，该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维背包问题等，显示了其适用于组合优化类问题求解的优越特征。蚁群算法之所以能引起相关领域研究者的注意，是因为这种求解模式能将问题求解的快速性、全局优化特征以及在有限时间内答案的合理性结合起来。其中，寻优的快速性是通过正反馈式的信息传递和积累来保证的。而
14、算法的早熟性收敛又可以通过其分布式计算特征加以避免，同时，具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答。这种优越的问题分布式求解模式经过相关领域研究者的关注和努力，已经在最初的算法模型基础上得到了很大的改进和拓展。以蚁群算法为代表的群智能已成为当今分布式人工智能研究的一个热点，许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究2。美国五角大楼正在资助关于群智能系统的研究工作-群体战略（Swarm Strategy），它的一个实战用途是通过运用成群的空中无人驾驶飞行器和地面车辆来转移敌人的注意力，让自己的军队在敌人后方不被- 1 -毕业设计（论
15、文）报告纸察觉地安全进行。英国电信公司和美国世界通信公司以电子蚂蚁为基础，对新的电信网络管理方法进行了试验。国内，国家自然科学基金”十五”期间学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了群智能领域的进化、自适应与现场认知主题。多年来世界各地研究工作者对蚁群算法进行了精心研究和应用开发，该算法现已被大量应用于数据分析、机器人协作问题求解、电力、通信、水利、采矿、化工、建筑、交通5等领域。蚁群算法最初用于解决TSP问题，经过多年的发展，已经陆续渗透到其他领域中，如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域已经获
16、得成功的应用，其中最成功的是在组合优化问题中的应用。1.2 论文的主要内容因为蚁群算法有很多种,并且 TSP 问题是蚁群算法众多解决问题中的经典问题,所以具有很大的随意性。虽然蚁群算法的选择性很多，但是所有的算法都是基于最基本的蚁群算法，并且基本蚁群算法也可以很好的解决 TSP 问题，以及说明参数选择问题。所以本文以基本蚁群算法为基础，通过 MATLAB 仿真这个平台，重点讨论了基本蚁群算法如何解决 TSP 问题。 第一章主要介绍了蚁群算法的历史、发展、应用，对蚁群算法原理的核心信息素作了简单的描述。第二章对基本蚁群算法的原理进行了介绍，包括基本蚁群算法的行为描述，机制原理。同时探讨了基本蚁群
17、算法的系统学特征。第三章对组合优化以及 TSP 问题的定义，实用价值，理论意义进行了描述。并且介绍了基本蚁群算法求解 TSP 问题的数学模型。第四章首先介绍了利用基本蚁群算法的参数仿真平台，及实现步骤和结构流程。并给出了用 MATLAB 实现的仿真结果。第五章主要讨论了蚁群算法中主要参数对于蚁群算法的全局搜索能力以及收敛性的影响，并做了相应仿真实验加以验证。第六章对蚁群算法的发展进行了展望，同时对本文进行了总结。- 2 -毕业设计（论文）报告纸第二章 基本蚁群算法简介2.1 基本蚁群算法的原理2.1.1 蚁群行为描述根据仿生学家的长期研究发现：蚂蚁虽然没有视觉，但运动时会通过在路径上释放出一种
18、特殊的分泌物信息素来寻找路径。当它们碰到一个还没有走过的路口的时，就随机的挑选一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口的时候，选择信息量较大路径的概率相对较大，这样便形成了一个正反馈机制。最优路径上的信息量越来越大，而其他路径上的信息量却会随着时间的流逝而逐渐消减，最终整个蚁群会找出最优路径。同时蚁群还能够适应环境的变化，当蚁群的运动路径上突然出现障碍物时，蚂蚁也能很快的重新找到最优路径。可见，在整个寻径过程中，虽然单只蚂蚁的选择能力有限，但是通过信息素的作用使整个蚁群行为找出最优路径。这里用人工蚂蚁觅食图来描述蚁群搜索
19、原理。EAd=1Bd=1CDd=0.5Fd=0.5图 2.1 人工蚂蚁觅食模拟- 3 -AB1515EF1515毕业设计（论文）报告纸CD图 2.2 人工蚂蚁觅食模拟EAB1020F1020CD图 2.3 人工蚂蚁觅食模拟图 2.1 中，设 A 点是蚁巢，D 点是食物源，EF 之间区域是障碍物。由于障碍物的存在，- 4 -毕业设计（论文）报告纸蚂蚁只能经由 A 经 E 或 F 到达 D，或由 D 到达 A，各点之间的距离如图 2.1 所示。假设每个时间单位有 30 只蚂蚁由 A 到达 D 点，有 30 只蚂蚁由 D 到达 A 点，蚂蚁过后留下的信息量为 1。为了方便起见，设该物质停留时间为 1
20、。在初始时刻，由于路径 BF、FC、BE、EC 上均无信息存在，位于 A 和 D 的蚂蚁可以随机选择路径，从统计学的角度可以认为蚂蚁以相同的概率选择 BE、FC、BE、EC，如图 2.2 所示。经过一个时间单位后，在路径BFC 上的信息量是路径 BEC 上的信息量的 2 倍。又经过一段时间，将有 20 只蚂蚁由 B、F 和 C 点到达D，如图 2.3 所示。随着时间的推移，蚂蚁将会以越来越大的概率选择路径 BFC，最终将会完全选择 BFC，从而找到由蚁巢到食物源的最短路径。2.1.2 基本蚁群算法的机制原理模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入，该算法基于以下基本假设：1
21、.蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对其周围的局部环境产生影响。2.蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的适应性表现，即蚂蚁是反应型适应性主体。3在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该路径越容易被选择；时间越长，信息量会越小；在协作阶段，候选解之间通
22、过信息交流，以期望产生性能更好的解。蚁群算法实际上是一类智能多主体系统，其自组织机制使得蚁群算法不需要对所求的问题的每一方面都有详尽的认识。自组织本质上体现了从无序到有序的动态演化，其逻辑结构如下图所示。- 5 -蚂 蚁 个体A信息 素 的增 量 构建蚁群活动规划信息素更新管理信息素决策点问题表达组 合 优 化 问题毕业设计（论文）报告纸蚂 蚁 个 体B信息素的 增 量 构建图 2.4 基本蚁群算法的逻辑结构由图 2.4 可见，先将具体的组合优化问题表述成规范的格式，然后利用蚁群算法在“探索”和“利用”之间根据信息素这一反馈载体确定决策点，同时按照相应的信息素更新规则对每只蚂蚁个体的信息素进行
23、增量构建，随后从整体角度规划出蚁群活动的行为方向，周而复始，即可求出组合优化的最优解。2.2 基本蚁群算法的系统学特征基本蚁群算法在系统学上表现以下三个特征：分布式，自组织，正反馈。三者表现出一个整体，相辅相成。2.2.1 分布式自然界中的真实蚁群行为也出现了分布式。当蚁群需要完成某项工作时，其中的许多蚂蚁都为共同目的进行着同样的工作，而最终任务的完成不会由于某些个体的的缺陷而受到影响。蚁群算法作为对蚁群觅食行为的抽象，也体现了群体行为的分布式特征。每只人工蚂蚁- 6 -毕业设计（论文）报告纸在问题空间的多个点同时开始相互独立地构造问题解，而整个问题的求解不会因为某只人工蚂蚁无法成功获得解而受
24、到影响。具体到不同的优化问题而言，蚁群算法体现出的分布式特征就具有了更加现实的意义。因为所有的仿生优化算法均可看做按照一定规则的问题解空间搜索最优解的过程，所以搜索点的初始选取就直接关系到算法求解结果的优劣和算法寻优效率。当求解许多复杂问题时，从一点出发的搜索受到局部特征的限制，可得不到所求问题的满意解；而基本蚁群算法则可看做是一个分布式的多智能系统，它在问题空间的多点同时独立地进行解搜索，不仅使得算法具有较强的全局搜索能力，也增加了算法的可靠性。2.2.2 自组织基本蚁群算法的另一个重要特征是自组织。自组织的概念是随着系统科学的发展而建立起来的。通常把系统论中的组织行为分为自组织和他组织两大
25、类4。其根本区别在于组织力或组织指令是来自于系统内部还是来自于系统外部，前者称为自组织，而后者即为他组织。如果系统在获得时间的、空间的或者功能的结果过程中，没有外界的特定干预，则称为系统是自组织的。从抽象意义上讲，自组织就是在没有外界作用下使得系统从无序到有序的进化过程。基本蚁群算法体现了这一过程，以蚁群优化为例，当算法开始的初期，单只人工蚂蚁无序地寻找解，经过一段时间的算法演化，人工蚂蚁越来越趋向于寻找到接近最优解的一些解，这恰恰体现了从无序到有序的自组织进化。自组织大大增强了算法的鲁棒性5（在这里可以理解为算法抗干扰性,就是指不是针对具体问题算法也同样可以求解,极大的体现了蚁群算法的抗干扰
26、能力），传统的算法都是针对某一具体问题而设计的，这往往建立在对该问题有了全面清晰认识的基础上，通常很难适应其他问题。而自组织的蚁群算法不需要对待求解问题的所有问题的所有方面都有所认识，因而较容易应用到一类问题中。2.2.3 正反馈反馈是控制论中的重要概念，它代表信息输入对输出的反作用。在系统学上认为，反馈就是把系统现在的行为作为影响系统未来行为的原因。反馈分正反馈和负反馈两种，前者指的是以现在的行为去加强未来的行为，而后者则是以现在的行为去削弱未来的行为。由自然界中真实蚂蚁的觅食行为可见，蚂蚁能够最终找到最短路径，直接依赖于最短路- 7 -毕业设计（论文）报告纸径上信息素的堆积，而信息素的堆积
27、却是一个正反馈的过程，对于基本蚁群算法而言，初始时在环境中存在完全相同的信息量，给系统一个微小的扰动，使得各个边上的信息量大小不同，蚂蚁构造的解就存在了优劣。算法采用的反馈方式是在较优解经过的路径留下更多的信息素，更多的信息素又吸引了更多的蚂蚁，这个正反馈的过程使得初始值不断地扩大，同时又引导整个系统向着最优解的方向进化。单一的正反馈或者负反馈存在于线形系统之中，是无法实现系统的自我组织的。自组织系统通过正反馈和负反馈机制，它体现于蚁群算法在构造问题解的过程中用到了概率搜索技术，通过该技术增加了生成解的随机性。随机性的影响就在于接受了解在一定程度上的退化，另一方面又使得搜索范围得以在一段时间内
28、保持足够大。这样正反馈缩小搜索范围，保证算法朝着最优解的方向进行；而负反馈保持搜索范围，避免算法过早收敛于不好的结果。恰恰是在正反馈和负反馈共同作用影响下，基本蚁群算法得以自组织地进化，从而得到问题在一定程度上的满意解。- 8 -3.1 组合优化简介3.1.1 引言毕业设计（论文）报告纸第三章 组合优化以及 TSP 问题简介伴随计算机技术的飞速发展，计算机正日益成为人们解决问题的不可或缺的重要工具。但在实践中人们发现，存在这样一类问题，运用精确的算法在多项式时间内无法找到问题的最优解，这类问题称为组合优化问题。这类问题通常随着问题规模的扩大，问题空间呈现组合爆炸特征，求解问题的空间、时间复杂度
29、将呈指数级增长，使用常规的方法求解，在现有条件下是无法实现的，属于NP完全问题6。TSP问题就是其中最经典问题之一。因此利用仿生进化算法，在较短的时间内，求得问题的满意解，就成为研究的重点。3.1.2 组合优化问题组合优化问题的目标是从组合问题的可行解中求出最优解。在现实世界里存在大量组合优化问题，其中许多问题如旅行商问题、图着色问题、分配问题、调度问题、布线问题及路由选择问题等7，至今没有找到有效地多项式算法，这些问题己被证明是NP完全问题。优化问题有三个基本要素:变量、约束和目标函数。在求解过程中选定的基本参数称为变量，对变量取值的限制称为约束，表示可行方案衡量标准的函数称为目标函数。组合
30、优化问题就是在给定的约束条件下，求目标函数最优值的问题。组合优化问题的一个实例可以表示为一个对偶（S，f），其中解空间 S 为可行解目标函数 f 是一个映射，定义为:f : S R求目标函数最小值问题称为最小化问题，记为：min f (i),i S求目标函数最大值问题称为最大值问题，记为：max f (i),i S显然，只要改变目标函数的符号，最小化问题与最大化问题就可以等价转换。使目标函数最优值的解称为最优解（整体最优解）。设（S，f）是组合优化问题的一个实例， iapt S ，- 9 -毕业设计（论文）报告纸若： f (iapt) f (i)（对所有的 i S 成立）,称 i为最小化问题
31、min f (i),i S 的最优解。apt优化问题在工程中有着广泛的应用，其涉及的问题是在一组限制条件下求解问题的最好(或最优)解的问题。按照人类认知问题的特点，最优化问题很自然的被划分为两类:一类是连续变量的问题，另一类是离散变量的问题。对于离散变量问题来说，一般是寻找离散事件的最优编排，分组，次序或筛选等。不难看出这些问题的解的个数是有限的。通常把这类问题称为组合最优化问题，而研究用数学方法来求解这些问题就被称为组合最优化。3.1.3NP 完全问题按照计算复杂性理论研究问题求解的难易性，可把问题分为P类、NP类和NP完全类8。定义一:对于判定问题 D，存在一个多项式 P（t），使得对其每
32、一输入规模为 n 的实例，可以在P(n)时间内求得最优解，此类问题称为P(Polynomial)问题。其它的则是NP(Non一Polynomial)问题。假如一个问题是 P 问题，我们通常认为它是“简单的”，而 NP 问题，通常认为它是“复杂的”。NP 问题是指可在多项式时间里检验的问题，至今尚未找到多项式时间算法。定义二：若问题 L NP ，所有 NP 问题都可以经过多项式计算时间转化为 L，则 L 称为NP 完全问题。如果 NP 完全类问题中有一个问题能用多项式确定性算法解决，则其他所有的 NP 完全类问题都能用多项式确定性算法来解决，很多问题被证明为 NP 完全问题，如 TSP 问题，N
33、P 完全问题也是检验仿生算法有效性和可靠性的有效平台。3.2TSP 问题简介3.2.1TSP 问题的定义TSP问题的英文名（traveling salesman problem）,中文译为旅行商问题9。问题的定义很简单，即为一个旅行商要走访N个城市，每个城市必须经过一次且只能经过一次，最后回到出发的城市就算是完成了一次旅行，问如何能找到一条最短的路径。其相应的数学描述如下：设有一个城市集合C= c1， c2， c3, ,. cn,其每对城市 ci， cj C 间的距离为d( , )ici Z+。求一条经过C中每个城市正好一次的路径（ c (1) ，n1d(c (i),c (i+1)+ d (c ( n),c (1)最小。i=1c (2)，c (3)， c (4) ，., c (n) ）,使得
