分?jǐn)?shù)階策略和帶有Lévy飛行的螺旋蝙蝠算法

李苗苗，王秋萍，惠 蕙

西安理工大學(xué) 理學(xué)院，西安710054

近年來，模擬自然現(xiàn)象的群智能算法常被用于解決優(yōu)化問題，以達(dá)到預(yù)期目的。群智能算法結(jié)構(gòu)簡單，具有并行和分布式特點，解決復(fù)雜問題時的效率和穩(wěn)定性高，而被廣泛用于實際優(yōu)化問題。

蝙蝠算法[1]是一種基于群體智能的啟發(fā)式搜索算法，可以有效地搜索全局最優(yōu)解。它是一種隨機搜索算法，通過模擬蝙蝠的回聲定位以檢測獵物并避開障礙物，并且結(jié)合現(xiàn)有優(yōu)化算法的優(yōu)點，使其在解決優(yōu)化問題方面更具優(yōu)勢?；贐A的算法已應(yīng)用于多個領(lǐng)域，例如優(yōu)化節(jié)能系統(tǒng)[2]、神經(jīng)網(wǎng)絡(luò)模型[3]、多級圖像閾值處理[4]等。與其他傳統(tǒng)的優(yōu)化技術(shù)相比，BA算法具有較強的優(yōu)勢，但存在陷入局部極值的可能，從而會降低收斂速度和準(zhǔn)確性。因此，國內(nèi)外學(xué)者對其進(jìn)行了各種改進(jìn)研究。Paiva等[5]使用柯西突變算子和精英反向?qū)W習(xí)策略來提高BA的多樣性和收斂速度。Cai等[6]提出了具有高斯隨機游走的BA算法，以增強局部搜索能力。Cui等[7]提出了一種具有慣性權(quán)重的蝙蝠算法，該算法可以控制每個蝙蝠先前速度的慣性影響，并提高了局部搜索能力。

上述基于蝙蝠算法的改進(jìn)，從不同方面提高了算法的性能。為了進(jìn)一步提升算法性能，本文提出一種新的改進(jìn)的蝙蝠算法，具體改進(jìn)如下：利用分?jǐn)?shù)階對歷史經(jīng)驗的記憶性，自適應(yīng)調(diào)整階次，增強種群多樣性，加快了算法收斂速度；將Lévy飛行與阿基米德螺旋結(jié)合產(chǎn)生局部新解，增強了算法的局部開發(fā)和跳出局部最優(yōu)能力；為更好地平衡算法的探索和開發(fā)能力，采用新的動態(tài)機制調(diào)節(jié)響度和脈沖發(fā)射率。最后，將FOSBA在CEC2014測試集和減速器設(shè)計問題上進(jìn)行對比實驗，驗證其有效性。

1 蝙蝠算法

1.1 基本的蝙蝠算法

蝙蝠算法[1]是在理想狀態(tài)下，利用蝙蝠在覓食時所發(fā)出的脈沖頻率、響度、脈沖發(fā)射率的變化而設(shè)計的一種群智能算法。蝙蝠使用聲波回聲定位、檢測獵物、躲避障礙，并且在逼近目標(biāo)時會增大脈沖發(fā)射率，減小響度。蝙蝠尋找獵物理想化過程如下：

（1）蝙蝠使用回聲定位來確定與目標(biāo)的距離。

（2）蝙蝠以速度vi向一個位置xi飛行，并通過不同波長(λ)和響度(A)搜索位置，在給定的頻率間隔(fmin,fmax)內(nèi)發(fā)射，以檢測獵物或躲避障礙。

（3）蝙蝠在計算與目標(biāo)的距離時，可以調(diào)節(jié)信號的波長和脈沖速率。

（4）A從最大值(Amax)降到最小值(Amin)。當(dāng)Amin=0意味著蝙蝠剛剛找到了獵物，暫時停止發(fā)出任何聲音。在d維搜索空間中，第i只蝙蝠在第t次迭代中的位置和速度更新公式為：

