基于生物地理優(yōu)化算法的數(shù)值積分方法實(shí)驗(yàn)

張 晶， 唐權(quán)華， 賈 璐

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

0 引 言

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

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

1 BBO的基本原理

BBO算法通過(guò)群體中相鄰個(gè)體的遷徙和特殊個(gè)體的變異來(lái)尋找全局最優(yōu)解[7-10]。在BBO算法中，生物種群生活在不同的棲息地 (Habitat，H)，每個(gè)棲息地根據(jù)物種種類(lèi)的多少?zèng)Q定該棲息地的適應(yīng)性特性。

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

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

BBO算法的核心操作是物種的遷徙和變異。每個(gè)棲息地都有自己的遷入率和遷出率，通過(guò)棲息地之間的遷移，棲息地之間可以直接分享適應(yīng)性特性，個(gè)別棲息地物種的變異能進(jìn)一步提升該棲息地的適應(yīng)性。設(shè)棲息地具有物種種類(lèi)S的概率為PS，在t到t+Δt時(shí)間內(nèi)，概率PS改變?yōu)镻S(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分別表示該棲息地物種種類(lèi)為S時(shí)的物種遷入率和遷出率。為了使式(1)成立，即使得t+Δt內(nèi)有S類(lèi)物種，必須滿足相關(guān)條件[11]，當(dāng)Δt足夠小，式(1)對(duì)時(shí)間取極限，得：

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

(2)

設(shè)物種種群最大數(shù)為Smax，最大遷入率為E，最大遷出率為I，并令E=I。物種遷移模型如圖1所示。從圖中可以看出，在遷移率為E時(shí)，μS為0，物種種類(lèi)為0；當(dāng)λS=μS時(shí)，物種種類(lèi)達(dá)到穩(wěn)定狀態(tài)S0；當(dāng)λS=0，uS=E時(shí)，物種種類(lèi)達(dá)到最大值Smax。因此，可以得到：

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

Hi(SIV)=Hj(SIV)

(6)

設(shè)最大變異率為mmax，棲息地個(gè)數(shù)為n，則基于線

圖1 棲息地物種遷移模型

性的變異率模型如下：

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

(7)

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

2 BBO求解數(shù)值積分

依據(jù)不等距節(jié)點(diǎn)原理，BBO求解數(shù)值積分具體算法如下：

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

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

(8)

(3) 計(jì)算棲息地的遷入率和變異率，重新計(jì)算適應(yīng)度f(wàn)(xi)。計(jì)算棲息地i對(duì)應(yīng)的物種種類(lèi)Si，遷入率λS和遷出率uS，通過(guò)遷移和變異，重新計(jì)算棲息地i的適應(yīng)度函數(shù)f(xi)。

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

(9)

式中：gj為積分區(qū)間第j個(gè)端點(diǎn)的積分函數(shù)值;gj+0.5為第j和j+1端點(diǎn)之間的積分函數(shù)值。

3 仿真實(shí)驗(yàn)

(a) x2

(d) sinx

(e) 1/(1+x)

(f) ex

圖2 積分函數(shù)的適應(yīng)度變化

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

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

4 結(jié) 語(yǔ)

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

[1] 王能超.計(jì)算方法—算法設(shè)計(jì)及其Matlab實(shí)現(xiàn)[M ].北京：高等教育出版社, 2008：45-55.

[2] 李慶揚(yáng)，王能超，易大義.數(shù)值分析[M].4版. 武漢：華中科技大學(xué)出版社，2006：86-89.

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

[4] 韋杏瓊，周永權(quán).基于粒子群算法的數(shù)值積分方法研究[J].微電子學(xué)與計(jì)算機(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] 黃少榮.粒子群優(yōu)化算法綜述[J].計(jì)算機(jī)工程與應(yīng)用，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] 張 萍，魏 平，于鴻洋，等.基于混沌的生物地理分布優(yōu)化算法[J].電子科技大學(xué)學(xué)報(bào)，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] 馬海平，李 雪，林升東.生物地理學(xué)優(yōu)化算法的遷移率模型分析[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版)，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] 馬海平，陳子棟，潘張?chǎng)?一類(lèi)基于物種遷移優(yōu)化的進(jìn)化算法[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] 張 萍，魏 平，于鴻洋.一種基于生物地理優(yōu)化的快速運(yùn)動(dòng)估計(jì)算法[J].電子與信息學(xué)報(bào),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] 王存睿，王楠楠，段曉東,等.生物地理學(xué)優(yōu)化算法綜述[J].計(jì)算機(jī)科學(xué)，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ìn)化規(guī)劃的新型生物地理學(xué)優(yōu)化算法研究[J].系統(tǒng)工程理論與實(shí)踐，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] 畢曉君,王 玨.基于混合遷移策略的生物地理學(xué)優(yōu)化算法[J].模式識(shí)別與人工智能,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.