基于生物地理優化算法的數值積分方法實驗

張 晶， 唐權華， 賈 璐

(1. 四川宜賓學院 圖書館， 四川 宜賓 644007； 2. 江西師范大學 軟件學院，江西 南昌 330022；3. 西南交通大學 峨嵋校區， 四川 峨嵋 614202)

0 引 言

數值積分計算方法是連接工程問題與科學計算的橋梁；是便于應用計算機解決實際工程問題的具體算法。在數值積分計算中，常用的有梯形法、Simpson法等很多傳統計算方法[1-3]。這些傳統的計算方法精度較低，可利用非數值優化方法來求解數值積分，例如粒子群算法[4]。數值積分計算方法通過不等距節點積分方法，在積分區間內任意選取一定節點，通過粒子群算法(Particle Swarm Optimization，PSO)優化這些節點，得到了比較精確的積分結果。該方法好于梯形法和Simpson法，但PSO算法收斂速度慢、收斂精度低[5-6]，在一定程度也會降低數值積分的精度。因此，有必要采用更有效的智能優化算法來求解數值積分問題。

Simon依據生物種群在棲息地的分布、遷移、變異和滅絕的規律，首次提出了生物地理優化算法(Biogeography-Based Optimization，BBO)[7]。與PSO相比，BBO具有簡單方便、參數少、收斂速度快、收索精度高的特點，已經被應用到很多工程技術問題[8-15]。因此，本文利用BBO算法求解數值積分問題，并與傳統的計算方法和PSO算法進行對比。

1 BBO的基本原理

BBO算法通過群體中相鄰個體的遷徙和特殊個體的變異來尋找全局最優解[7-10]。在BBO算法中，生物種群生活在不同的棲息地 (Habitat，H)，每個棲息地根據物種種類的多少決定該棲息地的適應性特性。

定義1適合物種居住的棲息地有較高的棲息地適應性指數(Habitat Suitability Index,HSI)：H→R，R表示實數，表示對解集適應度的評價[9-10]。在優化問題中，若選擇HIS適應度函數量化，則好的解集具有高HIS的棲息地;反之則具有低HSI的棲息地。

定義2與HSI有關的特性如雨量、溫度等，用適合指數變量(Suitability Index Variables,SIV)描述：SIV∈C，C為整數集，表示構成H的元素。若存在H∈SIVn，則由n個SIV構成的矢量表示優化問題的可能解[10]。

BBO算法的核心操作是物種的遷徙和變異。每個棲息地都有自己的遷入率和遷出率，通過棲息地之間的遷移，棲息地之間可以直接分享適應性特性，個別棲息地物種的變異能進一步提升該棲息地的適應性。設棲息地具有物種種類S的概率為PS，在t到t+Δt時間內，概率PS改變為PS(t+Δt)，則有：

PS(t+Δt)=PS(t)(1-(λS+μS)Δt)+

PS-1(t)λS-1Δ(t)+PS+1(t)μS+1Δ(t)

(1)

式中：λS和μS分別表示該棲息地物種種類為S時的物種遷入率和遷出率。為了使式(1)成立，即使得t+Δt內有S類物種，必須滿足相關條件[11]，當Δt足夠小，式(1)對時間取極限，得：

PS=-(λS+μS)PS+λS-1PS-1+μS+1PS+1

(2)

設物種種群最大數為Smax，最大遷入率為E，最大遷出率為I，并令E=I。物種遷移模型如圖1所示。從圖中可以看出，在遷移率為E時，μS為0，物種種類為0；當λS=μS時，物種種類達到穩定狀態S0；當λS=0，uS=E時，物種種類達到最大值Smax。因此，可以得到：

遷移算子采用離散方式，即將鄰近棲息地Hj中的SIV遷移給Hi中的SIV：

Hi(SIV)=Hj(SIV)

(6)

設最大變異率為mmax，棲息地個數為n，則基于線

圖1 棲息地物種遷移模型

性的變異率模型如下：

m(S)=mmax(1-PS/Pmax)

(7)

式中，Pmax=arg maxPi，i=1,2,…,n。

2 BBO求解數值積分

依據不等距節點原理，BBO求解數值積分具體算法如下：

(1) 初始化BBO算法參數。首先給出棲息地數量n、棲息地最大種群數Smax、最大遷入率E和最大遷出率I，最大變異率mmax，優化問題的維度D等參數，然后隨機初始化每個棲息地的HIV向量xi(i=1,2,…,n)，每個HIV向量對應于優化問題的一個可能解。

(2) 計算棲息地的適應度f(xi)。根據文獻[4]，將xi置于積分區間的左右端點之間，并按照升序排列，積分區間總共有D+2個節點和D+1小段。先計算D+2個節點相鄰節點之間的距離dj(j=1,2,…,D)，再計算D+2個節點對應的函數值和D+1個小段中間節點的函數值。對比每小段左端點、中間節點和右端點積分函數值，函數值最小的記為wj，最大的記為Wj(j=1,2,…,D+1)，從而得到第i個棲息地的適應度為

(8)

(3) 計算棲息地的遷入率和變異率，重新計算適應度f(xi)。計算棲息地i對應的物種種類Si，遷入率λS和遷出率uS，通過遷移和變異，重新計算棲息地i的適應度函數f(xi)。

