基于GA的网络最短路径多目标优化算法研究

247Vol.24No.7ControlandDecision20097Jul.2009:2008208228;:2008212230.:(60772109).:(1982),,,,;(1963),,,,,.:100120920(2009)0721104206GA,(,100876):(GA),GA.,.,,.:;;;;:TN967.2;TN929.5:AResearchonmulti2objectiveoptimizationforshortestpathalgorithmbasedonGAYANXiao2tian,WUMu2qing(SchoolofInformationandCommunicationEngineering,BeijingUniversityofPostsandTelecommunications,Beijing100876,China.Correspondent:YANXiao2tian,E2mail:[e-mail])Abstract:Thesinglenessoftheoptimizationobjective,poorperformanceofgeneticrepresentation,unbalancebetweensearchingstrategies,andlowefficiencyoffitnessassignmentaremainproblemsoftheconventionalshortestpath(SP)geneticalgorithms(GA).Therefore,anadaptiveSPmulti2objective(MO)GAisproposed.Priority2basedgeneticencodingandpriority2indexedcrossoverareintroduced.Fuzzylogicbasedgeneticoperatoradaptationandadaptiveweightfitnessassignmentmethodsaredesigned.SimulationsofthemodelbasedonvariousscaleofnetworkseffectivelyshowthatthehighrequirementofSPproblemiswellfulfilledwithhighaccuracyandstabilityoftheproposedMOGA.Keywords:Shortestpath;Multi2objectiveGA;Priorityencoding;Fuzzycontrol;Priorityindexedcrossover1[1],,[124].NP2Hard[1,2].,[426];.,,[1,2].,,,,[2,3,5].,.,,;,,,;Pareto,.,,,.7:GA2G=(V,E).V={p}(p=1,2,,n)n;E={(sq,tq)}(q=1,2,,m)m.(sq,tq)E,(sq,tq)cq(cq0)dq(dq0).st,ctotdtotRs,s,t,021[123]:minctot=ti=stji,j=scijxij,(1)mindtot=ti=stji,j=sdijxij.(2)s.t.tj=s,jixij-tk=s,kixki=1,i=s;-1,i=t;0,is,it;(3)xij=1,(i,j)Rs;0,(i,j)|Rs.(4):(3),Rsst,i:nj=1xij=nk=1xki.(4)xij(i,j),(i,j)Rs,Rs(i,j),xij=1;xij=0.33.1,[2,7].(),,,.11(),,,,.,.(locus),(allele).,12.2.1,(s=1)2,3,4;111/2222,2,3,4310.3s.,63.,(t=11),(1365811).,1.,:1);2);3),.,,,.,().1mnnO(mlogm)O(nlogn)O(nlogn)11n1n13.2.:(PMX)(OX)(PX)[1,7].,501124,,.,(PIX).3.31.v1v21r1r2.v1v2PIX:1)n(n=11)p;2)v1,v2ps1,s2,v1,v2;3)s1,s2(),s1,s2;4)(3),v1,v2s2,s1,v1,v2.v1,v2r1,r2.3.,,PIX,,.,,.3.3[1].()!-1,N,N.,[1].,,.3.4.;,.,.,,,,;,,.,[1,8].[1,9]..,.,,.:pc,pm,pi,u,pm,pc,pi,,,;pc,pi,pm,.tsizeP,sizeC,ifipar(t),fichi(t),fpar(t),fchi(t).tf(t)=fpar(t)-fchi(t)=1sizePsizePi=1fipar(t)-1sizeCsizeCj=1fjchi(t).(5)pm,pc4,pm,pc,pi60117:GA[1,5,8]pm=0.2,f(-,];0.2+m(f-),f[,2u-];0.8,f|[2u-,+).(6)pc=0.8(1-pm)-c(f-),f[,2u-];0.8(1-pm),f|[,2u-].(7)pi=1-(pc+pm).(8)m,c,fm=0.12u-1-,[0,2u-2];(9)c=0.4(1-pm)2u-1-,[0,2u-2];(10)f=ui=1{2t-i-1[sgn(Šf(t-i))+2]},tu.(11):uu1;uu=2,=0.5.u.u,,,,;,,.,(),,.4pm,pc3.5:Pareto[10,11].1,.1,[1,10,11].,.z1,z2,,zq(,q=2,z1,z2).Pvifi(v).Pz+z-:z-={zmin1,zmin2,,zminq},(12)z+={zmax1,zmax2,,zmaxq}.(13)vzizmaxizmini:zmaxi=max{fi(v)|vP},i=1,2,,q;(14)zmini=min{fi(v)|vP},i=1,2,,q.(15)(12)(15),z+z-.(14),(15)iwi=1zmaxi-zmini,i=1,2,,q.(16)(14)(16),Pz(v)=qi=1wi(zmaxi-fi(v)),PvP.(17)(17)p(v),vp(v)=0;p(v)=1.PvFP(v)=z(v)+p(v)=qi=1zmaxi-fi(v)zmaxi-zmini+p(v),PvP.(18),,.4:P41.7GHzCPU,512MBRAM,Linux.PythonScipy.50.[12]100,200,5006,2.:n,m,;unif,2nm(c)(d)1100955unif(m,10,50)unif(m,5,100)2100959norm(m,50,10)norm(m,50,5)32001971norm(m,50,10)norm(50,5)42002080lnorm(m,1,1)lnorm(m,2,1)55004978norm(m,50,10)norm(m,50,5)6500486810exp(m,0.5)10exp(m,2)701124norm,lnormexp.:1000,200.4.1(q=1),[2]:(20),,Dijkstra3.3(priority)(var2len)pc=pm=0.3var2lenprioritypc=pm=0.5var2lenpriority142.7542.7542.7542.7542.752218.53359.62242.47232.93224.913254.45308.27292.71288.14260.5841.723.442.552.502.165337.57390.44372.19642.6392.5177.473,.3,,.4.24.1,,.64.34,,.,21(30),pcpm,5.412345642.75223.07275.261.98366.2472.3154.3(AW),,Pareto,Pareto(SP)(RW)(NS)[10,11]3,5.5,AWPareto,.5SPRWNSAWParetoSPRWNSAW11.641.631.71.840.000.000.000.0025.004.905.185.740.100.170.231.1031.741.551.401.960.160.150.230.1144.164.093.854.330.400.390.430.0952.612.492.372.611.170.690.750.5465.826.126.046.250.170.170.150.154.4(PIX)(PMX,PX,OX)(HM,IM)(IO)[1,7],7,6.6,726.50,6.6,(PIX+HM+IO)50,26,.5,:1),,80117:GA..2).,.3),,.,Ad2hoc.(References)[1]GenM,ChengRW,LinL.Networkmodelsandoptimization[M].London:Springer2Verlag,2008:30282.[2]AhnCW.Ageneticalgorithmforshortestpathroutingproblemandthesizingofpopulations[J].IEEETransonEvolutionaryComputation,2002,6(6):5662579.[3]WenHY.Geneticalgorithm2basedcomputationofshortestpathindiscrete2timenetworks[J].JofSouthChinaUniversityofTechnology,2008,36(2):13216.[4],.[J].,2006,11(3):4192424.(ChenJ,LuF.Anoptimizationalgorithmofpallottinoimplementedwithtwoqueuesintransportationnetwork[J].JofImageandGraphics,2006,11(3):4192424.)[5],.[J].,2008,23(1):79282.(LiQ,ZhangW.Anewadaptivealgorithmforregulatingtheprobabilitiesofcrossoverandmutation[J].ControlandDecision,2008,23(1):79282.)[6],.A3[J].,2007,19(22):517525177.(LiDW.ConverselyimprovedA3routealgorithm[J].JofSystemSimulation,2007,19(22):517525177.)[7]RetvariG,BiroJ.Onshortestpathrepresentation[J].IEEETransonNetworking,2007,15(6):129321306.[8]WangY,CaiZX.Anadaptivetradeoffmodelforconstrainedevolutionaryoptimization[J].IEEETransonEvolutionaryComputation,2008,12(1):80292.[9]WhitleyD,GordanV.Lamarckianevolution,baldwineffectandfunctionoptimization[M].Berlin:Springer2Verlag,1994:1332152.[10]ZitzlerE.Improvingstrengthparetoevolutionaryalgorithmformulti2objectiveoptimization[C].ProcoftheEUROGENC