其中，β是[0，1]均勻分布的隨機數(shù)；fi是蝙蝠的搜索脈沖頻率，fi∈[fmin,fmax]；x?是當(dāng)前最好的解。

對于算法的局部搜索，一旦從當(dāng)前解集選取最好的解，那么通過隨機游走產(chǎn)生新解：

這里ε∈[-1,1]是服從均勻分布的隨機數(shù)，At是所有蝙蝠在t次迭代中的平均響度。響度和脈沖發(fā)射率的更新公式為：

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

蝙蝠算法是基于蝙蝠回聲定位設(shè)計的一種隨機搜索算法，具有較好的搜索能力。然而，同其他智能優(yōu)化算法一樣，基本的蝙蝠算法在優(yōu)化過程中存在收斂速度低，易陷入局部極值等不足，譬如在蝙蝠的位置中，個體的位置與速度有關(guān)，而速度依賴于當(dāng)前全局最好解，每次進(jìn)行全局位置更新時，就會受上一代位置與當(dāng)前最好解位置的距離牽制，導(dǎo)致算法的全局搜索能力不足，易陷入局部最優(yōu)；另外，基本的蝙蝠算法在迭代后期響度趨于零，脈沖發(fā)射率趨于最大值，如果產(chǎn)生的優(yōu)良新解，由于不滿足條件而不能被接受，就會導(dǎo)致算法早熟。

針對上述問題，本文將分?jǐn)?shù)階策略、帶有Lévy飛行的阿基米德螺旋策略以及動態(tài)調(diào)整響度和脈沖發(fā)射率進(jìn)行結(jié)合，其目的是提高算法的收斂速度，加強算法的局部開發(fā)和跳出局部極值能力，避免迭代后期出現(xiàn)早熟，具體的改進(jìn)策略如下。

1.2.1 基于分?jǐn)?shù)階的改進(jìn)策略

分?jǐn)?shù)微積分是公認(rèn)的有效工具，可用來描述自然的行為，以及許多研究領(lǐng)域的實際問題，如工程、數(shù)學(xué)、物理、金融領(lǐng)域等[8]。其中，Grunwald Letnikov分?jǐn)?shù)階微積分形式[9]如下：

其中，Dβ(z(t))是Grunwald Letnikov（GL）的β階導(dǎo)數(shù)，Γ是伽馬函數(shù)。

從式（7）可以得到，整數(shù)階導(dǎo)數(shù)具有有限項，而分?jǐn)?shù)階導(dǎo)數(shù)具有無限項，因此，整數(shù)導(dǎo)數(shù)是局部算子，而分?jǐn)?shù)導(dǎo)數(shù)對所有過去事件具有記憶性。然而，對過去事件的影響隨著時間的推移而減小。基于式（7），離散Grunwald Letnikov分?jǐn)?shù)階微積分可表述如下：

其中，P是采樣周期，r為截斷階次，β表示階次。

在基本蝙蝠算法中，蝙蝠位置更新如式（3）所示，將其變形為式（9）：

考慮前四項微分，得到本文的蝙蝠位置更新式如式（13）：

分?jǐn)?shù)階的階次β影響著蝙蝠的位置更新，當(dāng)β很小時，將忽略蝙蝠先前的活動容易陷入局部極值，但β太大，算法的復(fù)雜度會增加，花費時間更多。因此，本文采用式（14）調(diào)整分?jǐn)?shù)階階次β,β取值范圍為[0.4，0.6][9]，式中T是最大迭代次數(shù)。

基于上述分析，將分?jǐn)?shù)階微積分嵌入到蝙蝠算法[9]，在搜索前期，分?jǐn)?shù)階微積分憑借自身的記憶特性，可以提升算法的探索能力，隨迭代次數(shù)增加，分?jǐn)?shù)階階次不斷減小，有利于后期算法開發(fā)。因此結(jié)合階次自適應(yīng)調(diào)整的分?jǐn)?shù)階策略，可以增強種群多樣性，提高算法的收斂速度，獲得高質(zhì)量的解。

