王智昊，劉培玉，DING Ding

(1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院，濟(jì)南 250014; 2.山東省分布式計(jì)算機(jī)軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室，濟(jì)南 250014;3.Department of Mathematics, University of Padua, Padua 35100, Italy)

基于人工螢火蟲局部決策域的改進(jìn)生物地理學(xué)優(yōu)化算法

王智昊1,2，劉培玉1,2*，DING Ding3

(1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院，濟(jì)南 250014; 2.山東省分布式計(jì)算機(jī)軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室，濟(jì)南 250014;3.Department of Mathematics, University of Padua, Padua 35100, Italy)

(*通信作者電子郵箱liupy@sdnu.com)

針對(duì)生物地理學(xué)優(yōu)化(BBO)算法搜索能力不足的缺點(diǎn)，提出基于螢火蟲算法局部決策域策略的改進(jìn)遷移操作來提算法的全局尋優(yōu)能力。改進(jìn)的遷移操作能夠在考慮不同棲息地各自的遷入率與遷出率的基礎(chǔ)上,進(jìn)一步利用棲息地之間的相互影響關(guān)系。將改進(jìn)算法應(yīng)用于12個(gè)典型的函數(shù)優(yōu)化問題來測(cè)試改進(jìn)生物地理學(xué)優(yōu)化算法的性能，驗(yàn)證了改進(jìn)算法的有效性。與BBO、改進(jìn)BBO(IBBO)、基于差分進(jìn)化的BBO(DE/BBO)算法的實(shí)驗(yàn)結(jié)果表明,改進(jìn)算法提高了算法的全局搜索能力、收斂速度和解的精度。

生物地理學(xué)優(yōu)化；遷移策略；螢火蟲算法；局部決策域；鄰域范圍

0 引言

生物地理學(xué)優(yōu)化(Biogeography-Based Optimization, BBO) 算法是Simon受到生物地理學(xué)理論的啟發(fā)，在對(duì)生物物種遷移數(shù)學(xué)模型的研究基礎(chǔ)上，于2008年提出的一種新的智能優(yōu)化算法[1]。該算法的基本思想來源于Wallace[2]在19世紀(jì)提出的生物地理學(xué)理論，該理論研究了生物物種棲息地的分布、遷移和滅絕規(guī)律。BBO算法自提出之后，已經(jīng)得到了較廣泛的研究，BBO算法的理論分析、改進(jìn)以及應(yīng)用都取得了較好的研究成果:文獻(xiàn)[3]提出了混合遷移策略對(duì)BBO算法進(jìn)行改進(jìn)，提高了算法的收斂精度;文獻(xiàn)[4]提出了動(dòng)態(tài)遷移策略，利用自適應(yīng)約束方法來約束處理約束條件，更充分地利用了個(gè)體有效信息;文獻(xiàn)[5-6]利用馬爾可夫鏈模型對(duì)遷移模型進(jìn)行分析，驗(yàn)證不同的遷移率模型對(duì)算法性能產(chǎn)生重要影響，并得出符合自然規(guī)律的復(fù)雜遷移率模型的性能優(yōu)于簡單的線性遷移率模型的性能的結(jié)論;文獻(xiàn)[7]提出一種新的變異算法來改進(jìn)BBO算法，提高了算法的全局搜索與局部搜索能力;文獻(xiàn)[8-9]使用差分變異算法與BBO算法結(jié)合，利用差分變異算子的開采能力，有效改善BBO算法變異能力差的情況，避免陷入局部最優(yōu)，從而增強(qiáng)了算法的全局搜索能力。為了進(jìn)一步改進(jìn)BBO算法的探測(cè)與搜索能力，本文將人工螢火蟲群優(yōu)化(Glowworm Swarm Optimization, GSO) 算法的局部決策域策略引入BBO算法的遷移操作；并且，將改進(jìn)的BBO算法與原始BBO算法及文獻(xiàn)[7-8]的改進(jìn)算法作比較。實(shí)驗(yàn)結(jié)果證明，本文提出的改進(jìn)算法無論是探測(cè)能力還是搜索能力都能取得更好的結(jié)果。

