基于雙模式遷移策略的生物地理學(xué)優(yōu)化算法

李昌興, 張 穎

(西安郵電大學(xué) 理學(xué)院， 陜西 西安 710121)

生物地理學(xué)優(yōu)化(biogeography-based optimization, BBO)算法是一種基于生物學(xué)種群遷移理論的進(jìn)化算法[1]，BBO算法具有良好的性能，目前已被廣泛應(yīng)用到多目標(biāo)規(guī)劃[2]、復(fù)雜系統(tǒng)優(yōu)化[3]等多個(gè)領(lǐng)域中。BBO算法具有獨(dú)特的遷移算子和變異算子，具有良好的全局搜索能力、較強(qiáng)的開發(fā)能力和信息共享能力[4]，但其探索能力較弱，局部搜索能力不強(qiáng)，特別是在迭代后期，算法搜索動(dòng)力不足，容易陷入局部最優(yōu)，導(dǎo)致收斂慢或者無(wú)法收斂，其穩(wěn)定性和精度較差[5]。需要對(duì)該算法進(jìn)行改進(jìn)，以平衡算法的開發(fā)能力、探索能力[6]以及跳出局部最優(yōu)的能力，提高收斂速度。

差分進(jìn)化(differential evolution, DE)算法具有較強(qiáng)的探索能力，且能夠快速定位全局最小區(qū)域[7]，可將BBO算法與DE算法相結(jié)合，以平衡算法開發(fā)能力和探索能力，目前已存在很多將BBO算法與DE算法相結(jié)合的研究，如文獻(xiàn)[8]將DE算法的局部搜索策略與BBO算法的遷移策略相結(jié)合，融入DE算法中的選擇操作，提出了基于局部搜索策略的BBO算法。文獻(xiàn)[9]將DE算法與BBO算法相結(jié)合，提出一種兩階段差分BBO算法。文獻(xiàn)[10]結(jié)合DE算法和BBO算法的遷移策略，改進(jìn)BBO算法中的遷移算子和變異算子，給出了二重遷移算子和二重變異算子，使得棲息地個(gè)體具有更高的進(jìn)化概率。文獻(xiàn)[11]將DE算法的差分算子引入個(gè)體遷移，并將改進(jìn)的個(gè)體遷移與傳統(tǒng)的基因遷移相結(jié)合。這些改進(jìn)均在一定程度上提高了算法的優(yōu)化性能，但在收斂精度、速度以及穩(wěn)定性上仍有待提高。

為了進(jìn)一步加快BBO算法的收斂速度，提高算法的收斂精度和穩(wěn)定性，本文擬提出一種基于雙模式遷移策略生物地理學(xué)優(yōu)化(dual-mode migration BBO, DMMBBO)算法，在標(biāo)準(zhǔn)的BBO算法基礎(chǔ)上，采用更接近自然規(guī)律的余弦遷移率模型，引入自適應(yīng)的差分變異算子，改進(jìn)遷移算子，并將改進(jìn)后遷移算子與標(biāo)準(zhǔn)的遷移算子相結(jié)合形成雙遷移模式，在迭代過程中利用參數(shù)平衡兩種遷移模式，優(yōu)化DMMBBO算法的性能。為了驗(yàn)證改進(jìn)算法的性能，采用10個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，并將改進(jìn)后算法的優(yōu)化結(jié)果和優(yōu)化曲線與兩種單模式算法進(jìn)行比較，驗(yàn)證改進(jìn)后算法的收斂速度、收斂精度和穩(wěn)定性。

1 標(biāo)準(zhǔn)BBO算法

BBO算法是一種基于生物學(xué)種群遷移理論的進(jìn)化算法。該算法的基本思想是通過物種遷移的方式，實(shí)現(xiàn)不同棲息地之間的交流與共享，從而尋求問題的最優(yōu)解[1]。BBO算法主要描述了生物如何從一個(gè)棲息地遷徙到另一個(gè)棲息地，物種數(shù)量在棲息地上如何上升或者下降。因每個(gè)棲息地在地理上與其他棲息地獨(dú)立，故只能通過遷移方式進(jìn)行物種交換。適合物種生存的棲息地具有較高的適宜度指數(shù)(habitat suitability index, HSI)。用適宜度指數(shù)變量(suitable index vector, SIV)來描述與HSI相關(guān)的因素，如棲息地的溫度、濕度、降雨量等，各適宜度變量被稱為SIVs[1]。在BBO算法中，每一個(gè)棲息地代表問題的一個(gè)解決方案，SIV等同于遺傳算法(genetic algorithm, GA)中的基因。HSI相當(dāng)于GA中的適應(yīng)度值，將這些解決方案按照HSI進(jìn)行排序，其中，HSI較高的棲息地被認(rèn)為是更優(yōu)的解決方案。此外，每個(gè)棲息地都有遷入率λ和遷出率μ兩個(gè)屬性，它們的大小取決于棲息地的HSI。一個(gè)棲息地的HSI越低，它的遷入率就越低，遷出率越高。

