蚁群算法在TSP问题中的应用.doc

《蚁群算法在TSP问题中的应用.doc》由会员分享，可在线阅读，更多相关《蚁群算法在TSP问题中的应用.doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单位代码 01 学号 090111004 分 类 号 O24 密 级 毕业论文蚁群算法在TSP问题中的应用 院(系)名称信息工程学院 专业名称信息与计算科学 学生姓名 王利超 指导教师王爱苹2013 年 5 月 15 日黄河科技学院毕业论文 第 12 页蚁群算法在TSP问题中的应用摘 要蚁群算法是近年来发展起来的一种新型模拟进化算法，它是由意大利学者MD0ri go等人在20世纪90年代初提出来的这种算法模仿了蚂蚁在搬运食物的过程中，自发寻找最短路径的行为特征，加以改进并应用到不同的领域蚁群算法作为一种新的启发式算法，它具有正反馈、分布式计算以及结构性的贪心启发等特点，使其能够成功地解决许多问

2、题. 本文首先介绍了蚁群算法的基本原理及相关背景；其次描述了蚁群算法在实际问题中的应用，如：旅行商问题；然后针对蚁群算法编写MATLAB程序求解最优路径；最后给出结论与展望。关键词：蚁群算法，TSP问题，最优路径，启发式算法Application of Ant Colony Algorithm In The TSP Problem Author: Wang Lichao Tutor: Wang AipingAbstractAnt colony algorithm is developed in recent years a new type of simulated evolutionary

3、algorithm, which is by the Italian scholar M. Dorigo people in the early 1990s. This algorithm mimics the ants in the process of transporting food, spontaneous behavior characteristics to find the shortest path to be improved and applied to different fields. Ant colony algorithm as a new heuristic a

4、lgorithm, it has a positive feedback, distributed computing and structural greedy inspired, to enable them to successfully solve many problems.This paper first introduces the basic principles of ant colony algorithm and background; Second, we describe the application of the ant colony algorithm in p

5、ractical problems, such as: traveling salesman problem; prepared for the ant colony algorithm MATLAB program for solving the optimal path; Finally conclusionsand Prospect.Keywords: Ant colony algorithm, TSP, The optimal path, Heuristic algorithm目 录1 绪论11.1 数值方法背景简介11.2 非线性方程简介21.2.1 非线性方程的背景21.2.2 非

6、线性方程的研究内容21.2.3 根的存在性定理32 非线性方程的数值解法42.1 引言42.2 二分法42.2.1 二分法简介42.2.2 二分法的原理42.3 牛顿迭代法52.3.1 牛顿迭代法的简介52.3.2 牛顿迭代法的原理52.3.3 牛顿迭代法的几何意义62.4 割线法72.4.1 割线法简介72.4.2 割线法的原理83 非线性方程的MATLAB实现93.1 二分法93.1.1 二分法的MATLAB程序93.1.2 应用举例103.2 牛顿迭代法123.2.1 牛顿迭代法的MATLAB程序123.2.2 应用举例133.3 割线法143.3.1 割线法的MATLAB程序143.3

7、.2 应用举例154 方法的分析与对比174.1 构造非线性方程迭代公式174.2 计算迭代公式175 实际应用215.1 引言215.2 问题提出215.3 模型建立225.4 模型求解23结论25致谢26参考文献271 绪论1.1 课题背景及意义伴随计算机技术的飞速发展，许多工程应用和科学研究领域都产生了一些组合优化问题，它们中大多都是NP-优化问题，对该类问题的研究具有广泛的应用价值和十分重要的理论意义，其研究成果对科学研究的发展及国民经济的建设都必将起到极大的推动作用。旅行商问题就是其中经典的问题之一。目前对求解该类问题的研究主要有两个方向：一是传统的数学规划方法来得到全局最优解，但这