1.2.2 結(jié)合Lévy飛行的阿基米德螺旋策略

阿基米德螺線[10]是以恒定角速度繞固定點旋轉(zhuǎn)并不斷遠(yuǎn)離固定點而產(chǎn)生的的軌跡。在極坐標(biāo)中，(R,θ)的定義如式（15）所示：

式中，θ是極角；參數(shù)a為起始點與極坐標(biāo)中心的距離；參數(shù)b控制螺線間的螺距。本文將Lévy飛行與阿基米德螺旋結(jié)合產(chǎn)生局部新解，如式（16）所示：

其中，x?是當(dāng)前所有蝙蝠中的最好解，xlevy是基于Lévy飛行[11]產(chǎn)生的解，l,ε是[-1,1]內(nèi)均勻分布的隨機數(shù)，At是所有蝙蝠在t次代里的平均響度，λ是[λmin,λmax]范圍內(nèi)的隨機數(shù)，xrr是在蝙蝠種群中隨機選取的個體，μ和v服從正態(tài)分布，v~N(0,1)，即標(biāo)準(zhǔn)正態(tài)分布，μ~

其中，Γ為伽馬函數(shù)，通常η的取值范圍為(0,2][11]。

該螺旋策略以一定的旋轉(zhuǎn)角度進(jìn)行搜索，最大限度地避免了生成重復(fù)個體，能夠有效提升算法的局部開發(fā)能力。Lévy飛行是一種隨機游走方式，并且在隨機游走過程中偶爾會出現(xiàn)長跳躍，在搜索過程中，Lévy飛行能夠擴大群體搜索范圍，協(xié)助算法在必要時跳出局部最優(yōu)。與其他螺旋方式不同的是，本文在算法的局部位置更新中將Lévy飛行與阿基米德螺旋相結(jié)合，生成局部新解，該策略不但可以增強算法的局部開發(fā)能力，而且能有效協(xié)助算法跳出局部最優(yōu)，提升算法搜索性能。

1.2.3 新的動態(tài)調(diào)節(jié)機制

脈沖發(fā)射率控制是否在當(dāng)前全局最好解附近進(jìn)行局部搜索，響度和個體適應(yīng)值控制是否接受由局部更新產(chǎn)生的新解，基本的蝙蝠算法在迭代后期響度趨于零，如果產(chǎn)生的優(yōu)良新解，由于不滿足條件而不能被接受，就會導(dǎo)致算法出現(xiàn)早熟現(xiàn)象。受文獻(xiàn)[12]的啟發(fā)，采用式（19）、（20）更新響度和脈沖發(fā)射率，以此來平衡算法的探索和開發(fā)。改進(jìn)后的脈沖發(fā)射率r″和原始脈沖發(fā)射率r、改進(jìn)后的響度A″和原始響度A分別隨迭代次數(shù)t的變化曲線，分別如圖1和圖2所示。改進(jìn)后r隨t的增加逐漸增加，且r″≤r,那么P(rand>r″)≥P(rand>r),此時有更高的概率在全局最好解附近進(jìn)行局部搜索，有利于尋找最優(yōu)解。原始A隨t的增加逐漸趨于0，rand

圖1 r″和r隨迭代次數(shù)的變化Fig.1 r″and r with the number of iterations

圖2 A″和A隨迭代次數(shù)的變化Fig.2 A″and A with the number of iterations

其中，Amax=0.5,Amin=0.2,rmax=0.7,rmin=0.1[12]，c是控制參數(shù)。在算法在迭代前期，通過使用較低的脈沖發(fā)射率，從局部隨機游走推進(jìn)全局搜索，可以有效地探索解空間；在迭代后期，脈沖發(fā)射率取較大的值，可以提高開發(fā)能力。

1.3 改進(jìn)的算法步驟

