职称论文发表 发表论文
职称论文 发表论文 合作流程 联系方式 论文发表
职称论文发表 会员登录 用户名: 密码: 我要注册
职称论文发表网   首页   经济论文 |法学论文 |理工科论文 |管理学论文 |计算机论文 |文史论文 |医学论文 |教育论文 |艺术论文 |社会学论文 |政治论文 |试题 |应用文 |论文投稿 |职称评定 |教案 |论文关键词 |电子商务 |体育论文 |学术机构 |发表论文 |教育资讯 |医学资讯 |物联网论文 |中国论文网 | 职称论文
职称论文 本站论文搜索
职称论文 设为首页 职称论文发表网 收藏本站 职称论文发表 联系我们
职称论文  首页-->理工科论文-->通信学-->文章正文
蚁群算法基本原理及其应用综述

作者 :程 艳 燕更新时间:2012-11-1

职称论文发表
职称论文发表 专业提供:发表论文、论文发表、毕业论文、职称论...
住在汉口网
住在汉口网是一个专业提供汉口房产信息、车辆服务、生活服务、招...
职称论文网
职称论文网提供:发表论文、论文发表、毕业论文、职称论等服务。
(南京信息工程大学 江苏 南京 210044)
摘 要:蚁群算法(ACA)是一种广泛应用于优化领域的仿生进化算法。从ACA发展背景着手,分析比较国内外ACA研究团队与发展情况,立足于基本原理,分析其数学模型,介绍了六种经典的改进模型,对其优缺点进行分析,简要总结其应用领域并对其今后的发展、应用做出展望。
关键词:蚁群算法;优化;改进;应用
0 引言
专家发现单个蚂蚁只具有一些简单的行为能力,但整个蚁群却能完成一系列复杂的任务,这种现象是通过高度组织协调完成的。1991年,意大利学者M.Dorigo首次提出一种新型仿生算法ACA,研究了蚂蚁的行为,提出其基本原理及数学模型,并将之应用于寻求旅行商问题(TSP)的解。
通过实验及相关理论证明,ACA有着有着优化的选择机制的本质,而这种适应和协作机制使之具有良好的发现能力及其它算法所没有的优点,如较强的鲁棒性、分布式计算、易与其他方法结合等;但同时也不应忽略其不足,如搜索时间较长,若每步进行信息素更新,计算仿真时所占用CPU时间过长;若当前最优路径不是全局最优路径,但其信息素浓度过高时,靠公式对信息素浓度的调整不能缓解这种现象,会陷入局部收敛,无法寻找到全局最优解;转移概率过大时,虽有较快的收敛速度,但会导致早熟收敛,所以正反馈原理所引起的自催化现象意在强化性能好的解,却容易出现停滞现象。笔者综述性地介绍了ACA,对一些已有的提出自己的想法,并对其应用及发展前景提出了展望。
1 蚁群算法概述
ACA源自于蚁群的觅食行为。S.Goss的“双桥”实验说明蚂蚁总会选择距食物源较短的分支。蚂蚁之间通过信息素进行信息的传递,捷径上的信息素越多,吸引的蚂蚁越多,形成正反馈机制,达到一种协调化的高组织状态,该行为称集体自催化。目前研究的多为大规模征兵,即仅靠化学追踪的征兵。
1.1 蚁群算法的基本原理
为便于研究提出以下基本假设:蚂蚁间通过信息素和环境进行间接通信;蚂蚁对环境的反应由其内部模决定;蚂蚁个体是独立的,但群体却呈现出一种随机性。
蚂蚁通过适应和协作两个阶段的调整从无序到有序,得到最优解,完成对路径的搜索。对路径的选择,重点在转移概率,即某时刻蚂蚁k在城市i选择城市j的概率的大小
pijk(t)=
arg■{[τ(r,u)α]·[η(r,u)β]}(q≤q0)■(j∈allowedk)(1)
其中,q0和q分别为[0,1]上的参数和均匀分布的随机数,其大小决定了利用先验知识与探索新路径之间的相对重要性。若q≤q0,则转移概率选取上面一个式子,即按照先验知识选择最好的边,否则,按照转移概率选择一条边,式1又被称为伪随机比例规则;j∈allowedk为蚂蚁k下一步允许选择的城市;ηis(t)为能见度因子;u为禁忌表;α,β分别反映蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性;τ(·)为信息素浓度的函数。根据不同的模型,信息素做不同的调整,如全局更新规则和局部更新规则。
2 蚁群算法的发展
蚁群优化(ACO)是研究受到真实蚁群行为启发的智能系统,常用于解决离散优化问题。启发式ACO是1991年由Dorigo和Gambardella提出定义的。
2.1 国外蚁群算法的发展概况
2.1.1 有关蚁群算法的研究团队
从ACO提出至今,越来越多的专家投身于蚁群算法的研究之中,其中较为突出的有以下四个:
(1)瑞士卢加诺IDSIA。1988年建立的IDSIA是非营利性研究人工智能研究所,2000年成为公共研究机构,隶属于卢加诺大学的信息学院和瑞士意大利语区高等专业学院的科技创新系,主要负责人为Luca,Lepori,Carlo和Schmidhuber。其中一研究主题是人工蚂蚁,该多代理方法是受基于信息素交流的生物蚂蚁启发而来,由前高级研究员Dorigo和联合负责人Luca领导研究的。其人工蚁和局部搜索算法的结合已经成为解决某些图形优化任务的方法选择,如车辆路径和网络路径,其迅速发展促成许多商业应用和关于人工蚂蚁的专门会议。
(2)比利时布鲁塞尔IRIDIA。IRIDIA是布鲁塞尔自由大学人工智能研究实验室,主要在理论上进行深入研究以及计算智能应用于优化。在Dorigo和Bersini领导下,其主要研究领域为群智能、组合问题的求解和连续空间优化问题的启发式、生物网络原理性研究以及商业智能应用四个方面,而有关于ACA的方向为群智能和元启发式。
IRIDIA在群智能的ACO和群机器人这两方面处于世界领先地位,对于具体元启发式的研究聚焦于ACO,主要研究点是研发一套合理的实验方法论,一套经验学习和元启发式构建的发展工具的应用,特别着重研究的是发展能够设计和完善随机局部搜索算法和元启发式算法的方法论。
近期研究ACA项目有:对ACA的基础理论研究、复杂系统的智能计算方法、使用生物启发和软件计算的医学成像、自组织的蚁群、走向型机器人群和群智能系统的通信策略。
(3)奥地利维也纳大学经济与统计商学院。由Richard和Artner等组成的团队,主要研究遗传算法、项目管理、最优控制、ACO和电子装配等研究课题。其中,关于ACO方面的工作由Richard和Karl负责,从1999年开始至今。
(4)德国莱比锡大学并行计算与复杂系统。Martin领导的数学与计算机科学学院计算机科学研究所的并行计算与复杂系统团队,关于ACA的主要研究是由人类前沿科学组织自主计划的自然系统优化,以及东风集团项目中的一些关于系统、模型和硬件算法等。
2.1.2 有关蚁群算法的国际会议
随着人们对ACA越来越重视,相关会议也组织起来,来自世界各地的专家对ACA及其应用展开研究讨论,其中以Dorigo为大会总主席的ANTS最为权威。
1998年在比利时布鲁塞尔召开第一届ACA研讨会:从蚁群到人工蚁,每隔两年召开一次蚁群优化和群智能国际会议。期间,2000年召开第二届ACA国际专会:从蚁群到人工蚁。另外,自2005年在美国加利福尼亚州帕萨迪纳威斯汀召开了IEEE群智能讨论会,2006年、2007年分别在美国印第安州印第安纳波利斯和美国夏威夷檀香山希尔顿村延续召开此会。除以上较为权威的会议,还有很多相关的国际会议,说明ACA在国际范围内得到越来越多的重视,研究亦广泛展开。
2.2 国内蚁群算法的发展概况
国内对该算法研究最早的是张纪会博士和徐心和教授。1999年3月,他们首次简单引进ACA,从其基本原理、模型、伪码流程进行说明,对Oliver30 TSP问题分析说明,但未对基本模型中的参数进行详细地理论说明,且停止条件的界定较含糊,主要靠经验决定。其后引入的变异机制加快了收敛速度,使得到较优解的周期缩短,并从计算机仿真层面上证明其有效性。
2001年,陈烨引入遗传算法中用到的杂交算子来改善蚁群搜索速度慢、容易陷入局部最优。但随路程的增长,每次的代数显著增加,计算量较大。同年8月,郝晋等通过将转移概率设置为转移系数,结合扰动策略以防止漏选最优路径,能够节约计算时间,且能够很好的克服算法容易陷入局部最优的缺陷,计算精度也有提高。但在关于倒指数的扰动因子和均匀分布的随机数的选择并未解决,仍以实验为主要获取手段。而后李艳君等对自适应ACA进行了进一步研究,对信息素采取自适应更新,应用于连续空间优化问题的求解,并进行了证明。
2002年,王颖等对自适应ACA作出了改进,获得了很好的结果。该ACA在进化代数减少的情况下,解的质量也得到了一定提高,在一定程度上实现了收敛速度与解的质量的平衡。但分析其复杂度可知,蚂蚁的数目与问题规模不相上下,蚂蚁数目增多会使收敛速度过快,为防止该现象而将信息素挥发悉数设置得比一般情况低一个数量级,而相关系数α、β、ρ等则由实验设定。当蚂蚁数量与问题规模相当时,实验次数与时间是不容忽视的一个问题。ACA除在原理层面进行模型改进,在应用方面也有一定发展,如张宗永等将ACA作出改进,配合随机分布技术,应用到分析上海市整个内河航道和集装箱运输的过程中,对内河航道进行规划,最终得出合理的分配方案并提出了满足最优分配的河道改造的建议。
2003年,陈崚等令人工蚁模仿真实蚂蚁的感觉和知觉行为,设置合理绝对感觉阈值以克服蚂蚁在初始选择时容易失去解的多样性,改进选择策略以自适应的修改路径上的信息量,通过对不同规模和不对称TSP的仿真说明算法具有较好的收敛性和稳定性。新提出的启发式搜索方法——智能ACA,通过取消外激素、自动调整选择最优路径的比例,改变了选择目标城市的依据和引入扰动,仿真结果说明在减少计算量的同时,可取得更好的搜索结果,但也指出通过实验确定相关的物理系数不利于算法的推广。但该文仅针对TSP,对其他问题能否应用仍不明确。
2004年,黄国锐等提出采用不同于传统基本ACA所采用的蚁周模型,它采用了更贴近于真实蚂蚁行为的蚁量模型,建立信息素扩散模型,使相距较近的蚂蚁之间能够更好地进行协作,文中仿真结果表明该算法的有效性。然而文中虽在达到收敛所需进化代数上较基本ACA有了很大的改进,减少约4倍,但最短路径长度的减少并不明显,且参数的设定仍是以试验为手段,缺乏理论支撑。
针对基本ACA容易陷入局部最优、收敛慢等缺陷,许多新模型陆续提出,如基于云模型的ACA、对信息素的限制、回归型的等,甚至还有不少研究者试图从新的角度重新审视并尝试性研究ACA,较为新颖的有从蚁群社会的“多态性”出发,试图以更贴近真实世界中蚂蚁行为来研究ACA,发现更适应较大规模的问题,以及将着眼于蚁群整体的研究角度转换到关注蚂蚁个体的速度对算法的影响。为从根本上解决ACA不足,其收敛性的分析也在不断展开,如用动态分阶段的方式,而具体影响ACA的参数也越来越得到关注,如有相关讨论,但参数如何设定并未有理论依据,如何建立通用标准来对参数进行最优设置仍是难点。在研究的应用范围方面也从一开始的离散域扩展到连续域,连续域中有关于收敛性的研究,以及新模型的设计也在进行着。
全国各高校及研究机构也对该算法展开了研究,如徐锋、杜军平的《改进蚁群算法在旅游路线规划中的应用研究》等。1999年从首次引入ACA至今,相关研究蓬勃发展,右图为相关的论文题名和关键字的论文数量增长表。
国内对于ACA的研究也越来越深入,基于各类模型的ACA层出不穷,研究域也从离散域扩展到连续域,同时ACA在不断与其他算法结合以克服本身的缺陷。但国内的研究起步较晚,对于影响收敛性的α、β等相关参数至今无法确定一套相关的理论来进行设置,只能通过反复试验来大致确定一个参数范围,且研究较多地停留在理论仿真,应用到实践中仍较少,而国外对于这些范围的研究已经较为成熟。
2.3 蚁群算法的改进型
ACA的收敛速度和最优解的全局性是一对矛盾体,收敛速度过快,会导致早熟,陷入局部最优解,而当信息素更新不及时或算法计算量过大时,则导致收敛速度过慢而应用不现实,为克服这些问题,相应的改进的ACA不断提出。
(1)带精英策略的蚁群系统(AS)。在带精英策略的AS中,为了使到目前为止所找出的最优解在下一个循环中对蚂…… 职称论文发表网http://www.issncn.com 职称论文发表网http://www.issncn.com

