遗传算法时间复杂性的研究-戴晓晖

①戴晓晖②　李敏强　寇纪淞(,300072)　　　遗传算法的时间复杂性是目前研究的焦点之一.本文以模式生存的概念为基础,将模式风险函数引入遗传算法的分析中,建立了一种随机可靠性模型,分析了遗传算法的时间复杂性.:,,,:N94THESTUDYONTHETIMECOMPLEXITYOFGENETICALGORITHMSDaiXiaohui　LiMinqiang　KouJisong(InstitueofSystemsEngineering,TianjinUniversity,Tianjin300072)Abstract　Inpresent,theoneoftheresearchfocusesongeneticalgorithmisthetimecomplexityofgeneticalgorithm.Webaseonthenotionofschemasurvival,drawthenotionofschemahazardfunctionintotheanalysisofgeneticalgorithm,setupastochasticreliabilitymodel,andanalyzethetimecomplexityofgeneticalgorithm.Keywords:geneticalgorithms,schema,reliability,timecomplexity0　　(geneticalgorithm,GA),MichiganHolland1975[1],,,,,、、.,,[2,3],:(1);(2)Holland;(3)[4,5,6]..,,,.14119993　　　　　　　　　　　　　JOURNALOFSYSTEMSENGINEERING　　　　　　　　　　　　　　Vol.14No.1Mar.1999①②,.male,doctoralstudent.199855.(79400013,69574022).1　,“”,H,rH,r.,r.,r1,r=2,3,4….tHmH(t),mH(t)fH.,,ifi/∑Nj=1fj,N.　　psH,　　　　　ps=∑mH(t)i=1(fi)∑Nj=1fj=mH(t)fH∑Nj=1fj(1)N,HmH(t)RHHN-mH(t)RH.N.,Hps,H1-ps,HN　　　　　Nxpxs(1-ps)N-xxRH.,,.　　　　　psurv=1-pcW(H)L-1-o(H)pm(2)pc、pm、L、W(H)H、o(H)H.,j(x)、　　　　　　　　　　xjpjsurv(1-psurv)x-j,rH　　　　　∑Nj=r∑Nx=jNxpxs(1-ps)N-xxjpjsurv(1-psurv)x-j,r-1　　　　　1-∑Nj=r∑Nx=jNxpxs(1-ps)N-xxjpjsurv(1-psurv)x-j,Ht,t+1.Z(t)Δt,Z(t)“”[7],Δt,Z(t)ΔtHt,Δt.,,Δt=1,　　　　　Z(t)=1-∑Nj=r∑Nx=jNxpxs(1-ps)N-xxjpjsurv(1-psurv)x-j(3)　Z(t)∈[0,1],(t=0),Z(t).Holland[1,8],　　　　　mH(t+1)=mH(t)fHfpsurv(4)fHHt,ft.fH=(1+c)f,c—74—　　　　　　　　　　　　　　　14　1,mH(t+1)=mH(t)(1+c)psurv.　　　　　mH(t+1)=mH(0)(1+c)t+1pt+1surv(5)(5)(1),(),t→∝,ps→0,Z(∝)→1;,t→∝,ps→1,Z(∝)→1-∑Nj=rNjpjsurv(1-psurv)N-j.(1)、(4)(5)　　　　　　　　　　ps=k1kt(6)k1=(1+c)mH(0)N,k=(1+c)psurv.(6)(3)　　　　　Z(t)=1-∑Nj=r∑Nx=jNx(k1kt)x(1-k1kt)N-xxjpjsurv(1-psurv)x-j(7)　　　　　N(N-x)!j!(x-j)!(1-k1kt)N-x(k1ktpsurv)j(k1kt-k1ktpsurv)x-j.N、1-k1ktk1ktpsurv、N(1-k1kt)Nk1ktpsurv,[9],　　　　　e-N(1-k1kt+k1ktpsurv)[N(1-k1kt)]N-x[Nk1ktpsurv]j((N-x)!j!-1=p(t)(8),H　　　　　　　　　　Z(t)=1-e-λ(t+h)(9)λ、h,N、pc、pm、rHλh　　　　　　　　　　Eλ=0,Eh=0E=∑i{Z1(ti)-Z2(ti)}2,Z1(ti)=1-∑Nj=r∑Nx=jp(ti),Z2(ti)=1-e-λ(ti+h).t,.2　X,,　　　　　Z(t)=Prob(tXt+Δt|Xt)=Prob(tXt+Δt)/Prob(Xt)=(Prob(tXt+Δt)-Prob(Xt))/Prob(Xt)(10)HR(t)t,　　　　　R(t)=Prob(Xt)=1-Prob(Xt)(11)　　　　　Z(t)Δt=(R(t)-R(t+Δt))/R(t)(12)　,Δt=1.(9)　　　　　R(t+1)=R(t)e-λ(t+h)(13)t=0,1,2…,,　　　　　R(1)=R(0)e-λh　　　　　R(2)=R(1)e-λ(1+h)=R(0)e-λhe-λ(1+h)=R(0)e-λ(1+2h)　　　　　R(3)=R(2)e-λ(2+h)=R(0)e-λ(1+2h)e-λ(2+h)=R(0)e-λ(3+3h)　　　　　…—75—19993　　　　　　　　　　　:,　　　　　R(t+1)=R(0)e-λ(t(t-1)/2+th)(14),,.R(0)=1(),　　　　　R(t+1)=e-λ(t(t-1)/2+th)(15),R(∝)=0.3　Mt=0,MR(t),1-R(t).Q(t)t,Q(t)　　Prob(Q(t)=q)=(M!/(q!(M-q)!)[R(t)]q[1-R(t)]M-q　　q=1,2,…,M(16)t,,MR(t).,.MR(t)=0T.yiyf.Tyf,　　　　　　　　　　yiR(T)=yf(17)(15)T=0.5(1-2h+(2h-1)2-(8/λ)ln(yi/yf))(18)T.4　4.1　5[10,11]:　　1)F1(xi|i=1,2,3)=∑3i=1xi,-5.12≤xi≤5.12;2)F2(xi|i=1,2)=100(x21-x2)2+(1-xi)2,-2.048≤xi≤2.048;3)F3(xi|i=1,…,5)=∑5i=1integer(xi),-5.12≤xi≤5.12;4)F4(xi|i=1,…,30)=∑30i=1x4i+Gauss(0,1),-1.28≤xi≤1.28;5)F5(xi|i=1,…,25)=0.002+∑25i=11j+∑2i=1(xi-aij)6,-65.536≤xi≤65.536、　　　[aij]=-32-1601632-32-16…01632-32-32-32-32-32-16-16…323232;5:;;;;;.4.2　,5.:N、pc、pm,50,100,(H,mH(0)).50Z(t).,R(t).—76—　　　　　　　　　　　　　　　14　1H,:　　　　　Z(t)=(S(t)-S(t+Δt))/S(t)ΔtS(j)Hj,(R(t)=S(t))/S(0).,mH(0)(1+c),Z(t)(7).,N=50,100,200,300,500;pc=0.6,0.7,0.8,0.9,1.0;pm=0.001;r=2,3,…,10.,(1-5).1　F1(N=300,pc=0.6,r=4):11*...*811*...*811*...*8　　　　　　　　　　2　F2(N=100,pc=0.8,r=2):0000*...*80000*...*83　F3(N=300,pc=0.6,r=2):11*...*811*...*811*...*81*...*91*...*9　　　　　4　F4(N=100,pc=0.8,r=2):000*...*5...000*...*5304.3　1-5,,,:(1);(2),,.,,,.,(1).—77—19993　　　　　　　　　　　:5　F5(N=100,pc=0.8,r=2):*...*171111*...*131　　　rN1+cpcmH(0)()()F10...07***000*...*1782000.7910.81608.5498.440F20...05*...*70...05*...*742000.6990.81905.2615.395F31...15*...*51...15*...*35102000.9410.818015.4115.26F40...06**0...06**0...06*...*16242000.8960.8206.9177.255F5*...*1711*...*1521000.4790.8425.7015.665:,yf/yi=0.0000001.5　,,,.,.1　HollandJH.Adaptationinnaturalandartificialsystem.AnnArbor:TheUniversityofMichiganPress,19752　,　.(Ⅰ)—.,1995;(2):1～133　FogelDB.Anintroductiontosimulatedevolutionaryoptimization.IEEETrans.onNeuralNetworks.1994;5(1):3～144　AsohH,MuhlenbeinH.Onthemeanconvergencetimeofevolutionaryalgorithmswithoutselectionandmutation.Paral-lelProblemSolvingfromNature(Proceedings),19945　GoldbergDE,SegrestP.FiniteMarkovchainanalysisofgeneticalgorithms.Proceedingsofthe2ndInternationalCon-ferenceonGenticAlgorithms,1987.1～86　AnkenbrandtCA.Anextensiontothetheoryofconvergenceandaproofofthetimecomplexityofgeneticalgorithms.in:G.J.E.Rawlins,ed.,FoundationsofGenet2icAlgorithms,1994.53～587　TrivediKS.Probabilityandstatisticswithreliability,queuingandcomputerscienceapplications.NewDelhi:Prentice-Hall,19888　GoldbergDE.Geneticalgorithmsinsearch,optimizationandmachinelearning.MA:AddisonWelsey,19899　FellerW.Anintroductiontoprobabilitytheoryanditsapplications.WileyEastern,Calcutta,3rded.,1968;110　WhitleyD,MathiasK,RanaS,DzuberaJ.Buildingbettertestfunctions.Proceedingsofthe5thInternationalConfer-enceonGeneticAlgorithms,1995;239～24611　DeJongK.Ananalysisofthebehaviorofaclassofgeneticadaptivesystems.PhDthesis,UniversityofMichigan,D