Զѧ
ACTA AUTOMATICA SINICA
1997ꡡ236ڡVol.23No.61997




佹Ŵ㷨䲢ʵо
źᡡһ
ժҪŴ㷨(Genetic Alogrithm, GA)༰ӦԶù㷺Ӧ. ͨŴ㷨ڴʽƣռ估ֱ޵ģ ھֲ. ˴мı佹(Zooming)Ŵ㷨вԣ ˽ӡġٱȲռֱʵìܣڹվtransputerϷֱԴСзʽʵ˱佹Ŵ㷨. 
ؼʡ佹Ŵ㷨(ZGA) ӣģ. 
ON ZOOMING GENETIC ALGORITHM AND
ITS PARALLEL REALIZATION
QIN ZUXUZHANG HONGYUECHEN YIHONG
(Department of Automatic Control, Beijing University of Aeronautics and Astronautics,Beijing 100083)
AbstractGenetic algorithm (GA) is widely applied to many fields due to its simplicity and adaptability. Generally, the search space and resolution of GA are limited by the string of GA, therefore, the solutions given by GA are usually local results. This paper analyzes the problems in GA and proposes the zooming GA(ZGA), which is suited to sequential and parallel computation. Strategies such as decoded factor, search center, fast mutation, etc. are adopted and the ZGA is realized on a wokrstation and transputers in sequential and parallel manners, respectively.
Key wordsZooming genetic algorithm(ZGA), decoded factor, search center, parallel.
1
GAǽȻŴѧϵŻ㷨. ˼Դġ桱ԼŴĻ˼12. GAǿĽ͹㷺Ӧ͸򣬲ȡ˺ܺõЧ. кܶõԣ ֻĿ꺯Ҫ(ݶȵ)ڸֳϣͬʱռ㣬вԡӵĶֵռ. ڻŴ㷨-˼34ݵĻϣ˱佹Ŵ㷨˾GAŵ⣬ײдԼŻٶȿŵ. ͨ Ŵ㷨
max or minJ(),ȡD, DRn.(1)
ЦΪ DΪԼ޲. 㷨12ݵ£
(1) ȷҪŻĸֲ˳γȡRn, =[1,,n]TƺʵĴSɲȵSĹ̳Ϊ룬 ɴֵĹ̳Ϊ룬ʽʾ
(2)
tΪpΪ
(2) ⣬ѡʵʽĿ꺯ӦΪJ()J(S)
(3) ʼm(l)()Si(i=1,2,,m)ѡһʼ(һȺ)
(4) ÿн룬 ټÿĿ꺯ֵ(Ӧֵ)J(i)(i=1,,m);
(5) ȺlӦֵϴĴSi(i=1,2,,l);
(6) l(ƥ伯)ŴŴӶƥ伯ڵĴ㣬 Ҫǽ(crossover)(mutation) ʱҲһЩŴӣ12ݣ
(7) Բ´벢ӦӦֵ
(8) жӦֵ(Ŵ)ǷҪ󣬷ת(5)Ż. 
2佹Ŵ㷨
Ŵ㷨ԼŻУռΪRn. ڴʽƣŴ㷨ռ估ֱ޵ģֻܸǲֽռ䣬ҽľҲޣǾֲ.ɻGAԿҪƺʵĴSӦĽ.ȫŽ*DRn ƵĴSǵΪDS GAȫСıҪ
*DS.(3)
ʵһSĸʽȷDSҲȷ.ĳЩʱԡʽƣܱ֤(3)õĽǾֲ. Ͻȫ֪ŽλãƵĴӦܸRn Ҫ޳ģⲻ. ʵУŽŽӦǿʵֵ(ֵܴܺ)˿ɸʵ⣬ѡȡʽ. ⣬ڻGAôʽ棬Сʱ죬ֲڽӽŽʱǳνǰ. ϴڵ⣬˱佹Ŵ㷨. Ҫ˼£
 佹GA˽ӦĸҪΪ˽޴ʱֱ֮ìܣ ڴΧʱýϴĽ(ֱʽϵ)СΧڲýСĽ(ֱʽϸ). ˣΪ֤ȫţʼӦǽϴ򣬼ʼӦ0ӦѡһЩ. ڡ-. 
 ļ. SӦΪȡGADSΪŷϿռԦ0Ϊ(ԸʵҲԭ0=0)뾶Ϊȡ=Rĳ. ڹ̶ĴʽŴ㷨Ѱţ ϴ󣬻ȫŽĿԾͽϴ. ڱ佹Ŵ㷨УŴŻõĳһӦiӦĦi-1 仯ΧΪiRiΪ*iŽΪ0+Ʀ*i. һŴ㷨. ӡġŽγϵ
ӣ0,1,2,3,4,,i,;
ģ0,1,2,3,,i;
Ž⣺1=0+*1; 2=1+*2=0+*j,;i=i-1+*2=0+*j,.
 ˡٱ족. ˼ڽСĽ(ӽŽ)ʱýϴʱ죬ʹѸٱ仯򣬼ٶ. ڱ佹㷨
