ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.3P.416-420



ģ˻ƵĶȺŴ㷨
쳤
ժҪģ˻ͶȺŴֽϺõĸĽŴ㷨ܵķ.˼лؽ,һֻģ˻ƵĶȺŴ㷨.,㷨ǿ㷨ȫ,ܼӿŴٶ,õȫֵ.
ؼʡŴ㷨,ģ˻,Ⱥ,㷨.
ͼšTP18
A Multigroup Parallel Genetic Algorithm Based on Simulated Annealing Method
WU Hao-yangZHU Chang-chun
(Department of Microelectronic Engineering School of Electronic Information Engineering Xi'an Jiaotong University Xi'an 710049)
CHANG Bing-guoLIU Jun-hua
(Department of Automation Engineering School of Electrical Engineering Xi'an Jiaotong University Xi'an710049)
AbstractSimulated annealing and multigroup parallel evolution are two helpful methods which can improve the performance of genetic algorithm.These two ideas are well combined in this paper,and a new algorithm is derived,that is the multigroup parallel genetic algorithm based on simulated annealing method.Simulation results show that this method not only quickens the computation,but also improves the convergence efficiency,thus produces more satisfactory results.
Key wordsGenetic algorithm,simulated annealing,multigroup,parallel algorithm.
Ŵ㷨(genetic algorithm)һֽȻѡ˼ȻŴƵȫ㷨.ĿܽȺ,ÿһܵĽ⿴Ⱥĸ,ʱ㷨Ⱥռ,һ(ӦȺ)ÿһ,ʹѡ񡢽桢3Ŵ,ʹĽⲻϽ,ֱŽ.ΪŴ㷨ڽռ䡢ԡȫѰŵȸʱдͳ߱ĶصԽ,Դ70ѧJ.H.Holland,Ѿõ˹㷺оӦ.
ȻͳŴ㷨صȱ㣬׹ԼڽЧʽϵ.ʹõĽȫŽ,ǾֲŽ.ڴͳŴ㷨Чؿ˷,ˣڴоθĽͳŴ˼.ĿǰָĽ,Ѿȡ˴ɹ.,ģ˻ͶȺŴ˼ֱŴ㷨У13,ֳõӦǰ.Ľ˼лؽ,ģ˻ƵĶȺŴ㷨.ʵ,㷨ǿŴ㷨ȫ,ܼӿٶ35.
1 ģ˻˼
ģ˻㷨ԴͳѧжԹ˻̵ģ4.Boltzmann׼½,һΪȴϵĲ㷨,ʹ㷨ڶʽʱһŽ.£
(1) ʼ˻¶Tk(k=0),ʼX0;
(2) ¶Tkظִ²,ֱﵽ¶Tkƽ״̬
 ڽxвµĿнx;
 ½ۺf(x);ɽۺf(x)Ĳֵf;
 ոmin1,exp(-f/Tk)random0,1ݽ½,random0,1ǣ0,1ڵ.
(3) Tk+1=Tk,kk+1,Ц(0,1).о,˻̽,ת(2).
˻¶TСֵŻ,ͬʱԸexp(-f/Tk)ʽ,㷨ֲֵ.ֻҪʼ¶㹻,˻㹻,㷨ȫŽ.
2 ģ˻Ŵ㷨Ľ
Ŵ㷨(GA)ѧJ.H.Holland۵˼һȫŻ㷨,ͨѡƺŴӵ,ʹŻȺ岻Ͻ,״̬.׼Ŵ㷨ʵֲΪ:(1) Ⱥģ뷽ʡʵȿƲ(2) 3Ŵ,Եǰĸֳ,¸壻(3) ̭ӦȽϵ͵ĸ,Ӧȸߵ¸븸бĸΪȺ(4) ﵽ㾫Ȼ򳬹ԤŴ,,򷵻ز(2).
Ŵ㷨Ҫص:(1) ԴȾɫ()в,ֱ,ҪݶϢ(2) ֻӦȺΪ׼,רҵ֪ʶ(3) ʹ,ȷ.Щص,Ŵ㷨رʺڴͳܽĸͷ.
ȻʵӦҲִͳŴ㷨ײ󣬼ڽȺӦֵԶ,ˣǲѡƲĸʺܴ,ܽ桢ӰС,ǣε,ЩռȺ,ǰ.ĽŴ㷨ڣһ棬Ϊ˱֤Ŵ㷨ܹȫ,ʹȺ㹻Ĳͬĸ,ȺĶԣһ,Ϊ˼ӿ㷨ٶ,ֱʹȺеĸ御Žⷽ£,ɱؽȺĶ,ȺĿ.
ĿǰһЩоͼģ˻Ŵ㷨,־Զ1ѡʵʩ,ҰѽͱӴͬѩ÷3øĽİӦȱѡʽΪӴԣLin F.T.5Ŵ㷨ıģģ˻,㷨Ϊ,ͨŴ㷨һȺ,Ȼģ˻һŻ.
3 ȺŴ˼
ȺŴ2ǽĸĽŴ㷨ܵĽϺõһַ.˼öȺԭһȺ,ÿȺͬĽԡŴӲн(磬ÿȺвͬĽPcPm˻ȴϵ),öȺԭʼȺڿнռ.ͬȺԶ,ÿS(SΪȺ)ͰѵǰŸ䵽Ⱥȥ,ԴٽȺĽ.ѡȡͱÿȺ,ڱȶԵͬʱ,ӿٶ,ⵥȺгֵĹ.
ͼ1ʾΪ3Ⱥн.Ⱥ1Pc,Pmֵϴ,Ϊ̽Ⱥ,ܵĽвṩµĳƽ,˷Ⱥ2Pc,PmֵС,ΪȺ,ھֲΧ(ĳһƽ)Ѱ,䱣Ⱥ3Pc,Pmֵм,Ϊ̽⿪Ⱥ,ȺĹ.ÿһ,3ȺȴǰŸ,ȻٸԽ.,ֱҵŽ.