1 生物地理學(xué)優(yōu)化算法

在生態(tài)系統(tǒng)中，每一個(gè)棲息地是否適合物種生存可以用棲息適宜指數(shù)(Habitat Suitability Index, HSI)來描述。一個(gè)棲息地的適宜指數(shù)可以由適宜指數(shù)變量(Suitability Index Variables, SIV)來表示，該變量用來描述與適宜指數(shù)相關(guān)的特征，例如棲息地的降水量、濕度、植被多樣性等。HSI與棲息地中物種的多樣性成正比。對(duì)于某一塊棲息地，假設(shè)它所能容納的最大物種數(shù)量為Smax，物種的遷入率為λ，其最大值為I，遷出率為μ，其最大值為E，并且假設(shè)E=I。當(dāng)該棲息地物種數(shù)為0時(shí)，顯然，此時(shí)該棲息地物種的遷入率為最大值I。隨著物種的遷入，棲息地中物種數(shù)量增加，遷入率隨之減小而遷出率隨之增大，當(dāng)棲息地中的物種數(shù)量達(dá)到所能容納的上限Smax時(shí)，由于棲息地已經(jīng)達(dá)到飽和狀態(tài)，因此，遷入率下降為0，而此時(shí)遷出率達(dá)到最大值E。在圖(1)中，S1

有了對(duì)遷入率與遷出率的描述之后，可以計(jì)算某一時(shí)間段內(nèi)棲息地中所存在的物種數(shù)量的概率Ps(t+Δt)。它表示t+Δt時(shí)刻棲息地包含s個(gè)物種的概率。計(jì)算公式如式(1)所示:

Ps(t+Δt)=Ps(t)(1-λsΔt-μsΔt)+Ps-1λs-1Δt+Ps+1μs+1Δt

(1)

其中：λs與μs分別表示當(dāng)棲息地物種數(shù)量為s時(shí)的遷入率與遷出率。

根據(jù)圖遷入率與遷出率的線性關(guān)系，可得到物種數(shù)量為k時(shí)的遷入率與遷出率的計(jì)算方法，如式(2)與式(3)所示:

λk=I(1-k/n)

(2)

μk=E(k/n)

(3)

其中，n為棲息地可能存在的最大數(shù)目物種時(shí)的物種數(shù)量。由于假設(shè)棲息地物種的遷入率最大值與遷出率最大值相等，因此可得到λk+μk=E， 則當(dāng)Δt→0時(shí)，可以將概率公式轉(zhuǎn)化為式(4)。如果一個(gè)棲息地存在物種數(shù)量概率較低，則該棲息地容易發(fā)生突變行為。也就是說，突變概率函數(shù)與該棲息地的存在物種數(shù)量概率成反比，因此可以得到相應(yīng)的突變概率如式(5)所示。

(4)

ms=mmax(1-Ps/Pmax)

(5)

算法1 遷移算子。

end if

end if

end for

output： solution of immigration()

算法2 突變算子。

input：initial population fori=1 toNdoPs(λi,μi)

//根據(jù)式(1)計(jì)算存在物種數(shù)量概率Psms(Ps)

end if

end for

output： solution of mutation()

BBO是通過遷移操作實(shí)現(xiàn)可行解之間的信息共享的，棲息地中物種的數(shù)量正比于HSI。對(duì)于不同的棲息地之間的遷移運(yùn)動(dòng)而言，一塊棲息地發(fā)生遷入或遷出行為的概率與其遷入率或遷出率成正比。因此，將棲息地的遷入率的大小作為其是否發(fā)生遷入行為的判斷標(biāo)準(zhǔn)，進(jìn)一步通過對(duì)其他棲息地的遷出率考察選擇從哪塊棲息地進(jìn)行遷出操作。突變操作能夠使得低物種數(shù)量存在概率(existing probability of the number of species)的解具有一定的幾率突變?yōu)檩^好的解，防止算法陷入局部最優(yōu)，可以增加解的多樣性。為了防止最優(yōu)解被執(zhí)行突變操作，可以采用精英策略，將每一代的最優(yōu)解都保存到精英表中，參與到下一代的算法執(zhí)行過程中。如何執(zhí)行突變操作應(yīng)該根據(jù)具體解決的問題進(jìn)行設(shè)定。

