一种新的进化算法_蚁群算法_张纪会

　1999年3月系统工程理论与实践第3期　

一种新的进化算法——蚁群算法

张纪会　徐心和

(东北大学控制仿真研究中心,辽宁沈阳110006)a

摘要　介绍一种崭新的求解组合优化问题的方法一人工蚁群算法.该方法通过模拟蚁群搜索食物的

过程,达到求解比较困难的组合优化之目的.该方法的主要特点是:正反馈、分布式计算、与某种启发

式算法相结合.正反馈过程使得该方法能很快发现较好解;分布式计算使得该方法易于并行实现;与

启发式算法相结合,使得该方法易于发现较好解.研究表明该方法是一种基于种群的鲁棒性较强的算

法.

关键词　蚁群系统　模拟进化算法　组合优化

ANewEvolutionaryAlgorithm——AntColonyAlgorithm

ZHANGJihui　XUXinhe

(Control&SimulationCenter,NEU,Shenyang110006)

Abstract　Anewtypeofsimulatedevolutionaryalgorithm,antcolonyalgorithm,isin-

troducedinthispaper,whichisusedtosolvesomeNP-hardcombinatorialoptimization

problemsthroughsimulatingtheprocessofantssearchingforfood.Thisalgorithmhas

severalcharacteristicssuchaspositivefeedback,distributedcomputingandcombination

withcertainheuristics.Positivefeedbackmakesiteasiertofindbettersolutions.Simu-

lationsdemonstratethatitisarobustalgorithmbasedonpopulationandapromising

wayforoptimization.

Keywords　antsystem;simulatedevolutionaryalgorithm;combinatorialoptimization

1　引言

组合优化问题很早就引起了人们的兴趣,但是由于许多组合优化问题都是NP-难的,对于这类问题,至今尚无很好的解决办法.一般采用启发式算法来解决.近年来,随着计算技术的发展,一些新的智能算法(如遗传算法[5]、模拟退火算法[7]、禁忌搜索算法[8])得到了迅速发展和广泛应用.特别是模拟进化算法(GA、GP、ES),无论理论研究还是应用研究都空前活跃,同时,一些新的模拟进化算法也逐渐发展起来.本文介绍的人工蚁群算法就是一种新型的模拟进化算法.该算法是由意大利学者M.Dorigo、V.Maniez-zo、A.Colorini等人首先提出的[1～3],称之为蚁群系统(antcolonysystem),并应用该算法求解TSP问题[1]、分配问题[6]、job-shop调度问题[3],取得了较好的结果.受其影响,蚁群系统模型逐渐引起了其它研究者的注意,D.Costa和A.Hertz[6]在M.Dorigo等人研究成果的基础上,提出了一种求解分配类型问题(assignmenttypeproblem)的一般模型,并用来研究图着色问题.G.Bilchev、I.C.Parmee[4]研究了求解连续空间优化问题的蚁群系统模型.虽然这些成果仅是初步的,但是这些研究已显示出蚁群算法的一些优点.国内目前尚无这方面的研究发表,因此我们在此介绍这种方法的基本原理,希望对有关研究能有所启发.

a收稿日期:1997-10-14

:

第3期一种新的进化算法——蚁群算法852　原理

人工蚁群算法是受到对真实的蚁群行为的研究的启发而提出的.为了说明人工蚁群系统的原理,先从蚁群搜索食物的过程谈起.象蚂蚁、蜜蜂、飞蛾等群居昆虫,虽然单个昆虫的行为极其简单,但由单个简单的个体所组成的群体却表现出极其复杂的行为,原因是什么呢?仿生学家经过大量细致观察研究发现,蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递的.蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且蚂蚁在运动过程中能够感知这种物质,并以此指导自己的运动方向,因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大.蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的.