BBO算法是由初始化、遷移和變異3個(gè)過程組成。

(1) 初始化

對(duì)棲息地的適宜度指數(shù)變量SIV進(jìn)行初始化，令n個(gè)棲息地的D維適宜度指數(shù)變量可用矩陣

X=[X1,X2,…,Xn]

表示，第i(i=1,2,…,n)個(gè)棲息地的SIV表示為

Xi=(xi,1,xi,2,…,xi,D)，

棲息地Xi的第j(j=1,2,…,D)個(gè)元素可表示為

xi,j=Lj+rand×(Uj-Lj)。

(1)

其中，Lj表示第j列變量的下限，Uj表示第j列變量的上限。

(2) 遷移

為實(shí)現(xiàn)棲息地之間的信息流通，采用遷移操作模擬生物地理學(xué)的遷徙機(jī)制。將所有棲息地的解按照HSI從小到大的順序排列，對(duì)排序后棲息地編號(hào)賦予新的i值，計(jì)算棲息地的種群數(shù)量

Si=Smax-i(i=1,2,…,n)。

其中Smax為所有棲息地包含物種數(shù)的最大值，一般設(shè)Smax=n。

定義棲息地Xk的遷入率λk和遷出率μk，即令

(2)

其中k為棲息地Xk所包含的物種數(shù)量，I為最大遷入率，E為最大遷出率。

首先，根據(jù)全局遷移率Pmod選擇需要遷入的棲息地Xk，確定Xk后，以棲息地Xk的遷入率λk依概率選擇各SIV變量決定是否遷入。其次，根據(jù)遷出率μi(i≠k)選擇遷出地Xi，以棲息地Xi的對(duì)應(yīng)的SIV，替換棲息地Xk的SIV。

(3) 變異

為增加種群的多樣性，采用變異操模擬自然環(huán)境中的一些突發(fā)情況。首先，根據(jù)各棲息地的種群數(shù)量概率P(j)計(jì)算對(duì)應(yīng)的變異概率m(j)，突變概率函數(shù)與該棲息地的種群數(shù)量概率成反比，其相應(yīng)的函數(shù)關(guān)系為

其中，mmax為用戶自定義突變率的最大值，Pmax為P(j)中的最大值。

其次，以變異概率m(j)選擇進(jìn)行突變操作的棲息地Xj，在給定范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)SIV對(duì)Xj中的SIV進(jìn)行替換。

2 DMMBBO算法

DMMBBO算法是BBO算法的一種改進(jìn)，DMMBBO算法在標(biāo)準(zhǔn)的BBO算法的基礎(chǔ)上做了兩個(gè)方面改進(jìn)：一方面，采用余弦遷移率模型代替標(biāo)準(zhǔn)BBO算法的線性遷移率模型；另一方面，引入自適應(yīng)差分變異算子對(duì)遷移算子進(jìn)行改進(jìn)，并提出一種雙模式的遷移策略。

2.1 余弦遷移率模型

BBO算法對(duì)于遷移模型非常敏感。標(biāo)準(zhǔn)的BBO算法采用線性遷移率模型，其遷入、遷出率表達(dá)式如式(2)所示，該模型過于簡(jiǎn)單，且不符合自然規(guī)律。實(shí)際上，接近自然規(guī)律的遷移率模型性能要優(yōu)于簡(jiǎn)單的線性遷移率模型[12]，因此，選擇較接近自然規(guī)律的余弦遷移率模型，其遷移模型如圖1所示。

圖1 余弦遷移模型

從圖1中可以看出，當(dāng)棲息地物種數(shù)量較少或較多時(shí)，遷入率和遷出率變化較平穩(wěn)，而當(dāng)物種數(shù)量處于中間數(shù)量時(shí)，遷入率和遷出率變化較快。遷入、遷出率表達(dá)式分別為[12]

2.2 雙模式遷移策略

在標(biāo)準(zhǔn)BBO算法的基礎(chǔ)上，提出一種雙模式的遷移策略。遷移模式1引入一種帶有自適應(yīng)的差分遷移算子，遷移模式2為經(jīng)典的遷移算子。為了平衡兩種遷移模式，添加一個(gè)參數(shù)Pb來平衡這兩種遷移策略。

首先，隨機(jī)生成一個(gè)0～1之間的隨機(jī)數(shù)Pdr，當(dāng)Pdr>Pb時(shí)，遷移方式選擇模式2，即標(biāo)準(zhǔn)BBO算法遷移模式。當(dāng)Pdr