2 人工螢火蟲優(yōu)化算法

在BBO算法中，遷移操作僅考慮棲息地各自的遷入率與遷出率大小來判斷如何執(zhí)行遷移操作，并沒有考慮到棲息地之間的相互影響。所以，本文將GSO算法的局部決策域思想引入BBO算法的遷移操作，能夠增強(qiáng)算法的探測(cè)能力。GSO算法中的局部決策域策略能夠?qū)崿F(xiàn)決策鄰域內(nèi)個(gè)體間吸引關(guān)系的定量分析，通過計(jì)算棲息地之間的吸引度來判斷它們之間的吸引關(guān)系，能夠在遷入率與遷出率的基礎(chǔ)上更精確地執(zhí)行遷移操作。

3 基于局部決策域策略的改進(jìn)BBO算法

局部決策域策略的特點(diǎn)適合作為BBO中棲息地之間消息傳遞的輔助工具。在各個(gè)棲息地之間，待遷入的棲息地能夠吸引待遷出棲息地的物種。下面首先給出應(yīng)用于BBO的局部決策域策略相關(guān)定義。

定義1 棲息地遷移矩陣。設(shè)棲息地?cái)?shù)量為n，計(jì)算任意兩個(gè)棲息地之間的相似度S(Hi,Hj)(相似度可以是對(duì)稱的也可以是不對(duì)稱的)，表示棲息地Hj吸引物種從棲息地Hi遷出并且遷入到棲息地Hj的可能性，并將Hi稱為待遷出棲息地，Hj稱為待遷入棲息地。棲息地之間的相似度組成的n×n的相似度矩陣S稱為棲息地遷移矩陣。S(Hi,Hj)按照式(6)計(jì)算：

(6)

定義2 棲息地遷入?yún)⒖级?Habit Immigration Reference, HIR)。相似度S(Hk,Hk)表示棲息地Hk能否成為待遷入棲息地的參考度，并將其記為HIR(k)(k=1,2，…,n)。HIR(k)的取值能夠影響待遷入棲息地與待遷出棲息地?cái)?shù)量的比例，決定了LBBO的遷移操作能否有效地搜索到優(yōu)化問題的全局最優(yōu)解。

根據(jù)文獻(xiàn)[7]對(duì)參考度的定義可以得到，對(duì)于所有的棲息地，待遷入棲息地的數(shù)量正比于HIR(k)。對(duì)于任意棲息地Hk，根據(jù)式(1)可知，HIR(k)與遷入率λk成正比，與遷出率μk成反比。在本文中，令S(Hk,Hk)的取值為棲息地Hk遷入率λk與遷出率μk的比值λi/μk，并且在后面的仿真實(shí)驗(yàn)中采用HIR(k)取值為相似度S的中值、均值、中值的一半以及均值的一半等取值方法作比較，討論如何選擇更優(yōu)的HIR(k)取值方法。

定義3 棲息地吸引度(Habit Attraction Reference, HAR)。 將GSO算法思想引入BBO算法，GSO中Agent的蟲熒光素屬性可以視為BBO算法中任一棲息地對(duì)其他相鄰棲息地物種的吸引強(qiáng)度。令lHi(t)表示任意棲息地Hi在t時(shí)刻的HAR取值。在算法初始化時(shí)，令每一塊棲息地都具有相等的HAR值l0。HAR的更新公式如式(7)所示:

lHi(t+1)=(1-ρ)lHi(t)+γSt+1(Hi,Hj)

(7)

