ACO算法及应用

2007年第2期职业圈No.2,2007(总第54期)ZHIYE QUAN(Cumulatively No. 54)ACO算法及应用黄闻娴(温州大学瓯江学院,浙江温州325000)【摘要】AC0算法是一种新型模拟进化算法,为求解复杂一种新型模拟进化算法,研究表明该算法具有并行性,鲁棒的组合优化问题提供了一种新的思路和方法.文章对AC0算性等优良性质,为解决许多优化问题提供了新的方向。法理论做简要的综逑,并介绍其在实际问题中的应用,最后对AC0算法仍需要解决的问题和未来的发展方向进行了探讨AC0算法理论【关键词】AC0算法;組合优化;人工蚁群对于蚂蚁这类群居昆虫,其单个蚂蚁的行为极其简单【中图分类号】TP301【文献标识】A但由这些简单的个体组成的蚁群群体却表现出极其复杂的行【文章编号】1671-5969(2007)02-0127-02为,能够完成复杂的任务。蚁群会很快找到蚁穴到食物处的最短路径。此外,蚁群还能够适应环境的变化,当蚁群运动当今科学技术正处于多学科相互交叉和融合的时代。随路线上突然出现障碍物时,蚂蚁能够很快地重新找到最优路着人们认识与改进世界范围的扩大,人们对科学技术提出了径更高更新的要求,单一领城的研究已经无法满足人们改造世仿生学家通过大量的观察研究发现,蚂蚁在寻找食物或界的需求,人类面临的许多复杂课题都需要通过交叉学科研回穴的路径中,会在它们经过的地方留下一些“信息素”,用究才能够得到解决。随着科技和经济的高速发展,人们对高以与群体中的其他蚂蚁进行信息的交流。妈蚁在运动的过程效的优化技术和智能计算的要求日益迫切。中能感知这些物质,并以此来指导自己的运动方向。具体表优化技术是一种以数学为基础,用于求解各种工程问题现在蚂蚁以相对较高的概率选择信息素浓度较高的路径,而优化解的应用技术。作为一个重要的学科分支,一直受到人后到者留下的信息素会对原有的信息素进行加强。这样,蚁们的广泛重视,并在诸多工程领域得到迅速推广和应用,如群的集体行为便表现出一种信息正反馈现象:某一路径上走系统控制、人工智能、模式识别、生产调度、VLSI技术、多过的蚂蚁越多,在该路径上留下的信息素浓度也越高,后来代理机器人之间的任务协调和计算机并行处理等。鉴于实际的蚂蚁选择该路径的概率就越大。蚂蚁个体间就是通过这种工程问题的复杂性、约束性、非线性、建模困难等特点,寻信息的交流达到搜索食物的目的。找一种适合于大规模并行且具有智能特征的优化算法已成为20世纪90年代,意大利学者正是充分利用了蚂蚁搜索食有关学科的一个主要研究目标和引人注目的研究方向。物的过程与著名的旅行商问题之间的相似性,最早提出了蚁目前,除了已得到公认的遗传算法,模拟退火算法、禁群算法。不同的蚁群算法模型的定义虽然在一定程度上受到忌搜索法、人工神经网络等进化算法,近几年提出的蚁群算问题结构化的影响,但就求解组合优化问题而言,所有的蚁法正开始崭露头角,为复杂困难的系统优化问题提供了新的群算法都是以 Macro dorigo针对TSP问题提出的基本蚁群具有竞争力的求解算法,应用范围也开始遍及到许多科学技算法为基础。因此,下面先简要地介绍用于TSP问题求解的术及工程领域蚁群算法。、群集智能为模拟实际蚂蚁的行为,首先引入如下记号,设m是蚁群仿生学是人类一直使用的方法,如模仿海豚皮而构造的中蚂蚁的数量d(=1,2,…,n表示城市和之间的距离,海豚皮游泳衣”模仿人眼视网膜工作原理,制成的生物r()表示在时刻城市和之间的路径上残留的信息量来电子位置传递器”,模拟活细胞生化过程及其调控机制研制模拟实际蚂蚁的信息素浓度。的人工模拟线粒体膜,叶绿体膜的人造能量转换膜等。群居在初始化的时候,m个蚂蚁被放置在不同的城市上,赋予昆虫以集体的力量,进行觅食、御敌、筑巢等。这种群体所每条边上的信息量为r』0,每个蚂蚁k的tbu的第一个元表现出来的“智能”,就称之为群体智能。如蜜蜂采蜜、筑巢、素赋值为它所在的城市。蚂蚁觅食、筑巢等。从群居昆虫相互合作进行工作中,得到用g()表示在时刻蚂蚁k由城市i转移到城市j的概率,启迪,研究其中的原理,以此原理来设计新的求解问题的算则法。这是仿生学的另一重要领域,它是受自然界规律的启迪根据其原理,模仿设计求解问题的算法。如人工神经网络技中国煤化工术、遗传算法、进化规划、模拟退火技术和群集智能技术等。CNMHG(1)AC蚁群优化算法亦属于这一领城,它是近几年发展起来的其中 allowed表示蚂蚁k下一步允许走过的城市的集合127它随蚂蚁k的行进过程而动态改变;信息量r1)随时间的推信息,并且使用这些信息来修改问题的表现形式正如其它蚂移会逐步衰减用l—p表示它的衰减程度;α,B分别表示蚂蚁所看到的那样。蚂蚁既能共同的行动又能独立的工作,显示蚁在运动过程中所积累的信息量及启发式因子在蚂蚁选择路出了一种相互协作的行为,它们之间不使用直接通讯,而使用径中所起的不同作用;n()为由城市转移到城市的期望程信息激素指导着妈蚁间的信息交换。蚂蚁使用一种结构上的度,可根据某种启发算法而定贪婪启发式搜索可行解。根据问题的约束条件列出了一个解经过n个时刻,蚂蚁k走完所有的城市,完成一次循环。此作为经过问题状态的最小代价(最短路径)每只蚂蚁都能够找时,要根据下式对各路径上的信息量作更新:出一个解,但可能是较差解。蚁群中的个体同时建立了很多不(+)=pt1;·A同的解决方案找出高质量的解是群体中的所有个体之间全局性的相互协作的结果。只要我们擅于利用问题与蚁群算法之间的相似性,模拟出人工蚂蚁来帮助解决间题,那么蚁群算法的应用范围将是△rk表示妈蚁k在本次循环中在城市i和城市之间留广阔的下的信息量,其计算方法根据计算模型而定,在最常用的五、AC0算法在组合优化中的应用antcyclesystem模型中ACO蚁群算法主要用于求解不同的组合优化问题,一类t,{QA,若氨运本次环中壁过市和市应用于静态组合优化问题,另一类用于动态组合优化问题。静态问题指一次性给出问题的特征,在解决问题过程中,问题其中Q为常数L为蚂蚁k在本次循环中所走路径的长的特征不再改变。这类问题的范例就是经典旅行商问题度(TSP);动态问题被定义为一些量的函数,这些量的值由隐含系三、AC0算法流程统动态设置。因此,问题在运行时间内是变化的,而优化算法步骤lnc=0(nc为迭代步数或搜索次数);每条边上的须在线适应不断变化的环境。这类问题的典型例子是网络路r小Oc(常数,并且△r0,放置m个蚂蚁到n个城市上由问题步骤2将各妈蚁的初始出发点置于当前解集 tabuk(s)目前,在静态组合优化问题中,蚁群算法主要用于解决中:对每个蚂蚁k(k=1,…,m),按概率p移至下一城市j将城旅行商问题,二次分配问题,车间任务调度问题,车辆路线市j置于tabu,(s)中问题,图着色问题,有序排列问题等。步骤3经过n个时刻,蚂蚁k可走完所有的城市,完成在动态组合优化问题中,主要应用于有向连接的网络路次循环计箅每个蚂蚁走过的总路径长度L,更新找到的最短由和无向连接的网络路由等。研究表明,用蚁群算法研究解路径决包含带宽、延时、延时抖动、包丢失率和最小花费等约束步骤4更新每条边上的信息量rt+n)条件在内的QS组播路由问题,效果优于模拟退火算法及遗步骤5对每一条边置△r:=0,nc=nc+1传算法。步骤6若nc<预定的选代次数 NCMAX,则转步骤2;否另外,蚁群箅法在其他领域也得到了应用,如在解决管则打印出最短路径,终止整个程序。线敷设问题,机构同构判定问题,开关合布线问题等都取得四、人工蚂蚁了令人满意的结果人们利用蚁群优化算法解决实际问题的过程实际上是利六、结语用问题与真实蚂蚁觅食过程的相似性,把问题抽象为真实蚂ACO蚁群算法是一种新的仿生启发式优化算法,刚刚问蚁觅食的过程。这样,人们便抽象出许许多多的“人工蚂蚁”世几年,其理论还十分不完善,存在着搜索时间较长,在算来帮助我们解决实际问题。法模型、收敛性及理论依据方面还有许多工作有待进一步深人工蚂蚁吸收了蚂蚁群体行为的典型特征:一是能觉察研究。但其在解决组合优化问题中的优越性也是显著的小范围区域内状况,并判断出是否有食物或其他同类的信息它具有较强的鲁棒性、通用性、并行搜索等优点素轨迹;二是能释放自己的信息素:三是所遗留的信息素量对ACO算法的研究才刚刚起步,需要解决的问题还有很会随时间而逐步减少多很多,但这是一种用途广泛且高效的算法,值得我们去深蚂蚁算法通过候选解组织群体的进化过程来寻求最优解,人地研究和优化其算法。相信日后会在更多的领域用到“人这一过程包括适应阶段和协作阶段。在适应阶段,各候选解根工蚂蚁”!据积累的信息不断调整自身的结构;在协作阶段各候选解间通过信息交流,以便产生性能更好的解。在蚁群算法中,一个有【参考文献】限规模的人工蚁群体,通过相互协作搜索用于解决优化问題的[1]宋雪梅,蚁群算法及其应用【D].河北理工学院学报较优解。每只蚂蚁根据问题依赖的准则,从被选的初始状态出2006发建立一个可行解或是解的一个组成部分。在建立蚂蚁自己2]李士勇,蚁群优化算法及其应用研究进展[D],哈尔滨工中国煤化工的解决方案中,每只蚂蚁都搜集关于问题拓征和其自身行为的CNMHG-128