異質(zhì)空間結(jié)構(gòu)種群遷徙動(dòng)力學(xué)優(yōu)化算法*

黃光球，陸秋琴

西安建筑科技大學(xué)管理學(xué)院，西安 710055

1 引言

生態(tài)學(xué)理論認(rèn)為，生物群落具有不顧干擾在空間持續(xù)生存的能力，有強(qiáng)烈地改善在空間分布狀況的能力[1]。自然界中食物資源沿分布區(qū)往往相互鑲嵌，這導(dǎo)致生物群落出現(xiàn)斑塊分布。此外，在分布區(qū)出現(xiàn)混雜結(jié)構(gòu)，生態(tài)學(xué)上稱為斑塊現(xiàn)象[2]。物種個(gè)體和種群空間鑲嵌分布的結(jié)果也有類似的現(xiàn)象。若斑塊中的生物個(gè)體有著各自不同的活動(dòng)半徑且不同物種的活動(dòng)性有很大差異，種群規(guī)模具有非線性局部動(dòng)態(tài)變化特征，種群遷徙受邊界影響，這類結(jié)構(gòu)稱為異質(zhì)空間結(jié)構(gòu)[3]。

最早利用生物種群個(gè)體在不同斑塊間遷徙這一自然現(xiàn)象構(gòu)造出來的群智能優(yōu)化算法[4-7]是生物地理學(xué)算法（biogeography-based optimization，BBO）[8]，該算法通過種群在斑塊間的遷移實(shí)現(xiàn)了對(duì)優(yōu)化問題最優(yōu)解的搜索。BBO算法已在很多領(lǐng)域取得應(yīng)用[9-13]。因BBO算法只有遷移、變異和精英保留三個(gè)算子，故目前絕大部分研究工作是針對(duì)這些算子的改進(jìn)而提出的改進(jìn)算法。文獻(xiàn)[14]利用自適應(yīng)差分算子改進(jìn)BBO算法的遷移算子，該算子與原遷移算子相結(jié)合形成雙遷移模式，從而使得BBO算法的性能得到提高；文獻(xiàn)[15]利用差分?jǐn)_動(dòng)操作改進(jìn)變異算子，垂直交叉操作改進(jìn)遷移算子，從而提升了BBO算法的探索能力和求精能力；文獻(xiàn)[16]利用差分算子改進(jìn)遷移算子，趨優(yōu)變異算子改進(jìn)變異算子，從而提高了BBO算法的全局搜索能力，并平衡了其探索和求精能力；文獻(xiàn)[17]用嵌入變異和細(xì)菌趨化現(xiàn)象的融合替換遷移算子，用貪婪選擇算子替換精英保留策略，從而形成混合BBO算法。

此外，BBO算法的棲息地選擇策略也是一個(gè)改進(jìn)方向。文獻(xiàn)[18]采用引力學(xué)習(xí)策略來選擇棲息地，從而提出了一種基于鄰域引力學(xué)習(xí)的BBO算法NFBBO（neighbor force-learning biogeography-based optimization）。文獻(xiàn)[19]利用局部和全局自適應(yīng)鄰域校調(diào)策略來選擇棲息地，從而提出了一種基于自適應(yīng)鄰域校調(diào)策略的BBO算法。

大量測(cè)試與應(yīng)用表明[20-24]，BBO算法及其改進(jìn)版存在如下問題：（1）該算法對(duì)維數(shù)較低的優(yōu)化問題具有較好的性能，但當(dāng)優(yōu)化問題的維數(shù)很高，該算法的性能下降；（2）該算法的全局收斂性一直未被證明。出現(xiàn)上述問題的原因是BBO算法的遷移算子、變異算子和精英保留策略過于簡單，無法適應(yīng)復(fù)雜優(yōu)化問題的求解。