其中:lHi(t)表示棲息地Hi在t時(shí)刻的吸引度值;ρ(0<ρ≤1)為吸引度衰變常數(shù);γ為吸引度增強(qiáng)常數(shù);St(Hi,Hj)表示t時(shí)刻棲息地Hi的HIR值，由式(1)計(jì)算。

棲息地遷入?yún)⒖级菻IR反映一塊棲息地適合其他物種遷入的程度，HIR值越大則表明該棲息地適合其他物種遷入的程度越強(qiáng)，也就是說對(duì)其他棲息地的吸引度越強(qiáng)。對(duì)于任意棲息地Hi與Hj，其吸引度的更新需要考慮當(dāng)前吸引度與遷入?yún)⒖级菻IR的雙重影響。

根據(jù)棲息地的HAR能夠確定物種的遷移方向，每一塊棲息地的物種都會(huì)向該棲息地鄰域范圍內(nèi)其他吸引度更高的棲息地遷移。對(duì)于任意棲息地i，其物種向鄰域內(nèi)棲息地j的遷移概率如式(8)所示:

(8)

根據(jù)式(8)可以表明，物種選擇待遷入棲息地的概率是與其吸引度成正比的。

(9)

其中:β為常參數(shù)，nt為控制鄰居數(shù)量的參數(shù)。根據(jù)局部決策域策略為改進(jìn)的BBO算法作出定義。

定義5 棲息地遷移策略Ω(l,r)。Ω(l,r):Hn→H用來控制LBBO遷移操作。通過計(jì)算l與r求得棲息地吸引度HAR值來判斷物種何時(shí)從待遷出棲息地Hi遷出并且遷入到待遷入棲息地Hj。

LBBO的棲息地遷移策略執(zhí)行的基本流程如下所示。

1)對(duì)于任意棲息地，分別根據(jù)式(2)、式(3)與式(6)計(jì)算得到遷入率λ、遷出率μ以及棲息地相似度矩陣S，并根據(jù)λ與μ求得棲息地遷入?yún)⒖级菻IR(k)，根據(jù)式(7)、式(8)與式(9)求得l、r與遷移概率。

2)根據(jù)式(7)與式(8)以及步驟1)所求得的HIR(k)、l、r與遷移概率計(jì)算并更新每一塊每塊棲息地的棲息地吸引度HAR。

3)將HAR值排序，選擇取值最大時(shí)所對(duì)應(yīng)的棲息地Hi與棲息地Hj。

5)用SIVm隨機(jī)替換Hi的一個(gè)SIV。

定義6 棲息地突變策略M(λ,μ)。M(λ,μ):H→H通過棲息地物種數(shù)量存在概率Ps來確定隨機(jī)改變棲息地適宜度指數(shù)SIVm的棲息地突變操作，通過式(4)來計(jì)算。棲息地突變策略基本流程見BBO突變操作。

定義7 LBBO。LBBO={Φ,m,n,λ,μ,Ω,T}:Hn→Hn是一個(gè)八元組，能夠?qū)⒁呀?jīng)初始化的棲息地進(jìn)行迭代優(yōu)化。其中Φ=?→{Hn,HSIn}是初始化一組棲息地，并且計(jì)算棲息地的HSI值的函數(shù)。T=Hn(True,False)是算法終止的判定標(biāo)準(zhǔn)。

LBBO的偽代碼如算法3所示。

算法3 LBBO算法。

input：initial population forg=1 toMAXGENdo fori=1toNdoCalculateλi,μi,HIR,HAR

end for

fori=1toNdo

end for

mutation()

//根據(jù)算法2執(zhí)行突變算子

end if

end for

end for

output： best solutions

4 實(shí)驗(yàn)研究

4.1 測(cè)試函數(shù)