(4) 判斷是否滿足停止條件，并輸出數值積分結果。若達到指定精度或者迭代次數，停止迭代;否則跳轉到(3)，繼續迭代。算法結束時，采用改進的數值積分計算公式：

(9)

式中：gj為積分區間第j個端點的積分函數值;gj+0.5為第j和j+1端點之間的積分函數值。

3 仿真實驗

(a) x2

(d) sinx

(e) 1/(1+x)

(f) ex

圖2 積分函數的適應度變化

表2 基于不同積分方法的函數x/(4+x2)計算結果

圖3 積分函數x/(4+x2)的適應度變化曲線

4 結 語

本文介紹了生物地理優化算法的基本原理，并給出了基于生物地理優化算法求解數值積分方法和步驟。數值積分函數算例仿真結果表明，生物地理優化算法求解數值積分精度高，自適應性強，積分結果明顯好于粒子群算法、梯形法和Simpson法。

[1] 王能超.計算方法—算法設計及其Matlab實現[M ].北京：高等教育出版社, 2008：45-55.

[2] 李慶揚，王能超，易大義.數值分析[M].4版. 武漢：華中科技大學出版社，2006：86-89.

[3] 呂同富，康兆敏，方秀男.數值計算方法[M].2版. 北京：清華大學出版社，2012：258-264.

[4] 韋杏瓊，周永權.基于粒子群算法的數值積分方法研究[J].微電子學與計算機,2009,26(7)：118-119.

WEI Xing-qiong, ZHOU Yong-quan. Numerical Integral Method Research Based on PSO [J]. Microelectronics & Computer, 2009，26(7)：118-119.

[5] Kennedy J,Eberhart R C.Particle swarm optimization[C]//Proc of the IEEE International Conference on Neural Networks.Piscataway, NJ:IEEE Service Center,1995:1942-1948.

[6] 黃少榮.粒子群優化算法綜述[J].計算機工程與應用，2009，30(8)：1977-1980.

HUANG Shao-rong. Survey of particle swarm optimization algorithm[J].Computer Engineering and Design, 2009，30(8)：1977-1980.

[7] DAN Simon. Biogeography-based optimization[J].IEEE Transactions on Evolutionary Computation, 2008, 12(6): 702-713.

[8] 張 萍，魏 平，于鴻洋，等.基于混沌的生物地理分布優化算法[J].電子科技大學學報，2012,41(1): 65-67.

ZHANG Ping, WEI Ping, YU Hong-yang,etal. Biogeography-Based Optimization Algorithm by Using Chaotic Search[J]. Journal of University of Electronic Science and Technology of China, 2012,41(1): 65-67.

[9] 馬海平，李 雪，林升東.生物地理學優化算法的遷移率模型分析[J].東南大學學報(自然科學版)，2009，39(1)：17-21.

MA Hai-ping, LI Xue, LIN Sheng-dong. Analysis of migration ratemodels for biogeography-based optimization[J]. Journal of Southeast University ( Natural Science Edition), 2009，39(1)：17-21.

[10] 馬海平，陳子棟，潘張鑫.一類基于物種遷移優化的進化算法[J].控制與決策,2009，24(11):1621-1624.

MA Hai-ping,CHEN Zi-dong, PAN Zhang-xin. Evolutionary algorithm based on species migration optimization[J]. Control and Decision, 2009,24(11):1621-1624.

[11] 張 萍，魏 平，于鴻洋.一種基于生物地理優化的快速運動估計算法[J].電子與信息學報,2011,33(5):1018-1025.

ZHANG Ping, WEI Ping, YU Hong-yang. A Biogeography-based Optimization Algorithm for Fast Motion Estimation [J]. Journal of Electronics & Information Technology, 2011,33(5):1018-1025.

[12] 王存睿，王楠楠，段曉東,等.生物地理學優化算法綜述[J].計算機科學，2010，37(7)：35-37.

WANG Cun-rui, WANG Nan-nan,DUAN Xiao-dong,etal. Survey of Biogeography-based Optimization[J].Computer Science, 2010，37(7)：35-37.

[13] 蔡之華,龔文引,LING C X.基于進化規劃的新型生物地理學優化算法研究[J].系統工程理論與實踐，2010，30( 6) : 1106-1112.

CAI Zhi-hua,GONG Wen-yin,LING C X.Research on a Novel Biogeography-Based Optimization Algorithm Based on Evolutionary Programming[J].Systems Engineering-Theory & Practice，2010，30( 6) : 1106-1112.

[14] Boussad I,Chatterjee A,Siarry P,etal.Two-Stage Update Biogeography-Based Optimization Using Differential Evolution Algorithm ( DBBO)[J].Computers and Operations Research，2011，38 ( 8 ) : 1188-1198.

[15] 畢曉君,王 玨.基于混合遷移策略的生物地理學優化算法[J].模式識別與人工智能,2012,25(5):769-774.

BI Xiao-Jun,WANG Jue. Biogeography-Based Optimization Based on Hybrid Migration Strategy[J].PR & AI, 2012,25(5):769-774.