ѧ
JOURNAL OF SOFTWARE
1999 10 8 Vol.10 No.8 1999



һֺŻĻŴ㷨
ΰ¬
ժҪͳľֲ㷨Ŵ㷨,ԽϺõؽŴ㷨ڴﵽȫŽǰ.¸һֽϿɱ巨Ŵ㷨Ļ㷨.ʵ,ͨĽռ佻ȫֺ;ֲ,ܸЧ⺯Ż.
ؼʡŴ㷨,ɱ巨,,Ż.
ͼšTP
A Hybrid Genetic Algorithm for Function Optimization
PENG Wei LU Xi-cheng
(Department of Computer Changsha Institute of Technology Changsha 410073)
Abstract To overcome the problem of slow convergence before the genetic algorithms (GAs) reach the global optima, it is an effective way to combine the conventional local search algorithms with GAs. A new hybrid algorithm that incorporates the flexible polyhedron method into the orthogonal genetic algorithm (OGA) is presented in this paper. The experiments showed that it can achieve better performance by performing global search and local search alternately. The new algorithm can be applied to solve the function optimization problems efficiently.
Key wordsGenetic algorithm, flexible polyhedron, orthogonal crossover, function optimization.
Ŵ㷨genetic algorithmsͨģ;ĽжŽ,ŻѧϰӦơĿߵӦ.ڴͳһЩNP,Ŵ㷨ܵõõĽ.ԴͳܽϺý⣨һķŻ⣩,ʾǿ.ԭ,Ŵ㷨ض֪ʶݶȡHessianĳЩȣý.ҪȺ,ͨԽĲϡıԼԺѡѡ.ڴﵽȫŽǰ,д.Ŵ㷨ʱҪͨЧ֮.ضŴ,ԸЧ,ȱͨ.һ;ǽŴ㷨һЩͳѰŷɽģ˻𷨡ţٷȣ,ڱ㷨һͨʱ㷨Ч.㷨Ļͼ1ʾ.

ͼ1Ŵ㷨Ļ
ĿһԺŻ,
minf(x)xD
f(.)nԪ,DRnнӼ.ף2̽һֽţٷ봫ͳGA;.ţٷһ׵,÷ͨܵһ.ֽ̽ɱ巨flexible polyhedronGAϵ㷨,ֻúֵ,÷Χ.ɱ巨Nelder-Meadη,һŻ,ܽϿرƽŽ,нǿľֲ.ԳʼĹɾнǿ,㷨ִйڷµĿܴŽ.ͨGA,һֲ,һͨGAϡ֡µĸϣ,̬ɱ巨,Ӷʹ㷨иõ,Ҳʹ㷨ڲл.ʵ,Ż,Ϸ³ΪH-GAбȴͳGAͿɱ巨õ.
ĵ1ڸH-GA㷨,2ڸʵͼ㷨ܱ֮Ƚ,ܽ.
1 H-GA㷨
1.1 뷽ʽ
ʵĽռ㷨ռ֮佨һӳ.ͳGAһһֽʵռɢĶƱ뷽ʽ1.ַʽڱ볤Ӱ⾫ȡʱֱ۵ȱ,ʵֱӱ뷽ʽԻøõܣ3,4.ʵ뷽ʽ,ÿһnάʵʾ,ַʽֱۡײŵ,ҿƷǴͳĽ.Ĳô˱뷽ʽ.
1.2 ѡ
漰ѡԻƺͽ.ͨԷʽ.ΪάȺĶ,ѡ.ԷʽӰģʽȺеɢٶ.Ϊ˷ֹ㷨Ĳpremature convergence,ͨϣģʽȺйɢ.Ϊ,ǲһֽԭ5,Ⱥеĵi,һε֮Եǵ(i-1)(mod N),򱾴εõ(i+1)(mod N)֮,NΪȺĴС.Էɱģʽɢ,ҷŴ㷨ϸȲģ͵Ҫ,ڻýϴĲж.
Ŵ㷨orthogonal genetic algorithmڷŻ⼰ŻʾЧԣ5,6,ǵ㷨.һ,¸ѡŵĽһȺ壨Elitistԣ.ڲþֲѡȫѡ,һ̶ϱȺĶ,㷨ڲʵʱͨѶƿ.
ֱΪPQ,ʵ5Ҫ:
(1) Ͻ棨blend crossover:
X1i=Pi; X2i=Qi; X3i=r*Pi+(1-r)*Qi), i=1,2,...,n
rΪһ,0r1.ȡr=0.5;
(2) X1,X2X3L9(34)9¸岢ֱǵӦֵ;
(3) 鷽ˮƽϲӦĵ10,Ӧֵ;
(4) X1,X2,X3²ĸѡõȡPQ.
1.3 
ʵ뷽ʽ,ԸXÿXiһƫ,
Xi=Xi+, i=1,2,...,n
ڽ滮evolutionary programmingͽԣevolutionary strategy7,㷺˸˹,̬˹ֲΪеƫ,=*N(0,1),N(0,1)Ϊ׼̬.㷨Ӷ𽥼,=MUT-C/generation,MUT-CΪһ,generationΪĴ.ף8ƵĽGAĻϽ˹ϵ;.Ѱ˻Ͻ,Ŵ㷨ڸ㷨.
1.4 ֲ
ɱ巨(n+1)nάŷϿռеĶеĶ,ѡȡ(n+1)ڵĸΪʼ㣨nN-1.ɱ巨мֲ9:
(1) ҳ(n+1)кֵСĵXhXl,ȻҳȥXhn㹹ɵĶεXc;
(2) ͨõXr:Xrk=Xck+a*(Xck-Xhk),XkΪXĵk,aΪϵ;
(3) f(Xr)f(Xl),ִ,õXe:Xek=Xck+r*( Xrk-Xck),r1Ϊϵ;
(4) ԶгȥXhһXi,f(Xr)f(Xi),ִ,õXs:Xsk=Xck+b*(Xhk-Xck),0b1Ϊϵ;
(5) f(Xr)f(Xh),ʹеС㿿,Xik=Xlk+0.5*(Xik-Xlk),XikΪiĵk;
(6) Xr,XeXsõĵXh.
1.5 ֹ׼
㷨ֹͣµһֻǵĽʽ:
(1) 㷨һεõĸıСҪľֵ;
(2) ﵽ㷨涨ִʱ䡢ôԽռ.㷨ֹ.
1.6 㷨
H-GA㷨ҪΪ:
(1) ʼһֲȵĳʼȺ壨Nʼ⣩;
(2) 䣩ԵԭȺеĸԲִе1.2ڵ;
(3) 죩ȺÿPmĸʽб;
(4) ֲÿɱ巨оֲѰŲ,ѭɲLh;
(5) ֹֹ,㷨ֹ,ת(2).
2 ʵ
2.1 ܱȽϲ
һ㷨ܵĲ:
(1) սӶȻȷ.սӶֵͨ.ֵΪ2:

