毕业设计我帮你

蚁群算法的应用
摘要：蚁群算法，它是一种几率型算法，用以在图中探求优化途径。蚁群算法是它是一种模仿进化算法，初阶的钻研评释该算法具有许多的优秀的性质。在20世纪90年代初由著名的意大利的学者Marco Dorigo年在他的博士论文中首次提出，算法的灵感来自于他在观察蚂蚁在寻觅食物过程当中觉察途经的活动。本论文首先对蚁群算法的一些基本理论和应用场景进行了简单的说明，然后在蚁群算法的基础上，简要学习探究了基于蚁群算法的两个比较经典的问题，TSP问题和路径规划问题，测试经过matlab仿真解决问题，然后通过仿真结果得到最优的解决方案，最终得到对于蚁群算法的结论与展望。
关键词：蚁群算法；旅行商问题；TSP；路径规划。
 
Application of ant colony algorithm
Abstract: Ant colony algorithm, which is a probability based algorithm to explore ways to optimize in the figure. Ant colony algorithm is that it is an imitation of evolutionary algorithms, elementary assessment study release this algorithm has many excellent properties. In the early 1990s by the famous Italian scholar Marco Dorigo first proposed in his doctoral thesis, inspired by the algorithm from his perceived through the observation of ants foraging for food in the course of events. In this thesis, some of the basic ant colony algorithm theory and application scenarios for a simple explanation, and then based on the ant colony algorithm, a brief study explores the ant colony algorithm based on two more classic problem, TSP and path planning problem problem, problem-solving test after matlab simulation, then the optimal solution for the simulation results, and ultimately get the ant colony algorithm for the conclusion and outlook.
Keywords: Ant colony algorithm, Traveling Salesman Problem, TSP, Path planning.

目    录

一、绪论 1
（一）研究背景 1
（二）课题意义 2
二、蚁群算法概述 3
（一）算法介绍，使用场合 3
（二）工作原理 4
（三）优缺点 5
三、蚁群算法应用1 6
（一）应用场景 6
（二）算法流程 6
1.初始化参数 6
（三）算法实现 7
四、蚁群算法应用2 15
（一）应用场景 15
（二）算法流程 15
（三）算法实现 16
五、结论与展望 26
六、参考文献 26

一、绪论

（一）研究背景

在当今社会，随着人工智能的发展和网络技术的飞速发展，各种学科的科学和技术等相互交叉，互相浸透交融，不单给人们的生活、学习和工作等方面带了便当，并且也从根本上转变了人类的生活和生产。同时，随着人类生存空间的扩大以及世界知识水平的不断提高，提出了更高的要求，越来越多的人对科学技术的发展，期待更多的研究学者的不断研究和改进，其中包含的智能算法的优化的要求也是得到了非常迫切需求。为了抬高优化技术水平和智能计算的成长，近些年来有不少的研究学者，特别是在生物方面的研究专家和学者，通过对大自然中很多生物的生活现象和规律进行了大量的研究和探讨，提出了很多的群体智能算法。这些智能算法是一种基于生物信息系统的智能仿生算法，学者们是对社会性的虫豸互相合作并进行劳动的钻探，从生物进化和仿生学角度得到启迪而提出的。我们都知道，社会性虫豸如蜜蜂，蚂蚁等尽管其单个个别的力气很小，活动方法很简单、即刻，可是它们却可以凭仗团体的力量举行少许繁杂的社会性举动，更好地完成个人很难甚至无法完成的事情，因为他们可以通过劳动和其他方式的社会分工迅速找到食物，筑巢和防止入侵等。这样“聪明”的昆虫群体，我们便可能够称它为群体智能了。群体智能中的群被定义为“主体间一套的间接通信，身体可以分布式问题求解”。群体智能是“没有任何情报合作的主要特点表现出智能行为”。群体智能在没有集中控制而且是不提供全体模子的前提下，为找出繁杂的分布式题目的解决方案供应了底子。在许多专家和学者的集思广益、通力合作下，有很多的群体智能算法得到建议并有了很好的成长和利用。虽然一些智能算法已成熟的理论，但把它们很好的利用仍然是在现实生活中有一定的差距，我们需要参与，继续探索和尝试和研究。

