雙核因素蝙蝠算法

肖海軍，成金華，何　凡

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

1　研究背景

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

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

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

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

2　蝙蝠算法

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

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

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

(3) 假設響度從最大值A0到最小值Amin不等.

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

fi=fmin+α(fmax-fmin),

(1)

(2)

(3)

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

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

Xnew=Xold+δAt,

(4)

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

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

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

(5)

(6)

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

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

3.1　DCFBA的速度更新方法

(7)

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

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

(8)

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

(9)

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

(10)

(11)

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

3.2　DCFBA的更新方法

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

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ù)值驗證

4.1　基準問題

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

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

4.2　仿真平臺

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

4.3　參數(shù)設置

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

4.4　實驗結(jié)果

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

由表2可知，DCFBA可以在第I類函數(shù)中獲得最優(yōu)結(jié)果.對于這4個函數(shù)，DCFBA的最差適應度值，平均適應度值，最佳適應度值和適應度值的標準差均優(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在某項指標上不如其他算法，但其結(jié)果也是非常接近最優(yōu)值的.總體而言，DCFBA在高維多峰函數(shù)上的優(yōu)化性能優(yōu)于BA和PSO.

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

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

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

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

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

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

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

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

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

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

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

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

5　結(jié)語

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

[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.