為了解決上述問題，本文采用與BBO算法完全不同的理論基礎(chǔ)，將BBO算法的理論基礎(chǔ)即生物地理學(xué)理論改為群遷徙動(dòng)力學(xué)理論，而將生物地理系統(tǒng)設(shè)定為具有異質(zhì)結(jié)構(gòu)特征，從而形成一種新型的群智能優(yōu)化算法，稱為異質(zhì)空間結(jié)構(gòu)種群遷徙動(dòng)力學(xué)優(yōu)化算法（optimization algorithm of population migration dynamics with heterogeneous spatial structure，HSS-PMDO）。由于這兩種理論具有很大差別，因此本文提出的HSSPMDO算法與BBO算法及其改進(jìn)版完全不同。

2 HSS-PMDO算法基本原理

考慮優(yōu)化問題：

式中，X是一個(gè)n維向量；f(X)為目標(biāo)函數(shù)；gi(X)為第i個(gè)約束條件，I為約束條件個(gè)數(shù)；Rn是n維歐氏空間；S為解空間；f(X)和gi(X)沒有特殊的限制。

2.1 種群遷徙場景設(shè)計(jì)

假設(shè)某海島上有N個(gè)生物種群在W個(gè)獨(dú)立斑塊中活動(dòng)，這些斑塊的編號(hào)集合為H={1,2,…,W}。假設(shè)斑塊k上的種群集合為Pk，用種群編號(hào)表示為Pk=，k∈H，Nk表示斑塊k上的種群個(gè)數(shù)。該。假設(shè)所有種群中的每海島上種群總數(shù)為N=個(gè)生物個(gè)體具有特定的活動(dòng)方式，能夠從某一斑塊遷徙到另一斑塊。在同一時(shí)期，一個(gè)種群的個(gè)體能夠在多個(gè)斑塊上同時(shí)出現(xiàn)。

時(shí)期t，種群i在從斑塊s到斑塊k遷徙路線上的瞬時(shí)遷徙強(qiáng)度由下式?jīng)Q定[3]，即：

時(shí)期t，種群i中的生物個(gè)體數(shù)會(huì)受到遷徙的影響，其遷徙動(dòng)力學(xué)模型為：

式中，mi為種群遷徙強(qiáng)度因子，mi≥0表示種群特異性和遷徙路線的獨(dú)立性，mi=0表示種群i在所有斑塊中都不參與遷徙。

對(duì)于海島中的每個(gè)斑塊，可選的生存條件集合SC={競爭型，互利型，捕食-被食型，融合型}。若種群i遷徙到斑塊k，其對(duì)應(yīng)的生存條件為Ek∈SC，則該種群以該斑塊上的生存條件Ek生存。例如，假設(shè)斑塊2的生存條件是捕食-被食型，種群1遷徙到斑塊2上后，就會(huì)與該斑塊上已有種群構(gòu)成循環(huán)捕食-被食關(guān)系。

在海島中，種群根據(jù)其所在斑塊的狀況及其個(gè)體的意愿決定是否遷徙。當(dāng)某個(gè)種群發(fā)現(xiàn)本種群在當(dāng)前所在斑塊的密度過高或者生存適應(yīng)度變差，則該種群隨機(jī)選擇一個(gè)斑塊實(shí)施遷徙；當(dāng)一個(gè)種群發(fā)生遷徙時(shí)，其遷徙規(guī)模是隨機(jī)的。當(dāng)一種群遷徙到新的斑塊后，在該斑塊要生存一段時(shí)間。經(jīng)過一段時(shí)間后，種群再遷徙。如此重復(fù)，種群不斷得到進(jìn)化。

2.2 種群遷徙與生存策略

式中，ri稱為種群i的內(nèi)稟增長率；aij的正負(fù)符號(hào)和絕對(duì)值表示種群j對(duì)種群i的影響性質(zhì)和強(qiáng)度。

多個(gè)種群在某斑塊生活期間，其發(fā)展變化與所在斑塊的生存條件相關(guān)。對(duì)于斑塊k，有：

若斑塊k的生存條件為競爭型，則認(rèn)為種群間展開循環(huán)競爭活動(dòng)。對(duì)于種群i∈Pk，依據(jù)式（3）可得Lotka-Volterra多種群間循環(huán)競爭動(dòng)力學(xué)模型為：

