ѧ
JOURNAL OF SOFTWARE
1999 2 No.2 1999



ڿɵŴ㷨ƭ*
ơ1212
ժҪŴ㷨GA(genetic algorithm)ƭĳЩص,϶Աӽз,˽GAƭһµķ.㷨ܹŴиıӵķ͸,ʹӿɵ,ЧŴ㷨еƭ,ȺĶ,ʹGA˳ȫŽ.
ؼʡŴ㷨,ƭ,.
ͼšTP18
A Solution to Deceptive Problems in Genetic Algorithm Based on
an Adjustable Mutation Operator 
HUANG Yan1JIANG Pei2WANG Jia-song1YANG Jing-an2 
AbstractIn this paper, some characteristics of GA(genetic algorithm) deceptive problems are discussed, the performance of the mutation operators is analyzed theoretically, and a new method for solving GA deceptive problems is proposed. The proposed method can change the direction and the possibility of the mutation operators in the process of the genetic searching, making mutation operators adjustable. In this way, GAs can eliminate effectively their deceptive conditions, keep the diversity of population, and thereby converge conveniently on global solutions.
Key wordsGenetic algorithm, deceptive problem, mutation
ƭŴ㷨(Genetic Algorithm,GA)оеһȵ㣮ģʽͽס̾ģʽŴӴнָ,,ͬģʽ໥,ӶõŽ13.,ƭ,ƭġԻ,ʹŵͽģʽϺγɷŸ߽ģʽ,ӶʹGAƫŽ4.ƭĴ,ⱻΪGA,ʹGAӦܵһľ.һֻڿɵӵķ,Ŵͨıӵķ͸GAƭ.ַܹGAеƭͬʱȺĶ,ʹGA˳ȫŽ.
1ƭķʾ
ͨСƭѰGAƭķ.ڢСƭ(f(01)>f(00))ֻҪڳʼȺģʽĳʼ,ܹȫŽ,СƭⲢGA-5,6.,ĽֻۢСƭ,f(00)>f(01).
4ֶģʽ,ƽӦֱֵΪf(11)=1.1,f(10)=0.9,f(01)=0.5,f(00)=1.0.,ģʽ11Ϊģʽ,f(*1)=0.8<f(*0)=0.95,ʹøƭ.,f(01)ֵ̫Ͳų˴.f(01)>0.8,f(*1)>0.96,ƭԾʧ.,ȥģʽ01,ʣµ3ģʽͲƭ.,ͨıĳЩģʽӦֵƭǲʵģڽв޳ӦֵСĸ,ԼС˷ƭ,һֵóԵķ.
һȫƭ,һ˵.
f(000)=29,f(001)=26,f(010)=22,f(011)=0, 
f(100)=14,f(101)=1,f(110)=2,f(111)=30. 
ͬʱ3ƭ(1) f(0**)>f(1**);(2) f(*0*)>f(*1*);(3) f(**0)>f(**1).޳Ӧֵģʽ011,101,110֮,ģʽӦֵı仯1ʾ.
1ȫƭ޳ģʽ󵥽ģʽӦֵı仯
޳Ĵf(1**)f(0**)f(*1*)f(*0*)f(**1)f(**0)ƭ
11.7519.2513.517.514.2516.75(1),(2),(3)
01111.7525.671817.51916.75(1)
001,10115.3025.6718232816.75(1),(2)
001,101,1102225.6726232816.75(1)
001,101,110,1003025.672627.52825.5(2)
001,101,110,100,0103027.53027.52829(3)
001,101,110,100,010,001302930293029
2ɵӵĹ
ϽڵķԵó,ɾȺеģʽӸеƭ,ͬʱ÷صƻȺĶ,GAĲ.1еʾ,ֻе޳С26ĸ֮,ܽתΪƭ,ʱӽռֻʣģʽ,ռʼռ1/4.ʱҪ֤ӽͱĺڸӽռǲ׵,뾭ӽͱʵ.ȾɫĲͬ,äĿ,ģʽ111ģʽ000εģʽ001,000001ӽģʽ111,ֻܿ7.ȡΪ0.001,ҪO(109)αܲģʽ111.Զ׼,ַȻֱ,ܲʵ.
ͨ,ӦöĹ;дٽ.˸ıеŴ֮,ܹµŴʣҶͬһƶӣ8.ɵӾǻ˼Ƶ,ȾɫеĲͬ,䲻ͬĻֵ,ڽеʺͱ췽1001.
ɵӾзԺ͸ʿɵ,Ҫȷ췽ͿɵʵĴС.ڽ,ȡϢֻԴڽ̱,ҲֻܴȱȺӦֵصȡϢȷɵ.ʹȾɫеĵ仯,,ȡϢҲӦǵ,һģʽϢ.,ƭ,ͽģʽҲƭ,ƭڽÿһ.ƭ,Ⱥﶼƭ,f(0**)>f(1**),ƭԵϢf(0**)>f(1**)ȡ,Ϳܻɴľ췽Ϊ1**0**,Ӧ,ʹһ0**ģʽĸ,ʹGAƫŽ.
ع˱˼룺Ӧֵ½Ϊfinf,޳Сfinfƴ,ӶʹƭԼС.ĳһȷλõһģʽ,迪ʼʱfinfʹһֵ,ȡfinf=2,ڲfinfĹ,һģʽƭĴͻСڲĴ.ص,ȷ췽ʱ,ԸȺ趨һӦֵ½finf,ֵȡȺƽӦֵfavg.
,ν޳ǽСfinfĸ̭,Ⱥ,ǽи嶼Ⱥ.ֻڱȽͬһȷλõһģʽʱ,ڴfinfĴӽռнбȽ,õһģʽıȽϢ,f(*1*)ǴڻСf(*0*),Ӷ2λı췽01,10.ڱĿɵȡf(*1*)ڻСf(*0*)ĳ̶. 
3Сƭ
ôͳСƭʾɵӵЧ.ڴͳоڽǸƺӽӵ,еʽ
(1)
(2)
(3)
(4) 
ʽPtijģʽijڵtı,ǵǰȺƽӦֵ,ʽʾ.
=Pt11f(11)+Pt10f(10)+Pt01f(01)+Pt01f(01)+Pt00f(00). 
ʽPc=(/(L-1))Pc,Pcӽ,LΪ,Ϊ.
ʹõ1е,ȡPc=1.0,/(L-1)=1.0,ʱڸƭ.ڵоʾ,趨ʼ̬P0ij=0.25ʱ,11ĺõĽ;趨һǳѵĳʼ,P000=0.7,P010=P001=P011=0.1ʱ,ʷɢ2.ΪԺɵGAбȽ,ｫʷɢļʾͼ1ʾ.


