ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999



һָĽŴ㷨ڲŻеӦ
 ɡ

ժҪǲղΪ,оάƽ⼰ԼԲԲڵĲŻ,NP-.һĸĽŴ㷨,ʮƱƲӦŴ㷨,ӶˡϱըŴ㷨.¸(һΪ߹֪Ž),˴㷨Ч,ѧ滮ĳӷļ.ŴƹӦŻ.
ؼʡǲ,Ż,Լ,Բ,ʮ,,Ŵ㷨.
ͼšTP183

A Modified Genetic Algorithm and Its Application to Layout Optimization
TANG Fei1 TENG Hong-fei1,2
1(Department of Mechanical Engineering Dalian University of Technology Dalian 116024)
2(Open Laboratory of CAD/CAM Technology for Advanced Manufacturing The Chinese Academy of Sciences Shenyang 110003)
Abstract Taking the layout problem of satellite cabins as background, the authors make a study of the optimal layout problem of circle group in a circular container with performance constraints of equilibrium etc. in this paper, which belongs to NP-complete problem. A modified genetic algorithm called decimal coded adaptive genetic algorithm (DAGA) is presented to solve the problem. In this way, the algorithm relaxes the combinatorial explode and the premature convergence of genetic algorithm. Two examples are provided (one of them is proposed by the authors, and its optimal solution is known). The numerical results show that the DAGA is effective and superior to multiplicator algorithm. The DAGA can be developed to solve other layout optimization problems.
Key words Satellite cabin, layout optimization, performance constraint, circle group, decimal, coding, genetic algorithm.
һתǲ,дֱڲյߵԲθ,ҪҪõĲ(ϵͳĹܲ,豸)ŵЩ.ͼ1(a)ʾתҪָn,䲼¼Ҫ: ֮䡢֮䲻; ƽСֵ; ﾡľۼ; ҪڸĽٶȦ¸ĶƽСֵ,ȵ.

ͼ1ѿӱϵµķøϵĴﲼʾͼ
Ϊģ,ٶΪԲ,ڸϽв.⸴,Żɲ÷ֲŻķ,ڸĶάƽڽвŻ.Ҫоڴ˸ϵĶά,ΪеĿһǰ,Ǣ١µһάƽԼĶֳߴԲԲڵĲŻ.ǲղĹؼ.
װŻԹ[1,2].Щ״󲿷оάάھеװ.ĿǰõĲŻѧ滮ͼ۷ʽ˹(רϵͳ),ΪԼװ.[3]µ﷨ԽԼԲװ.[4]ǲղΪ,µʽ㷨ԽԼԲŻ.[5~7]˷ɴղΪ,Բ塢ڶԲеװо,ѧ渴ģ,ۺϵʽ㷨.ڴԼĲļ㸴,ѧ滮ͼ۷ǲ̫Ч.ʽȻΪЧ,ֻܽĳ,Խϴ.Ϊ,һָĽŴ㷨.Ϊֹ㷨ԼΪʺϲĴλҪ,ĸһֻʮƱĿƲӦŴ㷨,.
1ѧģ
оһƽͲԼԲԲеĲŻ.
IʾҪԲԲļ,iʾԲϵһԪ.riʾiԲİ뾶,miʾiԲ,RʾԲİ뾶.ͼ1ʾĵѿϵ,ԲԽٶȦת,Բġغ,.
ƱX=(xi,yi)T,xi,yiֱʾiԲԲx,yֵ᷽,ͼ1ʾ.
䲼Żѧģ:
minFX=1F1X2F2X. (1)
ɲƽ,
, (2)
ɾۼ,
,iI, (3)
s.t.,ɲ,
 (4)
(5)
RxiR,-RyiR,iI(6)
ϸʽ,miΪi,riΪiİ뾶,RΪԲİ뾶,w Ϊתٶ.R ΪԲΪԲĵдԲ뾶,1,2ΪĿ꺯Ȩֵϵ.Լ(4)֤ԲԲᳬԽԲı߽.Լ(5)֤ѾԲԲ,ص.Լ(6)˵˴ԲԲx-y,޶ԲĵֵΧ.
2ڲŻƵĸĽŴ㷨
Ŵ㷨ԴȻ,HollandGoldbergвŴ㷨˼[8,9].Ŵ㷨һЩNP-(TSP)ʱʾЧ,оνŴ㷨ȻҺӦNPѶȵĲŻǺ.Ŵ㷨ڲеӦĿǰոտʼ[10].ĸһֻʮƱĿƲӦŴ㷨,.
2.1 ʮƱ
PһѽķԹ滮.[9]֤ķ͹,öƱȻ൱ľʧ.ʹʮ,Բֵ(ʮ),γһ⴮,ÿһ(xi,yi)൱ڶƱһλ.Աĵ3ڵе5Ϊ,ֵʾΪһλ,ʾ.