式中，aij＞0。

若斑塊k的生存條件為互利型，則認(rèn)為種群間展開循環(huán)互利活動(dòng)。對(duì)于種群i∈Pk，依據(jù)式（3）可得Lotka-Volterra多種群間循環(huán)互利動(dòng)力學(xué)模型為：

式中，若i=j，則δij=-1；若i≠j，則δij=1;aij＞0。

若斑塊k的生存條件為捕食-被食型，則認(rèn)為種群間展開循環(huán)捕食-被食活動(dòng)。對(duì)于種群i∈Pk，依據(jù)式（3）可得Lotka-Volterra多種群間循環(huán)捕食-被食動(dòng)力學(xué)模型為：

式中，若i=j或j=i+1，則φij=-1；否則，φij=1;aij＞0。

2.3 優(yōu)化問題與海島的對(duì)應(yīng)關(guān)系

優(yōu)化問題的解空間與海島相對(duì)應(yīng)，每個(gè)種群對(duì)應(yīng)著優(yōu)化問題的一個(gè)試探解，種群的一個(gè)特征對(duì)應(yīng)于試探解中的一個(gè)變量。時(shí)期t，海島中斑塊k的Nk個(gè)種群所對(duì)應(yīng)的優(yōu)化問題的試探解集為；種群i的特征j與試探解的變量相對(duì)應(yīng)；種群i的強(qiáng)壯度指數(shù)與優(yōu)化問題（1）的目標(biāo)函數(shù)值的轉(zhuǎn)換關(guān)系為：

海島上的一個(gè)斑塊的生存適應(yīng)度（individual suitability index，ISI）描述了該斑塊的生存環(huán)境好壞，生存環(huán)境好的斑塊具有較高的ISI值。時(shí)期t，斑塊k的生存適應(yīng)度ISI(k,t)可用其上活躍的種群的平均強(qiáng)壯度指數(shù)（population suitability index，PSI）來描述：

2.4 種群進(jìn)化算子設(shè)計(jì)

2.4.1 斑塊上種群規(guī)模計(jì)算方法

（1）因種群遷徙導(dǎo)致的種群規(guī)模變化（遷徙算子）。假設(shè)種群i生活在斑塊k上，k∈H，該種群想遷徙到斑塊s上，依據(jù)式（2），斑塊k和s上的種群規(guī)模發(fā)生如下變化：

（2）因種群間競爭導(dǎo)致的種群規(guī)模變化。若斑塊k的生存條件為競爭型，則依據(jù)式（4），斑塊k上的種群i∈Pk的規(guī)模發(fā)生如下變化：

（3）因種群間互利導(dǎo)致的種群規(guī)模變化。若斑塊k的生存條件為互利型，則依據(jù)式（5），斑塊k上的種群i∈Pk的規(guī)模發(fā)生如下變化：

（4）因種群間捕食-被食導(dǎo)致的種群規(guī)模變化。若斑塊k的生存條件為捕食-被食型，則依據(jù)式（6），斑塊k上的種群i∈Pk的規(guī)模發(fā)生如下變化：

2.4.2 特征種群選擇

（1）普通種群集GSk的產(chǎn)生方法：從生活在斑塊k的Nk個(gè)種群中隨機(jī)挑出M個(gè)種群，但當(dāng)前種群i∈Pk不包括在內(nèi)，形成普通種群集合{a1,a2,…,aM}?Pk。

（2）優(yōu)勢(shì)種群集PSk的產(chǎn)生方法：從生活在斑塊k的Nk個(gè)種群中隨機(jī)挑出M個(gè)種群，這些種群的PSI指數(shù)要比當(dāng)前種群i∈Pk高，形成優(yōu)勢(shì)種群集PSk=

（3）強(qiáng)勢(shì)種群集QSk的產(chǎn)生方法：若當(dāng)前種群為i∈Pk，則從生活在斑塊k的Nk個(gè)種群中按照PSI指數(shù)和占比要比當(dāng)前種群i高，形成強(qiáng)勢(shì)種群集QSk=

