三角函數變異模型的生物地理優化算法

張晶

(宜賓學院圖書館，四川宜賓644007)

三角函數變異模型的生物地理優化算法

張晶

(宜賓學院圖書館，四川宜賓644007)

在介紹BBO算法的基本原理基礎上,提出了三角函數變異模型的生物地理優化算法,并進行了函數測試,測試結果表明,基于三角函數變異模型的BBO算法在算法穩定性和收斂精度上明顯好于線性模型．

生物地理優化算法；變異率模型；三角函數

人們根據自然和生物種群演變和進化過程，提出了很多智能優化算法，常見的有遺傳算法、粒子群算法、蟻群算法等．這些智能優化算法具有并行計算、自適應和魯棒性強的特點，因此被廣泛地應用到傳統數值算法難以解決的優化問題中．美國學者Simon依據生物種群在棲息地的分布、遷移、變異和滅絕的規律，首次提出了生物地理優化算法(Biogeography-based optimization,BBO)[1]．與遺傳、粒子群和蟻群算法相比, BBO具有簡單方便、參數少,收斂速度快、收索精度高的特點,已經被應用到很多工程技術問題[2]．

在生物地理優化算法中,最核心的就是遷移和變異策略,很多文獻關注于遷移算子的改進,并提出了很多改進算法．例如,文獻[3]利用柯西算子來改進BBO的遷移算子,仿真結果表明該算法優于普通的BBO算子；文獻[4]對遷移算子中引入了擾動因子,結果驗證該方法對于求解多目標優化問題是有效可行的；文獻[5]提出了基于線性、三角、指數、二次型等幾種遷移算子模型,并對各模型進行了測試,測試結果表明三角函數遷移模型的BBO算法優化效果較好．但是,關于變異算子改進的文獻較少,特別研究變異算子數學模型的．因此,本文針對BBO中的變異算法,研究基于三角函數的變異算子數學模型,并進行仿真對比．

1 生物地理的基本原理

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

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

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

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

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

設物種種群最大數為Smax,最大遷入率為E,最大遷出率為I,并令E=I．物種遷移模型如圖1所示．

圖1 棲息地物種遷移模型

從圖中可以看出,在遷移率為E時,μS為0,物種種類為0；當λS=μS時,物種種類達到穩定狀態S0；當λS=0,uS=E時,物種種類達到最大值Smax．因此可以得到以下公式:

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

設最大變異率為mmax,棲息地個數為N,則基于線性的變異模型如下:

式中Pmax=argmaxPi，i=1,2,…,N．

2 基于三角函數的變異率模型

變異算子中分別引入三角函數,可以分別得到不同的變異模型．基于正弦函數的變率可以表示為:

基于正切的變異率可以表示為:

設mmax=1,以PsPmax為自變量,基于線性、正弦和正切的變異模型分別如圖2所示,從圖2中可以看出,隨著PsPmax從0增加到1,三種模型的變異率都從1逐步減少到0；基于正弦和正切的變異模型都是典型的非線性函數,在PsPmax相同時,正弦函數模型的變異率最小，線性模型次之,正切函數模型最大．

圖2 三種不同的變異模型

3 仿真實驗

設BBO的最大迭代次數為50,最大遷移率E=I=1,最大變異率mmax分別取0.01,種群維數D為20．為了驗證變異模型的有效性,分別采用以下5個函數進行測試,函數的最小值均為0,測試函數的表達式和定義域分別如表1所示．

若某算法測試函數的最優值和平均值最小,則表明該算法穩定性好；若某算法測試函數的標準差最小,表示該算法的收斂精度高．測試函數的最優值、平均值和標準差如表2所示．在最優值上,基于線性變異模型BBO算法的f1和f2函數最優值最?。欢谡液瘮底儺惸Ｐ虰BO算法的f5和f6函數最優值最小；基于正切變異模型BBO算法的f3和f4函數最小值最?。虼?通過函數最優值暫時無法比較三種BBO算法的優劣．在平均值上,基于正切函數變異模型BBO算法的f1、f3、f4、f5和f6函數的平均值最?。换谡液瘮底儺惸Ｐ虰BO算法的f2函數平均值最小,因此,從平均值上看,基于正切函數模型的BBO算法穩定性和收斂性較好,基于正弦函數模型的BBO算法次之,而基于線性模型的BBO算法收斂性和穩定性最差．在標準差上,基于正切函數變異模型BBO算法的f1、f3、f5和f6函數的標準差最?。换谡液瘮的Ｐ虰BO算法的f2和f5函數的標準差最?。虼?從標準差上看,基于正切函數模型的BBO算法收斂精度最高,而基于正弦函數模型的BBO算法次之,基于線性模型的BBO算法收斂精度最差．綜上所述,由于三角函數是非線性函數,因而基于三角函數變異模型的BBO算法在穩定性和收斂精度上明顯好于基于線性模型的BBO算法．

表1 測試函數

表2 測試函數的最優值、平均值和標準差

4 結語

本文分析了基于三角函數變異模型的BBO算法特點，并證實該變異模型好于線性模型，為BBO提供了一種新的變異策略．

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

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

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

[4]徐志丹,莫宏偉.生物地理信息優化算法中遷移算子的改進[J].模式識別與人工智能,2012,25(3):545-549.

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

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

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

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

[9]紀潔,顧偉,張松勇.生物地理學優化算法綜述[J].上海電力學院學報,2012,28(1):48-50.

【編校：李青】

Research on Mutation Model for BBO Based on Trigonometric Function

ZHANG Jing
(Library of Yibin University,Yibin,Sichuan 644007,China)

The principle of BBO algorithm was introduced,and then the mutation model was proposed for BBO based on trigonometric function,the function test was carried out at the same time.The test results show that BBO algorithm based on triangle function variation model is obviously better than the linear model in algorithm stability and convergence precision.

biogeography-based optimization;mutation model;trigonometric function

TP18

A

1671-5365(2014)06-0089-03

2013-11-14修回：2014-01-04

國家自然科學基金(61262037)；四川省教育廳基金項目(13ZB0213)

張晶(1981-),女,講師,碩士,研究方向為計算機應用、智能信息處理

時間：2014-03-28 17:40

http://www.cnki.net/kcms/detail/51.1630.Z.20140328.1740.005.html