XiΪ㷨սĵi,X*iΪʵʵȫŽĵi,wiΪiȨֵ,ӳ˵iȡֵΧС.
(2) Žĸ.㷨гɹõŽĴΪֵ.ȺõĽﵽһʱ,Ϊ㷨õŽ.
(3) ʱ.ڱ֤һȷȵ,ʱԽ,Խ,㷨Խ.ǲúõĴʵʵʱ.
2.2 ܱȽ
ʵķȽŴ㷨OGAH-GA㷨.OGA㷨H-GA㷨ͬĽͱ.ʵ,ѡͬʵĺ:
(1) ,-5Xi5,i=1,2,...,n.ȫСֵΧдľֲСֵ.ȫСֵΪ0,0,...,0,ӦСֵΪ-4n.
(2) һRosenbrock:
f(X)=(100*(Xi+1-X2i)2+(1-Xi)2), -5Xi5,i=1,2,...,n
ȫСֵΪ1,1,...,1,ӦСֵΪ0.ף10вôͳGAn=2ʱ.Rosenbrockɽеĵ½򼸺뵽Сֵ÷ֱ,ͳ㷨½.ʵǷ,ڸά´ͳGAԸЧ.ɱ巨ڴ󲿷оδĽ.
Ժ(1),n=50n=100½㷨ֱ50.ÿо¼㷨ڲͬʱ״̬.ȺСֱΪ100150.H-GA㷨,Ϊ,ÿεпɱ巨ѭLΪȺС.ӦпɸݺԵȵѭȡøŵ.ÿ,㷨ܽϿرƽŽ.1ΪڲͬʱȺŽƽƽִʱ.ȡֵΧͬ,ֵиȨֵͬwi1.ʵһ̨586PCϵõ.
1 㷨⺯(1)ܱȽ

㣨սƽƽִʱ䣨s
(*105)OGAH-GAOGAH-GA
1(n=50)0.028 1660.001 72714.263 40218.444 399
2(n=50)0.002 3440.001 29028.357 40235.957 402
2(n=100)0.120 1880.004 12056.658 20394.781 807
4(n=100)0.010 8330.002 789112.587 607168.967 187 