2.4.3 演化算子設(shè)計(jì)

（1）競爭算子。若斑塊k的生存條件為競爭型，則對(duì)于當(dāng)前種群i∈Pk，k∈H，有：

式中，βs=Rnd(0.4,0.6)，αs=Rnd(0.6,0.9)，λs=Rnd(0.4,0.7)，p=Rnd(0,1)；j為從{1,2,…,n}中以概率E0隨機(jī)選擇的一個(gè)數(shù)，E0為特征影響概率；Rnd(a,b)表示在[a,b]區(qū)間產(chǎn)生的一個(gè)均勻分布的隨機(jī)數(shù)。

（2）互利算子。若斑塊k的生存條件為互利型，則對(duì)于種群i∈Pk，k∈H，有：

（3）捕食-被食算子。若斑塊k的生存條件為捕食-被食型，則對(duì)于種群i∈Pk,k∈H，有：

（4）選擇算子。將新一代種群與相應(yīng)的父代種群進(jìn)行比較，較優(yōu)者保存到下一代種群中，即：

2.5 HSS-PMDO算法設(shè)計(jì)

HSS-PMDO算法包括如下步驟：

（1）初始化：①令時(shí)期t=0，按第3章介紹的方法初始化本算法涉及到的所有參數(shù)。②將N個(gè)種群隨機(jī)分配給W個(gè)斑塊，使得W個(gè)斑塊上的種群數(shù)分別為N1,N2,…,NW；各斑塊上的種群編號(hào)的集合分別為P1,P2,…,PW；在生存條件集合SC中隨機(jī)選擇一個(gè)生存條件指定給每個(gè)斑塊，其結(jié)果是：W個(gè)斑塊的生存條件分別為E1,E2,…,EW。③隨機(jī)確定每個(gè)斑塊上的所有種群的生物個(gè)體數(shù)量，i∈Pk,k∈H。④隨機(jī)確定初始解，i∈Pk,k∈H；隨機(jī)確定Z*，Z*用于記錄當(dāng)前全局最優(yōu)解。

（2）執(zhí)行下列操作：。

2.6 時(shí)間復(fù)雜度估計(jì)

HSS-PMDO算法的時(shí)間復(fù)雜度計(jì)算過程如表1所示。

2.7 算法的收斂性分析

（1）Markov特性。從各算子式（14）～式（16）的定義知，時(shí)期t+1的任意新試探解的計(jì)算生成只與其在時(shí)期t的狀態(tài)有關(guān)，而與其以前是如何演變到當(dāng)前狀態(tài)的歷程無關(guān)，表明HSSPMDO算法的演進(jìn)過程具有Markov特性。

（2）“步步不差”特性。從選擇算子的定義式（17）知，時(shí)期t+1，對(duì)任一種群均有表明HSS-PMDO算法的演進(jìn)過程具有“步步不差”特性。

（3）HSS-PMDO算法全局收斂性。利用HSSPMDO算法的Markov特性和“步步不差”特性，可以證明HSS-PMDO算法的全局收斂性，其證明過程可參見文獻(xiàn)[25]。

3 HSS-PMDO算法的最佳參數(shù)確定

HSS-PMDO算法的參數(shù)由兩部分組成，一部分是與異質(zhì)空間結(jié)構(gòu)種群遷徙動(dòng)力學(xué)理論有關(guān)的參數(shù)，它們是mi、、ri、aij；另一部分是與算法時(shí)間復(fù)雜度相關(guān)的參數(shù)，即G、ε、W、M、N(N1,N2,…,NW)、R0、ISI0、E0。這些參數(shù)的確定方法如下：

（1）參數(shù)mi、、ri、aij的設(shè)置方法。這些參數(shù)由異質(zhì)空間結(jié)構(gòu)種群遷徙動(dòng)力學(xué)理論確定，是本算法的內(nèi)置參數(shù)，只要設(shè)置一次即可，無需修改。這些參數(shù)的設(shè)置方法如下[3]：

