高 超 梁昔明* 龍 文

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

0 引 言

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

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

1 蝙蝠算法

對無約束連續(xù)優(yōu)化問題：

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 改進蝙蝠算法設(shè)計

2.1 速度的越界處理

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

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

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

2.2 最速下降法

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

p0=-g(X0)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

2.3 改進算法步驟

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

第1步執(zhí)行BA的第1步。

第2步執(zhí)行BA的第2步。

(15)

(16)

第5步執(zhí)行BA的第6步。

第6步執(zhí)行BA的第7步。

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

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

3 數(shù)值實驗

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

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

3.1 固定迭代次數(shù)的數(shù)據(jù)對比

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

圖2 f1的平均進化曲線

圖3 f2的平均進化曲線

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

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

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

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

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

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

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

表1 在固定迭代次數(shù)下的數(shù)據(jù)對比

續(xù)表1

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

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

3.2 給定精度下所需的迭代次數(shù)

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

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

續(xù)表2

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

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

3.3 其他優(yōu)化算法的尋優(yōu)結(jié)果對比

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

表3 固定迭代次數(shù)下VCBA與 三種優(yōu)化算法所得函數(shù)值

續(xù)表3

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

由上述分析可知，VCBA在目標函數(shù)尋優(yōu)精度和穩(wěn)定性方面相比于PSO、FSABA及SABA算法有較大優(yōu)勢。

3.4 分析參數(shù)對算法的影響

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

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

續(xù)表4

由表4可知，對目標函數(shù)f3，當(A0,r0)取(0.5,0.01)時，VCBA在30次獨立求解中均達不到對應(yīng)目標函數(shù)的理論最優(yōu)值，當(A0,r0)取(0.9,0.5)、(1，rand)、(0.25,0.75)時，VCBA有時能達到目標函數(shù)的理論最優(yōu)值0，當(A0,r0)取(0.95,0.9)時，VCBA在30次獨立求解中得到的平均值、最好值、最差值都達到目標函數(shù)的理論最優(yōu)值0；對目標函數(shù)f4、f7，當(A0,r0)取(0.5,0.01)、(0.9,0.5)時，VCBA在30次獨立求解中均達不到對應(yīng)目標函數(shù)的理論最優(yōu)值0，當(A0,r0)取(1，rand)、(0.25,0.75)時,VCBA有時能達到目標函數(shù)的理論最優(yōu)值0，當(A0,r0)取(0.95,0.9)時，VCBA在30次獨立求解中得到的平均值、最好值、最差值都能達到目標函數(shù)的理論最優(yōu)值0；對目標函數(shù)f6，當(A0,r0)取(0.5,0.01)時，VCBA在30次獨立求解中均達不到對應(yīng)目標函數(shù)的理論最優(yōu)值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個多峰目標函數(shù)有較好的尋優(yōu)效果。

4 結(jié) 語

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