蝙蝠算法的一種改進(jìn)方法

魏三強(qiáng)，張 超

(1.宿州職業(yè)技術(shù)學(xué)院計(jì)算機(jī)信息系，安徽 宿州 234101；2.中國(guó)礦業(yè)大學(xué)信息與控制工程學(xué)院，江蘇 徐州 221116)

蝙蝠算法的一種改進(jìn)方法

魏三強(qiáng)1，2，張 超1

(1.宿州職業(yè)技術(shù)學(xué)院計(jì)算機(jī)信息系，安徽 宿州 234101；2.中國(guó)礦業(yè)大學(xué)信息與控制工程學(xué)院，江蘇 徐州 221116)

針對(duì)蝙蝠算法在進(jìn)行局部搜索時(shí)，易使算法陷入局部極值的束縛，導(dǎo)致算法收斂精度不高的缺陷，提出了使用t-分布對(duì)局部搜索時(shí)的最優(yōu)解進(jìn)行變異操作.為最優(yōu)解各維度增加t分布型隨機(jī)擾動(dòng)項(xiàng)，選取7個(gè)經(jīng)典測(cè)試函數(shù)做仿真實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明：改進(jìn)的蝙蝠算法在收斂精度和速度上有顯著提升，說(shuō)明通過(guò)對(duì)最優(yōu)解實(shí)施t-分布擾動(dòng)能夠使算法擺脫局部極值的束縛，顯著提高收斂精度.

蝙蝠算法；t分布；收斂精度；群體多樣性；智能算法

0 引言

X.S.Yang[1]根據(jù)自然界的蝙蝠能夠利用其發(fā)出聲波的回聲，從而準(zhǔn)確定位獵物位置的特征，于2010年提出了一種群智能優(yōu)化算法——蝙蝠算法(Bat Algorithm，BA).該算法能模擬蝙蝠在飛行或捕捉獵物時(shí)的回聲定位行為，每個(gè)蝙蝠通過(guò)改變聲波的頻率、音響強(qiáng)度、脈沖發(fā)射率來(lái)控制其飛行位置和速度，追隨最優(yōu)蝙蝠在解空間搜索最優(yōu)解.文獻(xiàn)[1-5]通過(guò)大量數(shù)值實(shí)驗(yàn)得出蝙蝠算法在尋找最優(yōu)解的成功率上優(yōu)于粒子群算法、和聲算法及遺傳算法.鑒于此，近年來(lái)蝙蝠算法在神經(jīng)網(wǎng)絡(luò)優(yōu)化[6]、資源調(diào)配[7]等領(lǐng)域已被應(yīng)用，但蝙蝠算法也存在收斂精度不高、易陷入局部極值點(diǎn)等缺陷[8]，為此，學(xué)者們對(duì)蝙蝠算法進(jìn)行了相關(guān)的改進(jìn)工作.改進(jìn)的策略主要集中在蝙蝠算法的兩個(gè)主要過(guò)程：個(gè)體飛行和局部搜索.在個(gè)體飛行方面，劉長(zhǎng)平等[9]提出使用Levy飛行取代原算法的速度和位置更新方式；謝健等[10]在原算法速度和位置更新方式上，對(duì)組成蝙蝠速度和位置的各維度添加Levy分布變異.在局部搜索方面，李雅梅等[11]引入Powell機(jī)制提高蝙蝠算法的局部搜索能力；劉萬(wàn)軍等[12]對(duì)最優(yōu)個(gè)體進(jìn)行SQP局部搜索，提高蝙蝠算法的局部深度搜索能力；陳梅雯等[13]使用隨機(jī)蝙蝠來(lái)引導(dǎo)個(gè)體飛行和局部搜索，以提高種群多樣性；臧慧芳等[14]通過(guò)引入早熟判斷機(jī)制，將差分進(jìn)化算法思想融入到蝙蝠算法中.這些改進(jìn)策略在不同程度上提升了蝙蝠算法的收斂精度.