采用上述參數(shù)設(shè)置方法，可保證遷徙的種群分布具有很好的異質(zhì)性，而種群中的生物個(gè)體數(shù)具有很好的隨機(jī)性[3]。

（2）參數(shù)G、ε、W、N(N1,N2,…,NW)、R0、ISI0、M、E0的確定方法如下：

①無需精確設(shè)置的參數(shù)G、ε的設(shè)置方法。G的取值依據(jù)是為了防止迭代過程不滿足收斂條件時(shí)出現(xiàn)無限迭代，G=8 000～100 000；ε越小，所獲得的最優(yōu)解的精度越高，但計(jì)算時(shí)間越長，可取ε=10-5～10-10。

②可自動(dòng)調(diào)整的參數(shù)R0、ISI0的設(shè)置方法。參數(shù)R0、ISI0用來控制種群遷徙的強(qiáng)度，種群遷徙強(qiáng)度會(huì)影響種群特征的變化水平，這些參數(shù)可采用下列方法進(jìn)行自動(dòng)動(dòng)態(tài)設(shè)置：

③需根據(jù)實(shí)際情況進(jìn)行設(shè)置的參數(shù)W、N(N1,N2,…,NW)、M、E0的設(shè)置方法。W相當(dāng)于給種群分類，W越大，種群多樣性越好，算法探索能力越強(qiáng)，陷入局部最優(yōu)陷阱的概率越低，但計(jì)算時(shí)間越長；N(N1,N2,…,NW) 控制著任意斑塊上種群數(shù)，可取N1=N2=…=NW=N/W，故只要確定N和W的取值規(guī)律，即可確定N1,N2,…,NW；M和E0用來控制種群特征的變化范圍和程度。

綜上所述，HSS-PMDO算法需要人工根據(jù)實(shí)際情況進(jìn)行設(shè)置的關(guān)鍵參數(shù)只有N、W、M和E0，下面以著名的BUMP優(yōu)化問題[26]為例來確定N、W、M和E0的取值規(guī)律，該問題與工程實(shí)際問題較類似，其數(shù)學(xué)模型為：

表2描述了當(dāng)N=200，W=10，E0=0.01，n=50，G=8×105時(shí)，參數(shù)M與平均最優(yōu)目標(biāo)函數(shù)值（Favg）和平均計(jì)算時(shí)間（Tavg）之間的關(guān)系。它表明，當(dāng)M增加，Tavg和Favg的精度均不產(chǎn)生明顯的變化。因此，M=3～6比較合適。

Table 2 Relationship of parameter M with Favg and Tavg表2 參數(shù)M 與Favg 和Tavg 之間的關(guān)系

表3描述了當(dāng)N=200，W=10，M=3，n=50，G=8×105時(shí)，參數(shù)E0與Favg和Tavg之間的關(guān)系。結(jié)果表明，當(dāng)E0=0.001～0.080，精度比較高，但CPU時(shí)間增加適度；當(dāng)E0＞0.08，CPU時(shí)間相差很大，但精度也大大降低；尤其當(dāng)E0=1時(shí)，它無法獲得最優(yōu)解。因此，當(dāng)E0＝0.008～0.080時(shí)，HSS-PMDO算法性能最好，此時(shí)意味著最多只有0.008～0.080變量參與運(yùn)算。

表4描述了當(dāng)W=10，M=3，E0=0.01，n=50，G=8×105時(shí)，參數(shù)N/W與Favg和Tavg之間的關(guān)系。結(jié)果表明，當(dāng)N/W=10～30，精度比較高，但計(jì)算時(shí)間增加不多。

表5描述了當(dāng)W=10，N/W=20，M=3，n=50，G=8×105時(shí)，E0、n、Favg和Tavg之間的關(guān)系。從表5可以看到：當(dāng)n增加時(shí)，Tavg大大增加；對(duì)于給定的n，如果E0增加，F(xiàn)avg的精度會(huì)降低，但Tavg增加。因此，如果n≥300，E0可取小值，如E0=0.001；如果n＜300，E0可取大值，如E0=0.01～0.04。

