三角函數(shù)變異模型的生物地理優(yōu)化算法

張晶

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

三角函數(shù)變異模型的生物地理優(yōu)化算法

張晶

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

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

生物地理優(yōu)化算法；變異率模型；三角函數(shù)

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

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

1 生物地理的基本原理

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

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

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

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

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

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

圖1 棲息地物種遷移模型

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

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

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

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

2 基于三角函數(shù)的變異率模型

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

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

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

圖2 三種不同的變異模型

3 仿真實驗

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

若某算法測試函數(shù)的最優(yōu)值和平均值最小,則表明該算法穩(wěn)定性好；若某算法測試函數(shù)的標準差最小,表示該算法的收斂精度高．測試函數(shù)的最優(yōu)值、平均值和標準差如表2所示．在最優(yōu)值上,基于線性變異模型BBO算法的f1和f2函數(shù)最優(yōu)值最??；而基于正弦函數(shù)變異模型BBO算法的f5和f6函數(shù)最優(yōu)值最??；基于正切變異模型BBO算法的f3和f4函數(shù)最小值最小．因此,通過函數(shù)最優(yōu)值暫時無法比較三種BBO算法的優(yōu)劣．在平均值上,基于正切函數(shù)變異模型BBO算法的f1、f3、f4、f5和f6函數(shù)的平均值最??；基于正弦函數(shù)變異模型BBO算法的f2函數(shù)平均值最小,因此,從平均值上看,基于正切函數(shù)模型的BBO算法穩(wěn)定性和收斂性較好,基于正弦函數(shù)模型的BBO算法次之,而基于線性模型的BBO算法收斂性和穩(wěn)定性最差．在標準差上,基于正切函數(shù)變異模型BBO算法的f1、f3、f5和f6函數(shù)的標準差最小；基于正弦函數(shù)模型BBO算法的f2和f5函數(shù)的標準差最小．因此,從標準差上看,基于正切函數(shù)模型的BBO算法收斂精度最高,而基于正弦函數(shù)模型的BBO算法次之,基于線性模型的BBO算法收斂精度最差．綜上所述,由于三角函數(shù)是非線性函數(shù),因而基于三角函數(shù)變異模型的BBO算法在穩(wěn)定性和收斂精度上明顯好于基于線性模型的BBO算法．

表1 測試函數(shù)

表2 測試函數(shù)的最優(yōu)值、平均值和標準差

4 結(jié)語

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

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

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

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

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

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

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

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

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

[9]紀潔,顧偉,張松勇.生物地理學優(yōu)化算法綜述[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