12345
x1y1x2y2x3y3x4y4x5Y5
- 494.30- 69.73533.156.37- 324.77700.70404.88- 463.24- 149.15438.69

 
ʮƱŴ㷨,ѰŵľȲܱ볤ȵ,ʹòѰŵķΧռ,ŽľȽȡڼֵ.ڴ˻,ƳӦʮƽͱ.
2.2 ӦȺ
ӦȺʱ,˿ǶԲƽҪ,ҪǴԲ֮䡢Բɲ߽Լ.GʾһȺеĸֵ,ӦȺΪ
MinF=1F1X+2F2X+3IG. (7)
Ц1,2,3ΪȨֵϵ,Ҧ1,2,30.
ΪŴ㷨,ӦȺб任.ָȿ÷ǳõĴн϶ĸƻ,ͬʱ临ĿܿȺ,ľ.ָ任õӦȺΪ
(f)=exp(-f). (8)
ϵµֵǳҪ,ѡǿ,ֵԽС,ѡǿƾԽЩӦֵĴ,PΪ:
Q:max(f) (9)
2.3 ƲӦ
ÿһȺӿøôȺƽӦFʾ,ôȺƽӦȵȶԿȺŸӦȺƽӦȵĹϵʾ.fmaxʾĳһȺӦĸӦֵ,FʾôȺƽӦֵ,
=fmax-F. (10)
Խ,ʾ֮ӦֵĲԽ,ȺиԷɢ;ԽС,ʾȺи֮ӦֵĲԽС,˵ȺֲżĿ.˿æӳȺ̶.,pcpmͿɦ.Ϊ˾˷,Ľϴʱ,Сpcpm;ĽСʱ,pcpm,pcpmֵĳɷ,ʽʾ.
Pc1/,Pm1/. (11)
ȺĽ,ʵʱƲpcpmֵ.Ⱥʱ,pcpmֵ,ӽͱĸ,ƻǰȶ;Ⱥڷɢʱ,򽵵ͽͱĸ,ʹȺ.
ǲһ,ȺʵѾȫʱ,޷жǷ񵽴ȫ,pcpm,ʹŸ⵽ƻ.Ȼ,ҲƻŸ,ʹ㷨޷ȫ.,Ҫֹ,ҲҪ.Ϊ,ͬһжԲͬĸ,pcpmҲӦӦͬ.ӦȸߵĸӦԱ,ʹpcpmӦС;Ӧȵ͵ĸ,ʹpcpmӦ.,ڻͬʱ⵽ƻ.һ,fcΪнСһӦֵ,fmΪӦֵ,ţFfc,ţ=F-fm,pcpmֱpcpm,
Pcئ,Pm1/ţ. (12)
Ϸ,ĸ¿Ʋ:
PcئŦ,Pm1/ţģ (13)
߱ʾΪ
pc=k1/,pm=k2ţ/,(14)
k1,k2Ϊϵ.Ҫע,˱ϵȡֵ㷨кܴӰ.
2.4 ʮŴ
2.4.1 
ȺģΪN,ӷʵʩ.
1:ʵʩű.νű,ҳȺõĸ,طһȺ֮.[11]ָ,ڲűŴ㷨,Ը1ȫŽ.
2:ԸȺĸ,ԵӦȺƽӦȵıʵʩתַ,һȺеN- 1.
2.4.2 
ʵֲֻ򻥻Ļ.ʮƱص,һ˫㽻㽻ʵֽ.ν˫㽻,˼,ʵʩһν,ν.1ǽ⴮Ľ,⴮Ļ;2ǻ򼶵Ľ,еԪ.ֽ,ֵطʮƱĽӵǱ,չ˽ӵĿ.˵.
ٶ⴮bʾ:

