基于速度越界處理與最速下降法改進的蝙蝠算法

高 超 梁昔明* 龍 文

1(北京建筑大學理學院 北京 102616)2(貴州財經大學經濟系統仿真貴州省重點實驗室 貴州 貴陽 550025)

0 引 言

近年來，受螞蟻、鳥類等群居生物的自組織行為的啟發，一些新穎的基于仿生的元啟發式算法相繼出現,其中較具代表性的元啟發式算法有：人工蜂群算法[1]、螢火蟲算法[2]、布谷鳥搜索算法[3]、蛙跳算法[4]、蝙蝠算法[5]。

蝙蝠算法是劍橋學者YANG教授在2010年基于蝙蝠的回聲定位特性提出的一種優化算法。蝙蝠算法主要通過改變聲音的響度、脈沖發射頻率和脈沖頻率來搜索最佳蝙蝠的位置。目前BA廣泛應用于各個領域，如：Alemu等[6]將BA應用于燃氣輪機發電系統模型中；Yang等[7]使用BA解決拓撲優化問題中的彈簧問題和減速器問題；Gandomi等[8]利用BA算法求解3個基準工程約束優化問題；還有一些學者將其應用于工程設計[9]、模糊聚類[10]、資源調配[11]等領域。但是從BA本身的迭代機制而言，當尋優區域較大時，BA存在著收斂于全局最優解的速度緩慢、收斂精度不高、易陷入局部極值等不足，這些都影響著BA應用。所以，針對這些問題，學者們提出了很多改進的BA，如謝健等[12]提出了一種基于Levy飛行軌跡的蝙蝠算法；高珊等[13]提出了函數優化的小生境蝙蝠算法；肖輝輝等[14]提出了基于DE算法改進的蝙蝠算法等。但上述幾種改進的BA也普遍存在著收斂精度不高、易陷入局部最優的問題。基于上述問題，本文提出一種基于速度越界處理與最速下降法改進的蝙蝠算法(VCBA)。實驗表明，VCBA在收斂精度和穩定性上都有較大的提高。

1 蝙蝠算法

對無約束連續優化問題：

minf(X)X∈Rn

若X∈Rn滿足

f(X*)≤f(X) ?X∈Rn

X*為f(X)在全空間Rn上的全局極小點。

蝙蝠算法的迭代流程如下：

Fi=Fmin+(Fmax-Fmin)×β

(1)

(2)

(3)

(4)

(5)

(6)

(7)

2 改進蝙蝠算法設計

2.1 速度的越界處理

文獻[5]指出，蝙蝠算法是一種特殊的標準粒子群算法，又由文獻[15]可知，粒子群算法中的粒子速度需要進行越界處理，這是為了使粒子在解空間中能夠均勻而全面的分布，使粒子群算法的搜索范圍更廣。在改進的蝙蝠算法中，對蝙蝠速度同樣需要進行越界處理。

在改進的蝙蝠算法中,對蝙蝠速度的越界處理采用如下方法：對v=(v1,v2,…,vn)T，如果vj>vmax，則令vj=vmax；如果vj

在改進的蝙蝠算法中將速度范圍控制在蝙蝠位置的范圍以內，即vj∈[vmin,vmax]?[Xmin,Xmax],j=1,2,…,n，這樣能夠控制蝙蝠位置更新的幅度不會太大，具體的速度范圍需要實驗確定。經實驗測試，本文取vmin=-5，vmax=5。若所選取的測試問題的范圍小于速度范圍，則令vmin=Xmin，vmax=Xmax。

2.2 最速下降法

1847年數學家Cauchy提出了最速下降法[16]，是求解無約束優化問題最簡單的方法之一。最速下降法是用負梯度方向作為搜索方向，其步長一般由線性搜索方法來確定。由于負梯度方向是函數的局部最速下降方向，所以若從某一點出發，用最速下降法進行迭代，得到的點一定比原來的點更優，不會出現無價值迭代。最速下降法的優勢在于算法簡單，而且從一個不好的初始點出發，往往也能收斂到局部最優值，具有快速精細的局部搜索能力。

p0=-g(X0)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

2.3 改進算法步驟

改進的蝙蝠算法步驟如下：

第1步執行BA的第1步。

第2步執行BA的第2步。

(15)

(16)

第5步執行BA的第6步。

第6步執行BA的第7步。

改進的蝙蝠算法(VCBA)的流程圖如圖1所示。

圖1 改進的蝙蝠算法流程圖

3 數值實驗