蝙蝠算法在局部搜索時(shí)采用隨機(jī)游走方式，通過(guò)對(duì)組成最優(yōu)解的各維度增加隨機(jī)數(shù)進(jìn)行擾動(dòng)，在最優(yōu)蝙蝠個(gè)體附近生成局部新解.當(dāng)局部搜索條件成立，算法進(jìn)行局部搜索時(shí)，容易被局部極值點(diǎn)吸引，導(dǎo)致算法不一定收斂到局部最優(yōu)，并且，隨著迭代進(jìn)程的推進(jìn)，當(dāng)?shù)竭_(dá)中后期階段時(shí)，蝙蝠個(gè)體集中在局部最優(yōu)解附近，致使種群多樣性消耗過(guò)快，易陷入局部最優(yōu)，從而導(dǎo)致算法不能夠收斂到全局最優(yōu)解，收斂精度不高.本文提出使用學(xué)生t-分布(簡(jiǎn)稱t分布)變異代替原算法的局部新解生成方式，即在最優(yōu)解best的基礎(chǔ)上增加t分布型隨機(jī)擾動(dòng)項(xiàng)best?t(Iteration)，對(duì)最優(yōu)解各維度進(jìn)行基于迭代次數(shù)Iteration為t分布自由度的自適應(yīng)變異.選用7個(gè)經(jīng)典測(cè)試函數(shù)做仿真實(shí)驗(yàn)，以驗(yàn)證本文提出改進(jìn)策略的有效性.

1 蝙蝠算法

1.1 蝙蝠算法基本原理

蝙蝠算法模擬蝙蝠的回聲定位行為，通過(guò)改變聲波的頻率、音響強(qiáng)度、脈沖發(fā)射率來(lái)控制其飛行位置和速度，追隨最優(yōu)蝙蝠在解空間搜索最優(yōu)解.蝙蝠算法可以歸納出如下7個(gè)步驟：

(1) 初始化參數(shù).設(shè)置種群規(guī)模為sizepop、最大迭代次數(shù)為maxgen(或目標(biāo)精度)、脈沖頻率范圍為[fminfmax]、最大脈沖頻度為r0、最大脈沖音強(qiáng)為A、音強(qiáng)衰減系數(shù)為α、頻度增加系數(shù)為γ、搜索變量的維度為d.

(2) 蝙蝠種群初始化.在搜索范圍內(nèi)隨機(jī)初始化蝙蝠個(gè)體位置xi(i=1，…，d)，找出當(dāng)前搜索中最佳蝙蝠位置x*.

(3) 種群迭代.蝙蝠個(gè)體飛行按照

(1)

對(duì)脈沖頻率fi，蝙蝠t時(shí)刻的速度vi，位置xi進(jìn)行更新.其中x*是當(dāng)前搜索全局最優(yōu)解，rand∈[0，1]的隨機(jī)數(shù).

(4) 生成隨機(jī)數(shù)rand.如果rand>ri，選擇最優(yōu)蝙蝠個(gè)體，按照

xnew=xold+ε×At，

(2)

(5)再次生成隨機(jī)數(shù)rand.如果rand

(3)

增大ri和減小Ai的值.其中t為當(dāng)前迭代次數(shù)，α和γ為常量.

(6) 對(duì)蝙蝠種群的適應(yīng)度值進(jìn)行排序.記錄當(dāng)前最優(yōu)蝙蝠位置及其適應(yīng)度值.

(7) 重復(fù)執(zhí)行步驟(3)—(6).進(jìn)入迭代尋優(yōu)，直至滿足最大迭代次數(shù)或設(shè)定精度停止算法，輸出全局最優(yōu)值及對(duì)應(yīng)蝙蝠位置.

1.2 改進(jìn)的蝙蝠算法

蝙蝠算法在局部搜索時(shí)采用隨機(jī)游走方式，通過(guò)對(duì)組成最優(yōu)解的各維度增加隨機(jī)數(shù)進(jìn)行擾動(dòng)，在最優(yōu)蝙蝠個(gè)體附近生成局部新解，當(dāng)算法進(jìn)行局部搜索靠近極值點(diǎn)時(shí)，容易被極值點(diǎn)吸引，致使種群多樣性消耗過(guò)快，導(dǎo)致算法收斂精度不高.本文使用t分布變異策略對(duì)原算法的局部搜索方式進(jìn)行改進(jìn).

1.2.1 t分布

t分布是英國(guó)統(tǒng)計(jì)學(xué)家Gosset于1908年以筆名“Student”提出的，因此稱學(xué)生氏t分布，簡(jiǎn)稱t分布.t分布曲線是左右對(duì)稱的，圍繞平均數(shù)向兩側(cè)遞降.t分布受自由度參數(shù)df=n-1的制約，每個(gè)自由度都有一條t分布曲線.和正態(tài)分布相比，t分布的頂部偏低，尾部偏高.自由度df越小，t分布曲線越低平；自由度df越大，t分布曲線越接近正態(tài)分布.柯西分布和高斯分布是t分布的兩個(gè)邊界特例.當(dāng)t分布自由度df=1時(shí)，t分布曲線和柯西分布曲線重合；當(dāng)自由度df>30時(shí)，t分布曲線開(kāi)始與正態(tài)分布曲線接近；當(dāng)df∞時(shí)，t分布曲線和高斯分布曲線重合.

