2022年蚁群算法 .pdf

《2022年蚁群算法 .pdf》由会员分享，可在线阅读，更多相关《2022年蚁群算法 .pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、蚁群算法学号：1101500449 姓名：赵亮民摘要：蚁群算法是优化领域中新出现的一种仿生进化算法。该算法采用分布式并行计算机制，具有较强的鲁棒性；但有搜索时间较长，易陷入局部最优解的缺点。本文首先讲述蚁群算法的来源和基本原理，然后讨论蚁群算法的几种改进策略，并简单介绍近年来蚁群算法在许多新领域中的发展应用，最后对今后进一步研究的方向作了展望。关键词：蚁群算法；蚂蚁；信息素；优化Abstract：Ant colony algorithm is a novel category of bionic algorithm for optim ization problems Parallel com

2、putation mechanism is adopted in this algorithmIt has strong robustness and is easy to combinewith other methods in optimization，but it has the limitation of stagnation，and is easy to fall into local optimums Firstly，the basic principle of ant colony algorithm is introduced Then。a series of schemes

3、on improving the ant colony algorithm are discussed，and the new applications are also provided Finally，somerem arks on the further research and directions are presented Key words：ant colony algorithm；ant；pheromone；optimization 概念各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种挥发性分泌物pheromone(称为信息素

4、,该物质随着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近)来实现的，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。原理设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路

5、径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼地编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100 多行！为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢

6、？现今有哪些关于蚁群算法的应用呢？1 大规模集成电路的线网布局在大规模集成电路的线网布局中，需要根据电路和工艺的要求完成芯片上单元或功能模块的布局，然后实现它们之间的互连。此问题可看作是寻找一个网格平面上两端点之间绕过障碍的最短路径问题。线网上的每个Agent 根据启发策略 像蚂蚁一样在开关盒网格上爬行，所经之处便设置一条金属线历经一个线网的所有引脚之后线网便布通了。应用蚁群算法，可以找到成本最低、最合理的线网布局而且由于其本身的并行性。比较适合于解决此类问题。2 通信网络路由名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 3 页 -近年来 许多学者将蚁群算法应用于通讯领域，特别

7、是通信网络中的路由问题。通信网络的路由是通过路由表进行的在每个节点的路由表中。对每个目的节点都列出了与该节点相连的节点，当有数据包到达时通过查询路由表可知下一个将要到达的节点。网络信息的分布性、动态性、随机性和异步性与蚁群算法非常相似，都是利用局部信息发现解，间接通讯方式和随机状态的转换。DorigoDi Caro 和 Gambardella 首先将蚁群算法应用于网络路由问题并称这种算法为AntNet。3 蚁群算法在电力系统中的应用电力系统优化是一个复杂的系统工程它包括无功优化、经济负荷分配、电网优化及机组最优投入等一系列问题，其中很多是高维、非凸、非线性的优化问题。其中机组最优投入问题是寻求

8、一个周期内各个负荷水平下机组的最优组合方式及开停机计划，使运行费用最小。利用状态、决策及路径概念，将机组最优投入问题设计成类似旅行商问题的模式从而可方便地利用蚁群算法来求解。还有人将蚁群算法编入水力发电规划能源管理软件可很好地节约能源。此外 对于电力系统中的故障检测，蚁群算法也表现出较好的应用前景。由于故障地点的估计信息来自保护继电器和电路断路器，那么对所有故障部分的估计可以看作是一个组合优化问题。蚁群算法的应用进展以蚁群算法为代表的蚁群智能已成为当今分布式人工智能研究的一个热点，许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究。美国五角大楼正在资助关于群智能系统的研究

9、工作-群体战略(Swarm Strategy)，它的一个实战用途是通过运用成群的空中无人驾驶飞行器和地面车辆来转移敌人的注意力，让自己的军队在敌人后方不被察觉地安全进行。英国电信公司和美国世界通信公司以电子蚂蚁为基础，对新的电信网络管理方法进行了试验。群智能还被应用于工厂生产计划的制定和运输部门的后勤管理。美国太平洋西南航空公司采用了一种直接源于蚂蚁行为研究成果的运输管理软件，结果每年至少节约了1000 万美元的费用开支。英国联合利华公司己率先利用群智能技术改善其一家牙膏厂的运转情况。美国通用汽车公司、法国液气公司、荷兰公路交通部和美国一些移民事务机构也都采用这种技术来改善其运转的机能。鉴于群