8、种算法的复杂性往往是不能接受的，因而难以适应大规模问题实例的求解；近年来发展起来的各种仿生进化算法能够在多项式时间内找到比较好的可以满足实际应用要求的解，但并不一定是全局最优解。考虑到，在大多数实际的工程应用中，使用有限的时间得到较好的可以满足实际需求的解是至关重要的，因此利用仿生进化算法，在较短的时间内，求得问题的满意解，就成为许多学者研究的重点。自然界一直是人类创造力的源泉，人类认识事物的能力就来源于与自然界的相互作用之中。因此，仿生一直是人类创新的基本方式之一，而仿生进化算法正是在这种认知方式下被提出来的。事实上，仿生算法模拟的正是自然界的趋优机制，其目的在于利用自然界的高效优化方法解决

9、工程实际问题。比如，对人脑神经细胞结构与功能的抽象模拟构成的人工神经网络，寄希望通过人脑处理复杂思维的高效性，获得处理复杂事务的方法。模拟生物遗传进化过程的遗传算法，希望借鉴生命进化过程的复杂性来解决复杂现象中的优化问题。而蚁群算法，则通过模拟现实世界中蚂蚁觅食的行为来求解复杂的组合优化问题。1.2 研究现状1991年，意大利学者Dorigo M 2 首次提出了蚁群算法，但在此后5年里并没有引起国际研究者的足够重视，直到1996年，Dorigo M 等人在IEEE Transactions on Systems, Man , and Cybernetics-Part B上发表了“Ant Sys

10、tem: Optimization by a Colony of Cooperating Agents”一文3，蚁群算法开始引起国际研究者的广泛关注在发表的这篇文章中，Dorigo M 等人系统地阐述了蚁群算法的基本原理和数学模型，并且将其与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等方法进行了仿真实验比较，并把单纯地解决对称旅行商问题 (Symmetric Traveling Salesman Problem, STSP)拓展到解决非对称旅行商问题 (Asymmetric Traveling Salesman Problem, ATSP)、指派问题（Quadratic Assignment

11、 Problem ,QAP）以及车间作业调度问题（Job-shop Scheduling Problem ,JSP）, 且对蚁群算法中初始化参数对其性能的影响作了初步探讨，这是蚁群算法发展史上的一篇奠基性文章此文章发表后的几年中，许多国家的学者开始转向进行蚁群算法研究，使其应用领域迅速扩展，并且发表了大量有价值的研究成果 2000年，Dorigo M和Bonabeau E等人4在学术刊物Nature上发表了蚁群算法的研究综述，进一步推动蚁群算法的研究走向算法科学的前沿 21世纪的最后几年中，在国内外许多学术期刊和会议上，蚁群算法己经成为一个备受关注的研究热点和前沿性课题特别是国际著名的顶级学术

12、刊物Nature曾多次对蚁群算法的研究成果进行报道5.6，另外，Future Generation Computer Systems(VOL16,No8)和IEEE Transactions on Evolutionary Computation(VOL6,No4)分别于2000年和2002年出版了蚁群算法特刊 首次对蚁群算法的收敛性进行描述和证明的是Gutjahr W J于1991年撰写的技术报告“A Generalized Convergence Result for the Graph-based Ant System”15和2000年发表的学术论文“A Graph-basedAnt S

13、ystem and its Convergence”7，这在蚁群算法的发展史上具有重要作用 蚁群算法在我国的研究起步比较晚，最先对蚁群算法进行研究的是东北大学控制仿真研究中心的张纪会博士与徐心和教授，他们在1997年10月发表的“一种新的进化算法蚁群算法”8算是对国内研究者的一个介绍性的引入 回顾蚁群算法自创立以来近二十年的发展历程，目前人们对蚁群算法的研究已由当初单一的TSP领域渗透到了多个应用领域，由解决一维静态优化问题发展到解决多维动态组合优化问题，由离散域范围内研究逐渐拓展到了连续域范围内研究，而且在蚁群算法的硬件实现上也取得了突破性进展，同时在蚁群算法的模型改进及与其它仿生优化算法的