為了驗證VCBA的尋優效果，使用7個基準測試優化問題進行數值實驗。各測試優化問題的目標函數的表達式、搜索范圍和理論最優值如下：

實驗中，參數設置如下：M=25；maxgen=500；α=0.95；γ=0.05；A=0.95；r=0.9；脈沖頻率最小值Fmin=-1，脈沖頻率最大值Fmax=1；誤差精度tol=1e-6。

3.1 固定迭代次數的數據對比

BA和VCBA對目標函數f1-f7各獨立求解30次，所得目標函數值的平均進化曲線如圖2-圖7所示，圖8表示所得目標函數值的平均值取以10為底的對數所得的進化曲線。

圖2 f1的平均進化曲線

圖3 f2的平均進化曲線

圖4 f3取30維時的平均進化曲線

圖5 f4取30維時的平均進化曲線

圖6 f5取30維時的平均進化曲線

圖7 f6取30維時的平均進化曲線

圖8 f7取30維時的平均進化曲線

由圖2可以看出，對2維的f1函數，BA大概在20次迭代后陷入局部極值，而VCBA大概在迭代110次后接近全局最優值；由圖3可以看出，對2維的f2函數，BA大概在50次迭代后陷入局部極值，而VCBA大概在60次迭代后接近全局最優值；由圖4可以看出，對30維的f3函數，BA大概在迭代50次后陷入局部極值，而VCBA大概在迭代250次后接近全局最優值；由圖5可以看出，對30維的f4函數，BA大概在20次迭代后陷入局部極值，而VCBA大概是在迭代100次后接近全局最優值；由圖6可以看出，對30維的f5函數，BA大概在迭代250次后陷入局部極值，而VCBA大概是在迭代5次后接近全局最優值；由圖7可知，對30維的f6函數，BA大概在300次迭代后陷入局部極值，而VCBA大概是在150次迭代后接近全局最優值；由圖8可知，對30維的f7函數，BA大概在400次迭代后陷入局部極值，而VCBA大概是在450次迭代后接近全局最優值。

BA與VCBA對目標函數f1-f7獨立求解30次，所得各方面數據對比如表1所示。

表1 在固定迭代次數下的數據對比

續表1

由表1可知，在獨立求解30次的情況下，對目標函數f1-f7，BA算法都得不到相應函數的理論最優值或達到較高的精度。對2維的目標函數f1，VCBA在獨立求解30次后，所得30個目標函數值的平均值、最好值、最差值的精度分別能達到1e-6、1e-10、1e-5，且所得均方差的精度能達到1e-6，比BA得到的結果更穩定，VCBA的運行時間不到BA的2倍；對2維的目標函數f2，以及30維的目標函數f3、f4、f5、f7，VCBA獨立求解30次后，所得30個目標函數值的平均值、最好值、最差值都能達到它們的理論最優值0，且所得均方差為0，比BA得到的結果穩定，VCBA的運行時間不到BA的4倍；對30維的目標函數f6，VCBA獨立求解30次后，所得30個目標函數值的平均值、最好值、最差值的精度都能達到1e-16，且所得均方差為0，比BA算法得到的結果要穩定，VCBA的運行時間不到BA的3倍。

由上述分析可知，在固定迭代次數為500的情況下，算法VCBA的運行時間雖然比BA耗費的時間要更長，但VCBA所得目標函數值的精度高于BA，且求解更加穩定。

3.2 給定精度下所需的迭代次數

在給定目標函數值的精度為1e-6的情況下，BA和VCBA獨立求解目標函數f1-f730次所需的迭代次數如表2所示，其中成功率表示達到給定目標函數值精度的次數除以獨立求解次數30，算法若迭代500次仍沒有達到給定的目標函數值精度，則終止迭代，此時認為算法求解問題失敗。

表2 算法達到目標函數值精度所需的迭代次數

續表2

由表2可知，在指定收斂精度下，對目標函數f1-f7，BA不能在500次迭代后達到所給定精度，即BA對7個目標函數的成功率為0。對2維目標函數f1，VCBA算法的成功率為93.333%，且最小迭代次數不到30次；對2維目標函數f2以及30維的目標函數f3-f7，VCBA的成功率為100%，且最小迭代次數不到100次，其中對目標函數f5的求解，平均迭代次數不到5次。

由上述分析可知，在給定目標函數值精度的情況下，不管目標函數是低維還是高維，VCBA的求解成功率相較于BA都有明顯優勢。

3.3 其他優化算法的尋優結果對比

