多目标旅行售货员问题的蚂蚁算法求解

系统工程理论方法应用

SYSTEMSENGINEERING-THEORYMETHODOLOGYAPPLICATIONSVol.8No.4

1999　

多目标旅行售货员问题的蚂蚁算法求解

马　良　蒋　馥(上海交通大学系统工程研究所,上海200052)3

【摘要】本文将近几年出现于优化领域的一种新的搜索策略——蚂蚁算法推广到多目标情形,并以旅行售货员问题为例,通过大量数据测试和验证,获得了较好的效果。

关键词　蚂蚁算法　多目标　旅行售货员1　引　言

蚂蚁算法(AntAlgorithm)是近几年问世并逐步引起重视的一种新的仿生类算法[1～5],已陆续应用于一些不同的学科领域。作为通用型随机优化方法,它吸收了昆虫王国中蚂蚁的行为特性,有时也称作蚂蚁系统(AntSystem)。生物世界中的蚂蚁在搜索食物源时,能在其走过的路径上释放一种信息激素(Pheromone),使得一定范围内的其他蚂蚁能够察觉到并影响其行为。当某些路径上通过的蚂蚁越多时,留下的信息素轨迹(Trail)也越多,以致信息素强度增大,后来的蚂蚁选择该路径的概率也越高,从而可增加该路径的信息素强度,这种选择过程被称为蚂蚁的自催化行为(AutocatalyticBehavior)。

旅行售货员问题(TravellingSalesmanProblem,TSP)是优化领域中一个著名的经典难题,迄今尚未彻底解决,现已被归入NP-完备的问题类。其一般提法为:有一货物推销员欲往若干个城市推销货物,从城市1出发,经其余各城市至少一次,然后回到城市1,问选择怎样的行走路线,才能使总行程最短(各城市间距离为已知)。由于该问题在许多实际领域中有着广泛的应用,因而寻找其有效的算法就显得颇为重要。然而,这种可能性到目前为止仍属未知。虽说也有一些指数级的算法可进行精确地求解,如分支定界法、割平面法等,但随着它们在大规模问题上的失效(组合爆炸),人们不得不转向近似算法或启发式算法。Dorigo等提出蚂蚁算法时,首先用TSP进行了测试。求解开始时,蚂蚁群各自随机行动,以后则按概率选择留有信息素轨迹的尚未走过的路径,直至完成一次搜索,即构成一个解。因此,蚂蚁群成功地搜索一轮所形成的是一组解,然后记录其中的最好解,各蚂蚁所遗下的信息素轨迹也将按持久程度保留到以后各轮搜索,从而产生特有的生物行为影响。

2　模　型

多目标旅行售货员问题是经典TSP的扩展和延伸[6,7],若给定图G的各边弧上有L个权值,则使得回路上相应的L个目标值都尽可能小的解就称为这个多目标TSP的(Pareto)有效解。如实际问题中常常需要考虑:路程最短、时间最少、费用最省、风险最小等多方面的

　　本文于1998年3月11日收到,修改稿于1999年7月19日收到

3

上海市高等学校青年科学基金资助项目(98QN28)

—24—系统工程理论方法应用1999年第4期

因素。由于多目标意义下的解是一种“折衷解”、“非劣解”,因此,多目标TSP解的含义可定义如下:

假定有一回路解H,若不存在任何其他回路解Q,使得Zr(Q)≤Zr(H),r=1,2,…,L,其中至少有一个不等式严格成立(Zr为相应的目标函数值),则H为一个非劣解或Pareto解。

记G=(V,E)为赋权图,V={1,2,…,n}为顶点集,E为边集,各顶点间的权值为dirj

r

(dirV,r=1,2,…,L),并设j>0,dii=+∞),i,j∈

xij=1　　　边(i,j)在解回路上0　　　其他

1

于是,多目标TSP的数学模型可写成:

　　　　minZ=　　　　minZ=　　　　

󰁰

∑

∑

i≠j

dijxijdijxij

2

i≠j

　　　　minZ=

　s.t.

∑　　∑∑∑

i≠j

dijxij

L

i≠j

xij=1　　　　　　　j∈Vxij=1　　　　　　　i∈V

j≠i

i,j

∈Sxij≤󰃜S󰃜-1　　对任何V的真子集S

i,j∈V

xij∈{0,1}　　　　　　　

