李昌興, 張 穎

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

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

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

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

1 標準BBO算法

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

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

(1) 初始化

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

X=[X1,X2,…,Xn]

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

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

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

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

(1)

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

(2) 遷移

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

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

其中Smax為所有棲息地包含物種數(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的對應的SIV，替換棲息地Xk的SIV。

(3) 變異

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

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

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

2 DMMBBO算法

DMMBBO算法是BBO算法的一種改進，DMMBBO算法在標準的BBO算法的基礎上做了兩個方面改進：一方面，采用余弦遷移率模型代替標準BBO算法的線性遷移率模型；另一方面，引入自適應差分變異算子對遷移算子進行改進，并提出一種雙模式的遷移策略。

2.1 余弦遷移率模型

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

圖1 余弦遷移模型

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

2.2 雙模式遷移策略

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

首先，隨機生成一個0～1之間的隨機數(shù)Pdr，當Pdr>Pb時，遷移方式選擇模式2，即標準BBO算法遷移模式。當Pdr

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

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

(3)

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

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

(4)

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

(5)

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

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

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

3 實驗結(jié)果及分析

3.1 測試函數(shù)

為了測試算法的性能，選取10個基準測試函數(shù)對優(yōu)化的結(jié)果進行測試。

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

表1 基準測試函數(shù)

3.2 參數(shù)設置

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

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

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

表2 3種算法對10個標準函數(shù)優(yōu)化的測試結(jié)果

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

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

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

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

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

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

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

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

4 結(jié)語

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