步驟1初始化參數(shù)，如種群規(guī)模n，速度vi(i=1,2,…,n)，響度Ai和脈沖發(fā)射率ri，蝙蝠位置xi，最大迭代次數(shù)T。

步驟2計算每只蝙蝠適應(yīng)度，并找出當(dāng)前最優(yōu)值x?。

步驟3當(dāng)前迭代次數(shù)小于最大迭代次數(shù)時，根據(jù)式（1）、（2）、（13）更新蝙蝠速度和位置。

步驟4產(chǎn)生隨機數(shù)rand1，若rand1>ri，則利用公式（16）在當(dāng)前最優(yōu)值附近產(chǎn)生一個局部新解。

步驟5產(chǎn)生隨機數(shù)rand2，若rand2

步驟6將所有蝙蝠適應(yīng)值排序，找出當(dāng)前最優(yōu)解x?。

步驟7更新算法迭代次數(shù)，判斷是否滿足終止條件，如果滿足，則停止迭代輸出最優(yōu)解，否則轉(zhuǎn)至步驟3，直到滿足終止條件。

2 數(shù)值實驗

為了評估本文算法（FOSBA）的數(shù)值優(yōu)化性能，選取CEC2014基準(zhǔn)測試函數(shù)進(jìn)行實驗，該測試集包含30個不同類型函數(shù)，其中F1~F3是單峰函數(shù)，F(xiàn)4~F16是多峰函數(shù)，F(xiàn)17~F22是混合型函數(shù)，F(xiàn)23~F30是復(fù)合型函數(shù)。所有的數(shù)值實驗在Matlab 2013（a）中進(jìn)行。實驗分為2個部分：第一，選取奇數(shù)組測試函數(shù)，將FOSBA與其他改進(jìn)的蝙蝠算法進(jìn)行實驗對比；第二，選取偶數(shù)組測試函數(shù)，將FOSBA與其他智能算法進(jìn)行實驗對比，并對實驗結(jié)果統(tǒng)計分析。

2.1 FOSBA與改進(jìn)的BA比較

本部分實驗選取全局混沌蝙蝠優(yōu)化算法（GCBA）[13]、自適應(yīng)改進(jìn)的蝙蝠算法（ICBA）[14]、基于橫向交叉策略的蝙蝠算法（IBA）[15]，與FOSBA在CEC2014奇數(shù)組測試函數(shù)上進(jìn)行實驗對比。為保持實驗的客觀性，4個算法基本參數(shù)設(shè)置相同，脈沖頻率取值范圍為(0,2),r0=0.7,A0=0.2,α=β=0.9；n=30,T=500,D=30，其中GCBA算法學(xué)習(xí)因子c1=c2=1.496 18,本文的控制參數(shù)c=1.3，每個函數(shù)運行51次，并記錄各算法結(jié)果的均值、標(biāo)準(zhǔn)差，結(jié)果如表1所示，其中最好的結(jié)果以粗體顯示，表中均值反映了算法的優(yōu)化能力，標(biāo)準(zhǔn)差反映了算法穩(wěn)定性。

表1結(jié)果顯示，F(xiàn)OSBA在多數(shù)函數(shù)上的尋優(yōu)結(jié)果都要優(yōu)于對比算法。對單峰函數(shù)F1、F3，F(xiàn)OSBA的均值和標(biāo)準(zhǔn)差都是最小的，說明該算法全局搜索能力較強。在多峰函數(shù)F5、F7、F9、F13、F15上，F(xiàn)OSBA優(yōu)化結(jié)果精度和標(biāo)準(zhǔn)差均是最好的，說明該算法具有一定的探索能力和跳出極值點的能力。在測試函數(shù)F11上，GCBA表現(xiàn)出較強的尋優(yōu)能力，在測試函數(shù)F13上，F(xiàn)OSBA與GCBA尋找到同樣的結(jié)果，但FOSBA的標(biāo)準(zhǔn)差較小。在復(fù)合函數(shù)F17~F21上，F(xiàn)OSBA較其他算法，無論是均值或標(biāo)準(zhǔn)差都具有明顯優(yōu)勢，說明帶有Lévy飛行螺旋策略和非線性轉(zhuǎn)換機制具有較強的適應(yīng)性，從而能快速尋找最優(yōu)解。

