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



̬ģ͵Ŵǿѧϰ*
ȱ򡡸ߡ㷨
ժҪδٶĿǰŴ㷨ȱ.ڻ̬ϵͳеģʽ,һ̬ģ.ģΪΪĳɳռʮҪĵλ,Ⱥʵ˸εŴͺ쾺ѧϰ,Ⱥʵֽһľǿѧϰ.ʵʾ˸ģڽʱЧ.
ؼʡŴ㷨,,̬,ǿѧϰ,Ż.
ͼšTP18
An Ecological Competition Model for Genetic Reinforcement Learning
CAO Xian-bin1GAO Jun2WANG Xu-fa1
1(Department of Computer Science and Technology University 
of Science and Technology of China Hefei 230027)
2(Department of Computer and Information Hefei University 
of Technology Hefei 230009)
Abstract Premature convergence and low converging speed are the distinct weaknesses of the genetic algorithms. Using the living things' growth pattern for reference, a new model called ECM(ecological competition model) is proposed, in which the competition is considered to be in important position. In the ECM model, the congenital genetic evolution and the postnatal competition learning on individuals' level are realized in each sub-population, moreover, the competition reinforcement learning on population level is realized. The experimental results show the ECM model's effectiveness.
Key wordsGenetic algorithms, convergence, ecological competition, reinforcement learning, function optimization.
ĿǰŴ㷨(GA)ΪĽ㷨չܿ,ۻܲ.ӦֳԵȱ,ٶҴδ1,2.ԭڣ㷨ǴȺȫɢԳ,ŴǲöԲ,໥ͻ.ǰ֤߱GAнϴΧ,ʹȺ岻ֲŻ,ǿƽȺĳһضӿռ.,ĿǰкܶصĸĽ,Ҫ335: 㷨еĲ,ŴʡŴСӦȺ; һά㷨еĸ,ȺģԸ.ЩǾ鷽,˼,ֽ㷨; Ⱥ(sub-population),ÿȺŴ.ַʹδֲ,Ȼ׻ȫ,δһ.ҪõؼԽ,бҪµ˼.
ڷ̬ϵͳĻһ̬ģ,Ϊڲͬ϶໥Э뾺.ģڸʵŴͺ쾺ѧϰ,ͬʱȺʵȺ֮Ľһǿѧϰ.ڱģ͵㷨ں̶ܴϼ,δ.
1 ̬ģ
Ϊһ㷨,GAͨģȻѡƶ,ʵֻƵһ.Ǵӻ̬ϵͳеõʾ,ΪȻеĳɳӦ¼:
(1) ҪǸĽΪ,ҪļŽΪ;
(2) ̬нʱ,ΧǾֲĺͿɱ;
(3) ڻ̬ϵͳռкҪĵλ,־ȴڸ֮,ҲȺ֮,ǿǶ̬;־ԲGAȻ̭,һ໥Э뾺Ĺϵ;
(4) һڻ̬ϵͳнŴͺ쾺ѧϰĸӹ.
Ӧ漸,GAҪģ˸ΪŴ,Ҫȡ(replacement).ȺGAģΧľֲ,δǾͺѧϰҪ,ĿǰGA,ȫԲ.
ģ⻷̬ϵͳ,ף6ECO(ecological)ģԽϺõĹ,ECOģȫģ(1)(2)(4)Ŵ,ͬδʶĸԺͺѧϰıҪ.
µ̬ģECM(ecological competition model),ͼ1ʾ.ECMǵ̬ʵ:һǾֲ֮,һǾֲڵĸ֮.ͬȺ,ȺΪȺ,ȺĳʼĿ͹ģ趨.ÿһȺִ̬㷨ECA(ecological competition algorithm),ʹȺܺܿ,ȺģӦ.ÿһȺﵽ,ȺȫȫȺľֲ,,ECMֲһܷӳоֲ໥ϵǿѧϰ,ʹȫֳ.ECM㷨ͼ2ʾ,ֱ˵.

ͼ1̬ģECMͼ2ECM㷨ܡ
1.1 ʼȺ
ȺģΪM,kȺ,ÿȺһΧɸ.2ά88դ,դѡһΪȺĴ,Ե8ľֲ,9һȺ,ͼ3ʾ.ͼжбߵդΪ,ߵդΪֲ.