其中,󰃜S󰃜为集合S中所含图G的顶点个数。前两个约束意味着对每个顶点而言,仅有一条边进和一条边出。第三个约束则保证了没有任何子回路解的产生。当dij=dji(i,j∈V)时,被称为对称问题。当对所有i,j,k∈V,有不等式dij+djk≥dik成立时,问题被称为是满足三角形不等式的,简写成∃TSP。三角形不等式在很多情况下是自动满足的,它是TSP中的一种主要类型。个别不满足的,也可进行等价转换。

3　算　法

在给出多目标TSP的蚂蚁算法之前,先对有关的变量和常数说明如下:m为蚂蚁个数;

r

Γij为边弧(i,j)在多目标意义下的能见度(visibility),即1󰃗dij,r=1,2,…,L(按概率选取,可体现优先级);Pikj(t)为蚂蚁k的转移概率,定义为

Pij(t)=

k

∑

[Σij(t)]Α[Γij]Β

　　　j∈UΑΒ

()[Σt]󰃖[Γ]iikkk∈U

0　　　　　　　　　　　　其他

其中:U为可行顶点集;Σij(t)为边弧(i,j)在t时刻的轨迹强度(intensity);∃Σikj为蚂蚁k在相邻时刻中于边弧(i,j)上留下的单位长度迹信息素量,按∃Σikj的不同取法,可形成不同类型的蚂蚁算法:

1999多目标旅行售货员问题的蚂蚁算法求解—25—

　　(1)　∃Σ=

kij

Z　　　(i,j)在解路径上(Z∑Q󰃗

r

rk

rk为目标函数值)

(2)　∃Σikj=(3)　∃Σikj=

0　　　　　　其他

Q　　　　　　(i,j)在解路径上0　　　　　　其他

d　　　(i,j)在解路径上∑Q󰃗

r

rij

0　　　　　　其他

上述三种情形可分别称为多目标的蚂蚁圈(Ant2蚂蚁密度(Ant2Cycle)模型、Density)模型和蚂蚁数量(Ant2Quantity)模型。

算法中所用到的参数有:Α为迹的相对重要性(Α≥0);Β为能见度的相对重要性(Β≥0);p为迹的持久性(0≤p<1),可将1-p理解为迹衰减度(evaporation);Q为体现蚂蚁所留迹数量的一个常数。

从而,可将多目标TSP的蚂蚁算法步骤按伪码形式叙述如下:

Begin

计算各蚂蚁的L个目标函数值;记录当前的非劣解;

fork←1tomdobegin

　初始化:

t←0(t时刻变量)

nc←0(nc为迭代步数或搜索次数)

对各边弧(i,j):

　　置Σij←常数c(较小的正数);　　置△Σi,j←0;

将m个蚂蚁置于n个顶点上;

Loop:

　对各边弧(i,j),计算　∃Σij←∃Σij+∃Σikj;　end

　对各边弧(i,j),计算

　Σij(t+n)←Θ・Σij(t)+∃Σij;　(其中,Σmin≤Σij≤Σmax)置t←t+n;

对各边弧(i,j),置∃Σij←0;

nc←nc+1;

　将所有蚂蚁的初始出发点置于当前解集中;

　fork←1tomdo　begin

按概率P(t)选择顶点j;移动蚂蚁k至顶点j;将顶点j置于当前解集;

end

kij

若nc<预定的迭代次数且无退化行为(即找到的都是相同解),则gotoLoop;输出目前的非劣解;

End

(1-Θ)Zopt;Σ其中:算法中的Σ5。max取为1󰃗min取为Σmax󰃗

如果忽略目标个数L(一般不会很大),则算法的复杂度为O(nc・m・n2)。Dorigo等对经典的TSP求解所得到的经验结果表明,当m大致等于n时,效果最佳,此时的时间复杂度为O(nc・n3)。算法对距离的对称性以及目标函数无特殊要求,因此可用于各种非对称性问

题和非线性问题。

上述求解多目标TSP的蚂蚁算法用Delphi4.0实现,在PC系列机的Windows98环境下运行通过。

—26—系统工程理论方法应用1999年第4期

4　实　例

下面用一个简单例子来说明算法的使用情况以及与其他算法的比较[7]。例　已知n=6,L=2,权矩阵分别为

∞817255813

81

72

55448781977

340212593

,　D2=

D1=

∞33∞44940