ʼP000=0.7,P011=P010=P001=0.1
ͼ1СƭһGAֵⷨ 
һGAɵ,þͲܺ.ķRtijʾtơӽ,ǰģʽiji.ʽ(1)(4)Ȼ㷨,轫ʽPtijֱ滻ΪRtij.Ϊʧһ,гAdjustiݣ0,i=0,1ʱ,ɵģʽijı仯ʽ.Ϊ򻯹ʽ,
Pm=(1+cAdjust0ݣ)Pm,Pm=(1+cAdjust1ݣ)Pm, 
¹ʽ:
Pt+111=Rt11(1-2Pm)+Rt10(1-Pm)Pm+Rt01(1-Pm)Pm+Rt00PmPm,(5)
Pt+110=Rt10(1-Pm-Pm)+Rt11(1-Pm)Pm+Rt00(1-Pm)Pm+Rt01PmPm,(6)
Pt+101=Rt01(1-Pm-pm)+Rt11(1-Pm)Pm+Rt00(1-Pm)Pm+Rt10PmPm,(7)
Pt+100=Rt00(1-Pm-Pm)+Rt10(1-Pm)Pm+Rt01(1-Pm)Pm+Rt11P2m.(8)
ùʽ(5)(8)ԸСƭ,ͼ2ʾ.
 
ʼP000=0.8,P010=0.0,P011=P001=0.1
ͼ2СƭʹôɵGAֵⷨ
ͼ1ͼ2ıȽϿԿ,Сƭ,ڱȽѵĳʼǰ,δʹÿɵӵGAܿ00ʹ˿ɵӵGAܹ˳11.رڽ,ɵܹʼձȺ4ģʽһGAܵƭġԻ,Ѹ̭3ģʽ.
ڸ,಻ͬĳʼӦֵԹ۲쵽ƵĽ.ҪڳʼȺдͨӽŻĽṹ,Ӧֵ,ʼ.,ȲɵӲ,ĳַģʽȺ,GA.
4ʵ
ͨÿɵӵGAԵ1ڸȫƭʵ,һ˵˿ɵӵ.Сƭи㷺Ĵ,Ϊʹÿɵ,ͨĳʼȺͻʹGA000;ʹ˿ɵԺ,ȫƭ,˳111.нͼ3ʾ.ͼе߱ʾһGAеĽ,ʵʾʹ˿ɵӵGAн.


ͼ3ȫƭ
ĻڱӼƭص,оνGAƭ,˾зԺͿɱʵĿɵ˼,СƭȫƭΪ,ʾ˿ɵӵЧ.
ͨо,ÿɵ,ЧŴ㷨еƭ,ȺĶ,ʹŴ㷨ܹ˳ȫֵŽ,ֿɵķΪGAƭṩһֶ.
߽ܣ,Ů,1969,ʿ,ҪоΪŻ,ֵ.
,1969,ʿ,ҪоΪ,ѧϰ.
,1936,,ҪоΪźŴۡ㷨Ӧ.
,1943,,ʿʦ,ҪоΪӾ,ģʽʶ,˹.
ͨѶϵˣ,Ϸ 230009,Ϸʹҵѧ315
ߵλơ͡ɡϾѧѧϵϾ210093
ࡡϷʹҵѧ˹оϷʡ230009
ο
1Holland J H. Adaptation in Nature and Artificial Systems(2nd ed.). Cambridge: MIT Press, 1992
2Goldberg D E. Genetic Algorithm in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989
3ݳ¹,㷨,ׯȪ.Ŵ㷨Ӧ.:ʵ,1996(Chen Guo-liang, Wang Xu-fa, Zhuang Zhen-quan et al. Genetic Algorithm and Its Applications. Beijing: People's Post and Telecommunications Press, 1996)
4Goldberg D E, Bridges C L. An analysis of a reordering operator on a GA-hard problem. Biological Cybernetics, 1990,(62):397405
5ޱ,,.Ŵ㷨о.ѧ,1996,19(10):794797(Wang Li-wei, Hong Yong, Hong Jia-rong. On the convergence of genetic algorithms. Chinese Journal of Computers, 1996,19(10):794797)
6Goldberg D E. Computer-aided gas pipeline operation using genetic algorithm and rule learning Ph.D. Thesis. University of Michigan, 1983
7Michael D V. Generalizing the notion of schema in genetic algorithms. Artificial Intelligence, 1991,50(3):385396
8A C++ Genetic Algorithms Library. Available online at http: lancet.mit.edu/ga/
1997-11-04յԭ,1998-02-11յ޸ĸ 
