Finite-time performance analysis for genetic algorithms

PROGRESS IN NATURAL SCIENCEVol. 12 ,No. 12 , December 2002Finite-time performance analysis for genetic algorithms'WANG Ling* and ZHENG Dazhong( Department of Automation , Tsinghua University , Bejing 100084 , China )Received May 17 ,2002 ;revised June 24 , 2002between evolution generation and the quality of the solution found best so far is analyzed. The estimating formulations of the expectationvalue as well as upper bound and lower bound for the evolution generation earliest achieving specific performance are provided.Keywords : genetic algorithm , finite-time performance , earliest achieving time.Performance analysis is one of the important the-space , in which 02 is the search space x∈∩is a so-oretical issues for genetic algorithms( GA{1~6] ,in-lution，f( x ) a bounded objective function andcluding convergence ability ，convergence rate , pa-|f(x )|<∞. Let X( k )be the population in the kthrameter selection and stopping criteria design and sogeneration ( suppose the population size is fixed ason. RudolpHt 21 used Markov chain theory to analyzen ),and let f( X( k ))= minf( x; ) be the objectivethe convergence property of canonical GA , and em-phasized the importance of elitism strategy for globalvalue of the population. The elitist GA studied in thisconvergence. Based on the eigenvalue analysis of thepaper can be described as follows , where" elitist'transition matrix , Suzukf 3] derived a lower bound formeans the best individual that will be reserved andsimple GA. He et al.L4) provided the convergencepassed to the next generation.conditions and convergence rate for generic GA. InStep 1 : Randomly generate initial population ,Ref. [ 1 ], Schmitt systematically reviewed the theoryof GAs. Guo et al.t51 presented a unified method toand evaluate all the individuals.Step 2 : Perform elitist selection.analyze the GAs' convergence. Although there areStep 3 : Repeat the following steps until themany results on convergence analysis , to our knowl-edge there is hardly any result on finite time perfor-stopping criterion is satisfied :( i ) perform elitist mu-mance analysis except for Aytug et al.' s study ontation and elitist crossover separately ,( ii ) evaluate allstopping criteria design of finite length GAL61 Withthe individuals ,( ii ) perform elitist selection.respect to the study on convergence ability with infi-Considering Step 3，essentially it performs anite time ,it is very important to analyze GAs' finite-time performance. In this paper , the finite-time per-probabilistic state transition in every generation ，soformance of elitist GA in finite search space is stud-Markov chain has been widely used to study the con-ied , and the relationship between the evolution gener-vergence of GA. In Ref.[4 ],it was pointed out thatation and the quality of the solution found best so farthe GA is convergent with probability 1 if all the ge-is analyzed. Finally , the estimating formulations ofnetic operators have elitist property and the global op-the expectation value as well as upper bound and low-timum is accessible from any initial population afterer bound for evolution generation earliest achievingfinite probabilistic transitions. Similar to Ref. [ 4 ],specific performance are provided.in this paper we suppose that the GA has such proper-1 Description of the elitist GA and some def-ties中国煤化工equirement on operatorsandinitionsMHCNMHG( onsider a mrnmuzation problem，a-acceptableConsider a minimization problem on finite searchpopulation space is defined as* Supported by the National Natural Science Foundation of China( Grant Nos.60074012 and 60174022 ) , and Basic Research Program of TsinghuaUrverivi,￥* To whotdence should be addressed. E-mail : wangling@ mail. tsinghua. edu. cnProgress in Natural Science Vol. 12 No.12 2002941S。= {X1X∈Q",f(X)≤a}(ii)P{r。= K}= μK a)II[1-Kk a)]Obviously ,if a=f*( best value), there must be op-k=1timal solution in the population of Sa. To considerthe finite- time performance , we define an event asProof. Property( i ) can be proved by the defini-Eq.( 1 ) that means GA can achieve a - acceptable pop-tionofτa.Then,letK=+∞,wecanget(i).ulation within K generations , and its complementaryFurthermore,by P{ta= K }= P{ra> K- 1 }-event is defined as Eq.( 2).P{tx>K }we can get( ii ).E(K ,a)={X; X2- Xk)| Xk∈Q”,Next, we will provide the expectation of Tak = 1.. ,K ,3kXk∈S.}, (1)when P{ra≤K }>0 ,K=1 2...E(K a)={X1 X2 r.. Xk)| Xk∈Q”，Theorem 1. Consider the above GA , given a >k=1..K,VkXptS。}(2)f* ,and P{ra≤K}>0 ,K=1 2... holds ,then :Due to the elitist property of theGA ,E(K ,a )(i)E[ra1 τa≤K]= KSE( K + 1 ,a ) obviously holds. And , the one step{1-I[1- Ki a)]}Ya -acceptable transition probability can be defined asEq.( 3 ), and the minimum generation to achieve a-acceptable population can be defined as Eq.(4 ).{1-T[1- (ke a)]}，pK(Ka)=P{E(K,a)|E(K-1ra)}(i)Var[ ra1 τa≤K]=(K+ 1尸= P{(X1 ,Xz ..Xx)1Xpt S。，k =1. ,K-1 ;Xk∈S。}-之{(2k+1) [1- I[(1-p;)]}yk=0/P{E(K-1 ra )},(3)Ta=min{k≥1|X∈S。}(4 )[1-1[(1-px)]ETr。Iτ.≤K]Proof. For convenience ,denote μk ,a )= Pk.Obviously，the smaller Ta , the faster GA canachieve a -acceptable performance. In the next sec-By the definition of expectation and Property 1 ,tion , the relationship between p( K ,a ) and Ta willwe getbe discussed.E τ。| ra≤K]2 Conditional expectation of Ta and its rela-: 2k. P{ra = k |τa≤K}tionship with one step acceptable probability2k. P{r。= kYP{r。≤K}According to the definition of one step a -accept-able probability.1- p(K a)= P{E(K a)| E(K-1 a)}之k [i(1-p;)- 1(1-p,)]i=1= P{E( K a)}P{E( K- 1 ra )}.Thus，/[1-11(1-px)]P{E'(K a)YP{E(0a)}= [1- f(k a)]Because po=0 ,If GA' s initialization cannot get a -acceptable popula-Zk[i(1-p;)- 1(1-p;)]tion ,i.e. P{E(0 ra )}=0 , then= 1-1[(1- p;)+2H[(1- p;)P{E(K xa)}= 1-1[1- μ(k a)]We keep this supposition in this paper.2J[(1- p;)+..-KI[(1- p;)中国煤化工Property 1. Consider the above GA ,MHCN MHG)- kI[(1- p;)k=1 i=1(i)P{ra> K}= 1[1- p(k a)]: P{E'(K ,a)};= K[1-1[(1-p;)](i)务务数据∞}= 1- T[1-μk a)];- 2[1- I(1- p:)]942Progress in Natural Science Vol. 12 No. 122002Thus ,( i) is proved.m(k )+j};Because(v)P{m( ta)=m(k )}= P{ta≤K: m( k )}-Va[ τa1 τa≤K]=E[ τ2 | ra≤K]P{ra≤K[ m(k)- 1 ]};ETτo 1 τa≤K],(vi)P{ta>K m(k )}≤P{ra>k}≤P{ta>to prove( ii),it only needs to prove that E[ τ2lτa≤K[ m( k )-1]}.K ]equals the former half part of( i).Proof. If ta=k , then m( τa )= m(k ). Butr21 τa≤K]conversely ,if m( Ta )= m( k ), then Ta may equal=k2. P{ta= k1τ。≤K}several values. So ,( i) holds.k≈0By the definitionof m( τo ),= 2ktP{ra≤k}- P{ra≤k-1}]P{m( ta)> m(k )}=P{X;∈S。;i=12...,Km(k)}/P{τ≤K}=P{ta>Km(k)}:=.{2jk?P{ro≤k}- 2(k+ 1)P{ra≤k}So ,( i) holds.From(i), V j≥0 ,+(K+ 1YP{rg≤K}P{t≤K}P{X;∈S。i=12.,Km(k)}=(K+ 19- >[(2k+ 1)P{r.≤k}]k=0≤P{X;∈S。i=12..,Km(k)-j}/P{τa≤K}= P{r。 > Km(k )- j},so( ili ) holds. Similarly ,( iv ) holds.=(K+1}- 2{<2k+1)[1-I[(1-p)]}P{m( ta)= m(k )}=P{m( Ta )≤m(k )}P{m( ta)≤m(k )- 1},[1-(1-px)](v ) holds because of(i)Because[ m( k )- 1 ]K Km(k)}= II(1- p;)≤P{r。> k}the whole evolution process into several sub-stages ,KTm(k)-1]where each sub stage includes K generations. Thus ,= HI(1- p;)≤II (1- p;)the sub-stage number of kth generation is m( k )=k/K, where x means the smallest integer= P{ra> K[ m(k )- 1]}.greater than or equal to x. And the first sub-stageSo ,( vi ) holds.achieve a -acceptable population isTheorem 2. Consider the above GA ,m( ta)=min{m( k )1 m(k )≥1 ,Km(k )≥Ta ，k = 1 2...}= r。/KEm(τ。)]= 211(1-p;)k=i =1Obviously ,[m(ta)-1]K k}(i)P{ra=k}≤P{m( r。)= m(k )};中国煤化工Thu.MYHCNMH Gerty2,(ii)P{m( ta)>m(k)}= P{ra>K m(k )};ET m(τ.)]=乙P{r。> kK}(ii)Vj≥0 P{m( to )>m(k)K≤P{ta> Km(k )-j };2c1-p;).k=1 i=1(iv )瓦市数据P{m( t。)>m(k )}≥P{to> K:Progress in Natural Science Vol. 12 No. 122002943Theorem 3. Consider the above GA ,Theorem 4. Consider the above GA,if p(k ,a)1+K.(E[m(ra)]-1)≤E(ra)= pa=p ,then≤1+K.Em(t。)]1+ K. P{ra> KYP{r。≤K}< Eτ。]≤1 + K/P{τa≤K}.Proof. Since Ta is a non- negative integer ,Moreover , based on the conditional expectationE[τ。]= 2P{r.> k}= 1+ ZP{t。> k}:in Section 2 , we get another estimating bound forBy Property 2 ,E[ ta]耳rτa]≤1 + 2P{r。> K[ m(k)- 1]}.Theorem 5. Consider the above GA,if p(k ra )k=1= Pk=p ,then .MoreoverVk = K(j-1)+ 1，K(j- 1)+2.. ,Kj，LB= ETτa1 τa≤K ]P{ra≤K}+[1 + K/P{τa≤K }]P{ta > K }P{ra> Km(k )}= P{ra > Kj },≤E[ τa]≤UBso= E[ta1 ta≤K ]P{rg≤K }1 + 2P{ta> K[ m(k)-1]}+[K+ 1 + K/P{ta≤K}} P{ta > K },and .= 1+ >K. P{ra> K(k-1)}Va[ ta]≤K{P{ra> K}+ 1)/( P{t。≤K}}-( LB).=1+K2P{m(Ta)>k}Proof. From the law of total probability ,=1+K.E{m(ta)}:E[ ta]=E[τa | τa≤K ]P{ra≤K }+ ETτa1 ta> K]P{r。> K}Similarly ,1 + K ( E[ m( τa)]- 1 )K≤E( Ta )canSince τa is a non- negative integer ,be proved.Obviously , Theorem 3 provides the upper andEτa1ta>K]P{ta>K}lower bounds for the expectation of Ta ,but it is not= 2P{ra>k1 ta> K}P{r.> K}computable because the formulations contain infinitesummations. So，we continue the next discussion.ZP{ra>k r。> K}4 Further discussion on the expectation of Ta=(K+ 1)P{r.> K}+ 2 P{ra> k}:Theoretically , GA can be formulated as a sta-tionary Markov chain whose one step probabilityDividing the stage from( K + 1 )th generation to +∞transition matrix is constant21. So , we also supposeinto several sub-stages with K generations in eachthe one step a -acceptable transition probability issub-stage , the above equation can be rewritten as( Kfixed ,i.e. p(k ,a )=pk=p ,thus. + 1)P{ta> K}+ 2乙P{to> kK + i}. Then,P{m(ta)=l}=P{l-1)K+1≤ta≤lK}by Property 2 ,it is true that the above equation is not= P{ta≤lK}- P{ra≤(l - 1 )K}less than= 1-I(1-p)-1+ (1- p)( K + 1)P{ra> K}k= 1=(1- p)(1-1[1-(1- p]P{m(ra)> m(kK + j)}Since中国煤化工<}P{r。≤K}= 1- I[(1-p)=1-(1-p义,MHCNMHG>k+1}m( Ta ) is subject to geometric distribution with pa-=(K+1)P{ta>K}+K(Em(ta)]rameter P{ta≤K } It is well known that the expec-tationof m( Ta )is 1/P{ta≤K }and its variance isP{m( ta)> 1}- 1).1/P{ta≤K }( 1/P{ra≤K}-1) So, we get The-Because m( Ta ) is subject to geometry distributionorem 4 wthou拥inite summations as follows.with parameter P{ta≤K }and by Property 2 ,it is944Progress in Natural Science Vol. 12 No. 122002true that the above equation equals=(1 + P{ra > K})(P{ra≤K}P.(K+1)P{t。>K}+K[1/P{τa≤K}So , the upper bound of Va[ τa ] holds.P{t。> K}- 1]Since Ki a)=p,=P{ta>K}-K+K/P{t。≤K}P{ra≤K}= 1-(1- p火,= P{r。> KE1 + K/P{r。≤K }]P{ta> K}=(1- p火,Thus , the lower bound holds.ET ta1 ta≤K]Similarly ,= K-2[1-(1-pYM1-(1-pV]耳Ta | ra> K]P{ra> K}k=1= K +1/p- K/[1-(1- p火]=(K+ 1)P{t.> K}+ 2ZP{t.> kK+ i}Thus , the upper and lower boundsof ET Ta ] and thek=1 i=1upper bound of Var[ Ta ] can be calculated based on≤(K+ 1)P{r。> K}+ kZP{m(t)> k}a ,p and K. And it can be proved that the bounds=(K + 1)P{ra> K}+ K(E[m(ta)]- 1)provided in Theorem 5 are tighter than those in The-orem 4 ,and it can provide good estimating results if=(K+1)P{ta>K}K is set big enough.+ K(1/P{ta≤K}- 1)[K+ 1 + K/P{ta≤K}]P{t。> K}Lastly , we have to point out that our theoreticalSo , the upper bound holds.work needs further research and extension , especiallyfor application. In particular ,just like the fact that inBecause Va[ ta]= E[ τ2]- ET Ta ]and by themany existing results on estimating convergence ratelower bound of E[ ta ], to prove the upper bound ofthe eigenvalue of the transition matrix may be un.Va[ τa ],it only needs to prove thatknown , the valueof p in this paper may be unknownE[ ζ]= K(1 + P{t。> K})(P{ta ≤K}9.or not fixed. So , the above theoretical result may bebiased, and when studying real problems , it needsEξ]= 2k2P{t。 = k}many random Monte Carlo simulations to get goodmeasure of p. Meanwhile , for an unsolved problem ,: Zk2P{m(τ.)= m(k)}the optimal value is unknown beforehand. So we cancarry out certain simulations to roughly observe theZ(2[<(m(k)-1)+ifperformance , and then determine reasonable value formdk)=1 i=1a to study the finite-time performance of the GA.P{m(τ.)= m(k)})The further research is to intensively study thebound , and carry out numerical simulation based onreal optimization problems to check the theoretical re-≤2(2[K(m(k)- 1)+K]二1sults , such as scheduling problems7].P{m(ra)= m(k)})References2(2.: Km(k)FP{n(t。)= m(k)})1 Schmitt ,L. M. Theory of genetic algorithms. Theoretical Com-mk)=1 i=1puter Science ,2001 ,259( 1/2):1.Rudolph ,G. Convergence analysis of canonical genetic algorithms.= 2 Ktm(k)}P{m(τg)= m(k)}IEEE Transactions on Neural Networks ,1994 ,5( 1 ):96.Suzuki J A Markov chain analysis on simple genetic algorithms.= K3>kZP{m( ta)= k}IEEE Transactions on Systems , Man , and Cybernetics ,1995 ,25 :655.rrates of genetie lgrthms. The= K3E[ {m( t.)} ]中国煤化工29 :23.-ethod analyzing convergence ofBecause m( Ta ) is subject to geometry distribu-MHCNMH Gmy d Aliaig , 200018( 3 ):443.tion with parameter P{ta≤K },) Ayug,H. et al. Stopping criteria for finite length genetic algo-E[{m(ta)}]=Va[m(Ta)]+(E[m(τa)]尸rithms. INFORMS Journal on Computing , 1996 ,82):183.= 1/P{r。≤K} (1/P{r。≤K}- 1)7 Wang,L. et al. An effective hybrid optimization strategy for jobshop scheduling problems. Computers and Operations Research ,万市敞握r。≤K}2001 ,28 6 ):585.