⴮x1y1x2y2x3y3x4y4x5y5
a- 494.30- 69.73533.156.37- 324.77700.70404.88- 463.24- 149.15438.69
b- 67.06- 418.41170.94305.04375.07682.41- 27.32229.13- 96.56685.91

 
1㽻λѡڽ⴮ĵ2͵4λ֮Ļ,õ½⴮Ϊ:

⴮x1y1x2y2x3y3x4y4x5y5
a - 494.30- 69.73170.94305.04375.07682.41- 27.32229.13- 149.15438.69
b - 67.06- 418.41533.156.37- 324.77700.70404.88- 463.24- 96.56685.91

2㽻Ե1㽻ĻΪ,ַʮƱǱ,εԪ.ٶԪѡΪʾx,λѡڰλʮλ֮,2㽻½⴮Ϊ:

⴮x1y1x2y2x3y3x4y4x5y5
A- 494.30- 69.73133.15305.04324.77682.41- 4.88229.13- 149.15438.69
b- 67.06- 418.41570.946.37- 375.07700.70427.32- 463.24- 96.56685.91

 
ʹ˫㽻,Ӧȸߵĸ,ĸλģŽȽϽӽ,ĸϢʱ,ͨʶʹλģ御ܵƻ,ͬʱֽĸĵλģ.,˫㽻ܹϢĿĵȺŽ.
2.4.3 
ٶȾɫΪ=((x1,y1),(x2,y2),(xn,yn)),һ±Ҫÿxiȫͬĸʽб,һαĽΪ=((xk,yk),(x2,y2),(xn,yn)),,1kn.(xk,yk)ֵʽȷ.
 (15)
UBxLBxֱΪkx½,UBy,LByֱΪky½,(gԦ)x[0,],[0,]ϵһ,ʹֵŴg0.ѡȡĺ㷨Ŀʼ׶һµռ,㷨ĺڽоֲ.
, (16)
rǣ0,1ϵ;gǵǰĴ;GŴ㷨õ;Ǿһ³̶ȵĲ.
2.5 㷨׼
Ϊ׼.
(a) һGϽGmax;
    (b) 
|(f*(G+1)-f*(G))/f*(G)|, (17)
f*(G)ΪGøӦ,ΪһС.
2.6 㷨
(1) ȺG=0,ɹģΪNĳʼȺ,ȷpr;
(2) Ӧm (f );
(3) ȷӦƲpcpm;
(4) ʵʩơͱ,һȺ;
(5) һȺӦ,¼ôȺеŸ.
(6) 2.5ڵ㷨׼.,ת(7);,G=G+1,ת(3);
(7) ĳּȶ(Ӧֵõĸ)ȽϸȺõĸ,õΪѰŵս.
3 
ڸԼԲ,2ΪǹһȤ֪Ž.
1:Բ뾶R=880mm,תٶw =1.0rad/s,Բε1ʾ,Ҫ1еĢ Ժ͢ ƽĲ.
1 й

Ű뾶
(mm)
(kg)Ű뾶
(mm)
(kg)Ű뾶
(mm)
(kg)Ű뾶
(mm)
(kg)
1106111189721108113111112
211212129282286732918
39891310911239383310110
4105111410410241001034918
5938151151325102103510811
610310161101226106113611412
7826171141227111123711813
893818897281071138857
91171319826291091139877
1081620120143091840989

 
P(ʽ(3))ѧģ,ֱŴ㷨ͳӷQ.Ŵ㷨ȺСΪN=60;ӷжάBFGS,һά߷.586΢(ͬ),2ͼ2ʾ.
2Ż
Ŵ㷨ӷ
ƽ
(kg mm rad2/s2)11.39542.190

(mm)00
ʱ
(h)0.460.58


3
ͼ21Ĳֽʾͼ
,ĽŴ㷨Žıƽ̶ȺͼЧʾڳӷ.
2:Ϊ֤Ŵ㷨Ч,⹹һ֪Ž,Ųͼ3(a)ʾ.Բ뾶R=130mm,Բġغ,תٶȦ=1.0rad/s,Ҫ㲻桢ƽԼʹԲԲľۼĲ.Բε3ʾ.

