生物地理学优化算法综述_王存睿

37720107ComputerScienceVol.37No.7July2010:2009-10-13:2010-01-11(60573124),(20072197),(20060146)(1980-),,,,,E-mail:[e-mail]1,2112(大连民族学院非线性信息技术研究所大连116600)1(东北大学系统科学研究所沈阳110004)2生物地理学(Biogeography)是一门研究自然界种群迁移机制的科学,DanSimon用生物地理学的方法和机制来解决工程优化问题,提出了生物地理学优化算法(BBO,Biogeography-BasedOptimization)生物地理学优化算法以其独特的搜索机制和较好的性能在智能优化算法领域得到了广泛的关注对生物地理学优化算法的设计原理迁徙模型算法流程及相应迁移和突变操作进行了综述通过BBO算法在14个基准函数下与传统算法,如遗传算法蚁群算法和粒子群等优化算法的性能比较,表明生物地理学优化算法是有效的论述了算法与传统优化算法之间的差异以及BBO算法有待解决的问题优化算法,生物地理学优化算法,智能优化TP18ASurveyofBiogeography-basedOptimizationWANGCun-rui1,2WANGNan-nan1DUANXiao-dong1ZHANGQing-ling2(TheResearchInstituteofNonlinearInformationTechnology,DalianNationalitiesUniversity,Dalian116600,China)1(TheResearchInstituteofSystemScience,NortheasternUniversity,Shenyang110004,China)2AbstractBiogeographyisthestudyofthegeographicaldistributionofbiologicalorganisms,Prof.DanSimontookthemechanismtoresolveengineeringproblems,andproposedanewoptimizationalgorithmnamedBiogeography-BasedOp-timization(BBO).BBOalgorithmhasawideattentionbyitsuniquesearchmechanismandgoodperformance.Weover-viewedtheBBOsnaturalmechanism,themathmodelofBBOmigration,theprogressofBBO,migrationandmutationoperationofBBO.WelistedtheresultsofBBOtestsonasetof14standardbenchmarksandcompareditwithGA,ACO,andPSOetctoproveitsgoodperformance.ThispaperalsodiscussedthedifferenceofBBOwithtraditionalopt-imizationalgorithmsandthefutureproblemsofBBO.KeywordsOptimizationalgorithm,Biogeography-basedoptimization,Intelligenceoptimization1,,,[1][2][3]AlfredWallace[4]CharlesDarwin[5]19,2060,[6],2.5,DanSimon2008IEEETransactionsonEvolution-aryComputation(BBO,Bioge-ography-BasedOptimization)[7](BBO),21,[8],(HIS,HabitatSuitabilityIndex)[9]HSI,SIV(SIV,SuitableIndexVector),SIVs(SuitableIndexVariables)1BBOHSIHSI34HSI,,HSI,HSI,,,,,HSI,HSI,HSIHIS,,,HSIHSIBBO,41)SIV,;(HSI)SIV,HIS,2)HSI,HSIHSIHSI,HSIHIS,3)BBO,,,2BBO2,[6],s,,(s)(s)2[6]2(s)I,s=0,,,,s=Smax,(s)0(s),0,(s)=0,,,,(s)s=Smax,(s)=E(s)=(s),S0,,S0,S0,,,;S0,[4,6]2(s)(s),,,,s,(s)(s)ss,sPs,(1)Pstt+tPs(t+t)=Ps(t)(1-st-st)+Ps-1s-1t+Ps+1s+1t(1)(t+t)s,:1)t,s,t(t+t);2)ts-1,1;3)ts+1,1tt0,(1),(2)Ps=-(s+s)Ps+s+1Ps+1,s=0-(s+s)Ps+s-1Ps-1+s+1Ps+1,1sSmax-1-(s+s)Ps+s-1Ps-1,s=Smax(2)n=Smax,P=[P0Pn]T,P:P=AP(3)A(4):A=-(0+0)1000-(1+1)2n-2-(n-1+n-1)n00n-1-(n+n)(4)2,k,:k=Eknk=I(1-kn)(5)2,E=I,(6),:k+k=E(6)A(7):35A=E-11n00nn-12n2n-1nn001n-1=EA(7)[7]A0,(8),ceil()v=[v1vn+1]vi=n!(n-1-i)!(i-1)!,(i=1,,ceil(n+12))vn+2-i,(i=ceil(n+12)+1,,n+1)(8):n,(9):P(n)=[P(s1)P(sn)]=vn+1i=1vi(9)n=10,P(10)=[0.0010.0010.0440.1170.2050.2460.2050.1170.0440.0010.001],33n=103,10,,,,3(BBO)[7],n,D,xi=(xi1,xi2,,xiD),i=1,2,,nDif(xi)Pmodmmaxisi,sif(xi),siSmax;si(5)(si)(si),(2)isiP(si)3.1BBO:Step1BBO,nDSmax;IEmmaxPmodzStep2xi,i=1,2,,nStep3if(xi),i=1,2,,n,isi(si)(si),i=1,2,,nStep4Pmod(n)ii,(si)ixij(D),ixij,(si),kiif(xi),i=1,2,,nStep5(2)P(si)(10),,,m(si)iif(xi)Step6,Step3,3.2BBO(Migration)BBO,,BBO,Smax=n,S(xi)=Smax-i,i=1,2,,n(xii)4s1,s2;s1(s1)s2(s2),s1(s1)s2(s2),,4[3],Pmod[0,1]i,(si)xixij,j=1,,D([0,1],[0,1])xixij,(sk),ki,k[1,n],k,xkxkjxixij,,,,BBO,,BBO;,BBO,,BBO,,363.3BBO(Mutation),,BBO,iP(si),i[1,n],BBO3,,,,,,(10):m(xi)=mmax(1-P(si)Pmax)(10),mmax,,,,,BBO,3.4BBOBBO,BBO(si)i,;,,BBOACO,ACO,BBOBBOPSODE,,,PSO,DE,BBO,BBO4DanSimonBBO,14BBO,7[7]7ACO[2]DE[10-12]ES[13-15]GA[1]PBIL[16]PSO[3,17-19]SGA[20],20,;,11ID名称多级值孤立极值分布定义域1Ackley是否规则302Flwtcher-Powell是否不规则3Griewank是否规则6004Penalty#1是否规则505Penalty#2是否规则506Quartic否是规则1.287Rastrigin是是规则5.128Rosenbrock否否规则2.0489Schwefel1.2否否规则65.53610Schwefel2.21否否不规则10011Schwefel2.22是否不规则1012Schwefel2.26是是不规则51213Sphere否是规则5.1214Step否是不规则200BBO,:Pmod=1;[0,1],1,0.005(BBO,)7[7]50,50232100,3100,2CPUIDACOBBODEESGAPBILPSOSGA11821001461971972321921032101310038549441591779911431621172726965162831102310042.22E71.16E49.70E41.26E62.46E52.82E72.09E610055.02E571558624.23E41.06E45.37E56.35E4100632132621176700828504.81E48570100745410039753642163447013481711102253716428186151610092021003914251666065921101016110022716218426517914611688100290109450086166514212108118137140142177142100131347100250910906278510001091424811230281355132711161100时间3.22.43.32.32.11.02.92.13IDACOBBODEESGAPBILPSOSGA120510017822022432526211421711109527544632197414511003240181576108140446652241100410036602.67E55.47E761981.65E104.05E71090510046513.42E74.69E88.79E52.60E101.13E9487861.64E443248472.50E443781.57E53.51E4100754110050256446679854412382012100418615443269655810393911741344120918620911742100102591095713812495973071001177910037456046812976701421210011921517416123118810413172111527811175151961445100142791065851155530559515801002,BBOSGA1473,SGA,BBO,4,ACO3372CPU,PBIL,BBO85,,DanSimon[7],,;,,;,,;,,,,,,,,5,,BBO,5,,BBO??[1].[M].:,2007[2]DorigoM,StutzleT.[M].,.:,2007[3],,.[M].:2007[4]Wallace.TheGeographicalDistributionofAnimals[M].Bos-ton,MA:AdamantMediaCorporation,2005[5]Darwin.TheOriginofSpecies[M].NewYork:Gramercy,1995[6]MacArthurR,WilsonE.TheTheoryofBiogeography[M].Princeton,NJ:PrincetonUniv.Press,1967[7]SimonD.Biogeography-basedOptimization[J].IEEETrans.Evo-lutionaryComputation,2008,12(6):702-713[8]GilpinHM.MetaPopulat