基于改進(jìn)的遷移率模型的生物地理學(xué)優(yōu)化算法

王雅萍 張正軍 顏?zhàn)雍? 金亞洲

摘 要：生物地理學(xué)優(yōu)化（BBO）算法通過遷移和變異不斷更新棲息地，以尋找最優(yōu)解，其中遷移率模型的優(yōu)劣會(huì)直接影響算法的優(yōu)化性能。針對原始BBO算法采用線性遷移率模型適應(yīng)性不足的問題，基于Logistic函數(shù)、三次多項(xiàng)式函數(shù)以及雙曲正切函數(shù)提出了三種新的非線性遷移率模型，并應(yīng)用于原始BBO算法中。對17個(gè)典型的基準(zhǔn)函數(shù)進(jìn)行優(yōu)化性能測試，結(jié)果表明，基于雙曲正切函數(shù)的遷移率模型所得解更接近函數(shù)的全局最小值，總體表現(xiàn)優(yōu)于原始線性遷移率模型的BBO算法以及相關(guān)改進(jìn)算法中表現(xiàn)優(yōu)異的余弦遷移率模型。穩(wěn)定性測試結(jié)果表明，在不同的變異率下，基于雙曲正切函數(shù)的遷移率模型在多數(shù)測試函數(shù)上表現(xiàn)優(yōu)于原始線性遷移率模型。在滿足解多樣性的基礎(chǔ)上，該模型能夠較好地適應(yīng)非線性遷移問題，提高尋優(yōu)能力。

關(guān)鍵詞：生物地理學(xué)優(yōu)化;遷移率模型;邏輯回歸函數(shù);三次多項(xiàng)式;雙曲正切函數(shù)

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A

Biogeography-based optimization algorithms based on improved migration rate models

WANG Yaping， ZHANG Zhengjun*， YAN Zihan， JIN Yazhou

School of Science， Nanjing University of Science and Technology， Nanjing Jiangsu 210094， China

Abstract：

Biogeography-Based Optimization （BBO） algorithm updates habitats through migration and mutation continuously to find the optimal solution， and the migration model affects the performance of the algorithm significantly. In view of the problem of insufficient adaptability of the linear migration model used in the original BBO algorithm， three nonlinear migration models were proposed. These models are based on Logistic function， cubic polynomial function and hyperbolic tangent function respectively. Optimization experiments were carried out on 17 typical benchmark functions， and results show that the migration model based on hyperbolic tangent function performs better than the linear migration model of original BBO algorithm and cosine migration model with good performance of improved algorithm. Stability test shows that the migration model based on hyperbolic tangent function performs better than the original linear migration model with different mutation rates on most test functions. The model satisfies the diversity of the solutions， and better adapts to the nonlinear migration problem with improved search ability.

Key words：

Biogeography-Based Optimization （BBO）; migration rate model; logistic regression function; cubic polynomial; hyperbolic tangent function

0 引言

受生物地理學(xué)[1-5]啟發(fā)，Simon[6]于2008年提出了生物地理學(xué)優(yōu)化（Biogeography-Based Optimization， BBO）算法。BBO算法中的主要操作為遷移和變異。根據(jù)物種中每個(gè)個(gè)體的適應(yīng)度函數(shù)，通過遷移和變異尋找全局最小值點(diǎn)。Simon在最初的BBO算法中采用線性遷移率模型，并實(shí)證證明與其他基于物種的優(yōu)化算法相比，BBO在多數(shù)特定測試函數(shù)上表現(xiàn)更好，具有一定的實(shí)際應(yīng)用價(jià)值。

馬海平等[7]根據(jù)生物地理學(xué)物種分布情況，提出了指數(shù)遷移率模型、二次遷移率模型和余弦遷移率模型，在8個(gè)基準(zhǔn)函數(shù)上進(jìn)行測試分析;Ma[8]還提出了常數(shù)與線性混合遷移率模型和梯形遷移率模型[8]。Simon[9]提出了簡化版的BBO算法，并且利用概率論分析其優(yōu)化性能。吳斌等[10]提出了三種遷移操作模式，實(shí)驗(yàn)結(jié)果表明遷入主導(dǎo)的部分遷移式算子優(yōu)化性能最佳。Feng等[11]在更新棲息地的過程中引入了隨機(jī)棲息地，進(jìn)而豐富物種多樣性。Farswan等[12]在更新棲息地的過程中引入了遷入棲息地、隨機(jī)棲息地，增加了解的多樣性;他們還引入最佳棲息地，進(jìn)一步修正更新規(guī)則[13]。Guo等[14]提出均勻混合遷移算子、啟發(fā)式遷移算子以及拓展式遷移算子，提高了基本BBO算法的探索能力。唐繼勇等[15]提出了一種基于動(dòng)態(tài)選擇遷出地與混合自適應(yīng)遷入的優(yōu)化策略，提高了全局搜索能力。

