雙核因素蝙蝠算法

肖海軍，成金華，何　凡

(1 中國(guó)地質(zhì)大學(xué)(武漢) 數(shù)學(xué)與物理學(xué)院，武漢 430074；2中國(guó)地質(zhì)大學(xué)(武漢) 經(jīng)濟(jì)管理學(xué)院 資源環(huán)境經(jīng)濟(jì)研究中心，武漢 430074)

1　研究背景

通過(guò)對(duì)生物行為的模擬，人們發(fā)現(xiàn)了均衡性強(qiáng)、優(yōu)化效果好的群智能優(yōu)化算法.受到群智能優(yōu)化算法的啟發(fā)，研究人員又提出了廣泛應(yīng)用的智能優(yōu)化算法.如：隨機(jī)擴(kuò)散搜索[1]，蟻群優(yōu)化[2]，粒子群優(yōu)化[3,4]和蝙蝠算法[5].Bishop[1,6]提出的隨機(jī)擴(kuò)散搜索(SDS)是一種具有良好數(shù)學(xué)概率的全局搜索算法[7-9]，雖然在全局搜索過(guò)程中SDS效率高、魯棒性好，但其優(yōu)化技術(shù)只適用于可分解為多個(gè)部分函數(shù)的目標(biāo)函數(shù).蟻群優(yōu)化算法[2](ACO)通過(guò)模擬“螞蟻”記錄位置和生物特征來(lái)尋找最優(yōu)路徑，這使得螞蟻在后續(xù)的探索中找到更優(yōu)的路徑[10].但是ACO的最優(yōu)解存在不確定性.粒子群優(yōu)化算法(PSO)可以在n維空間中搜尋點(diǎn)或面的最優(yōu)解[11-13]，該算法處理局部極值問(wèn)題時(shí)靈活性較強(qiáng).但是PSO算法需要大量的粒子群個(gè)體才能獲得相對(duì)滿意的優(yōu)化結(jié)果.蝙蝠算法(BA)是Yang[5]提出的一種全局優(yōu)化算法(蝙蝠通過(guò)模擬脈沖發(fā)射頻率和響度來(lái)搜索獵物)，通過(guò)調(diào)整頻率來(lái)加強(qiáng)解的多樣性，并利用自動(dòng)縮放能力來(lái)平衡尋優(yōu)過(guò)程中的搜索與開發(fā).

與其他算法相比，蝙蝠算法在處理一些復(fù)雜問(wèn)題時(shí)表現(xiàn)更好.因此，一些研究人員有效地改進(jìn)了蝙蝠算法.如：KHan等[14]提出了模糊邏輯蝙蝠算法，將模糊邏輯與蝙蝠算法相結(jié)合.Yang[15]提出了一種多目標(biāo)蝙蝠算法來(lái)解決某些工程問(wèn)題.Lin等[16]提出了組合蝙蝠算法，通過(guò)使用Lévy飛行和組合映射來(lái)估計(jì)算法參數(shù).Nakamura等[17]提出名為二進(jìn)制蝙蝠算法的離散版本來(lái)改進(jìn)分類和特征選擇.Xie等[18]提出了基于差分算子和Lévy飛行的蝙蝠算法，借此來(lái)解決優(yōu)化問(wèn)題.

此外，還有各種優(yōu)化的蝙蝠算法.例如，Zhang和Wang[19]引入生物突變，來(lái)提高解決圖像匹配多樣性的問(wèn)題.Xie和Zhou[20]提出了組合蝙蝠算法，通過(guò)組合蝙蝠算法與回聲搜索來(lái)優(yōu)化基準(zhǔn)函數(shù)的數(shù)值.Fister I等[21]使用差分進(jìn)化對(duì)蝙蝠路徑進(jìn)行局部搜索，然后結(jié)合四元數(shù)創(chuàng)建了四元數(shù)蝙蝠算法(QBA)，這種方法可以解決大規(guī)模的旋轉(zhuǎn)型和幾何計(jì)算型的優(yōu)化問(wèn)題[22].Li和Zhou[23]提出了一種基于復(fù)數(shù)編碼的新型蝙蝠算法，它對(duì)編碼的實(shí)部和虛部分別單獨(dú)更新.

