毕业设计论文

《毕业设计论文》由会员分享，可在线阅读，更多相关《毕业设计论文（19页珍藏版）》请在金锄头文库上搜索。

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

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

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

4、tecbmputing and structural greedy inspired, to enable them to successfully solve many problems.This paper first introduces the basic principles of ant colony algorithm and back Second, we describe the application of the ant colony algorithm in practical problems travelingalesmanproblem;preparedforth

5、e ant colonyalgorithnMATLABprogram forsolving the optimal path; Finally conclusionsand Prospect.Keywords: Ant colony algorithm, TSP, The optimal path, Heuristic algorith绪论1.1数值方法背景简介1.2非线性方程简介1.2. 1非线性方程的背景1.2.2非线性方程的研究内容错误！.未定义书签61.2.3根的存在，性定理,错误.未定义书签6非线性方程的数值解法2.1引言2.2二分法2.2.1二分法简介2.2.2二分法的原理2.3牛

6、顿迭代法错误！.未定义书签62.3.1牛顿迭代法的简介错误！.未定义书签62.3.2牛顿迭代法的原理错误！.未定义书签62.3.3牛顿迭代法的几何意义,错误.未定义书签62.4割线法错误！.未定义书签62.4.1割线法简介错误！.未定义书签62.4.2割线法的原理，错误1.未定义书签6非线性方程的MATLAB 实现3.1二分法3.1.1二分法的MATLAB程序3.1.2应用举例3.2牛顿迭代法,错误.未定义书签63.2.1牛顿迭代法的MATLAB 程序错误！.未定义书签。.3.2.2应用举例3.3割线法3.3.1割线法的MATLAB程序3.3.2应用举例4方法的分析与对比4.1构造非线性方程迭

7、代公式4.2计算迭代公式错误！.未定义书签6 错误！.未定义书签6 错误！.未定义书签。 错误！.未定义书签6 错误!未定义书签6 错误!.未定义书签6 ,错误.未定义书签65实际应用5.1引言5.2问题提出5.3模型建立5.4模型求解错误！.未定义书签6 错误!.未定义书签6 错误！.未定义书签6 错误.未定义书签6 错误！.未定义书签610结论致谢11参考文献121绪论1.1课题背景及意义伴随计算机技术的飞速发展，许多工程应用和科学研究领域都产生了一些组合优化 问题，它们中大多都是NP-优化问题，对该类问题的研究具有广泛的应用价值和十分重 要的理论意义，其研究成果对科学研究的发展及国民经济

8、的建设都必将起到极大的推动 作用。旅行商问题就是其中经典的问题之一。目前对求解该类问题的研究主要有两个方向：一是传统的数学规划方法来得到全局 最优解，但这种算法的复杂性往往是不能接受的，因而难以适应大规模问题实例的求解； 近年来发展起来的各种仿生进化算法能够在多项式时间内找到比较好的可以满足实际 应用要求的解，但并不一定是全局最优解。考虑到，在大多数实际的工程应用中，使用 有限的时间得到较好的可以满足实际需求的解是至关重要的，因此利用仿生进化算法， 在较短的时间内，求得问题的满意解，就成为许多学者研究的重点。自然界一直是人类创造力的源泉，人类认识事物的能力就来源于与自然界的相互作 用之中。因此

9、，仿生一直是人类创新的基本方式之一，而仿生进化算法正是在这种认知 方式下被提出来的。事实上，仿生算法模拟的正是自然界的趋优机制，其目的在于利用 自然界的高效优化方法解决工程实际问题。比如，对人脑神经细胞结构与功能的抽象模 拟构成的人工神经网络，寄希望通过人脑处理复杂思维的高效，性，获得处理复杂事务的 方法。模拟生物遗传进化过程的遗传算法，希望借鉴生命进化过程的复杂性来解决复杂 现象中的优化问题。而蚁群算法，则通过模拟现实世界中蚂蚁觅食的行为来求解复杂的 组合优化问题。1.2研究现状1991年，意大利学者Dorigo M2首次提出了蚁群算法，但在此后5年里并没有引起 国际研究者的足够重视，直到1