14、融合方面也取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前所未有的勃勃生机，并已经成为一种完全与遗传算法等其他智能算法相媲美的仿生优化算法1.3 论文的主要工作1.3.1 主要内容本文主要介绍了蚁群算法的基本机理，分析了其算法优点和不足之处，并以TSP问题为例，对蚁群算法的基本原理，蚁群算法的基本模型， 进行了系统的阐述，并以河南省内各大城市之间的最小路线，运用MATLAB进行求解。1.3.2论文组织本文共分为三章：第一章为绪论，着重阐述课题研究的背景和意义，国内外研究的现状。第二章介绍了蚁群算法的基本原理，并分析了它的优点和不足之处。对各种改进型的蚁群算法进行了研究，并分析的各

15、自的特点。第三章对蚁群算法在TSP问题中的应用进行阐述，介绍了蚁群算法在TSP问题中的应用及特点。最后为结束语，为本文工作的总结，及对未来的展望。2 蚁群算法的基本原理及其分析2.1 蚁群算法的基本原理蚁群算法是近年来发展起来的一种新型模拟进化算法，它是由意大利学者MDorigo等人在20世纪90年代初提出来的这种算法模仿了蚂蚁在搬运食物的过程中，自发寻找最短路径的行为特征，加以改进并应用到不同的领域蚂蚁是群体动物，它们没有视觉但是可以通过集体配合劳动找到从巢穴到食物源的最短路径仿生学家经过大量研究后发现，蚂蚁在搜索食物时个体之间能通过在路径上留下的气味来进行信息传递，这种气味称作信息素(ph

16、eromone)蚂蚁边运动边留下信息素，并且可以根据嗅到的信息素的浓度来进行前进路径的选择蚂蚁总是倾向于沿着信息素浓度高的方向来移动，而路径上的信息素会随着时间的推移而逐渐挥发信息素强弱指导蚂蚁行进，于是当一条路径上走过的蚂蚁越多，信息素浓度就会越强烈，后来的蚂蚁选择该路径的概率就越大这种群体行为构成了一种信息正反馈现象，蚂蚁就是通过这种反馈机制来进行信息交流，最终快速找到食物2.1.1 基本模型的描述假设将只蚂蚁放入个随机选择的城市中，为城市和城市之间的距离；为时刻在城市和城市连线上残留的信息量，初始时刻，各条路径上信息量相等，设蚂蚁在运动过程中，根据各条路径上的信息量选择下一个它还没有访问

17、的城市，同时在完成一步(从一个城市到达另外一个城市)或者完成一个循环(完成对所有个城市的访问)后，更新所有路径上的残留信息量选择下一个城市的依据主要为：为时刻在城市和城市连线上残留的信息量，即由蚁群算法所提供的信息；为蚂蚁由城市转移到城市的期望信息，这一启发式信息可由所要解决的问题给出，并由一定的算法来实现，在TSP问题中一般取，在这里可以称为先验知识为在t时刻蚂蚁由城市转移到目标城市的概率： (1)即人工蚂蚁选择下一个目标城市的可能性是题目本身所提供的启发信息与从“蚂蚁”目前所在城市到目标城市路径上残留信息量的函数由式(1)可知，蚂蚁在选择路径时会尽量选择离自己距离较近且信息素浓度较大的方向

18、，即概率值最大的方向式(1)中：为在t时刻蚂蚁下一步允许选择的城市(即还没有访问的城市)，与真实蚁群系统不同，人工蚁群系统具有一定的记忆功能，这里用记录蚂蚁目前已经走过的城市；为残留信息量的相对重要程度;为期望值的相对重要程度经过n个时刻，蚂蚁完成一次循环，在进行下一轮循环前，必须将最新的蚂蚁访问过的各路径上留下的新信息加入到中信息量要根据下式作调整： (2) (3)其中，为信息残留系数模仿人类记忆的特点，旧的信息将逐步削弱，随着时间的推移，以前留下的信息将要逐渐消逝，用参数表示信息消逝程度(即挥发程度)；为第k是只蚂蚁在本次循环中(在时间段内的访问过程中)留在t到j路径上的信息量关于的计算，