本文介紹了BBO算法，并針對BBO算法中線性遷移率模型適應(yīng)性不足的問題，分別基于Logistic函數(shù)、三次多項(xiàng)式以及雙曲正切函數(shù)提出了三種非線性遷移率模型應(yīng)用于BBO算法的遷移操作。實(shí)證表明，基于雙曲正切函數(shù)遷移率模型的BBO算法在多數(shù)測試函數(shù)下表現(xiàn)最佳，其解更接近函數(shù)的全局最小值。

1 生物地理學(xué)優(yōu)化算法

1.1 生物地理學(xué)

生物地理學(xué)由自然學(xué)家Alfred Wallace和Charles Darwin于19世紀(jì)提出，其數(shù)學(xué)模型描述了物種在棲息地之間的遷移、新物種的產(chǎn)生以及物種的滅絕。棲息地適宜度指數(shù)（Habitat Suitability Index， HSI）用以衡量棲息地適合物種生存的程度，該值越大則越適宜物種生存。HSI由許多因素構(gòu)成，包括氣溫、降水、植被的多樣性以及土地面積等。這些影響HIS的因素稱為適宜度指數(shù)變量（Suitability Index Variable， SIV）。由于棲息地的資源有限，通常適宜度高的棲息地趨向于容納較多物種，且本地物種有較大的可能性遷出到其他棲息地，同時(shí)外來物種的遷入率較低;而適宜度低的棲息地趨向于包含較少的物種，且外來物種有較大的可能性遷入本地，同時(shí)遷出的可能性較小。此外，自然災(zāi)害等大變動(dòng)事件也可能會(huì)改變棲息地的狀態(tài)，進(jìn)而影響HSI。

為了形式化地描述BBO模型，假設(shè)某棲息地容納物種數(shù)量為S的概率為Ps。則由Ps在t時(shí)刻的取值，可得其在（t+Δt）時(shí)刻的取值：

Ps（t+Δt）=Ps（t）（1-λsΔt-μsΔt）+Ps-1（t）λs-1Δt+Ps+1（t）λs+1Δt（1）

其中：λs和μs分別為當(dāng)前棲息地物種數(shù)量為S時(shí)的遷入率和遷出率。式（1）是考慮以下三種情況所得的：

1）當(dāng)前棲息地在t時(shí)刻的物種數(shù)量為S，并且在接下去的Δt時(shí)間內(nèi)不發(fā)生遷移。

2）當(dāng)前棲息地在t時(shí)刻的物種數(shù)量為S-1，并且在接下去的Δt時(shí)間內(nèi)有一個(gè)物種遷入。

3）當(dāng)前棲息地在t時(shí)刻的物種數(shù)量為S+1，并且在接下去的Δt時(shí)間內(nèi)有一個(gè)物種遷出。

當(dāng)Δt足夠小時(shí)，期間發(fā)生超過一次遷移的概率幾乎為0。令P=[P0，P1，…，Pn]T，n=Smax ，由此可得式（1）的極限形式：

=AP（2）

1.2 生物地理學(xué)優(yōu)化算法

基于以上生物地理學(xué)理論，通過遷移和變異不斷更新棲息地的適應(yīng)度，構(gòu)成了生物地理學(xué)優(yōu)化算法。遷移步驟如算法1所示。

算法1 BBO算法中的遷移步驟。

程序前

以正比于λi的概率選擇遷入棲息地Hi

If Hi被選擇

For每個(gè)棲息地

以正比于μi的概率選擇遷出棲息地Hj

If Hj被選擇

從Hj中隨機(jī)選擇遷出SIV σ

將Hi中隨機(jī)選取的SIV替換為σ

End

End

End

程序后

變異步驟如算法2所示。

算法2 BBO算法中的變異步驟。

程序前

對于棲息地Hi

For 每個(gè)SIV

根據(jù)λi和μi計(jì)算變異概率Pi

以正比于Pi的概率選擇變異SIV為Hi（j）

If Hi（j）被選擇

將Hi（j）替換為隨機(jī)產(chǎn)生的SIV

End

End

程序后

BBO算法流程如算法3所示。

算法3 BBO算法。

程序前

初始化物種數(shù)量、遷移率、變異率以及精英數(shù)。

