蚁群优化算法及其应用研究进展

专家论坛

计算机测量与控制.2003.11(12)　ComputerMeasurement&Control　

　

・911・

文章编号:1671-4598(2003)12-0911-03　　　　　　中图分类号:O231　　　　　　文献标识码:A

蚁群优化算法及其应用研究进展

李士勇

(哈尔滨工业大学控制科学与工程系,黑龙江哈尔滨　150001)

摘要:综述了近年来蚁群算法及其在组合优化中的应用研究成果。首先简述了蚁群的觅食行为及蚂蚁的信息系统,其次介绍了人工蚁群算法的基本原理及其主要特点。(TSP)、二次分配问题(QAP)、任务调度问题(JSP)、车辆路线问题(VR()(SOP)及网络由问题等。。

关键词:蚁群算法;蚂蚁系统;nmizationAlgorithmwithApplications

LIShi2yong

(DepartmentofControlScienceandEngineering,HarbinInstituteofTechnology,Harbin　150001,China)Abstract:TherecentresearchresultsofAntColonyAlgorithm(ACA)anditsapplicationsforcombinatorialoptimizationareoverviewed.Atfirstantcoloniesforagingbehaviorandtheircommunicationsystemarebrieflyintroduced.Thenthebasicprincipleandthemaincharacteristicsofartificialantcolonyalgorithmarepresented.ThirdlytheapplicationsofACAforthecombinatorialoptimizationproblemsaredescribed,suchasTSP,QAP,JSP,VRP,GCP,SOPandthenetworksroutingprob2lem.Finallytheproblemstobesolvedandthefutureworksarediscussed.

Keywords:antcolonyalgorithm;antsystem;combinatorialoptimization;meta-heuristicalgorithm

1　引言2　蚂蚁的群体行为及信息系统

随着科学技术的飞速发展,计算机测量与控制系统

的信息化、数字化及智能化的发展趋势锐不可挡。在自动化测试与控制系统中,存在着控制策略、规则、结构以及控制参数的组合优化问题,因此,在计算机自动控制系统中,控制和优化始终是两个重要问题。实际上,使用计算机进行控制和优化本质上都表现为对信息的某种处理。随着研究对象的日益复杂化,其特性表现为非线性、不确定性等,难以建立精确“数学模型”。因此,传统的基于对象精确模型的控制理论与使用确定性的优化算法都遇到了极大的困难。于是人们就从模拟人的智能控制行为得到启示,将人工智能同自动控制理论相结合,创立了智能控制理论;人们从生物进化及仿生学中受到启发,提出许多启发式的智能优化方法。如禁忌算法、神经网络算法、遗传算法、免疫算法及蚁群算法等,它们为解决许多复杂优化问题(NP-困难问题)提供了崭新的途径。

文章就蚁群优化算法的基本原理及其应用研究进展加以综述,旨在为进一步推动这一领域的理论与应用研究。

收稿日期:2003-07-31。

基金项目:哈尔滨工业大学跨学科交叉性研究基金资助项目

(HIT.MD2001.02)

蚂蚁是最古老的社会昆虫之一,它的个体结构和行为

虽简单,但由这些简单个体构成的蚂蚁群体,却表现出高度结构化的社会组织。蚂蚁王国俨然是一个小小“社会”。这里,有专司产卵的后蚁;有为数众多的从事觅食打猎、兴建屋穴、抚育后代的工蚁;有负责守卫门户、对敌作战的兵蚁;还有专备后蚁招婿纳赘的雄蚁等等。

蚂蚁是社会性昆虫,组成社会的三要素之一就是社会成员除有组织、有分工之外,还有相互的通讯和信息传递。研究表明,蚁群有着奇妙的信息系统。其中包括视觉信号、声音通讯和更为独特的无声语言,即包括化学物质不同的组合、触角信号和身体动作在内的多个征集系统,来策动其它个体。蚂蚁特有的控制自身环境的能力,是在高级形式的社会性行为及不断进化过程中获得的[1-2]。

觅食行为是蚁群一个重要而有趣的行为。据昆虫学家的观察和研究,发现蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径,并且能随环境变化适应性地搜索新的路径,产生新的选择。虽然单个蚂蚁的行为极其简单,但由大量的蚂蚁个体组成蚂蚁群体却表现出极其复杂的行为,能够完成复杂的任务。

生物学家和仿生学家经过大量的细致观察研究发现,蚂蚁在觅食走过的路径上释放一种蚂蚁特有的分泌物——信息激素(Pheromone)。蚂蚁个体之间正是通过

作者简介:李士勇(1943-),男,黑龙江省哈尔滨市人,教授,博士生导师,主要从事智能优化方法、智能控制系统的理论与应用研究。

　・912・计算机测量与控制　第11卷

这种信息激素进行信息传递,从而能相互协作,完成复杂任务。在一定范围内蚂蚁能够察觉到这种信息激素并指导它的行为,当一些路径通过的蚂蚁越多,则留下的信息激素轨迹(trail)也就越多,招致后来更多的蚂蚁选择该路径的概率也越高,于是越发增加了该路径的信息素强度。这种选择过程称之为蚂蚁的自催化过程,形成一种正反馈机制,可理解为增强型学习系统,蚂蚁最终可以发现最短路径。3　人工蚁群优化算法原理

411　ACA在静态组合优化中的应用

(1)旅行商问题(TSP):蚁群优化算法首先应用于

一个测试问题就是旅行商问题。TPS问题是组合优化中研究最多的NP—hard问题之一,该问题就是寻找通过n个城市,各1次且最后回到原出发城市的最短路径。许多研究表明,应用蚁群优化算法求解TSP问题优于模拟退火法、遗传算法、神经网络算法、禁忌算法等多种优化方法[5-6]。

(2)(:二次分配问题是指分配n,其中代。QAP是继TSP,实际上,QAP是一般化的TSP[3,7]。

(3)车间任务调度问题(JSP):JSP问题指已知一组

M台机器和一组T个任务,任务由一组指定的将在这些

人工蚁群算法是模拟真实蚁群觅食过程寻求最短路径的原理,由意大利学者M.Dorigo[3,4]题(TSP)(,经过改进后称为蚂蚁算法,或称蚁群算法。

蚁群算法吸收了蚂蚁群体行为的典型特征:一是能察觉小范围区域内状况,并判断出是否有食物或其他同类的信息素轨迹;二是能释放自己的信息素;三是所遗留的信息素数量会随时间而逐步减少。

蚂蚁算法通过侯选解组织群体的进化过程来寻求最优解,这一过程包括适应阶段和协作阶段。在适应阶段,各侯选解根据积累的信息不断调整自身的结构;在协作阶段各侯选解间通过信息交流,以便产生性能更好的解。在蚁群算法中,一个有限规模的人工蚁群体,通过相互协作搜索用于解决优化问题的较优解。每只蚂蚁根据问题依赖的准则,从被选的初始状态出发建立一个可行解或是解的一个组成部分。在建立蚂蚁自己的解决方案中,每只蚂蚁都搜集关于问题拓征和其自身行为的信息,并且使用这些信息来修改问题的表现形式,正如其它蚂蚁所看到的那样。蚂蚁既能共同的行动又能独立的工作,显示出了一种相互协作的行为,它们之间不使用直接通讯,而使用信息激素指导着蚂蚁间的信息交换。蚂蚁使用一种结构上的贪婪启发式搜索可行解。根据问题的约束条件列出了一个解,作为经过问题状态的最小代价(最短路径)。每只蚂蚁都能够找出一个解,但可能是较差解。蚁群中的个体同时建立了很多不同的解决方案,找出高质量的解是群体中的所有个体之间全局性的相互协作的结果。有关蚁群算法的具体实现可参阅有关文献。4　蚁群算法在组合优化中的应用

机器上执行的操作序列组成。车间任务调度问题就是给机器分配操作和时间间隔,从而使所有操作完成的时间最短,并且规定两个工作不能在同一时间在同一台机器上进行。Colorni,Dorigo等人将蚂蚁算法应用于车间任务调度问题[8]。

混流装配线问题:混流装配线是JIT生产方式的具体应用之一,它可以在不增加产品库存条件下满足用户多样化的需求。混流装配线有时也特指混合车型组装线,即在一定时间内,在一条生产线上根据顾客需求的变化生产出各种不同型号的产品,这一类问题同属生产调度问题。文献[9]研究用蚁群算法解决混流装配线调度问题。

(4)车辆路线问题(VRP):VRP问题来源于交通运

输。已知M辆车,每辆车的容量为D,目的是找出最佳行车路线在满足某些约束条件下使得运输成本最小。文献[10-12]利用蚁群算法研究VRP结果表明,该方法优于模拟退火和神经网络,稍逊于禁忌算法。

(5)图着色问题(GCP):已知一个图G=(N,E),G的一个q个颜色的着色是一个映射C:N→{1,…,q}使得如果(i,j)∈E,则C(i)≠C(j)。GCP就是找出图G的一种着色从而使得所使用的颜色数量q最小。Costa和Heits提出使用两条外激素轨迹解决图着色问题[13]。

(6)有序排列问题(SOP):给定一个有向图,图上的弧和节点都加了权,服从于节点间先后次序的约束,SOP指在有向图上找出一个最选权值的哈密顿路径。SOP

蚁群算法主要用于求解不同的组合优化问题,一类应用于静态组合优化问题,另一类用于动态组合优化问题。静态问题指一次性给出问题的特征,在解决问题过程中,问题的特征不再改变。这类问题的范例就是经典旅行商问题(TSP);动态问题被定义为一些量的函数,这些量的值由隐含系统动态设置。因此,问题在运行时间内是变化的,而优化算法须在线适应不断变化的环境。这类问题的典型例子是网络路由问题。

是NP难题,它以许多工程实际问题为模型,如有着接载和运送乘客约束的单车选路径问题,生产计划以及柔性制造系统中的运输问题等。Gambardella和Dorigo应用扩展的蚂蚁算法解决SOP,结果非常理想[14]。412　ACA在动态组合优化中的应用

在动态组合优化问题中,通讯网络是一个典型例子。网络优化问题有一些特征,如信息和计算分布,非

第12期李士勇:蚁群优化算法及其应用研究进展・913・　

静态随机动态,以及不同时的网络状态更新等。路由是网络控制中最关键的组件之一,它涉及到建立和使用路由表来指导数据通信量在网络范围内的分配活动。普通路由问题可以理解为是要建立一个路由表使得网络性能的一些量度最大化。

(1)有向连接的网络路由:在有向连接的网络中,同一个话路的所有数据包沿着一条共同的路径传输,这条路径由一个初步设置状态选出[15]。在国际上Schoonder2werd等人首先将ACO算法应用于路由问题。后来,White等人将ACO算法用于单对单点和单对多点的有

可用蚁群算法解决[24]。

(4)学习模糊规则问题:从组成系统模糊语言规则的数据中自动地学习问题,实际上是一个组合优化问题。J.Casil2

[25]

las等人研究利用蚂蚁优化算法学习模糊规则。5　结束语

向连接网络中路由[16],Bonabeau态规则机制改善ACO算法[17]效果最好的路由[18]、刘泽民等人提出了基于蚂蚁算法的QoS路由调度方法及分段QoS路由调度方法[19,20]。

(2)无连接网络系统路由:在无连接或数据包中,同一话路的网络系统数据包,可以沿着不同的路径传输,在沿着信道从源节点到终节点的每一个中间结点上,一个具体决策是由局部路由组件做出。

随着Internet规模不断扩大,在网络上导入QoS技术,以确保实时业务的通信质量。QoS组播路由的目的是在分布的网络中寻找最优路径,要求从源节点出发,历经所有的目的节点,并且在满足所有的约束条件下,达到花费最小或达到特定的服务水平。在分析路由问题时,为方便可将网络看成无向带权的连通图,顾军华等人用蚂蚁算法研究解决包含带宽、延时、延时抖动、包丢失率和最小花费等约束条件在内的QoS组播路由问题,效果优于模拟退火算法及遗传算法[21]。413　ACA在其他领域的应用

(1)管线敷设问题:电缆敷设问题与TSP问题类似。

蚁群算法作为一种新的仿生启发式优化算法,虽然

刚问世几年,但它在解决许多复杂组合优化问题方面,显示出了明显的优势。

。,环境的改变影。蚂蚁个体之间、群体之间以及与环境之间的相互作用、相互影响、相互协作,可以完成的复杂的任务,这种适应性表现为蚁群算法的鲁棒性。

自组织使得蚂蚁群体的行为趋向结构化,其原因在于包含了一个正反馈的过程。这个过程利用了全局信息作为反馈,正反馈使系统演化过程中较优解的自增强作用,使得问题的解向着全局最优化的方向不断变化,最终能有效地获得相对较优解。蚂蚁系统的另一个重要特征是分布式计算,这种分布式计算方法保证了算法在全局的多点同时进行解的并行搜索,有效地避免了陷入局部最优解。

虽然蚁群算法具有较强的鲁棒性、通用性、并行搜索等优点,但也存在着搜索时间较长,在算法模型、收敛性及理论依据等方面还有许多工作有待进一步深入研究。此外,将蚁群算法与遗传算法、免疫算法等优化方法相结合,也是改善和提高蚁群算法性能的有效途径。随着蚁群算法研究的深入,它将获得更加广泛的应用。

参考文献:

[1]杨沛.

蚁群社会生物学及多样性[J].昆虫知识,1999,36

昆虫知识,2001,38

要求每一根电缆在从电缆连接起点设备开始,通过不同

的通道、竖井至电缆连接终端,连接起来的电缆所经路径最合理且总长度最短。鉴于整个电厂电缆路径所形成的网络相互交叉,敷设系统纷繁复杂,为此将互相独立又相关的树分解一个个小的蚁群系统,用于解决发电厂计算机电缆敷设系统的复杂性等问题,获得了比较理想的结果。

(2)机构同构判定问题:在机械设计领域普遍存在的机构同构判定问题,将该类问题转化为求解其邻接矩阵的特征编码值的问题,利用蚂蚁群算法对NP完全问题所具有的抵御组合爆炸的能力进行求解,在参数选择合适的情况下,取得了令人满意的结果[23]。

(3)开关合布线问题:开关盒SB是一个M×Q的纵横网络,各线网的引脚分布在此网络的上、下、左、右方,顺着网络中走线,以形成对应于各线网且互不连通的N个树形的树支,可分布在SB的上、下两层,其间借过孔连接,这类问题的约束条件多,也是NP完全问题,

[22]

(4):243-247.

[2]杨沛,古德祥.蚁群的信息系统[J].

(1):23-25.

[3]DORIGOM,CAROGD,GAMBARDELLALM.Antalgo2

rithmsfordiscreteoptimization[J].ArtificialLife,1999,5(3):137-172.

[4]DORIGOM,BONABEAUE,THERAULAZG.Antalgorithms

andstigmergy[J].FutureGenerationComputerSystem,2000,16(6):851-871.

[5]马良,项培军.蚂蚁算法在组合优化中的应用[J].管理科学

学报,2001,4(2):32-36.

[6]陈永强.

人工蚁群算法及其在组合优化中的应用[D].哈尔

滨:哈尔滨工业大学,2003.

[7]STüTZLET,DORIGOM.ACOalgorithmsforthequadratic

assignmentproblem[A].Hill,1999.

InD.Corne,M.Dorigo,andF.

Glover,editors,NewMethodsinOptimization[C].McGraw-

(下转第917页)

第12期赵广社:数据挖掘中的统计方法概述・917・　

函数的二次规划问题,可以正,对ai存在唯一解,其中ai≠0,所对应的样本就是支持向量。3　结论

的评估,在结论的合理运用中用到大量的统计。

参考文献:

[1]HANJW.KAMBERM.

数据挖掘:概念与技术[M].范

明,孟小峰,译.北京:机械工业出版社,2001.

从统计学发展而来的方法与从机器学习中发展而来

的方法同样重要。可以把统计方法看作是数据分析的参数方法,这也就暗含了可以获得或收集到正确的函数类型,参数数目以及参数可能的值。在统计学里,需要对数据彻底地了解来获得正确(参数化)的模型。而机器学习能自动的产生和证实拟合数据的模型,不用预先定义模型。但是在实际运用中,可以互相补充,:

(1);

(2)用和挖掘不确定性而不是隐藏它;

(3)证实搜索误差即诚信度和模型均值的好处;(4)不会混淆带干涉的条件,即不要将假设检验的误差概率误认为搜索过程的误差概率。在理解搜索结构中很少用到统计,但在搜索过程中的评估,在搜索结论

[2]陆汝钤.世纪之交的知识工程与知识科学[M].北京:清华

大学出版社,2001.

[3]WANGXZ.Dataminingandknowledgediscoveryforprocess

monitoringandcontrol[M].Springer-VerlagLondon,1999.[4]于秀林,任雪松.[M].北京:中国统计出版

社,.

[5[M].北京:科学出版

[GELSR.Component-baseduserguidanceinknowledge

discoveryanddatamining[M].SanktAugustin:infix,1999.[7]边肇祺,张学工.模式识别[M].北京:清华大学出版社,1999.[8]GLYMOURC,MADI.StatisticalNGAND,PREGIBOND,etal

inferenceanddatamining[J].CommunicationsoftheACM,1996,39:35-41.

[9]FAYYADU,SHAPIROGP,SMYTHP.Fromdatamining

toknowledgediscoveryindatabases[M].AAAI,1997.[10]罗晓沛.数据挖掘在科学数据库中的应用探索[C].中国科

技大学,2002.

(上接第913页)

[8]COLORNIA,DORIGOM,etal.Antsystemforjob-shop

scheduling[J].BelgianJournalofOperationsResearch,Statis2

ticsandComputerScience(JORBEL),1994,34:39-53.[9]孙新宇,万筱宁,孙林岩.蚁群算法在混流装配线调度问题中

enceonParallelandDistributedProcessingTechniquesandApplications[C].CSREAPress,1998:802-809.[17]BONABEAUE,etal.Routingintelecommunicationnetworks

with“Smart”ant-likeagentstelecommunicationapplications[A].InProceedings.ofIATA’98SecondInt.WorkShoponIntelligentAgentsforTelecommunicationApplications[C]..SpringerVerlag,1998:1437.LecturesNotesinAIvol

[18]DICAROG,DORIGOM.ExtendingAntNetforbest-effort

Quality-of-Servicerouting[A].Proc.ANTS’98-FirstIn2ternationalWorkshoponAntColonyOptimization[C].Brus2sels,Belgium,1998:15-16.

[19]张素兵,吕国英,刘泽民,周正.基于蚂蚁算法的QoS路由

的应用[J].信息与控制,2002,31(6):486-490.[10]侯立文,蒋馥.一种基于蚂蚁算法的交通分配方法及其应用

[J].

上海交通大学学报,2001,35(6):930-933.

[11]BULLNHEI.AniMERB,etalmprovedantsystemalgorithm

forthevehicleroutingproblem[R].TechnicalReportPOM-10