BA從搜索轉(zhuǎn)向開發(fā)時(shí)收斂迅速，當(dāng)頻率、波長(zhǎng)或響度變化太快時(shí)，可能導(dǎo)致局部最優(yōu).因此，本文提出一種改進(jìn)的蝙蝠算法，稱為雙核因素蝙蝠算法(DCFBA).在DCFBA中，自適應(yīng)速度更新公式加入了兩個(gè)自適應(yīng)學(xué)習(xí)因子并且受到最優(yōu)和次優(yōu)蝙蝠位置的影響，再通過(guò)仿真實(shí)驗(yàn)驗(yàn)證DCFBA的有效性.

2　蝙蝠算法

蝙蝠是一種具有回聲定位能力的動(dòng)物.搜索獵物時(shí)，蝙蝠發(fā)出的聲波碰到一個(gè)物體后，聲波會(huì)返回到它的耳中[13]，蝙蝠可以由此估計(jì)與物體的距離[24].基于蝙蝠回聲定位的特性與狩獵習(xí)性，Yang[25]提出了標(biāo)準(zhǔn)蝙蝠算法，標(biāo)準(zhǔn)規(guī)則如下.

(1) 所有蝙蝠通過(guò)回聲定位感知距離，并以某種獨(dú)特的方式從背景障礙中區(qū)分獵物；

(2) 蝙蝠在位置Si以固定的頻率fmin和速度vi，變化的波長(zhǎng)λ和響度A0自由地狩獵；

(3) 假設(shè)響度從最大值A(chǔ)0到最小值A(chǔ)min不等.

2.1　蝙蝠的速度更新和位置更新

fi=fmin+α(fmax-fmin),

(1)

(2)

(3)

其中α代表[0,1]中的隨機(jī)數(shù)，fi表示當(dāng)前時(shí)刻蝙蝠i的變化頻率，Xbest是當(dāng)前的全局最優(yōu)解，可以通過(guò)比較所有解找到.

為了改善解的多樣性，從蝙蝠群體中選擇一只蝙蝠，并根據(jù)(4)式隨機(jī)地產(chǎn)生一個(gè)新的局部解.通過(guò)此設(shè)置，局部搜索可以順利進(jìn)行，并從已經(jīng)選擇的解中精選新的解.

Xnew=Xold+δAt,

(4)

其中At表示此時(shí)所有蝙蝠的平均響度，δ∈[-1,1]是一個(gè)隨機(jī)值，Xold代表從當(dāng)前最優(yōu)解中選擇的隨機(jī)解.

2.2　蝙蝠的響度更新和脈沖發(fā)射率更新

當(dāng)搜索開始時(shí)，為了延長(zhǎng)超聲波傳播的距離，將響度設(shè)置為最大值，將脈沖發(fā)射率設(shè)置為最小值.當(dāng)蝙蝠搜索獵物時(shí)，響度逐漸降低，脈沖發(fā)射率增大，這可以幫助蝙蝠更準(zhǔn)確地定位獵物.算法進(jìn)行迭代時(shí)響度Ai和脈沖發(fā)射率ri的更新公式如下:

(5)

(6)

3　雙核因素蝙蝠算法的速度更新方法及步驟

速度更新公式在蝙蝠算法中起關(guān)鍵作用，它決定了蝙蝠在搜索空間的速度.蝙蝠算法通過(guò)(2)式更新蝙蝠的速度，它考慮到以前的速度和當(dāng)前蝙蝠的最佳位置.然而，蝙蝠的最佳位置并不是改變搜索方向的唯一因素.我們?cè)谘芯窟^(guò)程中發(fā)現(xiàn)蝙蝠的次優(yōu)位置也是影響優(yōu)化結(jié)果的一個(gè)重要因素.因而在提出的DCFBA中我們考慮了這個(gè)因素，這種改進(jìn)的蝙蝠算法稱之為雙核因素蝙蝠算法(DCFBA).

3.1　DCFBA的速度更新方法

(7)

其中Xbest和Xsecond分別代表其他蝙蝠的最優(yōu)位置和次優(yōu)位置，c1(t)和c2(t)為學(xué)習(xí)因子.更新公式如下：