19、MDofigo曾给出三种不同的实现方法6,分别称之为antcycle system，antdensity system，antquantity sys tern它们的差别在于表达式的不同在ant-cycle system模型中：(4)在ant-density system模型中：(5)在ant-quantity system模型中：(6)其中，Q为一常量，为蚂蚁循环一周或一个过程在经过的路径上所释放的信息素总量；为第k只蚂蚁在本次循环中所选择路径的长度2.2 应用举例2.2.1 蚁群算法在电信中的应用 蚁群算法在电信路由中的应用有比较成功的例子，HP公司和英国电信公司在90年代中后期都开展了这

20、方面的研究，在每个节点的路由表中，对每个目的节点都列出了与该节点相连的节点，当有数据包到达时，通过查询路由表可知道下一个将要到达的的节点，首先对路由表中的信息素强度进行初始化。在节点x,，以节点i为目的地址，邻节点为j处的信息素强度为,为从x经节点j到节点i路径的最小费用值。然后周期性地释放蚂蚁来进行路由。并修改相应的信息素的值1517。在所采用的蚁群路由算法(Ant Colony Routing,ACR)中，蚂蚁根据它在网络上的经验与性能，动态地更新路由表项(Routing=Table Entries).如果蚂蚁因为它经过了网络中堵塞的路段，而导致了比较大的延迟，那么就对相应的表项做较小的增

21、强，如果某条路段比较顺利，那么就对该表项做较大的增强同时应用挥发机制，就可以做到系统信息的更新，使得那些过期的路由信息不再保留利用蚁群算法所得呼叫拒绝率和平均路径长度均小于最小负载法结果；在呼叫符合集中分布时，蚁群算法所得呼叫拒绝率低于最优路径。在当前最优路径出现阻塞时，ACR算法能很快找到另一条可替代的最优路径，从而提高网络的均衡性、网络负载量以及网络的利用率研究表明，蚁群算法已经成为解决多点路由、电网布线的一种较有效的方法。 2.2.2 蚁群算法在经济领域的应用 蚁群算法在经济领域也有很好的应用前景，比如利用它对内河航道提供科学合理的规划，解决集装箱的集散问题 2.2.3 蚁群算法在序列比

22、对中的应用 蚁群算法的良好鲁棒性是可以府用于序列比对的基础2.2.4 蚁群算法在组合优化问题中的应用 蚁群算法在旅行商(TSP)、作业调度问题(JSP)等组合优化问题当中均有较好的应用其中在旅行商问题(TSP)中的研究是最普遍的，国内在对蚁群算法的研究上，大多是基于旅行商问题进行理论探索和仿真实验的设是n个城市的集合，是集合N中城市两两连接的集合，是的Euclidean距离，即是一个有向图，TSP的目的就是从有向图G中寻出长度最短的Hamilton圈，即一条对中n个城市访问且只访问一次的最短封闭曲线3 旅行商问题概述3.1 旅行商问题的概念一个旅行商想去走访若干城市，然后回到他的出发地给定各城

23、市之间所需的旅行时间后，怎样计划他的路线，使得他能对每个城市恰好进行一次访问，而总时间最短，这个问题称为旅行商问题（或货郎担问题）3.2 解决TSP问题的数学模型及其意义3.2.1 TSP问题的数学模型旅行商问题就是在一个赋权图中，找出最小权Hamilton圈，称这种圈为最优圈目前还没有求解旅行商问题的有效算法，因此，只能找一种求出相当好（不一定最优）的解一个可行的办法是先求一个Hamilton圈C，然后适当修改C，得到具有较小权的另一个Hamilton圈设，则对于所有适合的和都可以得到一个新Hamilton圈如图632所示，它是有C中删去边和添加和得到的若对于某一对和有，则圈将是圈C的一个改