Table 3 Relationship of parameter E0 with Favg and Tavg表3 參數(shù)E0 與Favg 和Tavg 之間的關(guān)系

Table 4 Relationship of parameter N/W with Favg and Tavg表4 參數(shù)N/W 與Favg 和Tavg 之間的關(guān)系

Table 5 Relationship among parameter n,E0, Favg and Tavg表5 n、E0、Favg 和Tavg 之間的關(guān)系

4 與其他群智能算法的比較

本文選用測(cè)試包CEC2013[27]中所提供的10個(gè)基準(zhǔn)函數(shù)優(yōu)化問題來測(cè)試HSS-PMDO算法的性能，如表6所示。

表6中O是可以任意設(shè)定的理論全局最優(yōu)解，其維數(shù)為n。F15、F22、F23、F26、F28的理論全局最優(yōu)解目前尚未發(fā)現(xiàn)。本文用HSS-PMDO算法求解表6中的10個(gè)基準(zhǔn)函數(shù)優(yōu)化問題，其參數(shù)是W=10，N/W=20，M=3，E0=0.01，n=50，G=8×105，ε=10-7。與HSS-PMDO算法進(jìn)行比較的7個(gè)最新改進(jìn)型BBO算法為DBBO[28]（disruption in biogeography-based optimization）、HBP-FNN+WE[13]（hybrid biogeographybased presentation with fitted nearest neighbor and widest exploration）、B-BBO[29]（blended biogeographybased optimization）、CARC-BBO[30]（chaotic adaptive realcoded biogeography-based optimization）、MpBBO[31]（metropolis biogeography-based optimization）、RCBBO[32]（real-coded biogeography-based optimization）、HBBO[33]（hybrid biogeography-based optimization）。其中DBBO算法通過修改BBO算法的遷移和變異兩個(gè)算子并引入一個(gè)中斷算子，可以顯著提高BBO算法的探索和求精能力。HBP-FNN+WE算法是在BBO算法中采用一種新的方法來描述候選解，并將該表達(dá)法和局部搜索相結(jié)合，從而提高算法性能。B-BBO算法對(duì)BBO算法進(jìn)行兩次擴(kuò)展：一是提出了一個(gè)混合遷移算子；二是通過修改BBO算法的遷入和遷出機(jī)制來處理約束，該算法不需要任何額外的調(diào)整參數(shù)。CARC-BBO算法采用基于混沌自適應(yīng)實(shí)數(shù)編碼來改進(jìn)BBO算法。MpBBO算法采用BBO算法與模擬退火算法SA（simulated annealing）相結(jié)合的方法，以改善BBO算法的性能，該算法通過SA的Metropolis準(zhǔn)則選擇下一個(gè)遷移島。RCBBO算法是一種采用基于實(shí)數(shù)編碼的BBO算法。HBBO算法是一種將進(jìn)化算法EA（evolution algorithm）和BBO算法相結(jié)合的算法。該算法包括兩種雜交方法：一是迭代級(jí)雜交，其中各種EA和BBO按順序執(zhí)行；二是算法級(jí)雜交，它獨(dú)立運(yùn)行各種EA，然后利用BBO的思想在它們之間交換信息。這7個(gè)算法的參數(shù)設(shè)置可參見文獻(xiàn)[28-33]，求解優(yōu)化問題時(shí)的終止運(yùn)行條件與HSS-PMDO相同。

Table 6 10 benchmark function optimization problems表6 10個(gè)基準(zhǔn)函數(shù)優(yōu)化問題

針對(duì)表6中列出的10個(gè)優(yōu)化問題，用HSSPMDO算法和7個(gè)被比較算法進(jìn)行求解，每個(gè)算法均獨(dú)立求解51次，表7給出了求解結(jié)果。

表7中總排名1是這8個(gè)算法基于平均最優(yōu)目標(biāo)函數(shù)值進(jìn)行的排名，總排名2是這8個(gè)算法基于平均最優(yōu)目標(biāo)函數(shù)值和適應(yīng)度評(píng)價(jià)次數(shù)進(jìn)行的排名；最終總排名1和最終總排名2是分別基于總排名1和總排名2所進(jìn)行的排名。

