黃光球,陸秋琴
西安建筑科技大學(xué) 管理學(xué)院,西安 710055
非線性規(guī)劃問題的全局最優(yōu)解的求解是一個非常困難的問題,因?yàn)橹挥型挂?guī)劃且其數(shù)學(xué)表達(dá)式可導(dǎo)時,采用傳統(tǒng)優(yōu)化理論才能獲得其全局最優(yōu)解。若非線性規(guī)劃是非凸非凹或者是其數(shù)學(xué)表達(dá)式不可導(dǎo),則傳統(tǒng)優(yōu)化理論失效。為了解決該問題,人們發(fā)明了群智能優(yōu)化算法來求取非線性優(yōu)化問題的全局最優(yōu)解[1-3]。此類算法對非線性優(yōu)化問題的結(jié)構(gòu)沒有特殊限制條件,因而具有廣泛的適應(yīng)性。
傳統(tǒng)的群智能優(yōu)化算法是依據(jù)一些特殊的自然現(xiàn)象構(gòu)造而得,自然現(xiàn)象本身的特征對群智能優(yōu)化算法的性能影響很大。因此,尋找具有優(yōu)良特性的自然現(xiàn)象來構(gòu)造群智能優(yōu)化算法是提升群智能優(yōu)化算法的有效手段。最近幾年,人們已提出了很多新型的群智能優(yōu)化算法,如蝙蝠算法[4]、蜂群算法[5]、鯨魚算法[6]、蛙跳算法[7]、灰狼算法[8]、布谷鳥算法[9]等,這些算法的共同特征是算法所依據(jù)的自然現(xiàn)象非常簡單,無法用數(shù)學(xué)模型進(jìn)行描述。由于存在此缺陷,關(guān)于算法的參數(shù)確定和性能分析變得異常困難。
為了解決上述問題,人們開始尋求能被數(shù)學(xué)模型很好描述的自然現(xiàn)象來開發(fā)新一代群智能優(yōu)化算法,其中能夠被種群動力學(xué)數(shù)學(xué)模型[10-11]描述的自然現(xiàn)象就是其中的一種。文獻(xiàn)[12]采用兩個種群Lotka-Volterra 種群動力學(xué)模型構(gòu)建出了第一個種群動力學(xué)算法,種群間的作用關(guān)系有競爭、互利、捕食-被食、融合、突變和選擇;以文獻(xiàn)[12]為基礎(chǔ),文獻(xiàn)[13]構(gòu)建出了基于3 個種群的Lotka-Volterra 種群動力學(xué)優(yōu)化算法。
在自然界中,很多種群的增長是通過脈沖出生新生個體來完成的,一段時間后,從幼年種群成長而來的成年種群的捕獲也是季節(jié)性的。該自然現(xiàn)象非常普遍,且能被具脈沖出生和季節(jié)性捕殺的種群動力學(xué)數(shù)學(xué)模型[14-15]很好描述。本文正是依據(jù)該自然現(xiàn)象構(gòu)造出了一種新的群智能優(yōu)化算法——具脈沖出生和季節(jié)性捕殺的種群系統(tǒng)優(yōu)化算法(population system optimization with impulsive birth and seasonal killing,PSO-IBSK)。與現(xiàn)有的種群動力學(xué)優(yōu)化算法相比,本文算法具有如下特點(diǎn):
(1)種群個體自然地劃分成幼年個體(簡稱幼體)和成年個體(簡稱成體)兩類,每類個體數(shù)是依據(jù)具脈沖出生和季節(jié)性捕殺的種群動力學(xué)模型自動進(jìn)行動態(tài)計算而得,避免了人工確定個體數(shù)的困難。
(2)所有算子是通過幼體的脈沖出生、幼體演變?yōu)槌审w、成體的季節(jié)性捕殺、虛弱個體的死亡而構(gòu)造出來的,符合種群動力學(xué)規(guī)律,且與所求解的實(shí)際優(yōu)化問題無關(guān),故具有很好的普適性。
(3)每個算子具有明確功能,其中出生算子和成長算子可分別實(shí)現(xiàn)成體向幼體瞬時和延遲傳遞信息,有助于搜索跳出局部陷阱;捕殺算子可周期性地將不良成體清除,死亡算子可將虛弱個體隨機(jī)清除,該兩個算子有利于提升算法的求精能力;強(qiáng)勢算子可實(shí)現(xiàn)強(qiáng)壯個體向虛弱個體擴(kuò)散強(qiáng)壯信息,競爭算子可實(shí)現(xiàn)幼年和成體之間的有效信息交換,該兩個算子有利于提升算法的探索能力;進(jìn)化算子可確保算法具有全局收斂性。
(4)采用具脈沖出生和季節(jié)性捕殺的種群動力學(xué)模型確定PSO-IBSK 算法中的相關(guān)參數(shù),使算法的參數(shù)確定具有科學(xué)性。
(5)計算過程中,PSO-IBSK 算法每次只處理個體特征數(shù)的6‰~8%,從而使時間復(fù)雜度大幅降低。
假設(shè)要求解的優(yōu)化問題如下:
式中,X=(x1,x2,…,xn)為變量,在求解過程中X的不同取值稱為試探解,Rn是n維歐氏空間;f(X)為目標(biāo)函數(shù);H為搜索空間。
在一個生態(tài)系統(tǒng)G中生活著一個生物種群,該種群由具有兩種階段狀態(tài)的若干生物個體組成,即階段狀態(tài)s=1 的幼體和階段狀態(tài)s=2 的成體,其中幼體經(jīng)過一段時間的生長后會長大成為成體,而幼體是由成體出生的,幼體的出生持續(xù)時間很短,故稱之為脈沖出生。為了節(jié)省資源,降低種群中的個體密度,需要周期性(季節(jié)性)地對該生態(tài)系統(tǒng)中一些生長狀況不良的成體進(jìn)行捕殺,以便提升種群的整體質(zhì)量。
在時期t,假設(shè)該種群的幼體數(shù)和成體數(shù)分別為N1(t)和N2(t),個體總數(shù)為N(t)=N1(t)+N2(t);每個幼體和每個成體都用唯一編號表示,于是所有幼體和所有成體的編號集合分別為種群中的每個幼體和每個成體都具有n個特征,于是對于階段狀態(tài)為s的個體i來說,用其特征表示就是,其中就是階段狀態(tài)為s的個體i的第j個特征,i∈Cs(t),j=1~n,s=1~2。
搜索空間H中優(yōu)化問題式(1)的試探解與生態(tài)系統(tǒng)G中種群的幼體和成體的對應(yīng)關(guān)系如下所述。
時期t,在式(1)的搜索空間H中隨機(jī)生成N(t)個試探解,即∈Cs(t),s=1~2},其中。將搜索空間H視為生態(tài)系統(tǒng)G,則時期t在生態(tài)系統(tǒng)G中階段狀態(tài)為s的個體i就與搜索空間H中的試探解一一對應(yīng),也就是階段狀態(tài)為s的個體i的特征與試探解的分量相對應(yīng)。在生態(tài)系統(tǒng)G中,生物個體的動力學(xué)演化規(guī)律總結(jié)如下:
(1)幼體是由成體以脈沖方法突然產(chǎn)生的;
(2)幼體經(jīng)過時間段T后成長為成體;
(3)在某個季節(jié)內(nèi),某些生長狀況不良的成體會被捕殺掉;
(4)某些虛弱的幼體和成體會死亡;
(5)幼體和成體的生長狀況越好,繼續(xù)生存下去的概率會越高,即個體的演化規(guī)律符合達(dá)爾文進(jìn)化論規(guī)律。
個體的生長狀況由優(yōu)化問題式(1)的目標(biāo)函數(shù)值描述,個體的生長狀況越好,其對應(yīng)的目標(biāo)函數(shù)值就越小。時期t階段狀態(tài)為s的個體i的生長狀況用IGI(individual growth index)指數(shù)來表示,其計算方法為:
在生態(tài)系統(tǒng)G中,假設(shè)幼體的出生具有規(guī)則脈沖性,則具有階段結(jié)構(gòu)和脈沖出生的單種群離散模型為[16]:
其中,t∈Z+,Z+為非負(fù)整數(shù)集;令從t到t+1 的幼體的出生數(shù)=0,b>0,當(dāng)t=kω(k∈Z+,ω為正數(shù))時,幼體數(shù)N1(t)增加了N2(t);δ為幼年種群的成長率,0<δ<1;幼年和成年的死亡率分別為d1和d2,0 若考慮對成體的捕殺,E為對成體進(jìn)行捕殺的捕殺率,0 考慮脈沖出生,并考慮對式(4)的成體進(jìn)行季節(jié)性捕殺,不失一般性,設(shè)對成體的捕殺發(fā)生在(T1/ω,T2/ω](0 ≤T1 迭代N1(t)和N2(t),可得式(5)在脈沖區(qū)間內(nèi)的解析解,即: 式(6)在脈沖區(qū)間成立且α≠μ,α≠β。為簡單起見,下面總是設(shè)α≠μ,α≠β。當(dāng)t=(m+1)ω時,由式(6)得: 定義內(nèi)稟再生數(shù)R0為R0=bp/(1-r)(1-q),令b0=(1-r)(1-q)/p。當(dāng)R0<1 時,如果在平均數(shù)量上,個體在死亡前沒有得到替補(bǔ)和補(bǔ)充,則種群會走向滅絕。式(8)滿足: 當(dāng)R0>1 時,存在一個正平衡點(diǎn)E*(u*,v*),其中: 定理1[17]令γ=若b>b0,則式(8)存在一個正不動點(diǎn)E*(u*,v*) ;若b0bc,則E*(u*,v*) 是不穩(wěn)定的。若b作為一個分支參數(shù),則b=bc是一個Flip 分支。 PSO-IBSK 算法的算子是通過各生物個體及其相互之間的作用關(guān)系構(gòu)造而成。令: (1)出生算子。該算子描述的是由成體產(chǎn)生幼體。首先生成階段狀態(tài)為s的強(qiáng)壯個體集合SIs(t),該集合中的個體的IGI 指數(shù)高于同一階段狀態(tài)的IGI 指數(shù)的平均值,SIs(t)集合中的個體數(shù)為L,L稱為特征個體數(shù);然后,從SI2(t)中隨機(jī)選出兩個成體i1和i2,由其產(chǎn)生的幼體數(shù)為B(t+1)個,B(t+1)=,即: 式中,i=1~B(t+1) ;MF(t) 為從{1,2,…,n} 中以概率Z0隨機(jī)選擇所形成的特征編號集合;Z0稱為個體特征受影響的最大概率;λ=Rand(-1,1),Rand()為均勻分布隨機(jī)取值函數(shù);ρ=Rand(0,1)。 由式(11)產(chǎn)生的B(t+1) 個幼體的編號集合為BI(t+1)={i0,i0+1,…,i0+B(t+1)-1},i0=|C2(t)|+1。 一方面,因幼體是通過兩個強(qiáng)壯個體雜交產(chǎn)生的,故幼體的質(zhì)量普通較高;另一方面,因幼體是瞬時產(chǎn)生的,故一定數(shù)量的優(yōu)質(zhì)個體的瞬時投放有助于搜索跳出局部最優(yōu)解陷阱。 (2)成長算子。該算子描述的是幼體經(jīng)過一段時間后長大為成體。假設(shè)當(dāng)前幼體i以概率δ要轉(zhuǎn)變?yōu)橐粋€成體,為了使該幼體具有成體的一些特征,首先,在階段狀態(tài)為s的個體中隨機(jī)選擇L個個體,由其編號形成的集合為GIs(t),然后,將GI2(t)中的成體的部分特征傳給該幼體,使其成為成體,即: 然后,將幼體i從幼體集合中刪除,即C1(t+1)=C1(t)-{i},將該個體的階段狀態(tài)改為成年?duì)顟B(tài),其編號為|C2(t)|+1,即C2(t+1)=C2(t)+{|C2(t)|+1}。 成長算子描述了質(zhì)量較高的幼體演變?yōu)槌审w的過程。成體是由高質(zhì)量的幼體演變而來,若成體的質(zhì)量不斷得到提升,則意味著搜索向全局最優(yōu)解不斷靠近;若成體質(zhì)量沒得到提升,則會被死亡算子和捕殺算子清除掉。因此,在這兩個算子輔佐下,成長算子有利于提升本算法的全局尋優(yōu)能力。 (3)捕殺算子。該算子描述的是將生長狀態(tài)不良的成體進(jìn)行人為刪除,刪除數(shù)目為E個。從成體集合選擇IGI 指數(shù)最低的E個個體,其編號形成的集合為WI2(t),將WI2(t)中的所有個體進(jìn)行人為清除: (4)死亡算子。該算子描述的是虛弱個體的自然死亡。對當(dāng)前階段狀態(tài)為s的個體i,若該個體的IGI 指數(shù)低于處于該階段狀態(tài)的個體平均IGI 指數(shù),則以概率ds令其死亡,即: (5)強(qiáng)勢算子。該算子描述的是強(qiáng)壯個體的特征向虛弱個體擴(kuò)散的現(xiàn)象,即強(qiáng)壯的個體對虛弱的個體產(chǎn)生影響。對階段狀態(tài)為s,個體編號為i的當(dāng)前個體來說,有: (6)競爭算子。該算子描述的是幼年和成體之間的相互競爭現(xiàn)象。對階段狀態(tài)為s,個體編號為i的當(dāng)前個體來說,有: (7)進(jìn)化算子。該算子描述的是個體的進(jìn)化需滿足達(dá)爾文進(jìn)化論規(guī)律。對于階段狀態(tài)為s的當(dāng)前個體i,其進(jìn)化算子的定義如下: 式中,函數(shù)IGI()按式(2)計算。 算法1PSO-IBSK 步驟1初始化: (1)令演化時期數(shù)G=105~108,誤差要求ε=10-5~10-10,L,Z0;N1(0)=N2(0)=200,m=0。 (2)依據(jù)2.1 節(jié)確定參數(shù)b、δ、d1、d2、ω、T1、T2。 (3)在搜索空間H中隨機(jī)生成試探解集: (4)確定個體編號集合C1(0)={1,2,…,N1(0)},C2(0)={1,2,…,N2(0)}。 (5)以X(0)為基礎(chǔ),找出初始全局最優(yōu)解Y*0。 步驟2執(zhí)行下列操作: 步驟3結(jié)束。 1.5.1 時間復(fù)雜度 PSO-IBSK 算法的時間復(fù)雜度計算如表1 所示,其中 1.5.2 PSO-IBSK 算法的全局收斂性分析 Table 1 Time complexity表1 時間復(fù)雜度 不失一般性,令f1即為所求的全局最優(yōu)解。由式(18)的下標(biāo)形成的集合為U={1,2,…,Z(t)}。 ?X∈H,有f1≤f(X)≤fZ(t),將H劃分為如下非空子集={X|X∈H且f(X)=fi},i=1~Z(t),顯然有: 令Xi,j(i=1~Z(t),j=1~表示中的第j個狀態(tài);個體從狀態(tài)(i,j) 轉(zhuǎn)移到狀態(tài)(k,l) 表示為Xi,j→Xk,l;設(shè)pij,kl、pij,k為從Xi,j分別到Xk,l、中任一狀態(tài)的轉(zhuǎn)移概率,pi,k為從中任一狀態(tài)到中任一狀態(tài)的轉(zhuǎn)移概率,則: 引理1在PSO-IBSK 算法中,,i=1~Z(t),j=,滿足: (1)引理式(20)的證明:設(shè)狀態(tài)i為時期t個體i的狀態(tài),其空間位置為,由式(17)知,該個體具有適應(yīng)度遞增特性,故在時期t+1 有: (2)引理式(21)的證明:設(shè)狀態(tài)i為時期t個體i的狀態(tài),在時期t+1,個體i隨機(jī)選各算子進(jìn)行演化以便轉(zhuǎn)移到更好的狀態(tài)k上。此時,存在有如下兩種情況: ①若狀態(tài)i=1,即全局最優(yōu)狀態(tài),因下一步不會轉(zhuǎn)移到較差的狀態(tài)上去,故必以概率p1,1=1 留在原狀態(tài)i上。因p1,1=1>0。命題得證。 ②若狀態(tài)i≠1,則在狀態(tài)1 和當(dāng)前狀態(tài)i之間必至少存在一個中間狀態(tài)k,使得f1≤fk 綜上所述,可得?k0。證畢。 定理2[18]設(shè)P′是一n階可歸約隨機(jī)矩陣,即通過相同的行和列變換后可得到,其中C是m階本原隨機(jī)矩陣,且T≠0,R≠0,則有: 上述矩陣是一個穩(wěn)定隨機(jī)矩陣,P′∞=1′P′∞,P′∞=P′0P′∞唯一確定且與初始分布無關(guān),P′∞滿足條件: 定理3PSO-IBSK 算法具有全局收斂性。 證明從各算子的定義式(11)~式(16)可知,與滿足關(guān)系,表明PSO-IBSK算法的演變過程具有Markov特性。每個,i=1~Z(t)是有限Markov 鏈上的一個狀態(tài),根據(jù)式(20)可得狀態(tài)轉(zhuǎn)移矩陣為: 且P′的每行均滿足式(19)。根據(jù)式(21)可得: 于是,P′是一個Z(t)階可歸約隨機(jī)矩陣,滿足定理2 的條件,故有: 因C∞=C=(1),T∞=0,故必有R∞=(1,1,…,1)T,于是: 上式表明,當(dāng)k→∞時,pi,1=1,i=1~Z(t),于是: 因此,PSO-IBSK 算法具有全局收斂性,證畢。 目前,進(jìn)行群智能算法收斂性分析的方法有圖搜索法[19]、代數(shù)方法、解析分析法、狀態(tài)空間模型法和馬爾科夫分析法[20]等,這些方法的證明過程復(fù)雜,僅適合于特定算法的收斂性分析,沒有通用性。本文提出的群智能算法收斂性分析法是基于有限馬爾科夫鏈的可歸約隨機(jī)矩陣穩(wěn)定性定理,證明過程非常簡單,可適用于所有群智能算法的收斂性分析,具有通用性。同時,本證明過程表明,對一個群智能算法來說,只要其種群個體演化符合達(dá)爾文進(jìn)化論規(guī)律,該群智能算法就是全局收斂的。 種群系統(tǒng)模型的參數(shù)是算法的內(nèi)置參數(shù),由1.2節(jié)介紹的理論進(jìn)行設(shè)置,用戶無需修改。下面討論這些參數(shù)的設(shè)置方法。 首先討論捕殺時間T1和T2選取對式(9)描述的幼年和成體數(shù)量的影響,以及種群最大可持續(xù)捕殺量E。由定理1 可知,式(9)的正平衡點(diǎn)依賴于收獲的時間,盡管捕殺量E相同,太遲的捕殺將導(dǎo)致種群的滅絕。在每個繁殖季節(jié)后,收獲成體越早,系統(tǒng)可承受的捕殺量越大,對生存下來的個體來說,其存活的概率也越大。從生物學(xué)角度來看,捕殺成體可以減少種內(nèi)競爭,使得其他個體得到充足的食物和空間,進(jìn)而增加存活概率。因此,在繁殖季節(jié)結(jié)束后,收獲成體對具有脈沖出生的種群是比較有利的。同時也可得到成年種群的平衡態(tài)v*是關(guān)于T1的減函數(shù)。事實(shí)上,如果τ為一常數(shù),則: 由于0 由定理1 知,若b0 因此,只需考慮一個周期內(nèi)的可持續(xù)捕殺量。不失一般性,取m=0,則可持續(xù)捕殺量為: Fig.1 Changes of the number of juveniles and adults with time圖1 幼年和成體數(shù)隨時間的演變規(guī)律 人工控制參數(shù)包括Z0和L,需要用戶根據(jù)所求優(yōu)化問題的實(shí)際特征進(jìn)行人工設(shè)置。下面通過Awad等人最新發(fā)布的智能優(yōu)化算法測試包中所介紹的基準(zhǔn)函數(shù)F6[21],該函數(shù)由Scaffer 函數(shù)經(jīng)旋轉(zhuǎn)和平移擴(kuò)展而得,其表達(dá)式如下:式中,M為n×n維旋轉(zhuǎn)矩陣;O為n維向量,其中每一維的值在[-80,80]中隨機(jī)選取。 令n=50,Z0=0.01,G=108,PSO-IBSK 算法運(yùn)行100 次,表2 描述了L與最優(yōu)目標(biāo)函數(shù)值的平均值(OFV)和計算時間的平均值(CT)之間的關(guān)系。表2 表明,當(dāng)L=3~7 時,OFV的精度達(dá)到最佳,而CT遞增不大,建議L=3~7。 Table 2 Relationship of L with OFV and CT表2 L 與OFV 和CT 之間的關(guān)系 令n=50,L=3,G=108,PSO-IBSK 算法運(yùn)行100 次,表3 描述了Z0、OFV和CT之間的關(guān)系。結(jié)果表明,當(dāng)Z0=0.006~0.080 時,OFV精度較高,但CT增加不大,建議Z0=0.006~0.080。 Table 3 Relationship of Z0 with OFV and CT表3 Z0 與OFV 和CT 之間的關(guān)系 本文選用CEC2013[22]智能優(yōu)化算法測試包中12個難度很大優(yōu)化問題來對PSO-IBSK 算法與其他算法進(jìn)行比較,如表4 所示。 Table 4 12 benchmark functions in CEC2013表4 12 個CEC2013 基準(zhǔn)函數(shù)優(yōu)化問題 求解這些優(yōu)化問題時,PSO-IBSK 算法的參數(shù)設(shè)置是n=50,G=108,ε=10-8,Z0=0.01,M=3。與PSOIBSK 算法進(jìn)行比較的7 種智能優(yōu)化算法為BRKGA(biased random-key genetic algorithm)[23]、ACO-IM(ant colony optimization-influence maximization)[24]、SRPSO(self-regulating particle swarm optimization)[25]、SLIWBBO(self learned invasive weed-mixed biogeography based optimization)[26]、DE-DMSC(differential evolution with dual mutation strategies collaboration)[27],DARSRWO(double adaptive random spare reinforced whale optimization)[28]、GABC(genetic artificial bee colony)[29],這些算法各參數(shù)設(shè)置可參見其對應(yīng)文獻(xiàn)。 求解各個優(yōu)化問題時,每個算法均獨(dú)立求解51次。表5 給出了各算法的求解結(jié)果,表中計算結(jié)果是各算法求解各優(yōu)化問題時的計算值與理論值之間的偏差。 Table 5 Results obtained by each algorithm表5 各算法的求解結(jié)果 Fig.2 Sample convergence curves圖2 樣本收斂曲線 從表5 可以看出,這8 個算法按最終排名1 和最終排名2 排序所得的結(jié)果均如下: PSO-IBSK>DARSR-WO>DE-DMSC>BRKGA>ACO-IM=GABC>SRPSO>SLIW-BBO 圖2(a)~(f)給出了各算法求解優(yōu)化問題F3、F7、F14、F20、F22、F23 時的樣本收斂曲線。 本文基于具脈沖出生和季節(jié)性捕殺的種群動力學(xué)模型提出的PSO-IBSK 算法能夠動態(tài)自動計算幼年和成體數(shù),從而使得種群個體數(shù)的確定具有科學(xué)性;PSO-IBSK 算法中的算子是依據(jù)幼體的脈沖出生、成體的長成和季節(jié)性捕殺、個體間的競爭關(guān)系和虛弱個體的死亡而構(gòu)造出來的,符合種群動力學(xué)規(guī)律。各個算子分工明確,個體間信息交換充分,出生算子和成長算子的綜合作用有助于搜索跳出局部最優(yōu)解陷阱,強(qiáng)勢算子和競爭算子的綜合作用有利于提升算法的求精能力和探索能力,而進(jìn)化算子能確保算法具有全局收斂性。PSO-IBSK 算法中的大量參數(shù)采用具脈沖出生和季節(jié)性捕殺的種群動力學(xué)模型確定,提升了算法參數(shù)確定的合理性和科學(xué)性。PSO-IBSK 算法每次處理的個體特征數(shù)很少,適應(yīng)于求解維數(shù)較高的優(yōu)化問題。 PSO-IBSK 算法的下一步改進(jìn)方向如下: (1)深入研究各算子的動態(tài)特征; (2)深入研究個體的動態(tài)特征。1.3 算子設(shè)計
1.4 PSO-IBSK 算法構(gòu)造
1.5 算法特點(diǎn)分析
2 算法參數(shù)確定
2.1 種群系統(tǒng)模型的參數(shù)設(shè)置方法
2.2 人工控制參數(shù)設(shè)置方法
3 PSO-IBSK 算法與其他算法的比較
4 結(jié)束語