蚁群算法综述.doc

《智能计算—蚁群算法基本综述》班级:研1102班专业:计算数学姓名:刘鑫学号:2012年蚁群算法基本综述刘鑫(西安理工大学理学院,研1102班,西安市,)摘要:蚁群算法(ACA)是一种广泛应用于优化领域的仿生进化算法。ACA发展背景着手,分析比较国内外ACA研究团队与发展情况立足于基本原理,分析其数学模型,介绍了六种经典的改进模型,对其优缺点进行分析,简要总结其应用领域并对其今后的发展、应用做出展望。关键词:蚁群;算法;优化;改进;应用引言专家发现单个蚂蚁只具有一些简单的行为能力。但整个蚁群却能完成一系列复杂的任务。这种现象是通过高度组织协调完成的1991年。。研究了蚂蚁的行为。提出其基本原理及数学模型。并将之应用于寻求旅行商问题(TSP)的解。通过实验及相关理论证明,ACA有着有着优化的选择机制的本质。而这种适应和协作机制使之具有良好的发现能力及其它算法所没有的优点。如较强的鲁棒性、分布式计算、易与其他方法结合等;但同时也不应忽略其不足。如搜索时间较长,若每步进行信息素更新,计算仿真时所占用CPU时间过长:若当前最优路径不是全局最优路径,但其信息素浓度过高时。靠公式对信息素浓度的调整不能缓解这种现象。会陷人局部收敛无法寻找到全局最优解:转移概率过大时,虽有较快的收敛速度,但会导致早熟收敛。所以正反馈原理所引起的自催化现象意在强化性能好的解,却容易出现停滞现象。笔者综述性地介绍了ACA对一些已有的提出自己的想法,并对其应用及发展前景提出了展望。1蚁群算法概述ACA源自于蚁群的觅食行为。“双桥”实验说明蚂蚁总会选择距食物源较短的分支蚂蚁之间通过信息素进行信息的传递,捷径上的信息素越多,吸引的蚂蚁越多。形成正反馈机制,达到一种协调化的高组织状态该行为称集体自催化目前研究的多为大规模征兵,即仅靠化学追踪的征兵。:蚂蚁间通过信息素和环境进行间接通信:蚂蚁对环境的反应由其内部模决定:蚂蚁个体是独立的,但群体却呈现出一种随机性。蚂蚁通过适应和协作两个阶段的调整从无序到有序,得到最优解,完成对路径的搜索。对路径的选择,重点在转移概率,即某时刻蚂在城市选择城市的概率的大小。(1)其中,和分别为上的参数和均匀分布的随机数,其大小决定了利用先验知识与探索新路径之间的相对重要性。若,则转移概率选取上面一个式子,即按照先验知识选择最好的边,否则,按照转移概率选择一条边,式又被称为伪随机比例规则;为蚂蚁下一步允许选择的城市;为能见度因子;为禁忌表;,分别反映蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性;为信息素浓度的函数根据不同的模型,信息素做不同的调整,如全局更新规则和局部更新规则。2蚁群算法的发展蚁群优化(ACO)研究受到真实蚁群行为启发的智能系统,常用于解决离散优化问题启发式ACO是1991年由Dorigo和Gambardella提出定义的。国外蚁群算法的发展概况有关蚁群算法的研究团队从ACO提出至今,越来越多的专家投身于蚁群算法的研究之中,其中较为突出的有以下四个:(1)瑞士卢加诺IDSIA。1998年建立是IDSIA是非营利性研究人工智能研究所,2000年成为公共研究机构,隶属于卢加诺大学的信息学院和瑞士意大利语区高等专业学院的科技创新系,主要负责人为Luca,Lepori,Carlo和Schmidhuber。其中一研究主题是人工蚂蚁,该多代理方法是受基于信息素交流的生物蚂蚁启发而来,由前高级研究员Dorigo和联合负责人Luca领导研究的。其人工蚁和局部搜索算法的结合已经成为解决某些图形优化任务的方法选择,如车辆路径和网络路径,其迅速发展促成许多商业应用和关于人工蚂蚁的专门会议。(2)比利时布鲁塞尔IRIDIA。IRIDIA是布鲁塞尔自由大学人工智能研究实验室,主要在理论上进行深入研究以及计算智能应用于优化。在Dorigo和Bersini领导下,其主要研究领域为群智能、组合问题的求解和连续空间优化问题的启发式、生物网络原理性研究以及商业智能应用四个方面,而有关于ACA的方向为群智能和元启发式。IRIDIA在群智能的ACO和群机器人这两方面处于世界领先地位,对于具体元启发式的研究聚焦于ACO,主要研究点是研发一套合理的实验方法论,一套经验学****和元启发式构建的发展工具的应用,特别着重研究的是发展能够设计和完善随机局部搜索算法和元启发式算法的方法论。近期研究ACA项目有:对ACA的基础理论研究、复杂系统的智能计算方法、使用生物启发和软件计算的医学成像、自组织的蚁群、走向型机器人群和群智能系统的通信策略。(3))奥地利维也纳大学经济与统计商学院由Richard和Artner等组成的团队,主要研究遗传算法、项目