Table 7 Solution results表7 求解結(jié)果

續(xù)表

從表7可以看出，對(duì)7個(gè)算法進(jìn)行排序所得的結(jié)果均為：

HSS-PMDO＞RCBBO＞B-BBO＞HBP-FNN+WE＞DBBO＞HBBO＞MpBBO＞CARC-BBO

圖1（a）～圖1（j）給出了各個(gè)算法求解時(shí)的樣本收斂曲線，其中的水平和垂直軸采用對(duì)數(shù)刻度。

Fig.1 Sample convergence curves圖1 樣本收斂曲線

5 算法的性能分析

5.1 算子的性能分析

在HSS-PMDO算法中，只要每個(gè)斑塊上的任意一個(gè)種群的規(guī)模發(fā)生變化，其生存條件對(duì)應(yīng)的算子就會(huì)被執(zhí)行。當(dāng)HSS-PMDO算法求解F3時(shí)，隨機(jī)選擇斑塊3、5、8，其對(duì)應(yīng)的生存條件分別為競爭型、互利型和捕食-被食型，圖2描述了競爭、互利和捕食-被食算子被觸發(fā)執(zhí)行的次數(shù)與CPU計(jì)算時(shí)間之間的關(guān)系。從圖2可知，每種算子被觸發(fā)執(zhí)行的次數(shù)隨CPU計(jì)算時(shí)間隨機(jī)變化，但平均觸發(fā)執(zhí)行次數(shù)接近于水平，表明競爭、互利和捕食-被食算子幾乎被均勻觸發(fā)執(zhí)行。

Fig.2 Relationship between the number of times the operator is triggered to run and CPU time圖2 算子被觸發(fā)執(zhí)行的次數(shù)與CPU時(shí)間之間的關(guān)系

5.2 種群的動(dòng)態(tài)行為分析

為了分析種群的動(dòng)態(tài)行為，當(dāng)使用HSS-PMDO算法求解基準(zhǔn)函數(shù)F3時(shí)，隨機(jī)選擇種群27實(shí)施追蹤，圖3描述了種群27在搜索空間進(jìn)行搜索時(shí)的運(yùn)動(dòng)軌跡。從圖3可以看出，種群27并沒有朝著更壞的方向移動(dòng)，因?yàn)樵摲N群對(duì)應(yīng)的PSI指數(shù)一直在增加。

5.3 求精能力、探索能力及其平衡性分析

Fig.3 Moving track of population 27圖3 種群27的移動(dòng)軌跡

（1）求精能力分析。求精能力描述了HSSPMDO的算子在局部區(qū)域內(nèi)（即某個(gè)鄰域）提升最優(yōu)解精度的能力，表現(xiàn)方式是個(gè)體在其收斂曲線上的某些區(qū)段以近似水平方式緩慢提升最優(yōu)解的精度。圖4描述了當(dāng)HSS-PMDO算法求解F2時(shí)，各個(gè)算子被調(diào)用的情況。從圖4可以看到，只要收斂曲線出現(xiàn)近似水平發(fā)展態(tài)勢(shì)，競爭算子被執(zhí)行的次數(shù)明顯高于互利算子和捕食-被食算子。此現(xiàn)象表明競爭算子主要負(fù)責(zé)HSS-PMDO算法的局部區(qū)域求精。

Fig.4 Analysis on ability of exploitation,exploration and their balance圖4 求精能力、探索能力及其平衡性分析

（2）探索能力分析。探索能力描述了HSS-PMDO算法探索新空間的能力，表現(xiàn)方式是個(gè)體在其收斂曲線上的某些區(qū)段以傾斜向上的方式快速更新最優(yōu)解。從圖4可以看到，只要收斂曲線出現(xiàn)以傾斜向上的發(fā)展態(tài)勢(shì)，競爭算子被執(zhí)行的次數(shù)明顯降低，互利算子和捕食-被食算子執(zhí)行的次數(shù)不斷增多。此現(xiàn)象表明互利算子和捕食-被食算子主要負(fù)責(zé)HSSPMDO算法的新空間探索，這兩個(gè)算子只需被調(diào)度執(zhí)行較少次數(shù)，就可以快速探索出新空間，其執(zhí)行效率很高。

