蚁群算法文献综述

1、 成绩： 西安建筑科技大学毕业设计 (论文)文献综述院 （系）： 信息与控制工程学院 专业班级： 自动化1003班 毕 业 设 计论 文 方 向 ： 智能算法 综述题目： 蚁群算法基本原理和应用学生姓名： 张航宇 学 号： 100610324 指导教师： 张娜 2014 年 3 月 23 日信息与控制工程学院毕业设计（论文）文献综述蚁群算法及其在组合优化问题中的应用研究摘要：本次文献综述主要收集了与蚁群算法相关的基本资料，了解了蚁群算法的提出和发展，掌握了蚁群算法的基本原理，了解了其所应用的领域，并针对本次要研究的静态组合优化问题搜集了一些文献，进行了初步学习。关键词：蚁群算法；组合优化；TS

2、P1. 前言蚁群算法（Ant Colony Optimization, ACO），它由Marco Dorigo于1992年在他的博士论文“Ant system: optimization by a colony of cooperating agents”中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。其机理是:生物界中的蚂蚁在搜寻食物源时,能在其走过的路径上释放一种蚂蚁特有的分泌物信息素,使得一定范围内的其他蚂蚁能够觉察并影响其行为.当某些路径上走过的蚂蚁越来越多时,留下的这种信息素轨迹也越多,以至信息素强度增大,使后来蚂蚁选择该路径的概率也越高,从而更

3、增加了该路径的信息素强度. 蚁群算法是一种仿生类非线性优化算法,具有并行性、正反馈性和全局极小搜索能力强等特点.蚁群算法最早应用于旅行商问题（Travelling Salesman Problem）简称TSP问题，后来陆续渗透到其他领域，在很多领域已经获得了成功的应用，其中最成功的是在组合优化问题中的应用。组合优化问题分为两类：一类是静态组合优化问题，其典型代表有TSP，车间调度问题；另一类是动态组合优化问题，例如网络路由问题。本次毕业论文主要聚焦于静态组合优化问题。2蚁群算法原理2.1 蚂蚁的启发蚁群算法是受到对真实的蚁群行为的研究启发而提出的，像蚁群、蜜蜂等群居昆虫，虽然单个昆虫的行为很简

4、单，但是组成的群体却表现出极其复杂的行为。仿生学家经过大量细致观察研究发现，蚂蚁个体之间是通过一种称为外激素的物质进行信息传递的，蚂蚁在运动过程中，能够在它所经过的路径上留下外激素，而且蚂蚁在运动过程中能够感知这种物质，并且以此指导自己的运动方向，所以，大量的蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象。2.2 人工蚂蚁与真实蚂蚁的主要的区别人工蚂蚁与真实蚂蚁有三个主要的区别： 人工蚁群有一个记忆其本身过去行为的内在状态人工蚁群存在于一个与时间无关联的环境之中 人工蚁群存在于一个离散的空间中，它们的移动是从一个状态到另一个状态的转换人工蚁群不是完全盲从的，它还受到问题空间特征的启发 2.

5、3 双桥实验原理 如图1所示，设，0.我们假定在每个离散的等时间间隔：，有蚂蚁从到达，同时有个蚂蚁从到，每只蚂蚁的速度为，并且，每有一只蚂蚁经过时，在时间留下信息素密度为。蚂蚁在选择路径时，那些有更多蚂蚁曾经选择过的路径（也就是具有更高信息素密度的路径），被再次选中的可能性最大。当时，没有信息素，有只蚂蚁分别在和。蚂蚁走哪条道路是完全随机的。因此，在每个点上蚂蚁将有只经过，另外只经过。当时有只蚂蚁从到，它们发现指向道路上的信息素密度是，是由从出发的蚂蚁留下的；指向道路上的信息素密度是，其中是由出发蚂蚁留下，另外是从出发经过已经到达的蚂蚁留下。因此，选择经过到的可能性就更大，从出发到的只蚂蚁也面

6、临着同样的选择，由此产生一个正反馈过程，选择经过的蚂蚁越来越多，直到所有的蚂蚁都选择这条较近的道路。图1是著名的双桥实验的简化描述。3蚁群算法理论在理论建设方面，ACO取得的成果比较少，也是最薄弱的一方面。1999年Gutjahr W J在撰写的技术报告和2000年发表的论文中首次对蚁群算法的收敛性进行了证明，将蚁群算法的行为简化为在一幅代表所求问题的有向图上的随机行走过程，进而从有向图论的角度对一种改进蚁群算法图搜索蚂蚁系统（Graph-Based Ant System，GBAS）的收敛性进行了理论分析。采用的数学工具是Markov链，证明了在一些合理的假设条件下他所提出的GBAS能以一定概

7、率收敛到所求问题的最优解。4蚁群算法优势蚁群算法是一种近似算法，它不是用来解决已存在精确有效算法的问题的，而是用来解决至今没有找到精确的有效算法的问题的，例如旅行商问题（TSP）。旅行商问题也可以说是求“最短路径”，这个问题至今未找到多项式时间算法，属于NPC问题，也就是说，当问题规模稍大一点，现有的精确算法的运算量就会急剧增加。在上图中，可以看到，当问题规模为10时，复杂度为O(3.4n3) 的算法运行时间要0.0034s，复杂度为O(2n) 的算法运行时间要0.001s，此时相差还不大，但当问题规模增加到100时，前者的运行时间只是增加到了3.4s，而后者的运行时间则增加到了4×

8、1016年！ 因为实际问题的规模都比较大，100还是小数字，所以对一个问题，都努力寻求多项式算法。但也有问题目前还没有找到多项式时间的精确算法，比如旅行商问题，因此就产生了各种近似算法，以解的质量来换取效率，寻求满意解而不是最优解。*图片来源：Sara Baase, Allen Van Gelder，Computer Algorithms: Introduction to Design and Analysis，影印版第三版，高等教育出版社，2001 （第49页 图1.5）4总结在本次完成文献综述的过程中，我了解了蚁群算法的起源和发展，最基本的原理，以及其越来越广的应用领域，对蚁群算法有了整体

9、上的初步理解。基于正文分析，可以得到蚁群算法所求解的问题空间可用一个重要的数学工具-图（graph）来描述，在工程实际中很多问题都可以用图来描述，这就为蚁群算法的应用提供了广阔的空间。在组合优化问题中，很多精确算法的时间复杂度远大于正常要求，这让蚁群算法有了很大的比较优势。参考文献1 段海滨，蚁群算法原理极其应用M，2007.科学出版社 2 林家恒 贺庆，一种求解TSP的蚁群算法，山东大学控制科学与工程学院，2500613 M. Dorigo and T. Stutzle, Ant Colony OptimizationM: MIT Press, 2004 4李士勇, 陈永

10、强, 李研, 蚁群算法及其应用M, 2004哈尔滨工业大学出版社,5吴璇, 基于蚁群算法求解TSP问题的研究, 北京邮电大学计算机学院。100876邓江沙，姚钢 改进的蚁群算法在求解TSP中的应用, 长沙理工大学4100767 Martens, D ;Backer, M De ;Haesen, R ;Vanthienen, J ;Snoeck, M ;Baesens, B，Classification With Ant Colony Optimization，20098 Middendorf, Martin，Modeling the Dynamics of Ant Colony Optimization，20129 Xu, Benlian;Chen,，Qinglan;Wang, Zhiquan，Track initiation with ant colony optimization，200910 Naka