1.2.2 自適應(yīng)t分布變異蝙蝠算法

由于t分布隨著自由度的增加能夠在柯西分布和高斯分布之間轉(zhuǎn)換，柯西分布變異具有良好的全局開(kāi)發(fā)能力，而高斯變異具有穩(wěn)定的局部搜索能力.因此，文獻(xiàn)[15]將t分布應(yīng)用到人工魚(yú)群算法的改進(jìn)中，提出將算法的迭代次數(shù)作為t分布的自由度參數(shù)，對(duì)除了最優(yōu)魚(yú)之外的非最優(yōu)魚(yú)進(jìn)行t分布變異.文獻(xiàn)[16]將t分布引入到蝙蝠算法的改進(jìn)中，對(duì)除了最優(yōu)蝙蝠之外的非最優(yōu)蝙蝠進(jìn)行t分布變異.從文獻(xiàn)[15-16]的結(jié)果看出，經(jīng)過(guò)對(duì)非最優(yōu)解進(jìn)行t分布變異后，提高了算法的收斂精度和速度.本文使用

xnew=xold+xold?t(Iteration)

(4)

代替公式(2)，即提出使用t分布對(duì)最優(yōu)解進(jìn)行變異，進(jìn)行局部搜索生成新解的方式.其中?為點(diǎn)乘符號(hào)，t(Iteration)是以算法的迭代次數(shù)Iteration為自由度的t分布.

改進(jìn)策略在蝙蝠算法迭代初期，Iteration值較小，通過(guò)對(duì)最優(yōu)解進(jìn)行近似柯西分布變異能夠產(chǎn)生遠(yuǎn)離最優(yōu)解的下一代點(diǎn)，提高種群多樣性，避免算法過(guò)早早熟，陷入局部最優(yōu).算法運(yùn)行后期，Iteration的取值較大，對(duì)最優(yōu)解進(jìn)行t分布變異近似高斯分布，具有較好的局部搜索能力，能夠提高算法的收斂精度.

改進(jìn)的算法記為T(mén)BA.改進(jìn)的算法使用公式(4)進(jìn)行局部搜索，其執(zhí)行流程與原算法一致.

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

2.1 實(shí)驗(yàn)方案設(shè)計(jì)和部署

本文從兩方面對(duì)改進(jìn)的算法性能進(jìn)行仿真實(shí)驗(yàn)：(1)對(duì)BA和TBA做對(duì)比實(shí)驗(yàn)；(2)將TBA與其他改進(jìn)BA的結(jié)果進(jìn)行比較.

為了便于與其他改進(jìn)BA的比較，本文選用7個(gè)測(cè)試函數(shù)，使用比較苛刻的參數(shù)設(shè)置，函數(shù)的表達(dá)式、變量范圍、理論極值和目標(biāo)精度見(jiàn)表1.實(shí)驗(yàn)在主頻2.50 GHz的CPU、2 GB內(nèi)存、32位Win7操作系統(tǒng)的計(jì)算機(jī)上使用Matlab R2012a編程實(shí)現(xiàn)仿真程序.

算法參數(shù)設(shè)置：蝙蝠種群規(guī)模sizepop=20，迭代次數(shù)maxgen=1 000，脈沖頻率范圍為[0，2]，音強(qiáng)衰減系數(shù)α=0.95，頻度增加系數(shù)γ=0.05，每個(gè)蝙蝠的脈沖頻度ri∈[0，1]，脈沖音強(qiáng)Ai∈[1，2].

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

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

2.2.1 TBA與BA性能比較分析

對(duì)表1中的7個(gè)測(cè)試函數(shù)按照指定維度和變量范圍，使用BA和TBA仿真程序，分別隨機(jī)獨(dú)立連續(xù)運(yùn)行20次.固定迭代次數(shù)下的實(shí)驗(yàn)結(jié)果見(jiàn)表2.由表2可見(jiàn)，改進(jìn)的蝙蝠算法TBA在衡量算法性能的4個(gè)指標(biāo)上均明顯優(yōu)于BA，收斂精度顯著提高.圖1為T(mén)BA和BA的適應(yīng)度收斂進(jìn)化曲線(為了便于觀察，對(duì)Michalewicz函數(shù)除外的其他6個(gè)函數(shù)的適應(yīng)度值取10為底的對(duì)數(shù)處理).從圖1中可以看出，TBA較BA收斂速度有大幅提升.函數(shù)f1，f5，f6和f7理論極值為0， TBA在這4個(gè)函數(shù)上的適應(yīng)度進(jìn)化曲線出現(xiàn)間斷，表明已經(jīng)找到該函數(shù)的理論極值0，因?yàn)閷?duì)數(shù)的真數(shù)為0時(shí)不顯示.