ͼ3ʼȺ
1.2 ̬㷨
ECAԸΪĹϵΪͶ.ͨŴ¸,ECMиŴ.ָ֮ͬʱ໥뾺Ϊ,Ƕָıͱ̬Ӧ,Ǹĺ쾺ѧϰ.ECAÿһȺ²:
Step 1. ѡ.ԴΪ,ٰŵԭ,ѡһӽڸĸΪĸ,ĸΪһԻ.
Step 2. н桢Ŵ,¸.
Step 3. ȡƽȺ.
Step 4. ָ徺.
һȺ,֮໥ϵ໥Ӱ.Ǽȿ໥Э,ʹԵıͶõ,Ҳ໥,һһĳɳ.Ϊֶָ໥Э뾺ϵ,ӦָĶֵ,ǽͿĶֵ,IACеGrossbergʽָ侺Ľչ7.GrossbergʽԪ֮໥˷ƹϵ,ڽԪӦ,¹ʽ:
f=(max-f)e-(f-min)c-decay(f-rest).(1)

fǸĶֵ,ֱӶӦӦȺ.max,minֱΪСֵ.eΪԱ˷,ʹĶֵֵķ.cΪԱ,ʹĶֵСֵķ.涨iյ˷Ϊ,еfj(max+min)2.fj(max+min)2,˷תΪ,ʱ.,restΪʱĻֵ,֮ΪϢֵ,һ涨minrest0.decay˥,ʹĶֵھϢֵˮƽ,ָڼʱ˥ϵ,0decay1.restdecay㷨ɵ,ȡrest=min2,decay=0.4.
Կ,ڹʽ(1),һòȷԵ,Ķֵϵʱ,˷ܵ,֮Ƶ.䶯ѧϵͳֳ໥Э뾺:Ǿеa,b,ǵ˷ֱΪea,eb,ǿв,eaeb,a,b붼Ϊr,abΪcb=fa,baΪca=fb,
fa=(max-fa)ea-(fa-min)(r+ca)-decay(fa-rest)
=(max-fa)ea-(fa-min)(r+fb)-decay(fa-rest),
fb=(max-fb)eb-(fb-min)(r+cb)-decay(fb-rest)
=(max-fb)eb-(fb-min)(r+fa)-decay(fb-rest).
ʼfa=fb,ڵ1ξʱ,fbfa,ʹbھд,aھʼ,ھнǿ.fa,fbĲϱ仯,пܦfafb,ʱʹb.
ڹʽ1,f=0,
(max-f)e-(f-min)c-decay(f-rest)=0,

f=(max.e+min.c+decay.rest)(e+c+decay).
ĳһĶֵʱ,ʹﵽƽ;Ȼ,Ⲣи嶼ﵽƽ.
Step 5. Ⱥģ.
ɴֲеĵλ¾ȺĹģ.2άդΪ,Ϊ:
(1) ȺѡһѸΪ;
(2) ӦfiȺƽӦȵıfi;
(3) fi1,Ը1-fiѡȺڱԵĸ,ɾ,ʹȺģС;
(4) fi=1,򱣳Ⱥģ;
(5) fi1,fi=m.n,Ը0.nѡȺԵm,ǼȺ,ʹȺģ.
1.3 Ⱥϵǿѧϰ
ȺԺ,Ҫڶֲж̬ѡȫ,ʱ,ȺںȺͬ໥̼뾺.һȺڸĹϵ˷Ե,ʹȺдĶ().ȺϵԵ,ʹͶȺܵ,߶Ⱥõǿ,Ӷʹȫֳ,ʵȺ֮Ľһǿ.һͼ4ʾ.