Fig.1Schematics of multigroup parallel evolution
ͼ1Ⱥнʾͼ
4 ˻ƵĶȺŴ㷨
Ľģ˻ͶȺŴ˼лؽ,˻ƵĶȺŴ㷨.㷨¹̽У
(1) ʼƲȺĸM,ÿȺĸ2N+1,S,ȺĽPic,Pim,¶ȴϵCi,˻ʼ¶Ti,i=1M;
(2) MʼȺ,趨Loop1=0
(3) 趨Loop2=0
(4) ÿһȺi(i=1M)ʵʩ²,ԲһȺ,ֱMȺ.
 ȺÿӦֵf(xj),j=1,2,...,2N+1
 ӵiȺѡȡxj,xk,Picн,¸xjxk,Ӧֵfxjfxk, min1exp-(f(xj-fxjTirandom,xjΪ¸,min1,exp(f(xk-fxkTirandom,xkΪ¸.randomΪ0,1ϵ
 Խĸ尴Pimб,еķǷ¸.,¸ΪȺĸ,,ɸΪȺĸ.ԲڡظNΣ
(5) Loop1Loop1+1.Loop2S,Loop2Loop2+1,ת(4),ת(6),Ÿ壻
(6) ҳǰMȺиŵĸ,ѡǰŸ,䴫MȺȥ
(7) ǰŸ,̳ɹ,ȫŽ⣻
(8) Loop1СԤMAXLOOP,޸ĸȺ˻¶,TiCiTi(i=1M),ת(3);
(9) Loop1MAXLOOP,㷨δҵҪĽ,㷨ʧЧ.
ϲԿ,ڶȺĲн,ȺÿSξҪд,ԹŸ,Ա㷨һͬ㷨.ΪÿȺӦвͬȺ塢ͬĿƲ˻ȴϵ,㷨ʵʩʱӦöָ(MIMD)ṹ.MIMDṹɶ,ÿеľֲݰִָ,ڸеĽ֮ͨϢķʽͬ(˴ΪһȺSκȴ״̬,ֱеȺSν)Ȼͨ߻洢ʹһȫֹͨ(ѵǰŸΪȫֹдȥ).
5 о
Ϊ۱˻Ŵ㷨,ֵ⣺
(1)
f1x-xsin10x1xʣ-11,
(2)
f2x1-x2xʣ-11.
f1(x)һֵ,ڣۣ1,111ֵ,ȫֵּΪ1.950 533,Ҫ㷨ȫԣf2(x)һκ,ڣۣ1,1ֻ1ֵ,ֵΪ1,ڸúֵȡֵ仯,˿㷨ĺ.㷨ĿƲ£Ⱥģ101,ȾɫΪx1 x2 x3 x4 x5 x6,ÿxi(i=1,2,...,6)ȡֵΪ09,ӦֵΪ.ӦȼΪֵ(ֵ,轫ĵ4Сֵ㷨ԼӸı),淽ʽΪ㽻,췽ʽΪ10(Ըxĳһλxi09֮,Ȼ10ȡ,Ϊxiı).㷨ֹǣȺǰŸӦȫֵ֮С1e-6ʱ,㷨ɹظŸ,ȺϽֱloopԤMAXLOOP,㷨ʧЧ.Ϊ㷨,ȡ㷨100ƽֵΪָ.1Ƚ˲ôͳģ˻Ŵ㷨(ȺΪ1ʱ)ͲöȺ˻Ŵ㷨Ժf1(x)f2(x)8ƽ.
Table 1The evolution epochs of multigroup parallel genetic algorithm and classic annealing genetic algorithm
1Ⱥ˻Ŵ㷨봫ͳģ˻Ŵ㷨ձ

FunctionAlgorithmEvolution epochs
Classic34.2630.3434.9530.9628.9736.3134.9633.90
f1(x)2 subgroups17.6215.0114.2915.9514.6013.9414.9315.14
3 subgroups11.3611.1610.9411.9511.0012.1110.6311.36
4 subgroups9.519.658.659.429.538.879.499.26
Classic13.9912.7315.4912.0811.7912.6412.1611.05
f2(x)2 subgroups5.975.695.134.885.055.514.994.79
3 subgroups3.243.072.592.873.343.303.103.58
4 subgroups2.202.232.552.302.381.972.462.08

ٺ,㷨,۽,ܴͳ㷨,Ⱥ.
ɱ1Կ,ȫԵĺf1(x)ۺٶȵĺf2(x),ĵ㷨ȴͳ˻Ŵ㷨нϴĸĽ.ȺĿ,㷨ƽд½,½ԽԽС.Կ,ȺĿȡ3ȽϺ,ʱ˻ƵĶȺŴ㷨ȴͳ˻Ŵ㷨ٶƽӿ35.ͨʵ黹,Ӧñ㷨ܱ⴫ͳ㷨ֵܳĲ.,ĵ㷨Чؿ˷,һܼӿŴٶ,ǿȫѰ.
6 ᡡ
ģ˻˼ĽŴ㷨ͨBoltzmannӴ,ı.Ž̵Ľ,¶½,ʽĸ𽥼С,ģ˻㷨ɽ㷨ٶ.
öȺŴ˼ĽŴ㷨ͨͬȺԶĽ,ÿνҵĵǰŽ䵽Ⱥȥ,ԴٽȺĽ,ѡȡͱÿȺ,ڱȶԵͬʱ,ӿٶ,ⵥȺгֵĹ.
оõȻѧ(No.69776037)ͽʿ(No.98069828) .,1976,ʿ,ҪоΪ磬 ܴ.,1965 ,ʿо,ҪоΪںϣܴ.쳤,1936 ,,ʿʦ,ҪоΪ΢ӣ.,Ů 1938,,ʿʦ,ҪоΪԶഫϢں.
ͨѶϵ:, 100084,廪ѧϵоƬ
ߵλ(ͨѧϢѧԺ΢ӹϵ710049)
(ͨѧѧԺԶϵ710049)
쳤(ͨѧϢѧԺ΢ӹϵ710049)
(ͨѧѧԺԶϵ710049)
ο
1Wu Zhi-yuan,Shao Hui-he,Wu Xin-yu.Genetic annealing evolutionary algorithm.Journal of Shanghai Jiaotong University,1997,31(12):6971
(־Զ,ۻݺ,.Ŵ˻㷨.Ϻͨѧѧ,1997,31(12):6971)
2Zhou Yuan-hui,Lu Yu-chang,Shi Chun-yi.Adaptive and parallel genetic algorithm based on solving premature convergence.Journal of Tsinghua University,1998,38(3):9395
(Զ,½,ʯһ.ڿ˷ӦŴ㷨.廪ѧѧ,1998,38(3):9395)
3Wang Xue-mei,Wang Yi-he.The combination of simulated annealing and genetic algorithms.Chinese Journal of Computers,1997,20(4):381384
(ѩ÷,.ģ˻㷨Ŵ㷨Ľ.ѧ,1997,20(4):381384)
4Kang Li-shan.Non-Numerical Parallel Algorithms ( )Simulation Annealing Algorithms.Beijing: Science Press,1997.2255
(ɽ.ֵ㷨(1)ģ˻㷨.ѧ,1997.2255)
5Lin F T,Kao C Y,Hsu C C.Applying the genetic approach to simulated annealing in solving some NP-hard.IEEE Transactions on SMC,1993,23(6):17521767
1999-01-12յԭ,1999-04-06յ޸ĸ