表1 FOSBA與改進(jìn)BA結(jié)果比較Table 1 Comparison of FOSBA and improved BA

2.2 FOSBA與其他智能算法的比較

本部分實驗選取差分進(jìn)化算法[16]（DE）、細(xì)菌覓食算法[17]（BFA）、正余弦算法[18]（SCA）與FOSBA在CEC2014偶數(shù)組測試函數(shù)上進(jìn)行實驗對比，各算法的具體參數(shù)設(shè)置和參考文獻(xiàn)相同。以上算法參數(shù)設(shè)置n=30,T=500,D=30，各算法獨立運行51次，記錄各算法結(jié)果均值、標(biāo)準(zhǔn)差，結(jié)果如表2所示，其中最好結(jié)果以粗體顯示。

根據(jù)表2結(jié)果，F(xiàn)OSBA在多數(shù)函數(shù)上的尋優(yōu)效果優(yōu)于其他對比算法，并且在函數(shù)F2、F4、F12、F14、F30上的收斂精度明顯提高且標(biāo)準(zhǔn)差相對較小。在多峰函數(shù)上F12、F14上，F(xiàn)OSBA的平均值與標(biāo)準(zhǔn)差更加優(yōu)異，說明該算法能夠有效避免局部最優(yōu)，進(jìn)而說明帶有Lévy飛行的螺旋策略的有效性。在混合復(fù)合函數(shù)F18、F24、F26上，F(xiàn)OSBA具有顯著優(yōu)勢，說明本文新的非線性轉(zhuǎn)換機制能夠有效平衡算法的探索和開發(fā)能力。而SCA在函數(shù)F6、F20的尋優(yōu)效果優(yōu)于FOSBA，表現(xiàn)出較好的尋優(yōu)能力。

表2 FOSBA與其他智能算法結(jié)果比較Table 2 Comparison of FOSBA and other intelligent algorithms

圖3給出了各算法在CEC2014測試函數(shù)上的部分收斂曲線圖，直觀反映了各算法的收斂性能。在單峰函數(shù)F1、F2上，F(xiàn)OSBA的收斂曲線下降快且曲線位于最下方，具有更高的尋優(yōu)精度。SCA和FOSBA在F4上的曲線收斂值接近，但FOSBA在前期收斂速度快。在多峰函數(shù)F4、F15上，其他對比算法出現(xiàn)了一定程度的停滯，出現(xiàn)陷入局部極值情況，而FOSBA在后期仍能繼續(xù)搜索，這歸因于帶有Lévy飛行的螺旋機制，加強了算法跳出局部最優(yōu)的能力，提高了算法的局部開發(fā)能力。在混合和復(fù)合函數(shù)F18、F30上，F(xiàn)OSBA具有較好的穩(wěn)定性，在搜索后期可能搜索速度稍慢，但尋優(yōu)精度優(yōu)于其他對比算法，說明新的動態(tài)調(diào)節(jié)機制可以有效平衡算法的探索和開發(fā)。

圖3 各算法在CEC2014測試函數(shù)上的部分收斂曲線圖Fig.3 Partial convergence curve of each algorithm on CEC2014 test function

采用Friedman秩方差檢驗分析FOSBA與其智能優(yōu)化算法結(jié)果在統(tǒng)計上有無顯著差異，取顯著性水平為0.05。Friedman檢驗統(tǒng)計量S：

如果經(jīng)過Friedman檢驗證明多樣本存在顯著性差異，再考慮Hollander-Wolfe檢驗來分析兩兩算法間的差異性。式（22）為兩樣本之間的比較公式：

其中，R.g和R.k為第g與第k個樣本的秩和，如果|Dgk|≥Z1-α*時，表示兩樣本之間有差異，反之則無差異，α*=α/m(m-1)，α是顯著性水平，Z1-α*為標(biāo)準(zhǔn)正態(tài)分布分位數(shù)。