計(jì)算各棲息地的HSI

While 停止條件未滿足 do

將各棲息地按照HIS從高到低進(jìn)行排序

利用算法1進(jìn)行遷移操作

更新各棲息地的HIS

利用算法2進(jìn)行變異操作

保持當(dāng)前迭代所有棲息地中的精英

End while

程序后

2 遷移率模型

Simon采用線性模型來模擬自然界中物種遷移的規(guī)律，即認(rèn)為隨著物種數(shù)量的增加，遷入率呈線性遞減趨勢，同時(shí)遷出率呈線性遞增趨勢。在相關(guān)改進(jìn)算法中，Ma等[7]提出的余弦遷移率模型在其測試的多數(shù)函數(shù)下表現(xiàn)最佳，認(rèn)為接近自然規(guī)律的遷移率模型優(yōu)于簡單的線性模型。

為了更好地適應(yīng)非線性遷移問題，本文提出三種不同變化趨勢的非線性遷移率模型，并與原始線性模型以及相關(guān)改進(jìn)算法中表現(xiàn)優(yōu)異的余弦遷移率模型[7]進(jìn)行對比分析。如圖1所示，在最大遷入率I和最大遷出率E下，遷入率λk和遷出率μk是關(guān)于物種數(shù)量k的函數(shù)，k0為遷入率等于遷出率的平衡點(diǎn)。

模型1 原始線性模型。

線性模型的遷入率和遷出率如下：

λk=I（1-k/n）

μk=E（k/n）（9）

如圖1（a）所示，在線性遷移率模型下，隨著物種數(shù)量的增加，遷入率從I開始線性下降至0，同時(shí)遷出率從0開始線性上升至E。

模型2 余弦模型。

余弦模型[7]的遷入率和遷出率如下。

λk=I2coskπn+1

μk=E2-coskπn+1（10）

如圖1（b）所示，在余弦遷移率模型下，當(dāng)物種數(shù)量較多或較少時(shí)，遷移率變化比較平穩(wěn);當(dāng)具有一定物種數(shù)量時(shí)，遷移率相對變化較快。

模型3 Logistic模型。

Logistic模型的遷入率和遷出率如下：

λk=I1-11+en2-k

μk=E1+en2-k（11）

如圖1（c）所示，在Logistic遷移率模型下，當(dāng)物種數(shù)量較多或較少時(shí)，遷移率變化非常平穩(wěn);當(dāng)具有一定物種數(shù)量時(shí)，遷移率變化很快。

模型4 三次多項(xiàng)式模型。

三次多項(xiàng)式模型的遷入率和遷出率如下：

λk=I2-（2k-n）3n3+1

μk=E2（2k-n）3n3+1（12）

如圖1（d）所示，在三次多項(xiàng)式遷移率模型下，在物種數(shù)量較多或較少時(shí)，遷移率變化較快;而具有一定物種數(shù)量時(shí)，遷移率變化趨于平緩。

模型5 雙曲正切變型模型。

雙曲正切變型模型的遷入率和遷出率如下。

λk=I2-ak-n2-a-k+n2ak-n2+a-k+n2+1

μk=E2ak-n2-a-k+n2ak-n2+a-k+n2+1（13）

如圖1（e）所示，在雙曲正切變型遷移率模型（本文取a=1.1）下，遷移率隨物種數(shù)量變化的趨勢類似于余弦模型，但是幅度比余弦模型更緩和些。

3 實(shí)證分析

在python3.6的環(huán)境下，針對17個(gè)典型的基準(zhǔn)函數(shù)，分別利用提出的三種基于非線性遷移率模型的BBO算法進(jìn)行測試，并與原始線性遷移率模型以及相關(guān)改進(jìn)算法中表現(xiàn)優(yōu)異的余弦遷移率模型[7]進(jìn)行對比分析?；鶞?zhǔn)函數(shù)信息如下所示。

1）Sphere：

f1（x）=∑Di=1xi2; -10≤xi≤10， D=20

2）Schwefel221：

f2（x）=maxxi; 1≤i≤D， -10≤xi≤10， D=20

3）Griewank：

f3（x）=∑Di=1xi24000-∏Di=1cos（xi/i）+1;

-600≤xi≤600， D=20

4）Axis parallel hyper ellipsoid：

f4（x）=∑Di=1ixi2; -5.12≤xi≤5.12， D=20

5）Alpine：

f5（x）=∑Di=1xi sin xi+0.1xi; -10≤xi≤10， D=20

6）Exponential：

f6（x）=-exp（-0.5∑Di=1xi2）; -1≤xi≤1， D=20

