第26卷 第6期

文章编号:1006-9348(2009)06-0200-04

计 算 机 仿 真

2009年6月

蚁群优化算法应用研究概述

杨 檬,宋建社,曹继平,朱 昱

(西安高技术研究所,陕西西安710025)

摘要:为了对蚁群算法近年来的应用研究情况进行总结,为后续的研究提供参考,综述了蚁群算法近年来的应用研究成果。在介绍蚁群算法基本特点的基础上,首先介绍了蚁群算法的一般模型,其次概述了蚁群算法近年来的研究进展与算法在各个领域的应用情况,最后指出了仍未解决的问题和当前的研究热点。蚁群系统所具有的分布式组织模型对解决复杂组合优化问题、分布控制问题提供了很好的思路,对蚁群系统行为及其自组织能力的研究具有积极意义。关键词:蚂蚁系统;蚁群系统;应用;综述中图分类号:TP118 文献标识码:A

ASurveyofModeling,AlgorithmsandApplications

ofAntColonyOptimization

YANGMeng,SONGJian-she,CAOJi-ping,ZHUYu

(Xi anInst.ofHigh-tech,Xi anShanxi710025,China)

ABSTRACT:InordertosummarizerecentapplicationsandresearchofAntColonyOptimization(ACO),andtoprovidereferenceforfuturestudy,achievementgainedinthelastdecadeisintroduced.Onthebasisofintroducing

thebasiccharacteristicsofthealgorithm,thegeneralmodelisfirstlyputforward.Thenrecentresearchachievementandapplicationsinvariousfieldsaregiven.Atlast,unsolvedproblemsandcurrenthottopicsarediscussed.Studyonantcoloniesbehaviorandtheirself-organizingcapacitieshasbeeninterestingformanyresearchersasitprovidesmodelsofdistributedorganization,whichareusefultosolvedifficultcombinatorialoptimizationproblemsanddistrib utedcontrolproblems.Deepresearchofthealgorithmisofpromisingsignificance.KEYWORDS:Antsystem;Antcolonysystem;Application;Survey

文献,本文针对蚁群优化(ACO)一般模型、研究进展、应用和

1 引言

蚁群算法(AntColonyAlgorithm,ACA)是一种源于生物世界的仿生类随机搜索算法,自意大利学者MDorigo,V

Maniezzo,AColorni等人在20世纪90年代初提出以来[1],其在不同的组合优化问题中得到长足的发展并取得了良好的效果。蚁群算法优化过程的本质在于: 选择机制。信息量越大的路径,被选择的概率越大; 更新机制。路径上面的信息量会随蚂蚁的经过而增长,同时也随着时间的推移逐渐减小;!协调机制。蚂蚁之间实际上是通过信息量来互相通信、协同工作的。这样的机制使得蚁群算法具有很强的发现较好解的能力。近年来研究蚁群算法的文献很多,对算法模型、性能、应用等方面取得了很多成果。为了对近年来的研究情况进行总结,为后续研究者提供参考,根据作者掌握的

基金项目:国家自然科学基金重点资助项目(69931040)收稿日期:2007-12-26 修回日期:2008-05-06

研究方向等情况进行综述。

2 蚁群算法的一般模型

考虑组合优化问题P=(S, ,f),其中S为问题的候选解集,定义在有限个离散决策变量Xi(i=1, ,n)之上;Xi取值依赖于Di=

|Di|

v1;对应S中每个候选s,有目标函i, ,vi

数f(s)与之对应f:S#R+0; 为问题的约束集合;如果对于 s S,有f(s*)%f(s),则称s* S为全局最优解。

上述模型用于定义ACO的信息素模型,信息素 ij的值与每个可能的解cij有关,Xi=vji,C为cij的集合。人工蚂蚁通过遍历完全连接的结构图GC(V,E)来求解,其中,V是点的集合,E是边的集合,最优的结构图可以从解元素的集合C中得到,可以用点或者边表示。蚂蚁在点之间移动,建立局部解(partialsolution),并在点或者边上留下信息素,而留下的信息素 与求得的解质量有关。后续蚂蚁根据这些信息

&&