在本文中，通過benchmark函數(shù)優(yōu)化問題來比較LBBO與基本BBO性能。為了提高實(shí)驗(yàn)結(jié)果的可靠性，選取了在函數(shù)極值個(gè)數(shù)、極值點(diǎn)分布方面有代表性的7個(gè)單峰函數(shù)Sphere function、Schwefel’s Problem 1.2、Schwefel’s Problem 2.21、Schwefel’s Problem 2.22、Rosenbrock function、Step function、Quartic function與5個(gè)多峰函數(shù)Schwefel’s Problem 2.26、Rastrigin function、Ackley function、Griewank function、Fletcher-Powell function作為測(cè)試函數(shù)[11]。為了描述方便將其標(biāo)記為F1～F12，如表1所示。其中，F(xiàn)1與F7～F8為分段函數(shù)，F(xiàn)1、F2、F5～F7以及F10與F12為正則函數(shù)。

表1 測(cè)試函數(shù)Tab. 1 Benchmark functions

4.2 LBBO算法性能分析

4.2.1 實(shí)驗(yàn)參數(shù)設(shè)置

為了比較LBBO算法與基本BBO算法及兩種改進(jìn)BBO算法的性能，種群規(guī)模及執(zhí)行代數(shù)均按照文獻(xiàn)[1]進(jìn)行設(shè)置，令棲息地最大物種數(shù)N=50; 每個(gè)函數(shù)運(yùn)行代數(shù)MAXGEN=50。

4.2.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)結(jié)果如表2所示。對(duì)于單峰函數(shù)F1～F7，通過對(duì)實(shí)驗(yàn)結(jié)果的觀察可以發(fā)現(xiàn)，各項(xiàng)指標(biāo)LBBO均優(yōu)于BBO算法及其他兩種改進(jìn)算法。對(duì)于函數(shù)F5，是非凸的病態(tài)函數(shù)，其全局最優(yōu)點(diǎn)位于一個(gè)平滑、狹長的拋物線形山谷內(nèi)，其最優(yōu)點(diǎn)較難求得。而LBBO采用了局部決策域策略，能夠通過不同解之間的相互吸引關(guān)系較為準(zhǔn)確的判斷全局最優(yōu)解。并且除了函數(shù)F3外，LBBO運(yùn)算30次所得到結(jié)果的標(biāo)準(zhǔn)差也小于BBO，表明LBBO在求解函數(shù)F1、F2以及F4～F7時(shí)更加穩(wěn)定。對(duì)于函數(shù)F3，通過對(duì)實(shí)驗(yàn)結(jié)果觀察可以發(fā)現(xiàn)，LBBO在求解過程中與BBO算法及其他兩種算法相比，大部分最優(yōu)解的取值與均值差距較大。

表2 F1～F12函數(shù)30次獨(dú)立實(shí)驗(yàn)平均結(jié)果比較Tab. 2 Comparison of benchmark functions F1～F12 averaged over 30 independent runs

對(duì)于多峰函數(shù)F8～F12，優(yōu)化結(jié)果LBBO算法優(yōu)于BBO算法與其他兩種比較算法。其中，函數(shù)F9峰形呈高低起伏不定跳躍性的出現(xiàn), 因此，LBBO中的吸引子策略能夠通過遷移信息在解之間的傳播而比較有效地發(fā)現(xiàn)函數(shù)最優(yōu)解。函數(shù)F10十分復(fù)雜，優(yōu)化過程中易落入局部最優(yōu)的陷阱。LBBO采用局部決策域策略，能夠在算法陷入局部最優(yōu)時(shí)使得算法在一定概率下接受較差解，使得算法具有更強(qiáng)的跳出局部最優(yōu)的能力。因此LBBO能夠較準(zhǔn)確地得到函數(shù)F10優(yōu)化問題的最優(yōu)解。函數(shù)F11具有許多局部極小值，較難求得全局最優(yōu)點(diǎn)，LBBO從全局搜索與局部搜索兩個(gè)方面對(duì)該復(fù)雜函數(shù)進(jìn)行優(yōu)化，具有更強(qiáng)的全局尋優(yōu)能力與跳出局部最優(yōu)的能力，所以LBBO能夠非常有效地求解函數(shù)F11這樣的復(fù)雜函數(shù)。