下面我们引用M.Dorigo所举的例子[1,3]来具体说明蚁群系统的原理.如图1所示,设A是巢穴,E是食物源,HC为一障隘物.由于障随物存在,蚂蚁只能经由H或C由A到达E,或由E到达A,各点之间的距离如图1所示.设每个时间单位有30只蚂蚁由A到达B,有30只蚂蚁由E到达D点,蚂蚁过后留下的激素物质量(以下我们称之为信息)为1.为方便,设该物质停留时间为1.在初始时刻,由于路径BH、BC、DH、DC上均无信息存在,位于B和E的蚂蚁可以随机选择路径.从统计的角度可以认为它们以相同的概率选择BH、BC、DH、DC.经过一个时间单位后,在路径BCD上的信息量是路径BHD上信息量的二倍.t=1时刻,将有20只蚂蚁由B和D到达C,有10只蚂蚁由B和D到达H.随着时间的推移,蚂蚁将会以越来越大的概率选择路径BCD,最终完全选择路径BCD.从而找到由蚁巢到食物源的最短路径.由此可见,蚂蚁个体之间的信息交换是一个正反馈过程

.

3　蚁群系统模型及其实现

我们以求解n个城市的TSP

问题为例说明蚁群系统模型.对于

其它问题,可以对此模型稍作修改

便可应用[6].为模拟实际蚂蚁的行

为,首先引进如下记号:设m是蚁

群中蚂蚁的数量,dij(i,j=1,2,…,

n)表示城市i和城市j之间的距

离,bi(t)表示t时刻位于城市i的蚂蚁的个数,m=图1　蚁群系统示意图6n

bi(t).Sij(t)表示t时刻在ij连线上残留的信息量.

i=1

初始时刻,各条路径上信息量相等,设Sij(0)=C(C为常数).蚂蚁k(k=1,2,…,m)在运动过程中,根据各条路径上的信息量决定转移方向,pkij(t)表示在t时刻蚂蚁k由位置i转移到位置j的概率,

BSAijGij(t)

BSAisGis(t)p=kijs∈allowedkj∈allowedk(1)

otherwise0

其中,allowedk={0,1,…,n-1}-tabuk表示蚂蚁k下一步允许选择的城市.与真实蚁群系统不同,人工蚁群系统具有一定的记忆功能,这里用tabuk(k=1,2,…,m)记录蚂蚁k目前已经走过的城市.随着时间的推移,以前留下的信息逐渐消逝,用参数1-Q表示信息消逝程度,经过n个时刻,蚂蚁完成一次循环,各路径上信息量要根据下式作调整,

Sij(t+n)=QõSij(t)+$Sij

$Sij=(2)(3)m6$Skij

k=1

k$Sijk,.

86系统工程理论与实践

Lk1999年3月$S=kij若第k只蚂蚁在本次循环中经过ij(4)

0否则

其中,Q是常数,Lk表示第k只蚂蚁在本次循环中所走路径的长度.在初始时刻,Sij(0)=C(const),$Sij=0,其中,i,j=0,1,…,n-1.A,B分别表示蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁选择路径中所起的不同作用.Gij表示由城市i转移到城市j的期望程度,可根据某种启发式算法具体确定.根据具体

k算法的不同,S$Sij(t)、ij(t)及pij(t)的表达形式可以不同,要根据具体问题而定.M.Dorigo曾给出三种不同

模型,分别称之为ant-cyclesystem,ant-quantitysystem,ant-densitysystem.参Q、C、A、B、Q可以用实验方法确定其最优组合.停止条件可以用固定循环次数或者当进化趋势不明显时便停止计算.

以上是蚁群系统模型,这是一个递推过程,很容易在计算机上实现,实现过程可以用伪代码表示为:begin

初始化过程:

ncycle:=0;

bestcycle:=0;

Sij:=C;

$Sij=0;

Gij由某种启发式算法确定;

tabuk=Á;

While(notterminationcondition)

{ncycle:=ncycle+1;

for(index=0;index<n;index++)这里,index表示当前已经走过的城市个数;

{for(k=0;k<m;k++)

{以概率pk[tabu[k][index-1]][j]选择城市j;

j∈{0,1,…,n-1}-tabuk中;

}

将刚刚选择的城市j加到tabuk中;

}

计算$Skij(index),Sij(index+n)

确定本次循环中找到的最佳路径

}

输出最佳路径及最佳结果

end