表2 BA和TBA的實(shí)驗(yàn)結(jié)果

圖1 BA和TBA的適應(yīng)度值進(jìn)化收斂趨勢(shì)比較

表3為固定精度下的BA算法和TBA算法的平均迭代次數(shù)和成功率.數(shù)值采用 “平均迭代次數(shù)/成功率”表示，1代表百分之百成功.從表3中可知，BA在預(yù)設(shè)精度下，均不能收斂到固定精度，而TBA在比較苛刻的精度設(shè)定下，均能百分百成功收斂到固定精度.從而說(shuō)明TBA有效地提高了算法的收斂速度.

表3 固定精度下平均迭代次數(shù)與成功率

2.2.2 TBA與其他BA改進(jìn)算法性能比較分析

為了將本文提出的改進(jìn)算法與其他蝙蝠改進(jìn)算法進(jìn)行比較，選取近兩年改進(jìn)效果較好的4個(gè)改進(jìn)算法：IBA[13]、CDEBA[14]、TMBA[16]、VBA[17].文獻(xiàn)[13]中f1，f2，f3，f4，f5，f6，f7函數(shù)變量范圍分別為±600，±15，[-5，10]，[0，π]，±600，±32.768，±15，種群規(guī)模sizepop=20，maxgen=3 000；文獻(xiàn)[14]中f1，f5，f6，f7函數(shù)變量范圍分別為±100，±600，±32，±5.12，種群規(guī)模sizepop=50，maxgen=200；文獻(xiàn)[16]中f1，f3，f5，f6，f7函數(shù)變量范圍分別為±5.12，[-5，10]，±600，[-15，30]，±15，種群規(guī)模sizepop=50，maxgen=1 000；文獻(xiàn)[17]中f1，f4，f5，f6函數(shù)變量范圍分別為±5.12，[0，π]，±600，±32，種群規(guī)模sizepop=50，maxgen=200.

TBA是在種群規(guī)模、迭代次數(shù)、測(cè)試函數(shù)變量范圍等指標(biāo)比較苛刻的約束設(shè)定下進(jìn)行的仿真.對(duì)比結(jié)果及對(duì)比算法的搜索空間維度見(jiàn)表4.從表4可知，除了Rosenbrock 函數(shù)外，本文的TBA適應(yīng)度平均值明顯優(yōu)于其他算法，并在f1，f5，f6，f74個(gè)函數(shù)上均能收斂到理論極值0.文獻(xiàn)[13] 提出的IBA在Rosenbrock 函數(shù)上的收斂精度優(yōu)于TBA，但在其他6個(gè)函數(shù)收斂精度上遠(yuǎn)低于本文提出的TBA.文獻(xiàn)[14]提出的CDEBA在搜索維度為2的情況下，能夠收斂到Griewank函數(shù)的理論極值0，但隨著維度的增加收斂精度明顯下降.

表4 TBA(30維)與其他蝙蝠改進(jìn)算法優(yōu)化平均值比較

綜上所述，本文提出的對(duì)原算法局部搜索使用的隨機(jī)游走方式進(jìn)行自適應(yīng)t分布變異能夠有效擺脫局部極值的束縛，避免算法“早熟”，在迭代早期近似柯西分布的t分布變異拓展了種群的多樣性，從而提高了算法的收斂精度和速度.

3 結(jié)論

對(duì)蝙蝠算法進(jìn)行局部搜索時(shí)的最優(yōu)解進(jìn)行t-分布變異操作后的改進(jìn)算法，在Sphere、Griewank、Ackley、Rastrigin函數(shù)上均能收斂到函數(shù)的理論極值0，在Zakharov、Michalewicz函數(shù)上的收斂精度也明顯優(yōu)于其他算法.結(jié)果表明，通過(guò)過(guò)對(duì)最優(yōu)解進(jìn)行t-分布擾動(dòng)能夠使算法擺脫局部極值的束縛，顯著提高收斂精度.

[1] YANG X S.A new metaheuristic bat-inspired algorithm[J].Nature Inspired Cooperative Strategies for Optimization(NICSO 2010)，2010，284：65-74.

