о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999ꡡ3610ڡVol.36No.101999



бȺ㷨
顡żͻᡡĺ
ժҪȺ㷨һ͵ģ㷨оѾ㷨ʣ㷨ҲһЩȱ㣬ʱϳ.Ϊ˿˷һȱ㣬иһµȺ㷨бȺ㷨.ڻȺ㷨ƣ2-Чص㣬ʹø÷нϿٶȣʡʱ.÷֮Ч.
ؼʡȺϵͳ, ģ㷨, 
ͼšTP301.6
AN ANT COLONY ALGORITHM WITH MUTATION FEATURES
WU Qing-Hong, ZHANG Ji-Hui, and XU Xin-He
(Control & Simulation Center, Northeast University, Shenyang 110006)
AbstractAnt colony algorithm is a novel simulated evolutionary algorithm which shows many promising characters, but it also has some shortcomings such as needing longer computing time etc.. In order to overcome this defect, a new ant colony algorithm, an ant colony algorithm with mutation features, is proposed in the paper here. Because of the introduction of mutation mechanism which makes full use of strength of 2-exchange method, it can quicken the convergence rate and decrease computing time. Computing simulation examples show its validity.
Key wordsant colony system, mutation mechanism, simulated evolutionary algorithm
1
50ڴ˷ѧǴĻܵԽŻ·Ŵ㷨滮Եȣ1ݣɹӦʵ2.Ⱥ㷨(ant colony algorithmACA)һ͵ģ㷨ѧM. DorigoV. ManiezzoA. Colorniģ35ݣǳ֮ΪȺϵͳ(ant colony system),ø÷TSP5ݡ3ݡjob-shop5,ȡһϵнϺõʵ.Ӱ죬Ⱥϵͳģоߵע⣬ø㷨һЩʵ6.ȻԴ˷оո𲽣ЩоʾȺ㷨⸴Ż(رɢŻ)һЩԽԣ֤һֺзչǰķ.ĶԸ÷һЩо.֯ṹ£ȼҪһȺ㷨ԭĵ3ֽȺ㷨ģͼʵ֣Ȼʵ˵Ⱥ㷨ŵ벻㼰Ľʵ֤ǸȺ㷨Ч.
2Ⱥ㷨ԭ
˹Ⱥ㷨ܵǶȻʵȺΪоɹһֻȺģ㷨㷨ѧM. Dorigo3.M. Dorigo״÷ʱȺʳĹ(TSP)֮ԣͨ˹ģʳĹ(֮ͨϢ໥ЭҵѨʳԴ·)TSP⣬ΪʵȺϵͳǳ㷨Ϊ˹Ⱥ㷨.Ϊ˵˹ȺϵͳԭȼҪһʳľ.
Ⱥ棬ȻûӾȴҵϳʳԴ·ԭʲôأȻϵΪ򵥣ĵ򵥵ĸɵȺȺȴֳ临ӵΪܹɸӵ񣬲ˣϻܹӦı仯:Ⱥ˶·ͻȻϰʱܹܿҵ·ȺЩ?Щ⣬ͼѧҺͷѧҵǿȤѧҾϸ¹۲о֣ϸ֮ͨһֳ֮Ϊ⼤(pheromone)ʽϢݣӶ໥Эɸӵ.Ⱥ֮ԱֳΪ֮Ϣ໥ЭҪ.
˶Уܹ·¸ʣ˶ܹ֪ʵĴڼǿȣԴָԼ˶ڳŸǿȸߵķƶ.ˣɴɵȺļΪֳһϢ:ĳһ·߹Խ࣬ѡ·ĸʾԽ. ϸ֮ͨϢĽﵽʳĿ.Դ˹̣M. Dorigoף7ͼʾʽһ̣ﲻ׸.
Ⱥ㷨һ㷨ģ㷨һͨѡɵȺĽѰŽ⣬ṵ̀׶:Ӧ׶κЭ׶.Ӧ׶Σѡݻ۵ϢϵṹЭ׶Σѡ֮ͨϢܸõĽ.
3Ⱥϵͳģͼʵ
Ϊ˱⣬ƽnеTSP(01n-1ʾ)Ϊ˵Ⱥϵͳģ.nеTSPѰͨnиһص·.֮ѡTSP⣬һΪȺ㷨TSP⣬ڱȽϣһ棬TSPǵ͵Ż⣬֤ĳһ㷨Ч.⣬ԶԴģ޸ıӦã6.ȻǴʽϿвͬԭͬģͨģȺΪŻ֮Ŀ.
ΪģʵϵΪ¼ǺţmȺϵdij(i,j=1,2,,n)ʾiͳj֮ľ룬bi(t)ʾtʱλڳiϵĸʾtʱijϲϢ.ʼʱ̣·Ϣȣij(0)=C(CΪ).k(k=1,2,...,m)˶,ݸ·ϵϢתƷ(t)ʾtʱkλiתƵλjĸʣ

