您好,欢迎访问三七文档
当前位置:首页 > 建筑/环境 > 工程监理 > 遗传算法时间复杂性的研究-戴晓晖
①戴晓晖② 李敏强 寇纪淞(,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
本文标题:遗传算法时间复杂性的研究-戴晓晖
链接地址:https://www.777doc.com/doc-5280243 .html