(1)從1～n中隨機(jī)選取兩個(gè)數(shù)r1和r2，選擇條件為r1≠r2≠k≠GBest，其中，k為本次根據(jù)遷入率選擇遷入地的棲息地標(biāo)號(hào)，Gbest為本次迭代的最優(yōu)棲息地標(biāo)號(hào)。

(2)引入差分變異算子，產(chǎn)生的新的候選解

(3)

其中，Hi為第i個(gè)候選解，i=1,2,…,n；Hr1、Hr2為2個(gè)不同的候選解；HBest為當(dāng)前最優(yōu)的候選解，F(xiàn)為縮放因子。

將差分變異算子與原遷移算子相結(jié)合，得到

(4)

其中，xBest,j、xr1,j、xr2,j分別為當(dāng)前最優(yōu)棲息地和2個(gè)隨機(jī)選中棲息地第j維的值；F1=(μBest+μk)/2，F(xiàn)2=(μr1+μr2)/2。

(5)

采用公式(5)對(duì)種群進(jìn)行遷移操作，其中，ω為0～1之間的隨機(jī)數(shù)。

雙模式的遷移策略，其流程如圖2所示。

圖2 雙模式遷移策略的流程

3 實(shí)驗(yàn)結(jié)果及分析

3.1 測(cè)試函數(shù)

為了測(cè)試算法的性能，選取10個(gè)基準(zhǔn)測(cè)試函數(shù)對(duì)優(yōu)化的結(jié)果進(jìn)行測(cè)試。

所選取的基準(zhǔn)測(cè)試函數(shù)，如表1 所示。其中，f1～f5皆為僅有一個(gè)極值點(diǎn)的單峰函數(shù)，用于測(cè)試算法的收斂特性。f6為只有一個(gè)極值點(diǎn)的梯狀函數(shù)，f7為一個(gè)帶有噪聲的多峰函數(shù)，極值點(diǎn)隨均勻分布隨機(jī)數(shù)的變化而變化。f8～f10皆為具有多個(gè)局部極值點(diǎn)的多峰函數(shù)，其極值點(diǎn)的個(gè)數(shù)隨問題的維數(shù)呈指數(shù)式增加[13]，用于測(cè)試算法跳出局部最優(yōu)能力和逼近全局最優(yōu)能力。

表1 基準(zhǔn)測(cè)試函數(shù)

3.2 參數(shù)設(shè)置

算法參數(shù)設(shè)置為，種群規(guī)模n=50，測(cè)試函數(shù)的維數(shù)D=20，迭代次數(shù)為G=50，最大遷入率I=1，最大遷出率E=1，變異率Pmutate=0.01，全局遷移率Pmod=1，精英個(gè)體保留數(shù)量為2。由于算法存在一定的隨機(jī)性，為了避免誤差，所有算法獨(dú)立運(yùn)行20次。

3.3 測(cè)試結(jié)果及分析

為了比較算法的性能，應(yīng)用基準(zhǔn)測(cè)試函數(shù)對(duì)改進(jìn)后的DMMBBO與標(biāo)準(zhǔn)的生物地理學(xué)算法(standard biogeography-based optimization, SBBO)和引入自適應(yīng)差分遷移算子的單模式BBO算法(single-mode migration BBO, SMBBO)進(jìn)行比較。以平均值和標(biāo)準(zhǔn)差對(duì)算法的優(yōu)化能力進(jìn)行評(píng)價(jià)。平均值用于評(píng)價(jià)算法的精度和可靠性，平均值越小，該算法的精度越高，可靠性越強(qiáng)。標(biāo)準(zhǔn)差用于評(píng)價(jià)算法的穩(wěn)定性，標(biāo)準(zhǔn)差越小，該算法穩(wěn)定性越高。3種算法的測(cè)試結(jié)果，如表2所示。

表2 3種算法對(duì)10個(gè)標(biāo)準(zhǔn)函數(shù)優(yōu)化的測(cè)試結(jié)果

從表2可見，不論單峰函數(shù)還是多峰函數(shù)，在參數(shù)相同的情況下，DMMBBO算法相較于SMBBO算法和SBBO算法更能收斂到較小值，結(jié)果更逼近于最優(yōu)解。DMMBBO算法的收斂精度更高，收斂性更強(qiáng)。改進(jìn)算法的平均值和標(biāo)準(zhǔn)差都相對(duì)較小，說明DMMBBO的算法的穩(wěn)定性更強(qiáng)，特別是函數(shù)f1，其平均值和標(biāo)準(zhǔn)差均達(dá)到了10-6數(shù)量級(jí)，相對(duì)于BBO算法和SBBO算法提高了6個(gè)數(shù)量級(jí)，算法的性能提升較大。這可能是因?yàn)橐氩罘肿儺愃阕赢a(chǎn)生的結(jié)果。DE算法具有較強(qiáng)的探索能力，在遷移算子中引入差分變異算子有效平衡了算法的開發(fā)能力和探索能力，使得算法能夠快速定位全局最優(yōu)位置，提升全局優(yōu)化能力。為了進(jìn)一步評(píng)價(jià)算法的收斂速度以及平衡參數(shù)Pb對(duì)算法收斂速度的影響，通過描繪算法的收斂曲線分析其性能。不同算法的最優(yōu)值收斂曲線，如圖3所示。