24、进若在接连进行上述的一系列修改之后，最后得到的一个圈不能再用此法改进了，则停止计算 图11 改进Hamilton圈的示意图3.2.2 TSP问题的计算3.2.3 结论本文对蚁群算法进行了介绍后，通过仿真实验形式对算法中各个参数的取值进行了详细地分析研究和仿真实验，得出了基本蚁群算法中各个参数的最优取值，这种取值组合能够更好的发挥算法的整体搜索性能。当然，这个结论对其他一些改进后的蚁群算法也有意义。接下来，对蚁群系统的收敛性进行了分析证明，归纳出几个可以改善蚁群算法性能的途径。然后，我们对蚁群算法进行了算法的改进研究，一是提出了基于信息熵的动态自适应蚁群算法。用信息熵作为桥梁，使得信息素残留度系

25、数值根据种群多样性状态的变化而自动进行调节；并且应用动态自适应蚁群算法解决经典TSP问题，实验证明相比改进前原算法，新算法增强了搜索随机性，提高了收敛速度。二是提出了一种贪心蚁群算法。将蚁群算法引入来解决实际应用中的Agent联盟生成问题，提取出联盟生成问题本身存在的固有特征，将其融入蚁群算法的框架结构，提出了一种解决Agent联盟生成问题的贪心蚁群算法；通过对比分析计算机实验结果，证明相对于一些解决联盟生成问题的其他算法，新算法无论是在收敛精确度上还是在收敛速度上，性能都得到了较大程度的提高。这无疑为解决此类问题又提供了一个新的思路。但是，本文的研究还只是刚刚开始，很多问题有待于进一步的深入

26、，接下来，我会在如下几个方面再进行研究。 1、 对蚁群算法的理论方面继续学习和研究，特别是努力探讨怎样从数学理论上来对各种蚁群算法的正确性和收敛性进行分析和证明。2、 智能优化算法是一个统称，包括了很多种具体算法；怎样将各种算法进行融合，特别是怎样将其他智能优化算法与蚁群算法进行结合，从而吸收其他算法好的特性来改善蚁群算法的性能，在这个方面，进行研究。3、 理论研究的最终目的是为社会应用服务。以后工作中会更加注重应用蚁群算法去解决社会实际中具体的优化问题。 致谢四年的大学生活即将接近尾声，经历过的点点滴滴仍时时浮现在眼前，倍感亲切和温馨本文是在我的导师张荣艳老师的精心指导和悉心关怀下完成的，从

27、论文的选题，调研到完稿，修改和最后完成，无不倾注着导师辛勤的汗水和心血导师那严谨的治学态度、渊博的知识、无私的奉献精神都使我深受感染，受益匪浅从尊敬的导师身上，我不仅学到了扎实、宽广的专业知识，还学到了为人处事的道理这些都将影响我今后的工作、学习和生活，对我走好今后的人生道路具有极其重要的作用，给予我帮助和启示在此我要向我的导师致以最真挚的谢意 另外，感谢学院给我们一个良好的学习环境，感谢每位任课老师、辅导员、教研办公室的老师给与我多方面的关心、指导与帮助，感谢同学们的热情帮助还要感谢我的家人多年来对我的关心和支持，正是他们无微不至的关爱激励着我不断前行感谢我的朋友们给我的鼓励和支持，是他们让

28、我变得更加勇敢坚强参考文献15 Ying Wang and Jian ying Xie,Ant Colony Optimization For Multicast RoutingA,IEEE,Circuits and Systems,2000.IEEE APCCAS2000.The 2000 IEEE Asia-Pa-cific conferenceon,2000,(12).16 Lu guo ying,Zhang su bing and Liu ze min,Distributed Dynamic Routing Using Ant Algorithm for Telecommu-nicat

29、ion NetworksA,IEEE,Communication Technology Proceedings,2000C.WCC-IC-CT2000.Intemational Conferenceon,2000,2(13).17 Griselda Navaro Varela and MarkC.Sinclair,Antcolony Optimisation For Virtual-Wavaelength-Path Routing and Wavelength AllocationA,IEEE,Evolution-aryComputationC.1999.CEC99.Proceedings of the 1999 Congresson,1999,3:1816.