10、996年，Dorigo M等人在IEEE Transactions on Systems, Man , and Cybernetics-Part上发表了 “Ant Sysm: Optimization by a Colony of Cooperating Agents文：3蚁群算法开始引起国际研究者的广泛关注.在发表的这篇文章中，Dorigo M等人系统地阐述了蚁群算法的基本原理和数学模型，并且将其与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等方法进行了仿真实验比较，并把单纯地解决对称旅行商问题(Symmetric Traveling Salesman Problem,字TSP)到解决非对称

11、旅行商问题(Asymmetric Traveling Salesman Problem, ATSpj)派问题(Quadratic Assignment Problem ,QAp 以及车间作业调度问题(Job-shop Scheduling Problem ,)J,SP 且对蚁群算法中初始化参数对其性能的影响作了初步探讨，这是蚁群算法发展史上的一 篇奠基性文章.此文章发表后的几年中，许多国家的学者开始转向进行蚁群算法研究， 使其应用领域迅速扩展，并且发表了大量有价值的研究成果.2000年，Dorigo M和Bonabeau E等人国在学术刊物Nature上发表了蚁群算法的 研究综述，进一步推动蚁

12、群算法的研究走向算法科学的前沿.21世纪的最后几年中，在国内外许多学术期刊和会议上，蚁群算法己经成为一个备 受关注的研究热点和前沿性课题.特别是国际著名的顶级学术刊物Nature曾多次对 蚁群算法的研究成果进行报道5.6，另外，Future GeneratiorComputer Systems (VOL . 16,No. 8)和IEEE Transactions on Evolutionary Computatio(VOL . 6,No. 4)分别于2000年和2002年出版了蚁群算法特刊.首次对蚁群算法的收敛性进行描述和证明的是Gutjahr W于1991年撰写的技术报 告 “A Gener

13、alized Convergence Result for thbaGedpAnt Systen&Q2000年发表的 学术论文“A GraphbasedAnt System and its Cogiviere”7，这在蚁群算法的发展史上具 有重要作用.蚁群算法在我国的研究起步比较晚，最先对蚁群算法进行研究的是东北大学控制仿 真研究中心的张纪会博士与徐心和教授，他们在1997年10月发表的一种新的进化算法 蚁群算法F算是对国内研究者的一个介绍性的引入.回顾蚁群算法自创立以来近二十年的发展历程，目前人们对蚁群算法的研究已由当 初单一的TSP领域渗透到了多个应用领域，由解决一维静态优化问题发展到解决

14、多维动 态组合优化问题，由离散域范围内研究逐渐拓展到了连续域范围内研究，而且在蚁群算 法的硬件实现上也取得了突破性进展，同时在蚁群算法的模型改进及与其它仿生优化算 法的融合方面也取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前 所未有的勃勃生机，并已经成为一种完全与遗传算法等其他智能算法相媲美的仿生优化 算法.1.3论文的主要工作1.3.1主要内容本文主要介绍了蚁群算法的基本机理，分析了其算法优点和不足之处，并以TSP 问题为例，对蚁群算法的基本原理，蚁群算法的基本模型，进行了系统的阐述，并以 河南省内各大城市之间的最小路线，运用MATLAB 进行求解。1.3.2论文组织本文共分

15、为三章：第一章为绪论，着重阐述课题研究的背景和意义，国内外研究的现状。第二章介绍了蚁群算法的基本原理，并分析了它的优点和不足之处。对各种改进型 的蚁群算法进行了研究，并分析的各自的特点。第三章对蚁群算法在TSP问题中的应用进行阐述，介绍了蚁群算法在TSP问题中 的应用及特点。最后为结束语，为本文工作的总结，及对未来的展望。2蚁群算法的基本原理及其分析2.1蚁群算法的基本原理蚁群算法是近年来发展起来的一种新型模拟进化算法，它是由意大利学者M .Dorigo 等人在20世纪90年代初提出来的.这种算法模仿了蚂蚁在搬运食物的过程中，自发寻找 最短路径的行为特征，加以改进并应用到不同的领域.蚂蚁是群体动物，它们没有视觉但是可以通过集体配合劳动找到从巢穴到食物源的 最短路径.仿生学家经过大量研究后发现，蚂蚁在搜索食物时个体之间能通过在路径上 留下的气味来进行信息传递，这种气味称作信息素(pheromone).蚂蚁边运动边留下信息 素，并且可以根据嗅到的信息素的浓度来进行前进路径的选择.蚂蚁总是倾向于沿着信 息素浓度高的方向来移动，而路径上的信息素会随着时间的