(a) 測(cè)試函數(shù)f1(b) 測(cè)試函數(shù)f2

(c) 測(cè)試函數(shù)f3 (d) 測(cè)試函數(shù)f4

(e) 測(cè)試函數(shù)f6 (f) 測(cè)試函數(shù)f7

(g) 測(cè)試函數(shù)f8 (h) 測(cè)試函數(shù)f9

圖3中，橫坐標(biāo)表示各函數(shù)的迭代次數(shù)，縱坐標(biāo)表示優(yōu)化得到的最小值。由于測(cè)試函數(shù)在迭代后期所得數(shù)值數(shù)量級(jí)差距較大，為便于觀察，縱坐標(biāo)的數(shù)值都取10為底的對(duì)數(shù)。當(dāng)平衡參數(shù)Pb取0～0.50時(shí)，測(cè)試函數(shù)均出現(xiàn)了早熟現(xiàn)象。圖3畫出了當(dāng)Pb分別取0、0.50、0.65、0.75、0.85、1.00時(shí)，函數(shù)f1～f4、f6～f9的最優(yōu)值收斂曲線，對(duì)應(yīng)曲線分別命名為SBBO、DMMBBO-0.50、DMMBBO-0.65、DMMBBO-0.75、DMMBBO-0.85，DMMBBO-1.00。

從圖3收斂曲線的趨勢(shì)可以看出，當(dāng)參數(shù)Pb取0時(shí)，在迭代中后期，SBBO算法因探索能力較弱，使得收斂速度過慢，易陷入局部最優(yōu)解；當(dāng)參數(shù)Pb值從0.50不斷增大時(shí)，隨著迭代次數(shù)的增加，DMMBBO算法的收斂速度明顯加快，但當(dāng)Pb取值過高時(shí)(如DMMBBO-1.00)，收斂速度又會(huì)變慢；如圖3(a)、圖3(b)、圖3(c)、圖3(d)和圖3(h)所示，對(duì)于單峰函數(shù)f1～f4和多峰函數(shù)f9，當(dāng)參數(shù)Pb取0.75時(shí)DMMBBO-0.75曲線的收斂速度最快，算法能夠收斂到更小值；如圖3(e)、圖3(f)和圖3(g)所示，對(duì)于測(cè)試函數(shù)f6～f8，比較參數(shù)Pb分別取0.50、0.65、0.75和0.85時(shí)的4種收斂曲線，發(fā)現(xiàn)當(dāng)參數(shù)Pb取0.65時(shí)DMMBBO-0.65曲線收斂速度最快，算法能夠收斂到更小值。

從圖3中的8種函數(shù)的收斂曲線可以發(fā)現(xiàn)，不論單峰函數(shù)還是多峰函數(shù)，改進(jìn)后算法的收斂速度都有了較大提升，且平衡參數(shù)Pb取過大或過小都會(huì)損害DMMBBO算法的性能，導(dǎo)致算法收斂速度過慢，出現(xiàn)早熟等現(xiàn)象，當(dāng)參數(shù)Pb取0.65～0.75時(shí)DMMBBO算法的性能達(dá)到最優(yōu)。

4 結(jié)語(yǔ)

標(biāo)準(zhǔn)的BBO算法存在局部探索能力不足，收斂速度過慢、收斂精度不高、算法不穩(wěn)定等問題，為此提出了一種基于雙模式遷移策略的生物地理學(xué)算法，該算法采用余弦遷移模型，在標(biāo)準(zhǔn)遷移策略的基礎(chǔ)上進(jìn)行了修改，將帶有自適應(yīng)差分算子的遷移策略與標(biāo)準(zhǔn)遷移策略結(jié)合，然后通過調(diào)節(jié)參數(shù)Pb平衡兩種遷移模式，以提升算法的性能。為了驗(yàn)證改進(jìn)后算法的性能，將DMMBBO算法應(yīng)用于10個(gè)基準(zhǔn)的測(cè)試函數(shù)上進(jìn)行測(cè)試，測(cè)試結(jié)果表明，DMMBBO算法相較于兩種單模式算法，收斂速度、收斂精度和算法穩(wěn)定性都有了較大的提升，并通過調(diào)整平衡參數(shù)，當(dāng)Pb取0.65～0.75時(shí)算法改進(jìn)的效果最佳。