其他文獻中大多用目標函數f3-f6對算法性能進行對比分析，本文同樣使用目標函數f3-f6對VCBA與三種優化算法進行對比。三種算法分別為基本粒子群算法PSO，基于頻率簡化的自適應蝙蝠算法FSABA，基于自適應步長的改進蝙蝠算法SABA。實驗中，參數設置如下：種群數M=40，最大迭代次數maxgen=500次，目標函數維數n=30，其余參數設置同3.1節，對每個目標函數，各算法均獨立求解50次，所得目標函數值的結果如表3所示，除VCBA外，另三種算法的結果均來自文獻[17]。

表3 固定迭代次數下VCBA與 三種優化算法所得函數值

續表3

由表3可知，對目標函數f3-f5，三種優化算法在50次獨立求解中均達不到對應目標函數的理論最優值0，而VCBA在50次獨立求解中，其得到的最好值、最差值以及平均值都能達到對應目標函數的理論最優值0；對目標函數f6，PSO以及FSABA在50次獨立求解中，得到的最好值、最差值以及平均值的精度都在1e+1以上，SABA得到的最好值、最差值以及平均值的精度都為1e-10，而VCBA得到的最好值、最差值以及平均值的精度都為1e-16。

由上述分析可知，VCBA在目標函數尋優精度和穩定性方面相比于PSO、FSABA及SABA算法有較大優勢。

3.4 分析參數對算法的影響

在蝙蝠算法的迭代機制中，響度A的初始值A0和脈沖發射頻率r的初始值r0的取值與算法效果的好壞息息相關。所以本文將驗證不同的(A0,r0)取值對VCBA的影響。具體方法如下：在固定迭代次數的情況下，分析五組不同的(A0,r0)對VCBA的影響。這里我們選取4個多峰函數f3、f4、f6、f7作為目標函數，(A0,r0)的五組不同取值為：(0.5,0.01)、(0.9,0.5)、(0.95,0.9)、(1，rand)、(0.25,0.75)，設置最大迭代次數maxgen=500，目標函數維數n=30，其余參數設置同數值實驗3.1，對每個目標函數，用VCBA獨立求解30次，所得函數值如表4所示。

表4 參數(A0,r0)不同取值時所得目標函數值

續表4

由表4可知，對目標函數f3，當(A0,r0)取(0.5,0.01)時，VCBA在30次獨立求解中均達不到對應目標函數的理論最優值，當(A0,r0)取(0.9,0.5)、(1，rand)、(0.25,0.75)時，VCBA有時能達到目標函數的理論最優值0，當(A0,r0)取(0.95,0.9)時，VCBA在30次獨立求解中得到的平均值、最好值、最差值都達到目標函數的理論最優值0；對目標函數f4、f7，當(A0,r0)取(0.5,0.01)、(0.9,0.5)時，VCBA在30次獨立求解中均達不到對應目標函數的理論最優值0，當(A0,r0)取(1，rand)、(0.25,0.75)時,VCBA有時能達到目標函數的理論最優值0，當(A0,r0)取(0.95,0.9)時，VCBA在30次獨立求解中得到的平均值、最好值、最差值都能達到目標函數的理論最優值0；對目標函數f6，當(A0,r0)取(0.5,0.01)時，VCBA在30次獨立求解中均達不到對應目標函數的理論最優值0，當(A0,r0)取(0.9,0.5)、(1，rand)、(0.25,0.75)時，VCBA有時能達到1e-16的精度，當(A0,r0)取(0.95,0.9)時，VCBA在30次獨立求解中得到的平均值、最好值、最差值的精度都能達到1e-16。

由上述分析可知，當(A0,r0)取(0.95,0.9)時，VCBA對于選取的4個多峰目標函數有較好的尋優效果。

4 結 語

本文在基本BA的基礎上提出了一種基于速度越界處理與最速下降法的改進蝙蝠算法(VCBA)。VCBA的特點在于速度的越界處理能夠有效地控制蝙蝠位置擾動的范圍。在蝙蝠進行局部搜索時，對當前不好的蝙蝠位置用最速下降法進行確定性的鄰域搜索，降低隨機性；對BA判斷局部搜索階段產生的蝙蝠位置是否滿足要求的條件進行改進，保留了最速下降法更新的蝙蝠位置。數值實驗結果表明，相比于基本BA、兩種改進的BA和PSO，VCBA在收斂精度和穩定性方面都有很大的優越性。如何將BA與其他優化算法進行有機融合是我們進一步研究的主要工作。