4.3 LBBO的HIR參數(shù)取值分析實(shí)驗(yàn)

4.3.1 實(shí)驗(yàn)設(shè)置

LBBO的吸引子策略HIR取值為棲息地遷入率與棲息地遷出率的比值，為了比較HIR不同取值情況下算法的效率設(shè)置對(duì)比實(shí)驗(yàn)。分別令HIR取值為棲息地遷入率與遷出率的比值、棲息地相似度矩陣S的中值(median)、棲息地相似度矩陣S中值的一半、棲息地相似度矩陣S的均值以及棲息地相似度矩陣均值的一半，采用4.1節(jié)所示12種測(cè)試函數(shù)，通過30次獨(dú)立測(cè)試結(jié)果的均值與標(biāo)準(zhǔn)差來比較算法的效率。五種HIR取值方法的LBBO的參數(shù)按照4.2.1節(jié)進(jìn)行設(shè)置，令棲息地遷移概率Pmod，突變概率m=0，精英棲息地?cái)?shù)量K=2，最大遷移率設(shè)置為E=I=1，最大突變率mmax，初始HARl0=5，初始決策域半徑=1; 棲息地最大物種數(shù)N=50; 每個(gè)函數(shù)運(yùn)行代數(shù)MAXGEN=50。

4.3.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)結(jié)果如表3與表4所示，通過觀察表3數(shù)據(jù)可以發(fā)現(xiàn)在12個(gè)函數(shù)求解中LBBO(HIR(k)=λk/μk)效果要優(yōu)于其他4種情況。主要原因是棲息地相似度矩陣S僅考慮了單一棲息地對(duì)遷移操作的影響，而遷入率與遷出率則綜合考慮了兩個(gè)棲息地之間的相互關(guān)系，因此HIR的值設(shè)置為棲息地遷入率與遷出率的比值能夠更好地利用棲息地物種數(shù)量信息，在棲息地之間傳遞吸引度與歸屬度信息時(shí)能夠更加準(zhǔn)確地指導(dǎo)棲息地間物種遷移行為。

表3 LBBO算法不同的HIR取值求解測(cè)試函數(shù)比較Tab. 3 Comparison of efficiency with different values of HIR for LBBO algorithm

4.4 LBBO初始種群與迭代次數(shù)參數(shù)分析實(shí)驗(yàn)

4.4.1 實(shí)驗(yàn)設(shè)置

為了分析算法的初始最大物種數(shù)以及算法執(zhí)行代數(shù)對(duì)算法效果的影響，在實(shí)驗(yàn)設(shè)置中均采用較大數(shù)值來分析較大取值的物種數(shù)及執(zhí)行代數(shù)是否能對(duì)算法效果帶來明顯的影響。采用4.1節(jié)所示F1、F5、F12等3個(gè)測(cè)試函數(shù)，通過30次獨(dú)立測(cè)試結(jié)果的均值與標(biāo)準(zhǔn)差來比較算法的效率。棲息地最大物種數(shù)N=500; 每個(gè)函數(shù)運(yùn)行代數(shù)MAXGEN=1 000，其他參數(shù)設(shè)置與4.2.1節(jié)相同。

4.4.2 實(shí)驗(yàn)結(jié)果與分析

對(duì)于簡單的單峰函數(shù)F1與復(fù)雜的多峰函數(shù)F5與F12增大物種數(shù)與執(zhí)行代數(shù)后能夠取得最優(yōu)值。對(duì)于測(cè)試函數(shù)F1，表4與圖1(a)中顯示在算法執(zhí)行600代之前隨著種群規(guī)模的增大算法的精確度會(huì)略微增加，但是600代之后基本上沒有差異。對(duì)于F5由圖1(b)可知在算法迭代800代之前初始種群數(shù)量對(duì)算法的結(jié)果有著顯著影響。圖1(c)表明相對(duì)F5更加復(fù)雜的函數(shù)F12在迭代1 000代初始種群的規(guī)模才開始不明顯。根據(jù)這一實(shí)驗(yàn)結(jié)果可以得出，測(cè)試函數(shù)的復(fù)雜程度與其對(duì)初始種群規(guī)模的敏感正度是成正比的，對(duì)于簡單函數(shù)而言更大的初始種群沒有很明顯的影響。