ͼ32Ĳֽʾͼ
3й
Ű뾶(mm)(kg)
120.7120.71
250.0050.00
350.0050.00
450.0050.00
550.0050.00

ŽΪƽиΪ0,ԲΪԭȫСԲ뾶R=120.71mm,λΪ:1ԲΪ(0,0);25Բλڰ뾶ΪRc=50.00+20.71=70.71mmԲ,λʽȷ:
. (18)
ʽr0Ǵ1İ뾶,rǴ25İ뾶,=min{2,3,4,5},ȡ [0,/2],iԭiԲԲĵxн(ʱ뷽);ni{0,1,2,3},i=2,3,4,5.
Pѧģ,ֱøĽŴ㷨ͳӷ.Ŵ㷨ȺСN=80,4ͱ5ʾ,ͼͼ3ʾ.
4Ż

ƽ
(kg mm rad2/s2)
(mm)Բ뾶
(mm)ʱ
(h)
ӷ3.6850129.560.10
Ŵ㷨1.2650123.200.18
Ž00120.71


5λ

ųӷŴ㷨
xyxy
1-4.639-7.841-0.5858-1.058
235.538-71.18165.97926.179
3-74.47226.25226.92968.061
4-26.27969.87227.891-66.894
567.19830.848-66.685-26.886

 
4
ǲղΪ,оάƽԼԲŻ,һָĽʮ롢ƲӦŴ㷨,಼.¸жԱ,һΪǹ֪Ž.ñͳӷֵ,㾫ѧ滮ĳӷ,Чģй.˵˱ĽŴ㷨ЧԺͿ.ģϴʱ,ĽŴ㷨ʾԽ.
עͣоõȻѧ
߼飺 ɣ1972,ʿ,ҪоΪCAD/CAMŻۣ
Żơ
ɣ1963,,ʿʦҪоΪCAD/CAMŻۣ
Ż.
ߵλ: ɡɣѧеϵ  116024
ɣйѧԺִCAD/CAMʵ  110003
ο
1Haessler R W, Sweeney P E. Cutting stock problems and solution procedures. 
European Journal of Operational Research, 1991, 54(2):141150 
2Dowsland K A, Dowsland W B. Packing problems. European Journal of Operational
Research, 1990,56(1):214
3,ղ.Packing﷽.Ӧѧѧ,1979,2(2):176180
(Huang Wen-qi, Zhan Shu-hao. A method to solve the packing problem by 
analogizing objects and their moving. Acta Mathematicae Applicatae SINICA, 
1979,2(2):176180)
4Teng Hong-fei, Sun Shou-lin, Ge Wen-hai et al.Layout optimization for the objects
installed on a rotating table-the packing problem with equilibrium behavioral 
constraints. Science in China (series A), 1994,37(10):754760
5Ge Wen-hai, Teng Hong-fei. Three-dimensional optimal layout of objects allocated 
inside a multi-cabin rotating vessel. In: Proceeding of the 18th International 
Conference on Computers and Industrial Engineering. Shanghai: China Machine 
Press, 1995. 13151320
6÷,,.ԲռгȺŻģ͡͹Լ㷨.Ӧѧѧ
,1997,20(1):159160
(Wang Xiu-mei, Feng En-min, Teng Hong-fei. Rectangle parallelepiped geometric 
layout optimization in cylinder space with behavioral constraints. Acta 
Mathematicae Applicatae SINICA, 1997,20(1):159160)
7Ʒ,.ӹϵͳļά.йѧڿժ,1997,(9):11371140
(Tang Fei, Teng Hong-fei. Three-dimensional computer-aided layout optimization 
for complicated engineering system. Academic Periodical Abstracts of China, 1997,
(9):11371140)
8Holland E A. Adaptation in natural and artificial systems. Ann Arbor, Mich.: 
University of Michigan Press, 1975
9Goldberg D. Genetic algorithms in search optimization and machine learning. New 
York: Addison-Wesley Publishing Company, 1989
10Jakobs S. On genetic algorithms for the packing of polygons. European Journal of
Operational Research, 1996,88(1):165181
11Suzuki Joe. A Markov chain analysis on simple genetic algorithms. IEEE 
Transations on System, Man and Cyber, 1995, 25(4):655659
ո:1998-08-12޸:1998-10-20