（3）求精和探索能力的協(xié)調(diào)性分析。從圖4可知，HSS-PMDO算法求解F2時(shí)，其收斂曲線的緩（求精能力）和陡（探索能力）交替出現(xiàn)，且緩的持續(xù)時(shí)間少于陡的持續(xù)時(shí)間，此表明HSS-PMDO算法的求精和探索能力的協(xié)調(diào)性很好。

6 結(jié)束語

本文依據(jù)生活在某海島上的生物種群在各斑塊之間的遷徙行為，采用種群遷徙動(dòng)力學(xué)理論提出了HSS-PMDO算法，該算法具有如下特征：

（1）HSS-PMDO算法采用與BBO算法完全不同的設(shè)計(jì)思路，即BBO算法采用的是生物地理學(xué)理論，而HSS-PMDO算法采用的是種群遷徙動(dòng)力學(xué)理論，這兩種理論存在很大差別。

（2）算法參數(shù)設(shè)置根據(jù)充足，需要人工依據(jù)實(shí)際情況設(shè)置的參數(shù)較少。算法中參數(shù)分為四部分，即依據(jù)種群遷徙動(dòng)力學(xué)理論進(jìn)行設(shè)置的內(nèi)置參數(shù)、依據(jù)演化進(jìn)程自動(dòng)進(jìn)行調(diào)整設(shè)置的參數(shù)、無需精確設(shè)置的參數(shù)、依據(jù)優(yōu)化問題的實(shí)際情況需人工設(shè)置的參數(shù)，需人工設(shè)置的參數(shù)只有四個(gè)。

（3）各算子分工明確。HSS-PMDO算法包括遷徙算子、競爭算子、互利算子、捕食-被食算子和選擇算子，這些算子大幅增加了其搜索能力。其中，競爭算子可提升算法的求精能力；互利算子和捕食-被食算子負(fù)責(zé)提升算法的探索能力；遷徙算子負(fù)責(zé)種群的多樣性動(dòng)態(tài)調(diào)整，使得種群間信息交換充分，從而提升了探索能力和求精能力的平衡性；選擇算子可確保算法具有全局收斂性。

（4）通過自動(dòng)降維方式提升算法收斂速度和對(duì)求解較高維數(shù)優(yōu)化問題的適應(yīng)性。因HSS-PMDO算法每次進(jìn)化時(shí)僅涉及到種群的極少部分特征（0.1%～8.0%）的信息更新，即當(dāng)種群間交換信息時(shí)，只有極少一部分特征參與運(yùn)算，故本文算法收斂速度快，具有求解維數(shù)較高的優(yōu)化問題的能力。

（5）具有全局收斂性。HSS-PMDO算法所涉及的演化過程能充分體現(xiàn)種群遷徙動(dòng)力學(xué)理論的基本特征，演化過程具有Markov特性和“步步不差”特性，從而確保HSS-PMDO算法具有全局收斂性。

本文算法下一步需要改進(jìn)的方向：

（1）進(jìn)一步利用種群遷徙動(dòng)力學(xué)理論優(yōu)化HSSPMDO算法的相關(guān)參數(shù)，使得這些參數(shù)設(shè)置更合理。

（2）深入研究種群遷徙算子、競爭算子、互利算子、捕食-被食算子的動(dòng)態(tài)特征。

（3）深入研究HSS-PMDO算法求解過程中各斑塊的動(dòng)態(tài)特征。

（4）依據(jù)種群遷徙動(dòng)力學(xué)理論的變種，對(duì)HSSPMDO算法進(jìn)行改進(jìn)。

（5）將BBO算法的一些特征，融入到HSSPMDO算法中。