c1(t)=1-exp(-Ψ(t)),

(8)

c2(t)=1-c1(t),

(9)

Ψ(t)=|Fitnessmean(t)-Fitnessbest(t)|,

(10)

(11)

依靠速度更新公式的創(chuàng)新，可以大大加強(qiáng)DCFBA在優(yōu)化過(guò)程中的靈活性，使算法具有提高收斂速度的優(yōu)點(diǎn)，更重要的是可以避免算法陷入局部最優(yōu).

3.2　DCFBA的更新方法

基于上述更新規(guī)則，DCFBA的實(shí)施步驟可概括如下.

DCFBA偽代碼Input：M：thepopulationsizeofbatsε：theloudnessγ：thepulseemissionfmax：themaximumpulsefrequencyfmin：theminimumpulsefrequencyitermax：themaximumnumberofiterationsOutput：thebatwiththebestfitnessvalueinthepopulation．Initialisethebats′positionsXi，velocityvi，frequencyfi，pulseratesriandtheloudnessAi．Assumethefitnessfunctionisminimum．whilethestopconditionisnotsatisfieddo　　forallbatsdo　　CalculatethefitnessvalueFitnessiandobtainthebestsolutionbyupdatingthebats′positionsandvelocityasdescribedinEqu．(3)and(7)．　　ifrand>rithen　　　ChooseasolutionamongthebestonesandrandomlygeneratealocalsolutionXnewaroundthebestchosensolution．　　endif　　EvaluatenewsolutionFitnessnew　　ifrand

4　數(shù)值驗(yàn)證

4.1　基準(zhǔn)問(wèn)題

在實(shí)驗(yàn)中，為了研究DCFBA的有效性、效率性和穩(wěn)定性，我們采用BA和PSO算法作為對(duì)比算法，選取了具有不同屬性的9個(gè)基準(zhǔn)優(yōu)化函數(shù).這9個(gè)基準(zhǔn)函數(shù)可以分為高維單峰函數(shù)(第I類)、高維多模態(tài)函數(shù)(第II類)和低維函數(shù)(第III類)，見表1.

表1　基準(zhǔn)優(yōu)化函數(shù)Tab.1　Benchmark functions

4.2　仿真平臺(tái)

用于評(píng)估DCFBA的平臺(tái)的配置為：Intel Pentium(R)雙核CPU，2.5GHz，2.00GB RAM，Windows 7操作系統(tǒng)，MATLAB 2014a(Windows)開發(fā)環(huán)境.

4.3　參數(shù)設(shè)置

在DCFBA算法中蝙蝠群體大小為20，響度衰減系數(shù)α=0.5，增加脈沖發(fā)射系數(shù)γ=0.5，脈沖頻率fi∈[0,2].BA算法的參數(shù)與DCFBA相同.在PSO算法中學(xué)習(xí)因子c1=c2=0.5，粒子群體大小為30.

4.4　實(shí)驗(yàn)結(jié)果

采用3種方法在9個(gè)基準(zhǔn)函數(shù)上的優(yōu)化對(duì)比結(jié)果如表2～4所示.其中Worst，Mean，Best和Std.分別表示最差適應(yīng)度值，平均適應(yīng)度值，最佳適應(yīng)度值和適應(yīng)度值的標(biāo)準(zhǔn)差.黑體數(shù)字表示DCFBA是優(yōu)選的，而加下劃線的數(shù)值表示其他算法是優(yōu)選的.

由表2可知，DCFBA可以在第I類函數(shù)中獲得最優(yōu)結(jié)果.對(duì)于這4個(gè)函數(shù)，DCFBA的最差適應(yīng)度值，平均適應(yīng)度值，最佳適應(yīng)度值和適應(yīng)度值的標(biāo)準(zhǔn)差均優(yōu)于BA和PSO，這意味著DCFBA在高維單峰函數(shù)下具有最佳的穩(wěn)定性.

表3　函數(shù)F5,F6,F7的仿真結(jié)果Tab.3　Simulation results for test functions F5,F6,F7