7）Cosine mixture：

f7（x）=∑Di=1xi2-0.1∑Di=1cos（5πxi）; -1≤xi≤1，D=20

8）Zakharov function：

f8（x）=∑Di=1xi2+（∑Di=10.5ixi）2+（∑Di=10.5ixi）4;

-5≤xi≤10， D=20

9）De jongs：

f9（x）=∑Di=1ixi4; -5.12≤xi≤5.12， D=20

10）Michalewicz：

f10（x）=-∑Di=1sin（xi）sin2m（ix2i/π）; 0≤xi≤π， D=10

11）Easom：

f11（x）=-cos（x1）cos（x2）e-（x1-π）2-（x2-π）2，

-100≤xi≤100， D=2

12）Ackley：

f12（x）=-20 exp（-0.21D∑Di=1x2i）-

exp（1D∑Di=1cos（2πxi））+20+e; -30≤xi≤30， D=20

13）Schwefel222：

f13（x）=∑Di=1xi+∏Di=1xi; -10≤xi≤10， D=20

14）Step function

f14（x）=∑Di=1（xi+0.5」）2; -100≤xi≤100， D=20

15）Schwefel：

f15（x）=418.9829D-∑Di=1xi sin（xi12）;-500≤xi≤500， D=20

16）Rastrigin：

f16（x）=10D+∑Di=1[xi2-10 cos（2πxi）];-5.12≤xi≤5.12， D=20

17）Salomon prol 3：

f17（x）=1-cos（2π∑Di=1xi2）+0.1∑Di=1xi2;-100≤xi≤100， D=20

所有測試函數(shù)有且僅有一個(gè)全局最小值點(diǎn)，其中f3、 f5、 f7、 f12、 f15和f16有許多局部極小值點(diǎn)，優(yōu)化算法在尋找最優(yōu)解時(shí)容易陷入局部極小值點(diǎn)而無法達(dá)到全局最小值點(diǎn)。

f10的全局最小值為-9.66015， f6和f11的全局最小值為-1， f7的全局最小值為-2，其余函數(shù)全局最小值均為0。

3.1 遷移率模型優(yōu)化性能分析

為了平行比較基于不同遷移率模型的BBO算法的性能，有關(guān)參數(shù)設(shè)置如下：

最大遷移率I=E=1，物種（棲息地）數(shù)量PopSize=30，迭代次數(shù)Iteration=50，變異率m=0.01。

為了降低算法中隨機(jī)因素的影響，各模型獨(dú)立運(yùn)行50次，觀察平均值和最小值。5種模型測試結(jié)果的平均值如表1所示。

由表1可知，從平均值的角度來看，不同遷移率模型優(yōu)化性能差別很大。總體來說，模型5在大多測試函數(shù)上表現(xiàn)最佳，模型2其次，而模型4表現(xiàn)差強(qiáng)人意，僅在3個(gè)測試函數(shù)上優(yōu)于模型1。

17個(gè)函數(shù)在不同遷移率模型下求解的平均最小值誤差百分比變化趨勢如圖2所示。

由圖2可知，就平均最小值誤差百分比而言，對于多數(shù)測試函數(shù)來說，模型4的誤差百分比最大，而模型2和模型5長期處于較低的誤差水平。在不考慮模型4的情況下，函數(shù)f5、 f6、 f8、 f9和f17受遷移率模型影響較大，其余函數(shù)受遷移率模型影響相對較小。

5種模型測試結(jié)果的最佳最小值如表2所示。

由表2可知，從最小值的角度來看，模型5的表現(xiàn)仍然優(yōu)異，并且模型4的優(yōu)化性能有所提升，而模型2的尋優(yōu)能力有所降低。

17個(gè)函數(shù)在不同遷移率模型下求解的最佳最小值誤差百分比變化趨勢如圖3所示。

由圖3可知，就最佳最小值誤差百分比而言，BBO算法尋找函數(shù)最小值時(shí)受遷移率模型影響很大。模型5的總體表現(xiàn)最穩(wěn)定，在14個(gè)測試函數(shù)上誤差小于模型1，并且長期處于低誤差水平。模型2的性能有所下降，僅在9個(gè)測試函數(shù)上誤差小于模型1。

3.2 穩(wěn)定性分析

改變物種最大變異率可以調(diào)節(jié)解的多樣性。為了研究不同

遷移率模型的穩(wěn)定性，對比分析原始線性模型（模型1）和本文所

提最佳模型（模型5）在不同遷移率下的表現(xiàn)，如表3所示。