(1)
Уallowedk={0,1,...,n-1}-tabukʾkһѡĳ.ʵȺͬ˹Ⱥϵͳм书ܣtabuk(k=1,2,...,m)Լ¼kǰ߹ĳ,tabukŽ̬.ʱƣǰµϢţò1-ѱʾϢų̶ȣnʱ̣һѭ·ϢҪʽ
ij(t+n)=.ij(t)+ijѡ(0,1)
(2)

(3)
ʾkֻڱѭ·ijϵϢʾѭ·ijϵϢ.

(4)
УQǳLkʾkֻڱѭ·ĳ.ڳʼʱ̣(0)=C(const),=0(i,j=0,1,...,n-1).,·ֱʾ˶۵Ϣʽѡ·Ĳͬ.ijʾɳiתƵj̶ȣɸĳʽ㷨ȷ.ݾ㷨Ĳͬ(t)(t)(t)ıʽԲͬҪݾ.M. Dorigo3ֲͬģֱ֮ͣΪant-cycle systemant-quantity systemant-density system7.ǵĲڱʽ(4)Ĳͬ.ant-quantity systemģУ

(5)
ant-density systemģУ

(6)
ǵںģõǾֲϢǰõϢTSPʱܽϺ.ǲΪģ.QC£ѣʵ鷽ȷ.ֹͣù̶ߵƲʱֹͣ.
㷨Ӷȷۿ֪㷨ӶΪO(nc.n3),Уncʾѭ.TSP˵Ⱥģ͵ģԸģӦ⣬һĳЩϺý֣6,8.
4Ⱥ㷨ŵ벻֮
Ϊ˵Ⱥϵͳŵ벻㣬ǸûȺ㷨Oliver30 TSPĵʵ(ͼ11)ʵԴף7,ȡ10ʵƽֵ.


ͼ1ýͼ
1Ⱥ㷨㷨ıȽ

㷨㷨2-opt L-K
ant colony system420
near neighbor587437421
far insert428421420
near insert510492410
space filling curve464431421
sweep486426420
random1212663421

ν㷨ָ㷨ʽ
һϵʵǿԷ֣Ⱥ㷨кǿķֽϺýֲţΪ㷨ԭһ̶ϿԼӿ̣һֱʲе㷨֮䲻ϽϢʹݣڷֽϺý.ھֲţͨܿڽռĳһӼڶԽռĽһ̽ӶֲţڷֽϺý.ǣ㷨ҲһЩȱݣ:Ҫϳʱ䣬һ⣬ף9ҲָûƷ.ȻٶȵߺȺ㷨ıʲһ̶ϿԻһ⣬ǶڴģŻ⣬⻹һܴϰ.
Ⱥи˶ģȻͨϢܹ·ǵȺģϴʱڽ϶̵ʱڴӴµ·ҳһϺõ·.Ϊڽĳ׶Σ·ϢԣͨϢʹýϺ·ϵϢ󣬾ϳһʱ䣬ʹýϺ·ϵϢԸ·ϵϢһ̵ĽУԽԽԣӶڽϺõ·.һһҪϳʱ.Ϊ˿˷ʱϳȱݣܵŴ㷨еıӵõһµȺ㷨бȺ㷨.ǲת췽ʽĳ·Ϊ:i0i1i2...i(n-1),(i0,i1,...,in-1ʣ0,1,2,...,n-1),