由表3可知，DCFBA在第Ⅱ類函數(shù)中的優(yōu)化結(jié)果也是最好的.即便DCFBA在某項(xiàng)指標(biāo)上不如其他算法，但其結(jié)果也是非常接近最優(yōu)值的.總體而言，DCFBA在高維多峰函數(shù)上的優(yōu)化性能優(yōu)于BA和PSO.

表4　函數(shù)F8, F9的仿真結(jié)果

由表4可知，對(duì)于函數(shù)F8，3種算法的最優(yōu)適應(yīng)度值相等，雖然DCFBA在平均適應(yīng)度值和標(biāo)準(zhǔn)偏差上比BA稍差，但是DCFBA的其他指標(biāo)都比BA和PSO好.對(duì)于F9，DCFBA優(yōu)于(超過(guò)或等于)BA和PSO的結(jié)果.顯然，在第Ⅲ類函數(shù)上，DCFBA的性能仍然優(yōu)于BA和PSO.

針對(duì)三類函數(shù)，圖1～9是適應(yīng)性演化曲線，函數(shù)F1，F(xiàn)2，F(xiàn)3，F(xiàn)5，F(xiàn)7和F8的迭代次數(shù)從10變化到810.圖4對(duì)應(yīng)的函數(shù)F4迭代次數(shù)為1110，圖9對(duì)應(yīng)的函數(shù)F9迭代次數(shù)為325.函數(shù)F1～F9的維度D設(shè)置為30，蝙蝠群體m為20，搜索步長(zhǎng)為0.01.算法經(jīng)過(guò)十折交叉驗(yàn)證后的結(jié)果表明：DCFBA在所有基準(zhǔn)函數(shù)上的優(yōu)化結(jié)果優(yōu)于BA和PSO算法.

圖1　F1適應(yīng)度值演化曲線，搜索范圍為[-100,100] Fig.1　Evolution curves of fitness value for F1,bounds ∈[-100,100]

圖2　F2適應(yīng)度值演化曲線，搜索范圍為[-100,100]Fig.2　Evolution curves of fitness value for F2, bounds∈[-100,100]

圖3　F3適應(yīng)度值演化曲線，搜索范圍為[-100,100]Fig.3　Evolution curves of fitness value for F3,bounds∈[-100,100]

圖4　F4適應(yīng)度值演化曲線,搜索范圍為[-100,100]Fig.4　Evolution curves of fitness value for F4, bounds∈[-100,100]

圖5　F5適應(yīng)度值演化曲線，搜索范圍為[-100,100] Fig.5　Evolution curves of fitness value for F5, bounds∈[-100,100]

圖6　F6適應(yīng)度值演化曲線，搜索范圍為[-32,32] Fig.6　Evolution curves of fitness value for F6,bounds∈[-32,32]

圖7　F7適應(yīng)度值演化曲線，搜索范圍為[-100,100]Fig.7　Evolution curves of fitness value for F7,bounds∈[-100,100]

圖8　F8適應(yīng)度值演化曲線，搜索范圍為[-5,5]Fig.8　Evolution curves of fitness value for F8, bounds∈[-5,5]

圖9　F9適應(yīng)度值演化曲線，搜索范圍為[-5,15]Fig.9　Evolution curves of fitness value for F9,bounds∈[-5,15]

5　結(jié)語(yǔ)

本文提出了一種新的改進(jìn)蝙蝠算法——雙核因素蝙蝠算法.通過(guò)3種算法在9個(gè)基準(zhǔn)函數(shù)的仿真實(shí)驗(yàn)表明DCFBA有效可行.雖然在實(shí)驗(yàn)中，DCFBA算法有比其他兩種算法更好的收斂速度，但在一些迭代中是不穩(wěn)定的.作為一個(gè)優(yōu)秀的優(yōu)化算法，DCFBA可以嘗試與其他優(yōu)化算法結(jié)合，這可能會(huì)改善其優(yōu)化性能.此外，DCFBA參數(shù)設(shè)置的合理性、函數(shù)維度設(shè)置對(duì)DCFBA的影響等，值得進(jìn)一步研究.

[1]Bishop J M. Stochastic searching networks[C]//IEEE. 1989 First IEEE International Conference on IEEE. California: IEEE, 1989:329-331.

[2]Dorigo M. Optimization, learning and natural algorithms[D]. Milano: Politecnico di Milano Italy, 1992.