ٱ첻ᶪʧŽ. 㷨СΧڣGAת.佹㷨ˡǿȱ족ԣЩӦ(ӦֵС)ĸǿȱ죻Ȼϲ ̭µĸȡ(). 
ĽϸĽŴ㷨Ϊ佹Ŵ㷨.ѿŴ㷨Ǳ佹Ŵ㷨һΣ൱ԭ㣬뾶ӹ̶. ˣZGAȫGAŵ㣬ͬʱŵ㣺׽м㣻ǳԼŻ㣬رԼΣͬ㷨(ݶ㷨)ʹ. 
3佹Ŵ㷨Ĳʵ
òд ͻƴͳмġƿ⣬ʹٶȳɱӿ죬ͬʱҲϵͳĿɿ. ڲдӲ棬ӢINMOS˾Transputer(Ƭ)ɵĻTexas˾TMSϵоƬɵĲмΪдṩõӲ. 
òдŴ㷨򡢼ӿٶǷǳЧֶ. TransputerĿǰ㷺õһֲӲ. TransputerܹɴģĲ߼ٶȣƬƵͨѶҲӰЧʣ˾Ƭͨٵм. ĲõINMOS T800ƬϵͳϵͳSun4Ϊ̫ɾƬɵĲмٶ. 
ñ佹Ŵ㷨ĵĸ԰ָ˱佹Ŵ㷨ȫмͨѶֻڼʱͨѶͼŽѡ. TransputerϳɹӦñ佹Ŵ㷨мºСֵͬʱҲSGIվñ佹Ŵ㷨伫Сֵ 
f(x)=3.59118910-6x8-3.109400410-4x7+1.1134545510-2x6-2.12881172610-1x5+
2.33974988x4-14.81638047x3+51.2109248x2-84.16690736x+49.51052631.
вʮƴʽΪ5ڴ˴ʽµΪ104.Ϊʹڹվϴмʱѡȡ16x0=0,x1,x2,,x15˳Ż. 16ƬTransputerϣÿƬѡȡһĽʱΪм1/16.x0=0ĴθıӼÿٱԣ90ŴŻСΪx*=1.738, f(x*)=-1.6008, ĵľֲСֵx*Сֵ.Ϊ˱ڱȽϣ˻Ŵ㷨x0=0Ѱţ3000СΪx*=1.74, f(x*)=-1.60079. ɴ˿ɼZGAGAٶȴߣҲˣŵ㸽ܽϺõؽǰ. 
4Ӧ
ｫ佹Ŵ㷨Ӧŷ綯CADϵͳеԼŻ5ݣ ȡ˽ϺõЧ. ŷѡһԼŻ⣬ҪС(Լ)ܴﵽҪļָ(ָԼ)ڶ״̬»Ч. Ŀ꺯Ϊ,VΪΪЧ. ŻıXҪѡΪṹߴX=[x1 x2 x3 x4 x5]Tx1Ϊоl1,x2ΪӲ۵׿bcd1,x3Ϊӳݿbz1,x4ΪתӲ۸hc2, x5ΪתӲۿbz2. ԼɵҪģɸݵƵļָƵ18ԼԼָԼ. 145SL-4D͵ߴļԼΪԼ˲ñ佹Ŵ㷨ǱȽϱ. ŻĿȡΪԼģX0=[154.751.551.20.6]. 2ʾΪZGASUMT+ģʽֱŻĽ. 
1Լ
123456
x110,30ݣ10,35ݣ10,40ݣ10,30ݣ5,30ݣ12,30
x21.2,1.7ݣ1.2,1.8ݣ1.2,1.9ݣ1.2,1.6ݣ1.1,1.7ݣ1.1,1.7
x34.0,6.5ݣ4.0,7.0ݣ4.0,7.5ݣ4.0,7.0ݣ3.5,6.5ݣ4.3,6.5
x40.6,1.4ݣ0.6,1.5ݣ0.6,1.2ݣ0.6,1.4ݣ0.5,1.4ݣ0.4,1.4
x50.5,0.8ݣ0.5,0.9ݣ0.5,1.0ݣ0.5,0.8ݣ0.4,0.8ݣ0.5,0.8

2ͬԼµŻ
Լ123456
SUMT
+ģʽĿ꺯ֵ8.7838.9828.7018.823/8.924
ʱ()3333/3
佹Ŵ㷨Ŀ꺯ֵ7.8318.3927.5567.8638.1448.367
ʱ()8614976

ӱ2Կ 佹Ŵ㷨ʱԳ ҪSUMT+ģʽڵԼ SUMT+ģʽδܸԼĽ.
5
ı佹Ŵ㷨ڴмʺڲдTransputerʵʮ. 佹Ŵ㷨ӦԼŻ⣬кܺõԣŻͬBP㷨Ͽɴӿٶ. 
лĵõ廪ѧϵͳӦʵҵ֧֣ڴ˱ʾл.
1) õȻѧ𼰺տѧ. 
ߵλպѧ301ҡ100083
ο
[1]David B Forgel. An introduction to simulated evolutionary optimization. IEEE Trans.Neural Networks,1994,5(1):3-14.
[2]¸磬º.Ŵ㷨оչ.Ϣƣ1994, 23(4):215-222.
[3]Nicol N Schroudolph. Dynamic parameter encoding for genetic algorithms. Machine Learning,1992,9(1):9-21.
[4]Shaleler C G .The ARGOT Strategy:Adaptive representation genetic optimizer technique. In:Proceeding of the second international conference on Genetic algorithms, 1987, Beijing, 50-58.
[5]Ρ.ŷ綯CADϵͳо뿪ѧλģ.պѧ1995.
ո 1995-05-18