表3 兩兩算法處理的Hollander-Wolfe計算表Table 3 Pairwise algorithm processing Hollander-Wolfe calculation table

2.3 算法復(fù)雜度分析

算法的復(fù)雜度是評估算法的重要指標(biāo)之一，下面分析算法迭代一次的復(fù)雜度。更新全局位置和基于變量的上下界修正蝙蝠位置的復(fù)雜度是O(N)；計算適應(yīng)度值和更新全局最優(yōu)位置的復(fù)雜度是O(N)；采用分?jǐn)?shù)階策略更新全局位置的復(fù)雜度為O(TNr)；采用阿基米德螺旋局部更新蝙蝠位置的復(fù)雜度是O(ND)；對響度和脈沖發(fā)射率更新的復(fù)雜度是O(N)；則算法迭代一次的復(fù)雜度是O(N)+O(N)+O(TNr)+O(ND)+O(N)=O(TNDr)。因此該算法的整體復(fù)雜度是O(TNDr)，其中N是種群規(guī)模，D是維數(shù)，T是最大迭代次數(shù)。

3 算法應(yīng)用

在本章中，選取機械工程優(yōu)化中的減速器設(shè)計問題，以進(jìn)一步驗證所提出算法解決實際工程約束優(yōu)化問題的能力。由于工程問題的約束不同，罰函數(shù)法是常用的約束處理方法，在目標(biāo)函數(shù)添加懲罰項，將問題轉(zhuǎn)化成無約束優(yōu)化問題進(jìn)行求解，本章中應(yīng)用罰函數(shù)法解決減速器設(shè)計問題。

如圖4所示，該設(shè)計是非線性有約束的優(yōu)化問題，目標(biāo)是使減速器重量達(dá)到最小[19]，該問題有7個設(shè)計變量，分別是齒面寬x1，齒輪模數(shù)x2，小齒輪齒數(shù)x3，軸承之間的第一軸的長度x4，軸承之間的第二軸的長度x5，第一軸直徑x6和第二軸的直徑x7。具體數(shù)學(xué)模型如下：

圖4 減速器問題示意圖Fig.4 Schematic diagram of speed reducer design optimization problem

將FOSBA用于解決該非線性問題，種群規(guī)模為30，最大迭代次數(shù)為500，獨立運行30次，并將實驗結(jié)果與文獻(xiàn)[20]、文獻(xiàn)[21]、文獻(xiàn)[22]進(jìn)行比較，記錄了各設(shè)計變量的取值以及最好的適應(yīng)值，比較結(jié)果如表4所示，F(xiàn)OSBA的優(yōu)化結(jié)果優(yōu)于其他對比算法。

表4 減速器設(shè)計問題優(yōu)化結(jié)果比較Table 4 Comparison of results for speed reducer design optimization problem

4 結(jié)論

本文提出一種改進(jìn)的蝙蝠算法（FOSBA），依據(jù)分?jǐn)?shù)階對歷史事件的記憶性，在蝙蝠位置更新中引入分?jǐn)?shù)階微積分，增加群體多樣性，提高了算法收斂速度；將Lévy飛行與阿基米德螺旋結(jié)合產(chǎn)生局部新解，增強算法的開發(fā)能力，同時Lévy飛行協(xié)助算法跳出局部最優(yōu)；通過新的方式動態(tài)調(diào)節(jié)響度和脈沖發(fā)射率來平衡全局勘探和局部開發(fā)能力。在CEC2014基準(zhǔn)測試集上和減速器設(shè)計問題上進(jìn)行實驗，結(jié)果表明本文算法具有較高的尋優(yōu)精度和收斂速度，并用Firedman統(tǒng)計分析證實了本文算法有效性和優(yōu)越性。最后，將FOSBA用于減速器設(shè)計問題，驗證了本文算法優(yōu)良性能。