蚁群算法是群智能算法的一个重要分支。在对像蜜蜂、蚂蚁等等生物昆虫进行了大量的长时间的考察和钻研后，生物学家们察觉了，像蚂蚁这样弱小的昆虫，在寻食的过程当中，经过一个团队的努力，通过反复的搜索和识别，最终仍然是找到了最短途径从蚂蚁巢到食品源。为了进一步的钻研，生物学家就在蚂蚁寻觅食品的途径上，设立少许障碍物来影响蚂蚁寻找路径，经由一段时间的搜索，最后蚂蚁照样找到了从巢穴到食物源的最短路径。通过各种各样的试验，生物学家进一步的钻研讲明，蚂蚁在寻觅食物的探寻过程当中，会在所经过的路途上开释一种蒸发的化学物质，这种特殊的物质称为信息素。信息素可以储存在路径上，并且随着时间的不断推移慢慢地的挥发。当蚂蚁在选择他们的途径时，它们就更加的倾向于往信息素浓度比较高的途径上前行，所以就是信息素能够引导蚂蚁更快，更容易的离开巢穴找寻到离它们最近的食品。各种试验的结果表明，就是这种特殊的物体，可以使得蚂蚁从巢穴探寻到通向食品的最短途径。也能够说，当蚂蚁的巢穴和食品之间有比较多的途径时，整个蚁群能够通过探寻各个个体蚂蚁留下来的信息素的痕迹，从而来找到往返于蚁穴和食品之间的最短的途径。

（二）课题意义

蚁群算法由意大利的学者 M. Dorigo ，V.Maniezzo等人在 20 世纪 的90 年代初期不断地深入钻研蚂蚁探求从蚂蚁巢穴到食品源的途径时，从生物进化的机制中得到了重要的启迪，从而提出了一种新式的模仿进化算法，蚁群算法。蚁群算法具有鲁棒性（稳妥性）、分布式计算与正反馈性等长处，在求解比较繁杂的组合优化题目上占着更大的上风，在分派问题、Job-shop 调节等问题上，都有了较好的实验结果。在解决计算机算法中经典的旅行商问题的求解时，许多的学者根据算法基本原理，在算法中设计了一个虚拟的“蚂蚁”寻找一条不同的路线，这是一个虚拟的“信息素”，它会随时间逐渐消失。在道路上的每一只蚂蚁每次随机的选择他们要去的途径，它们会尽量的选择较短、信息素浓度比较高的途径，并根据“信息素比较浓的路线更近”的这一原则，选择出最佳的途径。因为蚁群算法使用了正反馈的方式，使得较短的途径可以有比较大的机遇获得选取，而且还采取了几率的算法，从而来选择它们下一步即将要走的途径，所以它才能够不仅仅局限于部分最优解。尽管对蚁群算法的钻研功夫不是很长，远远不如像是遗传算法，模拟退火算法等算法那样形成2体系的剖析方法和坚固的数学底子和理论基础，可是它的出现，可以为解决少许繁杂的系统优化题目供应了一种新式的，更加好的求解算法，特别是在求解分离型组合优化的题目上，蚁群算法表现出了其余的进化算法没法相比的优越性。蚁群算法不但拥有鲁棒性、分布式计算、正反馈性、容易和其他的智能算法相结合的特质，并且还有能够智能搜索、全体优化等优点。该算法已经引发了许多专家和学者的注重，目下当今正被越来越多的专家和学者关心和钻探，算法的理论获得了不断的完善，使用范畴也遍及到了很多的科学技术及工程畛域，是一种有良好发展前景的模拟进化算法。

参考文献
[1] 刘阳阳.基于路径特征改进的蚁群算法求解旅行商问题[D].吉林大学，2013.
[2] 杨学峰.蚁群算法求解TSP问题的研究[D].吉林大学，2010.
[3] 李颖.用蚁群算法求解最小极大流问题[D].河南理工大学，2010.
[4] 曹桂文，张英.基于蚁群算法的TSP问题求解[J]，改革与开放，2010，16.
[5] 刘波.蚁群算法改进及应用研究[D].燕山大学，2010.
[6] 刘援农.蚁群算法在TSP问题中的应用研究[J]，硅谷，2011，13.