第40卷第11期計(jì)算機(jī)科學(xué)Vol. 40 No. 112013年11月Computer ScienceNov 2013種群動力學(xué)優(yōu)化算法黃光球李濤陸秋琴(西安建筑科技大學(xué)管理學(xué)院西安710055)摘要為了快速求解大規(guī)模復(fù)雜優(yōu)化問題基于種群動力學(xué)理論構(gòu)造出了可全局收斂的種群動力學(xué)優(yōu)化算法。在該算法中,每個(gè)種群對應(yīng)著優(yōu)化問題的一個(gè)試探解,種群的一個(gè)特征對應(yīng)于試探解的一個(gè)變量;采用正交拉丁方原理構(gòu)造出了種群初始值確定方法,以達(dá)到對搜索空間的均衡分散性和整齊可比性覆蓋;將任意兩種群間的競爭、互利、捕食被食、融合、突變和選擇等行為用于構(gòu)造種群的進(jìn)化策略,以使種群的適應(yīng)度指教要么保持原狀不變,要么向好的方向轉(zhuǎn)移,從而確保整個(gè)算法的全局收斂性;在種群演變過程中,種群從一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài),實(shí)現(xiàn)了種群對優(yōu)化問題全局最優(yōu)解的搜索。應(yīng)用可歸約隨機(jī)矩陣的穩(wěn)定性條件證明了本算法具有全局收斂性。測試結(jié)果表明本算法是高效的關(guān)鍵詞進(jìn)化計(jì)算,函數(shù)優(yōu)化,生物地理學(xué)優(yōu)化算法,種群動力學(xué)中圖法分類號TP18文獻(xiàn)標(biāo)識碼APopulation Dynamics-based OptimizationHUANG Guang-qiu LI Tao LU Qiurqin(School of Management, Xi'an University of Architecture& Technology, Xi'an 710055, China)Abstract To solve large-scale optimization problems(OP), a population dynamics-based optimization algorithm withglobal convergence was constructed based on the population dynamics theory. In the algorithm, each population is justan alternative solution of OP, and a feature attribute of a population corresponds to a variable of an altermative solution.The principle of orthogonal Latin squares is used to produce initial values of populations so as to cover search spacewith balance dispersion and neat comparability. The competition, mutual-benefit, predator-prey, mergence, mutation andselection behavior between any two populations are used to construct evolution policies of populations so as to ensurepopulation suitability index(PSDof each population to keep either to stay unchanged or to transfer toward better statestherefore the global convergence is ensured. During evolution process of populations, each population's transferringfrom one state to another realizes the search for the global optimum solution. The stability condition of a reducible sto-hastie matrix was applied to prove the global convergence of the algorithm. The case study shows that the algorithm isKeywords Evolutionary computation, Function optimization, Biogeography-based optimization, Population dynamics2008年, Dan Simon用生物地理學(xué)的方法提出了生物地1引言理學(xué)優(yōu)化算法( Biogeography-Based Optimization,BBO)1)。種群動力學(xué)模型是描述種群與環(huán)境、種群與種群之間相該算法通過種群在棲息地間的遷移實(shí)現(xiàn)了對優(yōu)化問題最優(yōu)解互作用的動力學(xué)關(guān)系的數(shù)學(xué)模型口,可用于描述預(yù)測以至調(diào)的搜索。BBO算法解決優(yōu)化問題主要依賴以下2方面2:節(jié)和控制物種的發(fā)展過程與發(fā)展趨勢。常用的種群動力學(xué)模(1)棲息地的特征向量SV對應(yīng)優(yōu)化問題的試探解;棲息地型包括 Malthus人口模型、 Logistic模型·和 Lotka-Vol-的適宜度指數(shù)(HS)對應(yīng)于優(yōu)化問題的目標(biāo)函數(shù)值,好的試terra模型3。近年來種群動力學(xué)模型得到廣泛的研究和應(yīng)探解具有較高HSI值;(2)棲息地的遷入和遷出機(jī)制對應(yīng)優(yōu)用先后得到了 Logistic模型和 Lotka-Volterra模型的滯后效化算法中的信息交互機(jī)制,高HSI的試探解以一定的遷出率應(yīng)模型、功能性反應(yīng)作用模型、反應(yīng)擴(kuò)散模型及年齡進(jìn)行相應(yīng)操作,將信息共享給低HSI試探解;低HSI試探解結(jié)構(gòu)種群模型等,這些修正模型考慮到了種群的增長率和通過高HSI的試探解接受許多新的特征,這些額外的新特征環(huán)境容納量的時(shí)間效應(yīng)、非線性繁殖特性進(jìn)化過程的時(shí)可以提高低HSI試探解的質(zhì)量。若棲息地的較高HSI使得滯效應(yīng)和隨機(jī)干擾等因素2。該棲息地種群數(shù)量增多,則調(diào)低遷入率、調(diào)高遷出率。到稿日期:201301-27返修日期:20130405本文受陜西省科學(xué)技術(shù)研究發(fā)展計(jì)劃中國煤化工科技計(jì)劃項(xiàng)目(12JK0789,陜西重點(diǎn)學(xué)科建設(shè)專項(xiàng)資金資助項(xiàng)目(E8),陜西房地產(chǎn)技術(shù)經(jīng)濟(jì)及管理研究CNMHG黃光球(1964-),男博士,教授,主要研究方向?yàn)橹悄苡?jì)算、計(jì)算機(jī)模擬Emil: huangnan93@so濤(1988-),男,碩土生,主要研究方向?yàn)橹悄苡?jì)算;陸秋琴(196-),女博土,教授,主要研究方向?yàn)橄冗M(jìn)計(jì)算、計(jì)算機(jī)模擬280本文提出的種群動力學(xué)優(yōu)化算法( Population dynamics-based Optimization,簡稱PDO算法)采用與BBO算法完全不dt =x(ntanztaiI2(4)同的設(shè)計(jì)思路,即:BBO算法采用的是生物地理學(xué)理論,而dt=x2(n2+ax1+a22x2)PD算法采用的是種群動力學(xué)理論這兩種理論存在很大差式中各符號及其含義說明如下:別。PDO算法假定一生態(tài)系統(tǒng)中存在多種不同種類的生物(1)n<0且n2<0,表示互利共生兩個(gè)種群如果分離則種群種群間進(jìn)行自由競爭、互利、捕食被食以及融合等活不能單獨(dú)存活的死亡率動,通過優(yōu)勝劣汰強(qiáng)壯者獲得進(jìn)化,虛弱者被淘汰。而BBO(2)n>0且n>0,表示種群1和2的自然增長率,種群算法是通過種群的遷人和遷出實(shí)現(xiàn)進(jìn)化1和種群2可以單獨(dú)存活測試結(jié)果表明,PDO算法具有很強(qiáng)的搜索能力,且具有(3)n>0且n2<0,表示種群1可以離開種群2而單獨(dú)存全局收斂性,可以用于求解大規(guī)模優(yōu)化問題?；畹N群2不能離開種群1而單獨(dú)存活,這是一種捕食被2種群動力學(xué)優(yōu)化算法構(gòu)造方法食關(guān)系。(4)當(dāng)a12<0且a2>0時(shí),表示式(4)是捕食被食關(guān)系2.1一般優(yōu)化問題定義系統(tǒng)?？紤]一般優(yōu)化問題(5)當(dāng)a1<0且a2<0時(shí),表示式(4)是競爭關(guān)系系統(tǒng)min f(X)(6)當(dāng)a12>0且a2>0時(shí),表示式(4)是互利關(guān)系系統(tǒng)。g;(X)≥0,i=1,2,…,I(1)(7)當(dāng)a12=0且ax>0或a12>0且a2=0時(shí),表示式st了h(X=0,i=1,2,…,E(4)是偏利關(guān)系系統(tǒng)x∈ScR,X0(8)當(dāng)a12=0且a<0或a1<0且a2=0時(shí),表示式式中,R是n維歐氏空間;X=(x,x…,x)是一個(gè)η維非(4)是偏害關(guān)系系統(tǒng)負(fù)實(shí)數(shù)決策向量;S為搜索空間,又稱解空間;f(X為目標(biāo)函(9)當(dāng)a12=0且an=0時(shí),表示式(4)是中性關(guān)系系統(tǒng)數(shù)g;(X)≥0為第i個(gè)約束條件,=1,2,…,1I為不等式約(10)當(dāng)a1<0且a2<0時(shí),表示式(4)是種內(nèi)密度制約束條件個(gè)數(shù);(X)=0為第i個(gè)等式約束條件,i=1,2,…,E,的。E為等式約束條件個(gè)數(shù)。目標(biāo)函數(shù)f(X和約束條件g;(X、2.3優(yōu)化問題試探解與種群動力學(xué)參數(shù)的關(guān)系h(X)不需要特殊的限制條件,傳統(tǒng)的基于函數(shù)連續(xù)性和可導(dǎo)生態(tài)系統(tǒng)中一個(gè)種群由n個(gè)特征來表示,一個(gè)種群對應(yīng)性的數(shù)學(xué)優(yōu)化方法無法解決該問題于一個(gè)優(yōu)化問題的試探解,N個(gè)種群所對應(yīng)的優(yōu)化問題的試為了使本文提出的算法適用于各種優(yōu)化問題,將優(yōu)化問探解解集為S={X1,x2,…,XN},X1=(x,x,…,x),i題(1)的目標(biāo)函數(shù)改寫成式(2):1,2,…,N;種群i中的一個(gè)特征j對應(yīng)于優(yōu)化問題試探解Xi∈(1,2,…,1,gA=0(2)解對應(yīng)具有較高F指數(shù)的種群,差的試探解對應(yīng)具有較低(X≥0;中的一個(gè)變量x6;種群的適應(yīng)度指數(shù)PSI( Population Suita-f(X,Vj{1,2,…,E}h(bility Index,PSD對應(yīng)于優(yōu)化問題的目標(biāo)函數(shù)值。好的試探FOXX∈ScR,X≥0其它PSI指數(shù)的種群即對于優(yōu)化問題(1),種群i中的適應(yīng)度指數(shù)式中Fa為非常大的實(shí)數(shù)用于對不滿足約束條件的試探解即PS指數(shù)為進(jìn)行懲罰。PSI(i)=Fm-F(X)(5)2.2 LotkaVolterra種群動力學(xué)模型24種群動力學(xué)進(jìn)化算子生物群落是在特定時(shí)間聚集在一定地域或生境中所有生PDO算法利用種群動力學(xué)模型來構(gòu)造進(jìn)化算子實(shí)現(xiàn)種物種群的集合。設(shè)群落由N個(gè)種群組成,N≥2。種群間相群間信息交換,進(jìn)而實(shí)現(xiàn)對優(yōu)化問題解空間的搜索。PDO算互作用關(guān)系可分為兩大類:a)無相互作用關(guān)系:包括互不影響法的進(jìn)化算法如下所述。的中性作用,一方受害另一方不受影響的偏害作用以及一方(1)竟?fàn)幩阕?。種群動力學(xué)競爭算子描述的是任意2個(gè)受益另一方不受影響的偏利作用;b)相互作用關(guān)系:包括競種群間的競爭行為。依據(jù)式(4),可以構(gòu)造出種群i與種群j爭(資源利用性競爭和相互干擾性競爭)互利(專性互利共生間的競爭算子即對于i,j∈{1,2,…,N},i≠j,s∈{1,2,…,和兼性互利共生)和捕食作用(捕食被食)。PDO算法中的n},有算子可利用上述各類相互作用關(guān)系進(jìn)行構(gòu)建?？擅枋龈鞣N群t=x(1+n-auxfl-anx: 1)(6)間相互作用的種群動力學(xué)模型為 Lotka-volterra模型,N個(gè)v=z1(1-n-a211-am1)種群的 Lotka-Volterra模型如下式中,和v為種群i與種群j的特征s在時(shí)期t時(shí)的狀態(tài)d=x(r;-∑ayx;),i=1,2,…,N(3)值,Ⅵ=(v,h…,)=(功,咖…,項(xiàng))右和¤為種群i與種群j的特征s在時(shí)的期t-1時(shí)狀態(tài)值,X式中,x是種群讠的大小,x≥0;n>0稱為種群i的內(nèi)稟增(x1,d1(2,1,…功1);參與競爭長率;a(i≠j的正負(fù)符號和絕對值表示種群j對種群i的影的種群=Ran中國煤化工;Rand(a,b)表響性質(zhì)和強(qiáng)度a表示種群i的種內(nèi)調(diào)節(jié)參數(shù),a<0表示種示在[ab區(qū)間產(chǎn)CNMHG正負(fù)號直接放內(nèi)競爭或種內(nèi)密度制約。下面我們重點(diǎn)研究2個(gè)種群間的入到表達(dá)式中,所以有n>0,a1>0,a12>0,n>0,a2>0,Lotka-volterra模型,由式(3)可得:a2>0,下同281(2)互利算子。種群動力學(xué)互利算子描述的是任意2個(gè)的求解性能。但對于高維優(yōu)化問題,進(jìn)化算法的求解性能則種群間的互利行為,依據(jù)式(4),可以構(gòu)造出種群i與種群j急劇下降。一個(gè)很重要的原因是在高維空間,單位體積內(nèi)初間的互利算子,即對于i,j∈{1,2,…,N},i≠j,s∈{1,2,始解的含量極低,當(dāng)然極難做到均勻分布。例如,在邊長為0的n維空間立方體中(即0≤x≤10,i=1,2,…,n),若100v=右1(1+n-a1x1+a121)個(gè)初始解分布于其中,則單位體積內(nèi)的初始解的個(gè)數(shù)為v=功1(1-n2+an1x1-a21)10-(m-2)。在2維空間內(nèi),單位體積內(nèi)的初始解的個(gè)數(shù)為1式中,參與互利的種群i=Rand(1,N),=Rand(1,N),ij。個(gè),而在1000維空間內(nèi),單位體積內(nèi)的初始解的個(gè)數(shù)為3)捕食被食算子。種群動力學(xué)捕食被食算子描述的1098個(gè),兩者相差10倍。若在100維空間要做到單位體是任意2個(gè)種群間的捕食被食行為依據(jù)式(4),可以構(gòu)造出積內(nèi)含1個(gè)初始解(即保持與2維空間具有相同的搜索效種群i與種群j間的捕食被食算子,即對于i,∈{1,2,…,力),則需要10∞0個(gè)初始解。顯然,這在工程應(yīng)用中是不可能N},i≠j,s∈{1,2,…,n},有實(shí)現(xiàn)的。如何讓很少的初始解盡可能地代表高維空間的分布v=右1(1+n-a1x-a12x1)(8)特性呢?正交表就是一個(gè)很好的解決方案v=d1(1-n2+a1G1-a21)正交表是遵循概率統(tǒng)計(jì)規(guī)律,依照一定原則(如正交拉丁式中,參與捕食被食的種群i=Rand(1,N),j=Rnd(1,N),方)生成的。通常等水平正交表寫成L(r),其中a表示正交表的行數(shù)或初始解的個(gè)數(shù);t表示正交表同一列中出現(xiàn)的因(4)融合算子。融合算子描述的是當(dāng)前種群i的某些特素的水平數(shù)(位級數(shù));m表示正交表的列數(shù)(即優(yōu)化問題解空性與其它若干個(gè)種群的某些特性融合在一起(而余下的特性卻保留下來),產(chǎn)生新一代種群,即對于∈1,2,…,N,∈優(yōu)的覆蓋度,關(guān)鍵在于它的均衡分散性和整齊可比性。正是{1,2,…,n},有這種均衡性帶來“冒尖”(即優(yōu)良的組合明顯化),這一點(diǎn)在非參數(shù)統(tǒng)計(jì)中有以下定理1保證。tax2+2Ax,若Ran(0,1)≤(9)定理113設(shè)隨機(jī)變量X遵守連續(xù)概率分布P(X),否則X1,X2,…,XN為總體X的一個(gè)容量為N的簡單樣本。把N式中,=Rand(1,N);Vk,v∈{1,2,…,B},≠L≠i;B次隨機(jī)變數(shù)X1,X2,…,XN按照觀測值從小到大排列起來,為與種群i發(fā)生融合的其它種群數(shù),稱為融合種群數(shù),B≥1,a,A,g稱為融合選擇率且0PS(x-2)i=1,2,…,N式中,k=(+j-1mdN;若k=0,則k=N其它算法1所確定的N個(gè)初始解X=(x1,x(11)1,2,…,N具有很好的均衡分散性和整齊可比性旦新的種群形成之后,PDO算法繼續(xù)通過競爭、互利、2.6PDO算法設(shè)捕食-被食融合突變和選擇等算子對群落不斷進(jìn)行演化,直算法2PI中國煤化工到找到最優(yōu)解。(1)初始化:a)令CNMHG到的所有參數(shù);2.5高維空間初始點(diǎn)的選擇方法c)按算法1確定N個(gè)初始解;d)對N個(gè)初始解的從優(yōu)到劣進(jìn)行排眾所周知,對于低維優(yōu)化問題進(jìn)化算法一般都具有很好序,使PSI值較高的初始解排在前面。282(2)執(zhí)行下列操作表1PDO算法時(shí)間復(fù)雜度計(jì)算表FORt=1TOG//G為演化最大代數(shù)時(shí)間復(fù)雜度最多循環(huán)次數(shù)EH-X-1,i=1,2,…,KP//將前KP個(gè)最佳試探解作為精英保存始化On+4nN+N(N+1)選代準(zhǔn)備OnKP)下來;竟?fàn)幩阕覱(2n)FOR i=l TON互利算子o(2n)隨機(jī)選擇種群 i=Rand(1,N),確保ij捕食被食算子O(2n)融合算子FOR s=l TO目標(biāo)函數(shù)計(jì)算Ip≤ PA THEN/A為當(dāng)前種群i與種群j發(fā)生競爭行為的概結(jié)果排序O4n+(N+1))率上限B1為該競爭行為出現(xiàn)的實(shí)際概率p1=Ran(0,1)突變算子O3mr-+4nme選擇算子O(3n)GN按式(6)執(zhí)行競爭算子,得到v和v結(jié)果排序O(n+(N+1))計(jì)算v=2(v+v)情英替換OnKP)結(jié)果輸出ELSEIF Pi,p=0的誤差滿足最低要求 E THEN轉(zhuǎn)(3)將倒數(shù)KP個(gè)最差的解用保存下來的精英進(jìn)行替換,即X-k1=E1,k=1,2,…,KP(1)式(12)的證明。設(shè)X’為第t次演化后的種群的狀END FOR態(tài),記為Y,設(shè)Y中狀態(tài)最好的種群為 g Best2=X,即有F(3)結(jié)束。( g Best)=F。通過PD算法存每次演化過程中對當(dāng)前種2.7算法的時(shí)間復(fù)雜度群最好狀態(tài)的更中國煤化工PDO算法(算法2)的時(shí)間復(fù)雜度計(jì)算過程如表1所列,CNMHG其時(shí)間復(fù)雜度與演化次數(shù)G種群規(guī)模N變量個(gè)數(shù)n搜索F(X+1)≤F(X)→Vk>i,內(nèi),k=0→Vk>i,p,算子的時(shí)間復(fù)雜度以及其他輔助操作相關(guān)力,,=0→Vk>i,戶,A=0·283·(2)式(13)的證明。在PDO化算法中設(shè)gesr+為Y+ Markov鏈上的一個(gè)狀態(tài),根據(jù)引理1中式(12)的結(jié)論可得,中最優(yōu)種群的狀態(tài),此時(shí)種群隨機(jī)選擇活動行為,有競爭行該 Markov鏈的轉(zhuǎn)移矩陣為:為、互利行為捕食被食行為融合行為和靜止行為5種情況。p2,1p2,20情形1當(dāng)前種群i選擇競爭行為。若種群i的狀態(tài)可以轉(zhuǎn)移到更優(yōu)的狀態(tài)上,則其將以概率P1= pI pMps+p(1PN. 1 PN.p)抄=力內(nèi)更新到新狀態(tài),顯然P1>0,命題得證。其根據(jù)引理1中式(13)的結(jié)論得中,pM為突變算子執(zhí)行成功的概率(即被突變了);ps為選擇p1>0,R=(p2,1,p31,pu…,px:)T算子執(zhí)行成功的概率(即被選中了)情形2當(dāng)前種群i選擇互利行為。若種群i的狀態(tài)可∵.:|≠0,C=(p)=(1)≠0以轉(zhuǎn)移到更優(yōu)的狀態(tài)上,則其將以概率P2=P2Mps+p(1AM)內(nèi)s=pps更新到新狀態(tài),顯然P2>0,命題得證。由以上可知轉(zhuǎn)移矩陣P是N階可歸約隨機(jī)矩陣滿足情形3當(dāng)前種群i選擇捕食被食行為。若種群i的狀定理2的條件,所以下式成立態(tài)可以轉(zhuǎn)移到更優(yōu)的狀態(tài)上,則其將以概率P3=力3Mps+0(1-pM)s=內(nèi)加s更新到新狀態(tài),顯然P3>0,命題得證情形4當(dāng)前種群i選擇融合行為。若種群i的狀態(tài)可以轉(zhuǎn)移到更優(yōu)的狀態(tài)上,則其將以概率P4= P4 PMPs+p4(1因C=C=(1),T=0,故必有R=(1,1,…,1),這是p)ps=p4p更新到新狀態(tài),顯然P4>0,命題得證因?yàn)镸kov轉(zhuǎn)移矩陣P中每行的概率之和為1。因此有P情形5當(dāng)前種群i選擇靜止行為。若種群i的狀態(tài)可以轉(zhuǎn)移到更優(yōu)的狀態(tài)上,則其將以概率P5=pMs+(110且為穩(wěn)定的隨機(jī)矩陣AM)內(nèi)=內(nèi)內(nèi)更新到新狀態(tài)顯然P3>0,命題得證。在任意一個(gè)時(shí)間段內(nèi),任一種群i必選上述5種行為之,即p+p2++p+p=1。綜合上述各種情況,可得總上式表明,當(dāng)k→∞時(shí),概率A1=1,i=1,2,…,N,也即概率為:無論初始狀態(tài)如何,最后都能以概率1收斂到全局最優(yōu)狀態(tài)Pa=P+P2+P,+P=(p+P2+P3+p4)Ps=ps1上。于是得因0≤內(nèi)≤1,易知P4≥0;如果P>0,命題得證;如果limp{F(Ⅺ)→F(X)}=1,=1,2,…,NP=0,說明p=0,即F(V)>F(X1)出現(xiàn)的概率永為0表因此,PDO化算法具有全局收斂性,證畢。明種群演化已經(jīng)到達(dá)全局最優(yōu)解狀態(tài) g Best+=x',而不是定理3表明:局部最優(yōu)解。(1)若隨機(jī)搜索的每個(gè)狀態(tài)都能以概率p>0轉(zhuǎn)移到綜合上述情況可得彐k0,證畢。個(gè)比當(dāng)前狀態(tài)更優(yōu)的狀態(tài)上,則該隨機(jī)搜索收斂,即搜索幾乎定理21設(shè)P是一n階可歸約隨機(jī)矩陣,也就是通過以概率1找到全局或局部最優(yōu)解。概率p越大,收斂越快(2)隨機(jī)搜索的某個(gè)狀態(tài)若無法以概率p>0轉(zhuǎn)移到一個(gè)相同的行變換和列變換后可以得到P其中C比當(dāng)前狀態(tài)更優(yōu)的狀態(tài)上,則寧愿保持當(dāng)前狀態(tài)不變也不要是m階本原隨機(jī)矩陣并且R≠0,T≠0,則有:轉(zhuǎn)移到比當(dāng)前狀態(tài)更差的狀態(tài)上。若該情況經(jīng)常出現(xiàn),則收斂過程很慢。(3)若隨機(jī)搜索的狀態(tài)以同樣的概率轉(zhuǎn)移到一個(gè)比當(dāng)前00狀態(tài)更好、保持不變或更差的狀態(tài)上(即下一個(gè)狀態(tài)是好是壞或保持不變隨機(jī)出現(xiàn))則該隨機(jī)搜索發(fā)散,即該隨機(jī)搜索找到全局或局部最優(yōu)解的概率幾乎為0。文獻(xiàn)[1]用很復(fù)雜的上述的矩陣是一個(gè)穩(wěn)定的隨機(jī)矩陣且P=1P理論證明了粒子群算法不收做,就是這個(gè)原因。P=PP唯一確定并且與初始分布無關(guān)。P∞滿足如下條順便指出,當(dāng)隨機(jī)搜索陷入局部最優(yōu)解狀態(tài)時(shí),很多隨機(jī)件搜索算法采用所謂的逃逸方法試圖跳出局部最優(yōu)解狀態(tài)。然P=[Ax,01n,1j≤m而,若跳出后的狀態(tài)比局部最優(yōu)解狀態(tài)差,這種情況幾乎以很內(nèi)=0,1≤i≤n,m