表4 F1、F5與F12的LBBO算法時(shí)間Tab. 4 Time of LBBO algorithm for solving F1, F5 and F12

對(duì)于執(zhí)行代數(shù)而言，從圖1中觀察可知在一定數(shù)量的代數(shù)之后精度幾乎不再提升，其主要原因是，算法能否求得最優(yōu)值主要取決于算法跳出局部最優(yōu)的能力。算法迭代次數(shù)的增加無疑會(huì)對(duì)算法執(zhí)行時(shí)間造成很大影響，然而，如表5所示，執(zhí)行代數(shù)相同時(shí)初始種群的規(guī)模對(duì)算法執(zhí)行時(shí)間的影響更加明顯。這是因?yàn)槌跏挤N群規(guī)模增加會(huì)使得遷入遷出率、HIR等參數(shù)的計(jì)算次數(shù)激增而顯著地增加算法執(zhí)行時(shí)間。因此對(duì)于算法在實(shí)際問題的應(yīng)用應(yīng)該通過大量實(shí)驗(yàn)考察初始種群規(guī)模與迭代次數(shù)在何時(shí)無法對(duì)算法的精度帶來提升，進(jìn)而選擇恰當(dāng)?shù)娜≈祦砥胶馑惴ň扰c算法效率的關(guān)系。

表5 LBBO算法不同最大物種數(shù)與執(zhí)行代數(shù)求解測(cè)試函數(shù)效果比較Tab. 5 Comparison of results with different values of N and MAXGEN

圖1 LBBO算法不同最大物種數(shù)與迭代次數(shù)求解測(cè)試函數(shù)的收斂對(duì)比曲線Fig. 1 Convergence curve of test functions of LBBO with different N and MAXGEN

5 結(jié)語

本文提出了一種基于局部決策域策略的LBBO算法，采用螢火蟲算法局部決策域策略來改進(jìn)算法的局部搜索能力。通過對(duì)LBBO算法在12個(gè)基準(zhǔn)函數(shù)的測(cè)試結(jié)果分析，該算法能夠較好地求解函數(shù)極值優(yōu)化問題。通過與BBO算法的比較，可以發(fā)現(xiàn)LBBO的性能明顯優(yōu)于原始算法。當(dāng)然，BBO算法的研究與其他進(jìn)化算法(Evolutionary Algorithm, EA)(例如遺傳算法(Genetic Algorithm, GA)、粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法等)相比仍處于較初級(jí)的研究階段。在今后的工作中，將嘗試?yán)闷渌乃惴蚣苣Ｐ?例如文化算法框架模型)來改進(jìn)BBO的性能。

References)

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

[2] WALLACE A R. The Geographical Distribution of Animals: with a Study of the Relations of Living and Extinct Faunas as Elucidating the Past Changes of the Earth’s Surface[M]. Cambridge: Cambridge University Press, 2011:15-25.

[3] 畢曉君, 王玨. 基于混合遷移策略的生物地理學(xué)優(yōu)化算法[J]. 模式識(shí)別與人工智能, 2012, 25(5):768-774.(BI X J, WANG J. Biogeography-based optimization based on hybrid migration strategy[J]. Pattern Recognition and Artificial Intelligence, 2012, 25(5):768-774.)

[4] 畢曉君, 王玨, 李博,等. 基于動(dòng)態(tài)遷移的ε約束生物地理學(xué)優(yōu)化算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(3):580-589.(BI X J, WANG J, LI B, et al. An ε constrained biogeography-based optimization with dynamic migration[J]. Journal of Computer Research and Development, 2014, 51(3):580-589.)

[5] MA H, SIMON D. Analysis of migration models of biogeography-based optimization using Markov theory [J]. Engineering Applications of Artificial Intelligence, 2011, 24(6): 1052-1060.