ͼ4ECMȺϵǿѧϰ
1.4 ECM
ECM,Ⱥʹδֲ,ÿһȺ,ڹģԽС,ٶȽϿ,һЩȺĸĽŴ㷨ŵ.ͬʱ,ECMֽGrossbergԪ໥̼ƹϵ,Ⱥڵĸк쾺ѧϰ,ʹıͱ̬Ӧ,ӶӿȺٶ.ȺģԵִʹȺģӦڻ,ͬʱҲʹȺڸԽԽ,ECOͲһ.һ,ECM㷨ûʶȺ֮ĸӾϵ,ECMͨȺ侺Ϊķ,ȺʵȺ֮Ľһǿѧϰ,ʹȺΪ໥Э뾺еõ̬,Ӷʹȫֳ.
2 ʵ
ԺŻΪ,챾̬ģͼǿѧϰ.GAӦںŻĹܶ,De JongĹӰ,ѡף8,9Ķ庯F5:

De Jong,SGA(standard genetic algorithm)һЩĽٶȺȫܶ.,áżģ(crowding factor model)R5.R5 ޶öʾѡơһ㽻λ.R5,һ嵮ʱ,ѡһ,ΪѡȡnCFƵĸ,nΪȺģ,CFDe Jongһ.,De Jongʹ˴ֵG=0.1.De Jongо,CF=2ʱ,R5Ŵ㷨ԺF5һƽȫŵ.
ǲECMŻF5.Ϊͬ㷨,ڴ˲De Jong׼F5(T):

fe(t) ǵtӦڻeƽӦȺ.ͼ5˻ECMĽ,ͬʱʾECOĽDe JongĽ.Կ,ECMں̶ܴϼ.㷨ִй,ǿԹ۲쵽1.4ECM,㷨ھֲֵʱ,ECMͨľʹıͷ仯,Ӷֲֵܿ.1SGA,ECOECMŻF5 ʱȫ,гǽ100ʱ㷨ﵽȫֵּĴ,ECMȫ.
13ַȫܱȽ

ʵSGAECOECM
1071010
50374147
100617592


ͼ5ECM
3 
GAΪĽ㷨ȻȡһЩɹ,Ҳٶδȱ.ڷ̬ϵͳĻ,Ϊͳ㷨ĿǰһЩĽûгֿڻеĽģʽ,Ӷһ̬ģECM.ECMǿΪеҪ,־ȴھֲڵĸ֮,ҲȺȺ֮,ҾĻǿǶ̬.Ԫ໥Э뾺˼,ECMʵ˸֮ľȺľ,ֳŴͺǿѧϰ˼.ʵ,ECMٶȺܿ,ȫ.
л ĵоõȻѧĿΪ69671029
*оõȻѧͰʡص㹥Ŀ.
߼顡ȱ,1969,ʿ,ʦ,ҪоΪ,,ר ϵͳ.
,1963,ڣҪоΪ.
㷨,1948,,ʿʦ,ҪоΪ,˹.
ͨѶϵ:ȱ,Ϸ 230027,йѧѧѧ뼼ϵ
ߵλȱ㷨йѧѧѧ뼼ϵ Ϸ 230027
ߡ(ϷʹҵѧϢϵϷʡ230009)
ο
1Goldberg D E. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley Publishing Company, 1989
2Rudolph G. Convergence analysis of canonical genetic algorithms. IEEE Transactions on Neural Networks, 1994,5(1):96101
3Schradoph N N et al. Dynamic parameter encoding for genetic algorithms. Machine Learning, 1992,9(1):921
4Srinivas M et al. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transactions on Systems, Man and Cybernetics, 1994,24(4):656667
5Cohoon J P et al. A multi-population genetic algorithm for solving the k-partition problem on hyper-cubes. In: Belew R K ed. Proceedings of the 4th International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann Publisher, Inc., 1991. 244248
6Yural Davidor. An ecological model for evolutionary computing. ƥ//鱨, 1993,31(8):468474
(Yural Davidor. An ecological model for evolutionary computing. System/Control/Information, 1993,31(8):468474)
7Rumelhart D E et al. Explorations in Parallel Distributed Processing. Cambridge, MA: MIT Press, 1988
8De Jong. An analysis of the behavior of a class of genetic adaptive system Ph.D. Thesis. University of Michigen, 1975
9¹,㷨.Ŵ㷨Ӧ.:ʵ,1996
(Chen Guo-liang, Wang Xu-fa et al. Genetic Algorithms and Its Applications. Beijing: People's Post and Telecommunications Publishing House, 1996)
1998-04-20յԭ,1998-06-29յ޸ĸ