877721

∞8214144347

8214147629

432931

4747516728

∞6161∞762947

293151

∞6767∞2593

∞∞7878∞6728

∞　　对该算例,分别运行算法的三种形式,其中,Q=1～1000,最大迭代次数=100,运行于

350系列微机上,得到的非劣解以及与边交换法(2-opt)、模拟退火法(SA)PENTIUM󰂫󰃗的比较结果如表1所示(各运行10轮)。

表1

Ant2cycle(158,280)(250,208)

Ant2density(158,280)(250,208)

Ant2quantity(158,280)(208,276)

SA(209,248)(158,280)(250,208)

22opt(158,280)

　　注:Α、=0.5～0.9。Β=1,2,3,Θ

参数的不同组合,将对算法的效果产生一定的影响。由于对多目标TSP而言,Α和Β过大将可能产生不合理结果,因此,比较理想的区间是在0～3,不仅可保证结果的合理性,还可加快算法的运行速度。此外,对求多目标问题的非劣解而言,迭代次数也不用像解单目标

问题那样定得很大。通过上述例子以及其他许多随机数值问题的求解(试验规模算到n=150),并与边交换法和模拟退火法进行比较,可以发现,本文的多目标TSP蚂蚁算法所得结

果明显优于边交换法,与模拟退火法则不相伯仲,但随着问题规模的增大,在运行效率上要好于后者。

5　结束语

蚂蚁算法是一种来自大自然的随机搜索寻优方法,是生物界的群体启发式行为,现已陆续应用到组合优化、人工智能、通讯等多个领域。蚂蚁算法的正反馈性和协同性使其可用于分布式系统,隐含的并行性更使之具有极强的发展潜力。从数值模拟结果来看,它比目前风行一时的遗传算法、模拟退火法等有更好的适应性。将该方法用于多目标优化问题是一种新的尝试,更多的工作尚有待于进一步展开。为使算法运行更为稳定,目前,我们在上述算法中进一步加入了局部搜索机制,经初步解算,不仅效果明显,收敛速度也大为提高。限于篇幅,有关结果不一一公布。总之,作为一种带有构造性特征的搜索方法,蚂蚁算法的应用前景和影响将是十分广阔和深远的。

1999多目标旅行售货员问题的蚂蚁算法求解—27—

参考文献

[1]　ColorniA,DorigoM,ManiezzoV.DistributedOptimizationbyAntColonies.ProcofECAL912EuropeanConfer2

～142.enceonArtificialLife.Paris,France:Elsevier,1991,134

[2]　ColorniA,DorigoM,ManiezzoV.AnIvestigationofSomePropertiesofanAntAlgorithmProcoftheParallel

～520.ProblemSolvingfromNatureConference(PPSN92).Brussels,Belgium:Elsevier,1992,509[3]　DorigoM,ManiezzoV,ColorniA.AntSystem:OptimizationbyaColonyofCooperatingAgents.IEEETranson

～41.Sys,ManandCyber.-PartB,1996,26(1):29[4]　DorigoM,GambardellaLM.AntColonySystem:ACooperativeLearningApproachtotheTravellingSalesman

～66.Problem.IEEETransonEvolutionaryComputation,1997,1(1):53

[5]　StutzleT,HoosH.TheMAX2MINAntSystemandLocalSearchfortheTravellingSalesmanProblem.Procof

～313.ICEC’97-1997IEEE4thIntConfonEvolutionaryComputation.IEEEPress,1997,308

[6]　TungCT.AMulticriteriaPareto2OptimalAlgorithmfortheTravellingSalesmanProblem.Asia2PacificJournalof

～115.OperationalResearch,1994,11(1):103

[7]　马　良.多准则货郎问题及其算法.运筹学的理论与应用.西安:西安电子科技大学出版社,1996.187～192.

SolvingMulti-CriteriaTravellingSalesmanProblem

byAntAlgorithm

MaLing,　JiangFu

(InstituteofSystemsEngineering,ShanghaiJiaotongUniversity,200052)

【Abstract】Thispaperextendstherecentlydevelopednewsearchingstrategyinoptimza2tionarea-antalgorithm,tothemulticriteriasituation.Byusingtravellingsalesmanprob2lemasanexample,seriesoftestsareimplementedwhichgivepromisingresults.Keywords:antalgorithm　multicriteria　travellingsalesman