張晶

(宜賓學(xué)院圖書(shū)館，四川宜賓644007)

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

張晶

(宜賓學(xué)院圖書(shū)館，四川宜賓644007)

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

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

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

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

1 生物地理的基本原理

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

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

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

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

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

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

圖1 棲息地物種遷移模型

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

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

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

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

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

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

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

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

圖2 三種不同的變異模型

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

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

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

表1 測(cè)試函數(shù)

表2 測(cè)試函數(shù)的最優(yōu)值、平均值和標(biāo)準(zhǔn)差

4 結(jié)語(yǔ)

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

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

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

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

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

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

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

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

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

[9]紀(jì)潔,顧偉,張松勇.生物地理學(xué)優(yōu)化算法綜述[J].上海電力學(xué)院學(xué)報(bào),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

國(guó)家自然科學(xué)基金(61262037)；四川省教育廳基金項(xiàng)目(13ZB0213)

張晶(1981-),女,講師,碩士,研究方向?yàn)橛?jì)算機(jī)應(yīng)用、智能信息處理

時(shí)間：2014-03-28 17:40

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