Уs1,s2{0,1,...,n-1}, %ʾ.в:inversion(s1s2,solutioni), inversion( )ĹǰѸsolutionis1+1s2һεߵ.磺
inversion(2,5,0123456)=0125436
УĴ.һ漰Ⱥ㷨еѭҪ򵥵öֻ࣬϶̵ʱͬ.һ棬ֱúһܻԸƣӶҲܸȺܣټʱ.ʹ˷˴ʵӣʵַǺЧ.
ǵ㷨αʾΪ
begin
ʼ:
ncycle=0;
bestcycle=0;
ij=C
ij=0
ijĳʽ㷨ȷ;
tabuk=
while (not termination condition)
{ncycle=ncycle+1;
for (index=0; index<n;index++)
indexʾ߳еĸ*/
{for (k=0; k<m; k++)
{Ըѡj;
j{0, 1, ..., n-1}-tabuk
}
ѡĳżӵtabuk
/*(̬tabuk);*/
}
㦤(index),ij(index+n)
ȷѭҵ·
}
·ѽ
end
5ʵ
ѡOliver30 TSPΪʵӽʵ.֮ѡøӣһΪM. DorigoѡøӣӶڱȽ.һ棬TSPǵ͵NP-hard⣬֤ĳһ㷨Ч.PCCԱʵָ㷨.ʵ10ʵƽ(ͼ2ͼ3ͼ4).


ͼ2ýͼ


ͼ3ͼ


ͼ4ҵ·
2㷨ڲͬµʵ

¦· 
ĳȡﵽ
ҪĽ
220.542456
220.9424.850
120.5428.262
520.9423.749
520.5423.844

ΪڱȽϣǸɻȺ㷨õĽ(ͼ5ͼ63).


ͼ5㷨ýͼ


ͼ6㷨ͼ
3Ⱥ㷨ڲͬµʵ

¦· 
ȴﵽ
ҪĽ
220.5424.8350
220.9427344
120.5423.7342
520.9430.5338
520.5445347

ף7Ҫ342ҵϺý(423.74),ĽҪԼ50ҵͬĽ.48еTSP⣬ñ㷨Ҳõ˽ϺõĽ(4).ͨϵʵȽϿԿڱӵ룬ٵĽͿҵͬĽϺý⣬ʡʱ䣬ģŻʮ. 
448TSPʵ

㷨¦· 
ȴﵽ
ҪĽ
㷨220.574.3390
㷨120.975.4357
㷨520.573.7347
㷨120.571.443
㷨520.972.747
㷨220.571.140

6
ľбȺ㷨Чؿ˷Ⱥ㷨мʱϳȱݣʵ.Ⱥ㷨оոտʼԶδGASA㷨γϵͳķͼʵѧдһо.϶Ը㷨и̵оԼθЧȺ㷨ʵ⽫ǽһо. 
õҡCIMS(Ŀ863-511-9508-004).
߼飺飬У19677ʿоҪоΪơҵԶ.
żͻᣬУ196910,ʿо,ҪоΪɢ¼̬ϵͳȡܼ. 
ĺͣУ194012,,ʿʦ,ҪоΪɢ¼̬ϵͳ桢ϵͳȵ.
ߵλѧƷġ110006
ο
1Goldberg D E. Genetic Algorithm in Search, Optimization and Machine Learning. New York: Addison Wesley, 1989
2Davis L. The Handbook of Genetic Algorithms. New York: Van Nostrand Reingold, 1991
3Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. In: Proc 1st European Conf Artificial Life. Pans, France: Elsevier, 1991. 134142
4Colorni A, Dorigo M, Maniezzo V. An investigation of some properties of an ant algorithm. In: Proc PPSN'92, London, 1992. 509520
5Colorni A, Dorigo M, Maniezzo V, Trubian N. Ant system for job-shop scheduling. Belgian Journal of Operations Research and Statistic Computing Science, 1994, 34(1): 3953
6Costa D, Hertz A, Dubuis O. Imbedding of a sequential algorithm within an evolutionary algorithm for coloring problem in graphs. Journal of Heuristics, 1995, 1: 105128
7Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperating agents. IEEE Trans on SMC, 1996, 26(1): 2841
8Bilchev G, Parmee I C. Searching heavily constrained design spaces. In: Proc 22nd Int Conf CAD-95, Yelta, Ukraine, 1995
9Dorigo M, Maniezzo V, Colorni A. Ant system: An autocatalytic optimizing process. Tech Rep: 91-016, 1991 
ԭյڣ1997-11-19
޸ĸյڣ1999-04-08.