[6] MA H, SIMON D, FEI M, et al. Variations of biogeography-based optimization and Markov analysis[J]. Information Sciences, 2013, 220(1): 492-506.

[7] YANG G P, LIU S Y, ZHANG J K, et al. Control and synchronization of chaotic systems by an improved biogeography-based optimization algorithm[J]. Applied Intelligence, 2013, 39(1): 132-143.

[8] BHATTACHARYA A, CHATTOPADHYAY P K. Hybrid differential evolution with biogeography-based optimization for solution of economic load dispatch[J]. IEEE Transactions on Power Systems, 2010, 25(4): 1955-1964.

[9] 葉開文, 劉三陽, 高衛(wèi)峰. 基于差分進(jìn)化的生物地理學(xué)優(yōu)化算法[J]. 計(jì)算機(jī)應(yīng)用, 2012, 32(11):2981-2984.(YE K W, LIU S Y, GAO W F. Biogeography-based optimization algorithm of differential evolution [J]. Journal of Computer Applications, 2012, 32(11):2981-2984.)

[10] KRISHNANAND K N, GHOSE D. Glowworm swarm optimization: a new method for optimizing multi-modal functions[J]. International Journal of Computational Intelligence Studies, 2009, 1(1): 93-119.

[11] YAO X, LIU Y, LIN G. Evolutionary programming made faster [J]. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 82-102.

This work is partially supported by National Natural Science Foundation (61373148, 61502151), the Shandong Province Natural Science Foundation (ZR2014FL010), the Shandong Province Social Science Project (2012BXWJ01, 15CXWJ13, 16CFXJ05).

WANG Zhihao, born in 1986, Ph.D. candidate. His research interests include intelligence algorithms.

LIU Peiyu, born in 1960, professor. His research interests include information security.

DING Ding, born in 1987, Ph. D. candidate. His research interests include network security.

Improved biogeography-based optimization algorithm based on local-decision domain of glowworm swarm optimization

WANG Zhihao1,2, LIU Peiyu1,2*, DING Ding3

(1.SchoolofInformationScienceandEngineering,ShandongNormalUniversity,JinanShandong250014,China;2.ShandongProvincialKeyLaboratoryforDistributedComputerSoftwareNovelTechnology,JinanShandong250014,China;3.DepartmentofMathematics，UniversityofPadua,Padua35100,Italy)

Aiming at the lack of searching ability of Biogeography-Based Optimization (BBO) algorithm, an improved migration operation based on local-decision domain was proposed to improve the global optimization ability of the algorithm. The improved migration operation can further utilize the interaction between habitats in consideration of the respective migration rates and evapotranspiration rates of different habitats. The improved algorithm was applied to 12 typical function optimization problems to test the performance, and the effectiveness of the improved algorithm was verified. Compared with BBO, Improved BBO (IBBO) and Differential Evolution/BBO (DE/BBO), the experimental results show that the proposed algorithm can improve the capacity of global searaching optimal solution, convergence speed and computational precision of solution.

Biogeography-Based Optimization (BBO); migration operation; Glowworm Swarm Optimization (GSO); local-decision domain; neighborhood range

2016-10-16;

2016-12-01。 基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(61373148, 61502151)；山東省自然科學(xué)基金資助項(xiàng)目(ZR2014FL010)；山東省社會(huì)科學(xué)規(guī)劃項(xiàng)目(2012BXWJ01,15CXWJ13,16CFXJ05)。

王智昊(1986—)，男，山東濟(jì)南人，博士研究生，主要研究方向:智能算法； 劉培玉(1960—)，男，山東臨朐人，教授，CCF會(huì)員，主要研究方向：信息安全; DING Ding(1987—)，男，山東濟(jì)南人，博士研究生，主要研究方向：網(wǎng)絡(luò)安全。

1001-9081(2017)05-1363-06

10.11772/j.issn.1001-9081.2017.05.1363

TP18

A