[2] YANG X S.Bat algorithm for multi-objective optimization[J].Int J Bio-Inspired Computation，2011，3(5)：267-274.

[3] YANG X S，GANDOMI A H.Bat algorithm：a novel approach for global engineering optimization[J].Engineering Computation，2012，29(5)：267-289.

[4] 李煜，馬良.新型全局優(yōu)化蝙蝠算法[J].計(jì)算機(jī)科學(xué)，2013，40(9)：225-229.

[5] 劉長(zhǎng)平，葉春明，劉滿成.來(lái)自大自然的尋優(yōu)策略：像蝙蝠一樣感知[J].計(jì)算機(jī)應(yīng)用研究，2013，30(5)：1320-1322，1356.

[6] 孔令春，孫瓊瓊，楊照峰.蝙蝠算法優(yōu)化極限學(xué)習(xí)機(jī)的電力負(fù)荷預(yù)測(cè)模型[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016，35(1)：89-92.

[7] 劉長(zhǎng)平，陳偉達(dá).求解零等待流水車(chē)間調(diào)度問(wèn)題的改進(jìn)蝙蝠算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2016，46(11)：38-46.

[8] 尚俊娜，劉春菊，岳克強(qiáng)，等.具有自學(xué)習(xí)能力的變異蝙蝠優(yōu)化算法及性能仿真[J].系統(tǒng)仿真學(xué)報(bào)，2017，29(2)：301-308.

[9] 劉長(zhǎng)平，葉春明.具有Lévy飛行特征的蝙蝠算法[J].智能系統(tǒng)學(xué)報(bào)，2013，8(3)：240-246.

[10] 謝健，周永權(quán)，陳歡.一種基于Lévy飛行軌跡的蝙蝠算法[J].模式識(shí)別與人工智能，2013，26(9)：829-837.

[11] 李雅梅，曹益華.基于Powell機(jī)制的改進(jìn)蝙蝠算法[J].微電子學(xué)與計(jì)算機(jī)，2015，32(3)：73-76，80.

[12] 劉萬(wàn)軍，楊笑，曲海成.基于SQP局部搜索的蝙蝠優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2016，52(15)：183-189.

[13] 陳梅雯，鐘一文，王李進(jìn)，等.一種求解多維全局優(yōu)化問(wèn)題的改進(jìn)蝙蝠算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2015，36(12)：2749-2753.

[14] 臧慧芳，高岳林.基于混沌和差分進(jìn)化的混合蝙蝠算法[J].蘭州理工大學(xué)學(xué)報(bào)，2016，42(5)：90-94.

[15] 王波.基于自適應(yīng)t分布混合變異的人工魚(yú)群算法[J].計(jì)算機(jī)工程與科學(xué)，2013，35(4)：120-124.

[16] 常青，賀興時(shí).基于t分布變異的蝙蝠算法[J].西安工程大學(xué)學(xué)報(bào)，2015，29(5)：647-653.

[17] 薛威力，賀興時(shí)，楊新社.蝙蝠算法的一種改進(jìn)[J].哈爾濱商業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016，32(6)：706-712.

Animprovedmethodforbatalgorithm

WEI San-qiang1，2，ZHANG Chao1

(1.Department of Computer and Information，Suzhou Vocational and Technological College，Suzhou 234101，China；(2.School of Information and Control Engineering，China University of Mining and Technology，Xuzhou 221116，China)

When the bat algorithm performs local search，random numbers are added to the optimal solution of each dimension.This mechanism makes the bat algorithm fall into local extremum，which leads to the low precision of the algorithm.In view of the shortcomings of the bat algorithm.This paper proposes a modified algorithm，which employed a student’st-distribution mutation operator to disturb the optimal solution of each dimension.The experimental results of seven function show that the modified algorithm improves the convergence precision and speed.Therefore，the modified algorithm whicht-distribution mutation operator is added can improve the abilities of seeking the global excellent result and evolution speed.

bat algorithm；student’st-distribution；convergence precision；population diversity；intelligence algorithm

1000-1832(2017)04-0076-06

10.16163/j.cnki.22-1123/n.2017.04.015

2017-04-12

國(guó)家自然科學(xué)基金資助項(xiàng)目(61572036)；安徽省高校自然科學(xué)研究重點(diǎn)項(xiàng)目(KJ2016A781).

魏三強(qiáng)(1980—)，男，副教授，博士研究生，主要從事智能算法、云計(jì)算研究.

TP 301.6學(xué)科代碼520·10

A

(責(zé)任編輯：石紹慶)