由算法复杂度分析理论可知,该算法复杂度为O(nc.n3),其中,nc表示循环次数.以上是针对求解TSP问题说明蚁群模型的,对该模型稍作修正,便可以应用于其它问题,这一方面已有某些较好结果出现[4,6].4　实验结果与应用

为说明蚁群算法的优点,我们给出应用该算法求解TSP(oliver30)问题的典型实验结果(十次实验取平均值),实验结果见图2～图4.

从该曲线上可以发现,蚁群算法具有快速发现较好解的特点.为便于比较,下面我们给出应用蚁群算

第3期一种新的进化算法——蚁群算法87

图2　最好解进化曲线图　　　　　　　　　　　　　　图3

　最差解进化曲线图

法求解oliver30TSP问题以及用其它算法求解的

结果,见表1¹.从这些实验结果不难看出,蚁群算

法具有较好的性质.

表1　蚁群算法与其它算法的比较算法

蚁群算法

2-opt

spacefillingcurve

random

GA

TS

SA最好解42343746412124700420422

图4　所找到的最优路径5　结　论

蚁群算法具有如下优点:

较强的鲁棒性:本文模型稍加修改,便可以应用于其它问题;

分布式计算:本算法是一种基于种群的进化算法,具有本质并行性,易于并行实现;

易于与其它方法结合:该方法可以与多种启发式算法结合,以改善算法的性能;

该算法的一个缺陷是计算时间较长,随着计算机的发展和计算速度的提高,可以弥补这一缺陷.

蚁群算法的研究刚刚开始,远未象GA、SA等算法那样形成系统的分析方法和坚实的数学基础,有许多问题有待进一步研究.但是目前的研究初步显示出其优势,我们相信,随着研究的深入,该方法必将获得越来越广泛的应用.

参考文献

1　ColorniA,DorigoM,ManiezzoV.Distributedoptimizationbyantcolonies.Proc1stEuropeanconf

artificiallife.Pans,France:Elsevier,1991:134～142

2　ColorniA,DorigoM,ManiezzoV.Aninvestigationofsomepropertiesofanantalgorithm.Proc

PPSN'92:509～520

(下转第109页)

¹

第3期京沪高速铁路一次规划分段建成的多指标综合评价109

参考文献

1　李鹏.建设全国统一的综合交通运输网络体系.中国交通报,1996-12-23

2　京沪高速铁路重大技术经济问题前期研究总报告.四委一部,1992

3　上海铁道大学.高速铁路研究报告(1)、(2),1995

4　张志尧.京沪高速铁路对上海市社会经济影响的研究.上海市科委课题报告,1995

5　沈志云.论兴建京沪高速铁路势在必行.科技导报,1996-11-5

6　华允璋.京沪高速铁路经济合理的方案.科技导报,1996-10-7

7　京沪高速铁路研讨会论文专刊.中国铁路,1996(8)

8　京沪高速铁路研讨会会议纪要,1996

9　姚佐周.再论新建高速铁路并非当务之急.上海交通运输,1995(8):4～5

10　姚佐周.九五兴建京沪高速铁路为时过早.上海交通运输,1996(9):7～8

11　铁道部第四勘探设计院.沪宁高速铁路可行性研究报告,1996

12　SattyTL.TheAnalyticHierarchyProcess.McGrawHill,1978

(上接第87页)

3　ColorniA,DorigoM,ManiezzoV,http://www.77cn.com.cnp.Sci.,1994,34

(1):39～53

4　BilchevGandParmeeIC.Searchingheavilycontraineddesignspaces.Proc22ndintconfCAD-95,

1995,Yelta,Ukraine

5　GoldbergDE.GeneticAlgorithminSearch,OptimizationandMachineLearning.AddisonWesley:Newyork,1989

6　CostaD,HertzAandDubuisO.Imbeddingofasequentialalgorithmwithinanevolutionaryalgorithmforcoloringproblemingraphs.Jofheuristics,1995(1):105～128

7　KirkpatrickS,GelattCDandVechiMP.Optimizationbysimulatedannealing.Science,1983,220:

551～580

8　GloverF.Tabusearch——part1/part2.ORSAJComputing,1989(3):190～206/1990(1):4～32

本文来源：https://www.bwwdw.com/article/azum.html