蚁群算法基本原理及其应用综述

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

1、蚁群算法基本原理及其应用综述程艳燕(南京信息工程大学江苏南京210044)摘耍：蚁群算法(ACA)是一种广泛应用于优化领域的仿生进化算法。从ACA发展背景着手，分析比较国内外ACA研究团队与发展情况，立足于基本原理，分析其数学模型，介绍了六种经典的改进模型，对其优缺点进行分析，简要总结其应用领域并对其今后的发展、应用做出展望。关键词:蚁群算法；优化；改进；应用中图分类号:TP273文献标识码：A0引言专家发现单个蚂蚁只具有一些简单的行为能力，但整个蚁群却能完成一系列复杂的任务，这种现象是通过高皮组织协调完成的。1991年，

2、意大利学渚MDorigo首次提出一种新型仿牛算注ACA.研究了蚂蚁的行为，提出其基环原理及数学模型，并将之应用于寻求旅行商问题(TSP)的解。通过实验及相关理论证明，ACA有着有着优化的选择机制的本质，而这种适应和协作机制使之具有良好的发现能力及其它算法所没有的优点，如较强的鲁棒性、分布式计算、易与其他方法结合等；但同时也不应忽略其不足，如搜索时间较长，若每步进行信息素更新，计算仿真时所占用CPU时间过长；若当前最优路径不是全局最优路径，伍其信息素浓度过高时，靠公式对信息素浓度的调整不能缓解这种现象，会陷乂局部收敛，无法寻

3、找到全局最优解；转移概率过大时，虽有较快的收敛速度,但会导致早熟收敛，所以正反馈原理所引起的自催化现象意在强化性能好的解•却容易出现停滞现象。笔者综述怕地介绍了ACA.对一些已有的提出自己的想法，并对其应用及发展前景提出了展望。1蚁群算法概述ACA源自于蚁群的觅食行为。SGoss的“双桥”实验说明蚂蚁总会选择距食物源较短的分支。蚂蚁之.间通过信息素进行信息的传递.捷径上的信息素越多，吸引的蚂蚁越多，形成正反馈柳制，达到一种协调化的JS组织状态，诊行为称集体自催化。目前研究的多为大规模征兵，即仅靠化学追踪的征兵。1.1蚁群算

4、法的基本原理为便于研究提出以下基本假设：虬蚁间通过信息素和环境进行间接通信;蚂蚁对环境的反应由其内部模决定；吳蚁个体是独立的，但群体却呈现出一种随机性。蚂蚁通过适应和协作两个阶段的调整从无序到有序，得到最优解，完成对路径的搜索。对路径的选择，重点在转移概率，即某时刻蚂蚁k在城市i选择城巾j的概率的大小P『(t)=max{[T(r,u)°]-[r](r,u)^]}(q

5、要性。若q

6、o和Gambardella提出定义的。21国外蚁群算法的发展概况211有关蚁群算法的研究团队从ACO提出至今，越来越多的专家投身于蚁群算法的研究Z中，其中较为突出的有以下四个：(1)瑞士卢加诺IDSIA01988年建立的IDSIA是非营利性研究人工智能研究所，2000年成为公共硏究机构，隶属于卢加诺大学的信息学院和瑞士总人利语区离等专业学院的科技创新系，主要负责人为Luca,Lepori,Carlo和Schmidhuber0其中一研究主题是人丁蚂蚁.该多代理方法是受基于信息索交流的生物蚂蚁启发而来，由前高级研究员Dorig

7、o和联合负贵人Luca领导研究的。其人工蚁和局部搜索算法的结合己经成为解决某些图形优化任务的方法迭择，如车辆路径和网络路径，其迅速发展促成许多商业应用和关于人工蚂蚁的专门会议。(2)比利时布鲁塞尔IRIDIAdRIDIA是布鲁塞尔自由大学人工智能研究实易失去解的多样性，改进选适应的修改路径上的信息同规模和不对称TSP的仿具有较好的收敛性和稳定啊启发式搜索方法——智能消外激索、自动调整选择最例，改变了选择目标城市的扰动，仿真结果说明在减少吋，可取得更好的搜索结通过实验确定相关的物理算法的推广。但该文仅针用他问题能否应用仍不明

8、确。2004年，黄国锐等提出传统基木ACA所采用的谢采川了更贴近于真实蚂蚁模型，建立信息素扩散模近的蚂蚁之间能够更好地中仿真结果表明该算法的笔文中虽在达到收敛所需进基本ACA有了很大的改进倍，但最短路径长度的减且参数的设定仍是以试验理论支撑。针对基本ACA容易优、收敛慢等缺陷，许多新出，如基于云模型的A