10、智能广阔的应用前景，美国和欧盟均于近几年开始出资资助基于群智能模拟的相关研究项目，并在一些院校开设群体智能的相关课程。国内，国家自然科学基金”十五”期间学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了群智能领域的进化、自适应与现场认知主题。蚁群优化算法最初用于解决TSP问题，经过多年的发展，已经陆续渗透到其他领域中，比如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域己获得成功的应用，其中最成功的是在组合优化问题中的应用。在网络路由处理中，网络的流量分布不断变化，网络链路或结点也会随机地失效或重新加入。蚁群的自身催化

11、与正向反馈机制正好符合了这类问题的求解特点，因而，蚁群算法在网络领域得到一定应用。蚁群觅食行为所呈现出的并行与分布特性使得算法特别适合于并行化处理。因而，实现算法的并行化执行对于大量复杂的实际应用问题的求解来说是极具潜力的。存在的问题及解决方法的进展蚁群算法以其分布式并发性、正反馈、鲁棒性强、收敛速度快、易获得全局最优解等特点，成为目前国内启发式算法研究的热点，但是蚁群算法也存在如下缺点：容易出现停滞现象（stagnation behaviour），算法运算时间过长。针对这些缺陷，近年来众多国内外的学者在蚁群的改进方面做了大量的研究工作,其目的是在合理时间复杂度的限制条件下，尽可能提高蚁群算法

12、在一定的空间复杂度下的寻优能力，从而改善蚁群算法的全局收敛性，扩宽蚁群算法的应用领域。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 3 页 -M.Dorigo 等人提出一种修正的蚁群算法为Ant-Q System，该算法和基本蚁群算法有如下不同：（1）状态转移规则不同：仅让信息量最大的路径以较大的概率选中。（2）全局更新规则不同：仅对一次循环中的最优的蚂蚁使用。（3）增加更新规则：在所有蚂蚁完成一次转移后执行。德国学者Thomastuzle 和 Holerhoos 提出了一种改进的算法即最大最小系统（MAX-MINant system，MMAS）。为了防止算法过早的停滞，MMA

13、S 限定了信息量允许的上下限，并且采用了平滑机制对蚂蚁系统的解进行了改进。1999 年，M.Dorigo 把先前的各种蚁群算法归结为 ACO元启发式算法（ant colony optimization metar-heuristic）的概念，把各种基于蚁群系统的算法归结到一个统一的框架中。作为一种新型的启发式算法，ACO元启发式算法近年来受到广泛的关注。一些学者把蚁群算法和其它的一些仿生优化算法进行融合，并且取得了较好的应用效果。Abbattista F 等人最早提出将遗传算法（GA）和蚁群算法相融合的策略，并且在 Oliver30TSP和 Eilon50TSP的仿真实验中得到了较好的结果。候

14、云鹤等人将微粒群（PSO）引入蚁群算法（GACA）的局部搜索中，采用 GACA进行全局搜索，确定最优解存在的领域。Lee Z J提出一种新的融合算法即免疫-蚁群算法，并将其成功应用在求解WTAP。蒋加伏等提出了一种基于免疫-蚁群算法的多约束QoS路由选择算法，也取得了很好的应用效果。参考文献：1 蚁群算法及其应用研究赵天男;王晓红软件导刊2010（6）2 蚁群算法的研究及应用进展张祖琼电脑知识与技术2009（9）3蚁群算法的研究进展及应用刘彩云;陈忠软件导刊2008（9）4侯云鹤，熊信艮，吴耀武等基于广义蚁群算法的电力系统经济负荷分配J3中国电机工程学报，2003，23(3)：59645 李有梅，王文剑，徐宗本关于求解难组合优化问题的蚁群优化算法J3计算机科学 200229(3)：115 118 6温文波杜维蚁群算法概述J石油化工自动化，2002，(1)：19227马良项培军蚂蚁算法在组合优化中的应用J3管理科学学报20014(2)：3236 8胡娟，王常青，韩伟，全智蚁群算法及其实现方法研究J计算机仿真 2004，21(7)：1lO 一 114名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 3 页 -