ʵ,Զʵĺ(1),ͬ,H-GA㷨ܸرƽŽ,ʱԶ.H-GA㷨ԺOGA㷨.
Ժ(2),nֱȡ1030.µȺСֱΪ3090.ʵ,ڹ涨Ĳ,OGA㷨Ž⣨2.50,H-GA㷨սŽĺֵ֮С10Ĵֱﵽ4344. 
2 㷨⺯(2)ܱȽ
սƽƽִʱ䣨sĺֵĺֵ
(*105)OGAH-GAOGAH-GAOGAH-GAOGAH-GA
1(n=10)2.293 560.287 491.259 401.629 800.250 710.000 009.329 173.987 23
2(n=10)1.974 560.283 222.522 203.202 200.158 370.000 008.550 583.987 20
3(n=30)5.125 953.738 009.847 2016.494 619.359 19.698 1228.165 717.293 5
6(n=30)5.056 492.464 9219.686 633.307 418.788 40.941 0927.686 78.950 50
10(n=30)4.986 160.287 3832.805 254.444 218.139 90.000 0127.102 13.988 85

ɱеĽɵ,ԺʽΪӵĺ(2),ͬĲ,OGA㷨˼ʱH-GA㷨,Ž.H-GA㷨ܸЧຯŻ. 
3 ܽ
ĸһȫŻĻŴ㷨,ͳѰŷɱ巨ӽ,ȿŴ㷨ȫ,ֲͨӿ㷨.ڲýԭ;ֲѡ,㷨õĲ.ǻɹؽеĸ˹ӽϵ㷨.ʵ,ĻŴ㷨ЧشһЩͳŴ㷨ѰŷѴĺŻ.
ڲͬʵ㷨ִеĲͬʱ,Ŵ㷨иֲǲͬ.ǡؿƸֲִʱһоĹ.
л ĵоõʿٺܺõĽ,ڴرл.
ͨѶϵ:ΰ,ɳ 410073,ɳѧԺϵ
߼飺ΰ,1973,ʿ,ҪоΪܼ,Ƚ缼.
¬,1946,,ʿʦ,ҪоΪֲ,Ƚ缼.
ߵλɳѧԺϵ ɳ 410073
E-mail: wpeng@csit.edu.cn
ο
1 Goldberg D E. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley, 1989
2 Renders J-M, Flasse S P. Hybrid methods using genetic algorithms for global optimization. IEEE Transactions on Systems, Man, and Cybernetics (Part B), 1996,26(2):243258
3 Wright A H. Genetic algorithm for real parameter optimization. In: Rawlins G ed. Foundations of Genetic Algorithms. San Francisco: Morgan Kaufmann, 1991. 205218
4 Eshelman L J, Schaffer J D. Real-coded Genetic algorithms and interval-schemata. In: Whitley L D ed. Foundations of Genetic Algorithms 2. San Francisco: Morgan Kaufmann, 1993
5 ฻,ΰ,ҵ.Ŵ㷨:һµȫŻ㷨.:˿,ʯһ,.4й˹ѧļ.:廪ѧ,1996.127133
(Zhang Qing-fu, Peng Wei, Wu Shao-yan et al. Genetic algorithm+orthogonal design method: a new global optimization algorithm. In: Li Nai-kui et al eds. Proceedings of the 4th Chinese Joint Conference on Artificial Intelligence. Beijing: Qinghua Press, 1996. 127133)
6 Wu Shao-yan, Zhang Qing-fu, Chen Huo-wang. A new evolutionary model based on family eugenics: the first results. In: Proceedings of 1996 IEEE International Conference on Evolutionary Computation (ICEC'96). Nagoya, Japan, May 1996. 350355
7 Fogel D B. An introduction to simulated evolutionary optimization. IEEE Transactions on Neural Networks, 1994,5(1):314
8 Yang J M, Kao C Y. A combined evolutionary algorithm for real parameters optimization. In: Proceedings of 1996 IEEE International Conference on Evolutionary Computation (ICEC'96). Nagoya, Japan, May 1996. 732737
9 أࣩ.˳ѧ滮ۼ.:廪ѧ,1993
(Wang Yong-xian. Operational ResearchProgramming and Networking. Beijing: Qinghua Press, 1993)
10 ޴,ܴ,ٷ.Ŵ㷨RosenbrockŻо.ѧ,1997,8(9):701708
(Lian Yan-chun, Zhou Chun-guang, Li Shou-fan. Genetic algorithm-based research on optimization of Rosenbrock function. Journal of Software, 1997,8(9):701708)
1997-12-08յԭ,1998-09-10յ޸ĸ