[3]Kennedy J, Eberhart R. Particle swarm optimization[C]//IEEE. IEEE International Conference on Neural Networks Proceedings(IEEE 4). New York: IEEE, 2002:1942-1948.

[4]Shi Y, Eberhart R. A modified particle swarm optimizer[M]. IEEE. IEEE International Conference on Evolutionary Computation. Anchorage: IEEE,1998: 69-73.

[5]Yang Xinshe. A new metaheuristic bat-inspired algorithm[J]. Computer Knowledge and Technology, 2010, 284:65-74.

[6]Nasuto S, Bishop J M. Stabilizing swarm intelligence search via positive feedback resource allocation[M]. Berlin, Heidelberg: Springer, 2008:115-123.

[7]Nasuto S, Bishop J M, Lauria S. Time complexity analysis of the stochastic diffusion search[M]. Berlin, Heidelberg: Springer, 1998: 260-266.

[8]Nasuto S, Bishop J M. Convergence analysis of stochastic diffusion search[J]. Parallel Algorithms and Applications,1999, 14(2):89-107.

[9]Myatt D R, Bishop J M, Nasuto S. Minimum stable convergence criteria for stochastic diffusion search[M]. Berlin, Heidelberg: Springer, 2004, 40(2):112-113.

[10]Parsons S. Ant Colony Optimization by Marco Dorigo and Thomas Stützle[J]. Knowledge Engineering Review, 2005, 20(1):92-93.

[11]Griffin D R, Webster F A, Michael C R. The echolocation of flying insects by bats[J]. Animal Behaviour, 1960, 8(3):141-154.

[12]Parsopoulos K E, Vrahatis M N. Recent approaches to global optimization problems through particle swarm optimization[J]. Natural Computing, 2002, 1(2-3): 235-306.

[13]Clerc M. The swarm and the queen:Towards a deterministic and adaptive particle swarm optimization[C]// IEEE. Proceedings of the Congress on Evolutionary Computation. Piscataway, NJ: IEEE Service Center, 1999: 1951-1957.

[14]Khan K, Nikov A, Sahai A. A fuzzy bat clustering method for ergonomic screening of office workplaces[C]//AINSC. Third International Conference on Software, Services and Semantic Technologies S3T 2011. Berlin, Heidelberg: Springer, 2011:59-66.

[15]Yang X. Bat algorithm for multi-objective optimisation[J]. International Journal of Bio-Inspired Computation, 2011, 3(5):267-274.

[16]Lin J H, Chou C W, Yang C H, et al. A chaotic Lévy flight bat algorithm for parameter estimation in nonlinear dynamic biological systems[J]. ResearchGate, 2012, 2(2):56-63.

[17]Nakamura R Y M, Pereira L A M, Costa K A, et al. BBA: A binary bat algorithm for feature selection[J]. Graphics, Patterns and Images, 2012(1): 291-297.

[18]Xie J, Zhou Y, Chen H. Anovel bat algorithm based on differential operator and Lévy flights trajectory[J]. Computational Intelligence and Neuroscience, 2013(2013):38-45.

[19]Zhang J W, Wang G G. Image matching using a bat algorithm with mutation[J]. Applied Mechanics and Materials, 2012, 203(1):88-93.

[20]Xie J, Zhou Y. A novel hybrid bat algorithm with harmony search for global numerical optimization[J]. Journal of Applied Mathematics,2013(3):233-256.

[21]Fister I, Fister D, Yang X S. A hybrid bat algorithm[J]. Electrotechnical Review,2013, 80(1): 64-73.

[22]Fister I. Using the quaternion′s representation of individuals in swarm intelligence and evolutionary computation[J]. Computer Science, 2013(1):34-47.

[23]Li L, Zhou Y. A novel complex-valued bat algorithm[J]. Neural Computing and Applications,2014, 25(6): 1369-1381.

[24]Metzner W. Echolocation behaviour in bats[J]. Science Progress, 1991, 75:453-465.

[25]Yang X S, Deb S. Eagle strategy using Lévy walk and firefly algorithms for stochastic optimization[J]. Studies in Computational Intelligence,2010, 284:101-111.