蚁群算法文献综述

《蚁群算法文献综述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、群算法(AntColonyOptimization,ACO),它由MarcoDorigo于1992年在他的博士论文''Antsystem:optimizationbyacolonyofcooperatingagents”中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。其机理是:生物界中的蚂蚁在搜寻食物源吋，能在其走过的路径上释放一种蚂蚁特有的分泌物信息素，使得一定范围A的其他蚂蚁能够觉察并影响其行为.当某些路径上走过的蚂蚁越来越多吋，留下的这种信息素轨迹也越多，以至信总素强度增人，使后来蚂蚁选择该路

3、径的概率也越高，从而更增加了该路径的信息素强度.蚁群算法是一种仿生类非线性优化算法,具有并行性、正反馈性和全局极小搜索能力强等特点.蚁群算法最早应用于旅行商问题(TravellingSalesmanProblem)简称TSP问题，后来陆续渗透到其他领域，在很多领域己经获得了成功的应用，其屮最成功的是在组合优化问题中的应用。组合优化问题分为两类：一类是静态组合优化问题，其典型代表有TSP,车间调度问题；另一类是动态组合优化问题，例如网络路由问题。木次毕业论文主要聚焦于静态组合优化问题。2.蚁群算法原理2.1蚂

4、蚁的启发蚁群算法是受到对真实的蚁群行为的研宄启发而提出的，像蚁群、蜜蜂等群居昆虫，虽然单个昆虫的行为很简单，但是组成的群体却表现出极其复杂的行为。仿生学家经过大量细致观察研究发现，蚂蚁个体之间是通过一种称为外激素的物质进行信息传递的，蚂蚁在运动过程中，能够在它所经过的路径上留下外激素，而II蚂蚁在运动过程中能够感知这种物质，并且以此指导自己的运动方向，所以，大量的蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象。2.2人工蚂蚁与真实蚂蚁的主要的区别人工蚂蚁与真实蚂蚁有三个主要的区别：•人工蚁群有一个记忆其

5、本身过去行为的内在状态•人工蚁群存在于一个与时间无关联的环境之屮•人工蚁群存在于一个离散的空间中，它们的移动是从一个状态到另一个状态的转换•人工蚁群不是完全盲从的，它还受到问题空间特征的启发2.3双桥实验原理如图1所示，设DH=HB=1,DC=CB=0.我们假定在每个离散的等时间间隔：t=0,1,2,……有30蚂蚁从A到达B，同时有30个蚂蚁从E到D,每只蚂蚁的速度为1/S,并且，每有一只蚂蚁经过时，在时间t留下信息素密度为1。蚂蚁在选择路径吋，那些冇更多蚂蚁曾经选择过的路径（也就是具冇更高信息素密度的路径

6、），被再次选中的可能性最大。当t=0时，没有信息素，有30只蚂蚁分别在B和D。蚂蚁走哪条道路是完全随机的。因此，在每个点上蚂蚁将有15只经过II,另外15只经过C。当t=i吋冇30只蚂蚁从A到B,它们发现指向H道路上的信息素密度是15,是由从B出发的蚂蚁留下的；指向C道路上的信息素密度是30,其中15是由B出发蚂蚁留下，另外15是从D出发经过C己经到达B的蚂蚁留下。因此，选择经过C到D的可能性就更大，从E出发到D的30只蚂蚁也面临着同样的选择，由此产生一个正反馈过程，选择经过C的蚂蚁越来越多，直到所冇的蚂蚁

7、都选择这条较近的道路。图1是著名的双桥实验的简化描述。1.蚁群算法理论在理论建设方面，ACO取得的成果比较少，也是最薄弱的一方面。1999年GutjahrWJ在撰写的技术报告和2000年发表的论文中首次对蚁群算法的收敛性进行了证明，将蚁群算法的行为简化为在一幅代表所求问题的有向图上的随机行走过程，进而从有向阁论的角度对一种改进蚁群算法一阁搜索蚂蚁系统（Graph-BasedAntSystem,GBAS）的收敛性进行了理论分析。采用的数学工具是Markov链，证明了在一些合理的假设条件下他所提岀的GBAS能以

8、一定概率收敛到所求问题的最优解。2.蚁群算法优势蚁群算法是一种近似算法，它不是用来解决已存在精确有效算法的问题的，而是用来解决至今没有找到精确的有效算法的问题的，例如旅行商问题（TSP）。旅行商问题也可以说是求''最短路径〃，这个问题至今未找到多项式时间算法，属于NPC问题，也就是说，当问题规模稍大一点，现有的精确算法的运算量就会急剧增加。Algorithmi234Timefunciicn(microsecJ33