基于改進的遷移率模型的生物地理學優化算法

王雅萍 張正軍 顏子寒 金亞洲

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

關鍵詞：生物地理學優化;遷移率模型;邏輯回歸函數;三次多項式;雙曲正切函數

中圖分類號：TP301.6

文獻標志碼：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 引言

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

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

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

1 生物地理學優化算法

1.1 生物地理學

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

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

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分別為當前棲息地物種數量為S時的遷入率和遷出率。式（1）是考慮以下三種情況所得的：

1）當前棲息地在t時刻的物種數量為S，并且在接下去的Δt時間內不發生遷移。

2）當前棲息地在t時刻的物種數量為S-1，并且在接下去的Δt時間內有一個物種遷入。

3）當前棲息地在t時刻的物種數量為S+1，并且在接下去的Δt時間內有一個物種遷出。

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

=AP（2）

1.2 生物地理學優化算法

基于以上生物地理學理論，通過遷移和變異不斷更新棲息地的適應度，構成了生物地理學優化算法。遷移步驟如算法1所示。

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

程序前

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

If Hi被選擇

For每個棲息地

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

If Hj被選擇

從Hj中隨機選擇遷出SIV σ

將Hi中隨機選取的SIV替換為σ

End

End

End

程序后

變異步驟如算法2所示。

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

程序前

對于棲息地Hi

For 每個SIV

根據λi和μi計算變異概率Pi

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

If Hi（j）被選擇

將Hi（j）替換為隨機產生的SIV

End

End

程序后

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

算法3 BBO算法。

程序前

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

計算各棲息地的HSI

While 停止條件未滿足 do

將各棲息地按照HIS從高到低進行排序

利用算法1進行遷移操作

更新各棲息地的HIS

利用算法2進行變異操作

保持當前迭代所有棲息地中的精英

End while

程序后

2 遷移率模型

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

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

模型1 原始線性模型。

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

λk=I（1-k/n）

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

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

模型2 余弦模型。

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

λk=I2coskπn+1

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

如圖1（b）所示，在余弦遷移率模型下，當物種數量較多或較少時，遷移率變化比較平穩;當具有一定物種數量時，遷移率相對變化較快。

模型3 Logistic模型。

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

λk=I1-11+en2-k

μk=E1+en2-k（11）

如圖1（c）所示，在Logistic遷移率模型下，當物種數量較多或較少時，遷移率變化非常平穩;當具有一定物種數量時，遷移率變化很快。

模型4 三次多項式模型。

三次多項式模型的遷入率和遷出率如下：

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

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

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

模型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）下，遷移率隨物種數量變化的趨勢類似于余弦模型，但是幅度比余弦模型更緩和些。

3 實證分析

在python3.6的環境下，針對17個典型的基準函數，分別利用提出的三種基于非線性遷移率模型的BBO算法進行測試，并與原始線性遷移率模型以及相關改進算法中表現優異的余弦遷移率模型[7]進行對比分析。基準函數信息如下所示。

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

所有測試函數有且僅有一個全局最小值點，其中f3、 f5、 f7、 f12、 f15和f16有許多局部極小值點，優化算法在尋找最優解時容易陷入局部極小值點而無法達到全局最小值點。

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

3.1 遷移率模型優化性能分析

為了平行比較基于不同遷移率模型的BBO算法的性能，有關參數設置如下：

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

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

由表1可知，從平均值的角度來看，不同遷移率模型優化性能差別很大。總體來說，模型5在大多測試函數上表現最佳，模型2其次，而模型4表現差強人意，僅在3個測試函數上優于模型1。

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

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

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

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

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

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

3.2 穩定性分析

改變物種最大變異率可以調節解的多樣性。為了研究不同

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

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

由表3可知，不同變異率下所得平均值和最小值變化不一， f7、 f8、 f9受變異率的影響較大，其余函數受影響較小?？傮w上變異率為0.01時模型性能最佳，并且在多數測試函數上模型5的表現優于模型1。

4 結語

生物地理學優化算法性能受其遷移率模型影響顯著。本文提出三種新的非線性遷移率模型，并應用于17個典型的基準函數求最小值問題。結果顯示，在多數測試函數下，基于雙曲正切變體遷移率模型的BBO算法尋優能力最佳，其解更接近函數的全局最小值。變異率作為影響BBO算法優化性能的另一重要因素，有待進一步研究。

參考文獻

[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]馬海平，李雪，林升東.生物地理學優化算法的遷移率模型分析[J].東南大學學報（自然科學版），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]吳斌，林錦國，崔志勇.生物地理學優化算法中遷移算子的比較[J].計算機工程與應用，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]唐繼勇，仲元昌，曾廣樸.基于遷出地動態選擇與自適應遷入策略的BBO算法[J].計算機科學，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.