由表3可知，不同變異率下所得平均值和最小值變化不一， f7、 f8、 f9受變異率的影響較大，其余函數(shù)受影響較小。總體上變異率為0.01時(shí)模型性能最佳，并且在多數(shù)測試函數(shù)上模型5的表現(xiàn)優(yōu)于模型1。

4 結(jié)語

生物地理學(xué)優(yōu)化算法性能受其遷移率模型影響顯著。本文提出三種新的非線性遷移率模型，并應(yīng)用于17個(gè)典型的基準(zhǔn)函數(shù)求最小值問題。結(jié)果顯示，在多數(shù)測試函數(shù)下，基于雙曲正切變體遷移率模型的BBO算法尋優(yōu)能力最佳，其解更接近函數(shù)的全局最小值。變異率作為影響B(tài)BO算法優(yōu)化性能的另一重要因素，有待進(jìn)一步研究。

參考文獻(xiàn)

[1]WALLACE A R. The geographical distribution of animals [J]. Nature， 1958， 182（4629）： 140-141.

[2]DARWIN C. The Origin of Species [M]. New York： Bantam Classics， 1995： 218-230.

[3]HANSKI I， GILPIN M E. Metapopulation Biology [M]. New York： Academic Press， 1997： 63-67.

[4]XING B， GAO W-J. Biogeography-based optimization algorithm [M]// Innovative Computational Intelligence： A Rough Guide to 134 Clever Algorithms， LSRL 62. Berlin： Springer， 2014： 81-91.

[5]GUO W， WANG L， WU Q. Numerical comparisons of migration models for multi-objective-biogeography-based optimization [J]. Information Sciences， 2016， 328（C）： 302-320.

[6]SIMON D. Biogeography-based optimization [J]. IEEE Transactions on Evolutionary Computation， 2008， 12（6）： 702-713.

[7]馬海平，李雪，林升東.生物地理學(xué)優(yōu)化算法的遷移率模型分析[J].東南大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，39（S1）：16-21.（MA H P， LI X， LIN S D. Analysis of migration rate models for biogeography-based optimization [J]. Journal of Southeast University （Natural Science Edition）， 2009， 39（S1）： 16-21.）

[8]MA H. An analysis of the equilibrium of migration models for biogeography-based optimization [J]. Information Sciences—Informatics and Computer Science， Intelligent Systems， Applications： An International Journal， 2010， 180（18）： 3444-3464.

[9]SIMON D. A probabilistic analysis of a simplified biogeography-based optimization algorithm [J]. Evolutionary Computation， 2011， 19（2）： 167-188.

[10]吳斌，林錦國，崔志勇.生物地理學(xué)優(yōu)化算法中遷移算子的比較[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（25）：61-64.（WU B， LIN J G， CUI Z Y. Compative study of migration operators in biogeography optimization [J]. Computer Engineering and Applications， 2012， 48（25）： 61-64.）

[11]FENG Q， LIU S， ZHANG J， et al. Biogeography-based optimization with improved migration operator and self-adaptive clear duplicate operator [J]. Applied Intelligence， 2014， 41（2）： 563-581.

[12]FSRSWAN P， BANSAL J C. Migration in biogeography-based optimization [C]// Proceedings of the 4th International Conference on Soft Computing for Problem Solving， AISC 336. Berlin： Springer， 2014： 389-401.

[13]FARSWAN P， BANSAL J C， DEEP K. A modified biogeography based optimization [M]// Harmony Search Algorithm， AISC 382. Berlin： Springer， 2016： 227-238.

[14]GUO W， WANG L， SI C， et al. Novel migration operators of biogeography-based optimization and Markov analysis [J]. Soft Computing， 2016， 21（22）： 6605-6632.

[15]唐繼勇，仲元昌，曾廣樸.基于遷出地動(dòng)態(tài)選擇與自適應(yīng)遷入策略的BBO算法[J].計(jì)算機(jī)科學(xué)，2016，43（10）：282-286.（TANG J Y， ZHONG Y C， ZENG G P. Biogeography-based optimization with adaptive immigration and dynamic selection emigration strategy [J]. Computer Science， 2016， 43（10）： 282-286.）

This work is partially supported by the National Natural Science Foundation of China （61773014）.

WANG Yaping， born in 1995， M. S. candidate. Her research interests include data mining.

ZHANG Zhengjun， born in 1965， Ph. D.， associate professor. His research interests include data mining， graphics and images.

YAN Zihan， born in 1995， M. S. candidate. Her research interests include data mining.

JIN Yazhou， born in 1993， M. S. candidate. His research interests include data mining.