1 2 3
论文首页】【设为主页】【加入收藏】【打印本文】【回到顶部
最新上传
 《美与时代》城市版杂志稿...
 让快乐体育走进孩子们心中
 武昌区开展小学体育教学研...
 中英校际交流,校园足球添...
 《原地单手肩上投篮》教学...
 七年级《篮球运球》教学设...
 职校教师的角色定位
 我对因材施教的看法
 物理教学中德育渗透
 中职德育课堂的应用表现性...
 肺结核治疗综述
 肺结核治疗方案
 肺结核治疗问题
 肺结核50例临床治疗
 肺结核病人护理
职称论文
本站推荐
 武昌区开展小学体育教学研...
 中英校际交流,校园足球添...
 《原地单手肩上投篮》教学...
 七年级《篮球运球》教学设...
 我对因材施教的看法
 中职德育课堂的应用表现性...
 肺结核治疗方案
 肺结核治疗问题
 肺结核50例临床治疗
 肺结核病人护理
 农村城镇化探析
 篮球运动员身体素质训练
 国防经济研究
 公共危机应急保障机制建设
 科研院所物业管理社会化
职称论文发表
所有资料均源于网上的共享资源及期刊共享,请特别注意勿做其他非法用途。
如有侵犯您的版权或其他有损您利益的行为,请联系指出,我们会立即进行改正或删除有关内容!
  网站介绍 联系我们 广告服务 网站导航 投诉建议 服务承诺 人才招聘 版权声明  
  •   投稿邮箱:83041061@qq.com    服务热线:027-62220402 手机: 18907137973
    点击及可直接咨询
    联系地址:武汉市江汉区新华下路江花苑13楼   电子地图
  • Copyright (C) 2007-2009 http://www.issncn.com/ All Rights Reserved.. 鄂ICP备:09016318号
    技术支持:腾浪科技    法律顾问:廖泉冰律师