梁毛毛,肖 文,王李進,鐘一文

(1.福建農(nóng)林大學計算機與信息學院,福建 福州 350002) (2.福建農(nóng)林大學智慧農(nóng)林福建省高校重點實驗室,福建 福州 350002)

元啟發(fā)式算法是一種基于經(jīng)驗的非確定性算法,在處理結(jié)構(gòu)不明確、缺少條件或大規(guī)模的優(yōu)化問題上具有優(yōu)勢,在環(huán)形電感建模[1]、優(yōu)化配電網(wǎng)網(wǎng)架[2]和儲能配置[3]、求取自由曲面最大主曲率[4]等方面有廣泛應(yīng)用. 布谷鳥搜索(cuckoo search,CS)算法[5-6]是其中的一種自然啟發(fā)式算法,起源于布谷鳥尋巢產(chǎn)卵并讓其他鳥為其孵卵的行為. CS算法利用Lévy Flights隨機走動和Biased隨機走動迭代地發(fā)現(xiàn)新的個體.

為了得到性能更好的CS算法,部分學者結(jié)合了其他優(yōu)化方法. Wang等[7]將和聲搜索與CS算法混合,提出HS/CS算法;Rosli等[8]結(jié)合正余弦算法,提出一種混合布谷鳥搜索算法(HMSCACSA);Shehab等[9-10]不僅提出與爬山算法結(jié)合的穩(wěn)定的布谷鳥搜索算法(CSAHS),且引入蝙蝠算法來求解全局數(shù)值優(yōu)化;還有研究[11-12]將合作協(xié)同進化框架、單位置繼承等技術(shù)引入CS算法. 部分學者致力于改進Lévy Flights和Biased隨機走動的過程. Wang等[13]提出采用均勻分布的隨機數(shù)動態(tài)設(shè)置步長因子的布谷鳥搜索算法(VCS);王李進等[14-15]分別采用逐維搜索和正交交叉操作加強了Biased隨機走動搜索效率. 為了改善CS算法在求解復(fù)雜問題時的性能退化,Salgotra等[16]提出了自適應(yīng)的CS算法;Wei等[17]提出一種基于柯西分布和萊默平均值更新Biased隨機走動中的變異算子的方法,并命名為CSAPC;Wang等[18]利用指數(shù)曲線模擬步長因子和發(fā)現(xiàn)概率的變化趨勢,提出基于指數(shù)函數(shù)的CS算法;Chen等[19]在Lévy Flights隨機走動中采用基于最優(yōu)解逐維更新個體的策略,提出逐維增強的CS算法.

Lévy Flights隨機走動中的步長比例因子是CS算法中的重要控制參數(shù),能夠影響算法的搜索能力并調(diào)整算法的收斂速度. 在標準的CS算法中,步長比例因子為固定的常數(shù),算法存在收斂速度慢、求精能力不足等缺陷,因而有很多學者圍繞該點展開了改進. 林要華等[20]引入貝塔分布動態(tài)設(shè)置步長因子;Walton等[21]提出利用迭代次數(shù)更新步長因子;Valian等[22]使用迭代次數(shù)構(gòu)建指數(shù)函數(shù)更新步長因子;Layeb等[23]將量子計算的概念應(yīng)用在步長因子上. 然而,以上優(yōu)化步長比例因子的研究均未利用到種群中個體本身的條件. 本文采用一種基于個體適應(yīng)值的步長因子更新策略,提出帶全局-局部最優(yōu)步長比例因子的布谷鳥搜索算法(cuckoo search algorithm with global-local best scaling factor,GLbestCS).

從仿真實驗的結(jié)果可以看出,GLbestCS可行且能有效改善CS算法的求精能力和收斂速度,其性能總體上比采用固定常數(shù)、均勻分布的隨機數(shù)以及貝塔分布的隨機數(shù)步長因子的CS算法更優(yōu).

1 布谷鳥算法

2009年,Yang等[5-6]提出CS算法. 初始化種群后,CS算法迭代執(zhí)行Lévy Flights隨機走動和Biased隨機走動來搜索新個體. 每次隨機走動結(jié)束,CS算法都會以適應(yīng)值為依據(jù)貪婪地選擇較優(yōu)個體來更新種群.

Lévy Flights是一種從Lévy分布中獲取步長的隨機走動,主要作用為全局搜索. 在第G代(G>0),Lévy Flights隨機走動可用以下公式表示:

(1)

式中,α0為比例步長因子(通常α0=0.01);Xbest表示目前發(fā)現(xiàn)的最優(yōu)個體;β為常數(shù),在CS算法中通常設(shè)置為1.5;μ和ν是隨機數(shù),服從均值為0、標準差為1的正態(tài)分布;Γ是一個伽馬(Gama)函數(shù),

(2)

Biased隨機走動是一個局部隨機游走過程,主要作用為局部開發(fā),以當前個體為基礎(chǔ),根據(jù)在搜索池中隨機選擇的兩個個體產(chǎn)生新個體. Biased隨機走動可用下式表示:

(3)

式中,?為乘法算子;m和n為隨機下標;pa為發(fā)現(xiàn)概率,其值為小數(shù).

2 帶全局-局部最優(yōu)步長比例因子的布谷鳥搜索(GLbestCS)算法

2.1 全局-局部最優(yōu)步長比例因子

步長比例因子α0是CS算法中的重要參數(shù)之一.當其值較大時,全局搜索能力較強,收斂速度較快,但算法的求精能力差;當其值較小時,局部搜索能力增強,收斂速度變慢,易陷入局部最優(yōu)的情況.因此,如何設(shè)定步長比例因子決定了能否實現(xiàn)全局與局部搜索之間的有效平衡.

參考文獻[24],本文引入種群中個體的信息更新CS算法中的步長比例因子,增加一個全局最優(yōu)適應(yīng)值和個體最優(yōu)適應(yīng)值的比值來調(diào)節(jié)算法的收斂度速度和求精能力之間的平衡,最終得到步長比例因子公式為:

(4)

式中,α0i是第i代的步長比例因子;fgbest代表全局最優(yōu)適應(yīng)值;fpi代表該個體的最優(yōu)適應(yīng)值;k為常數(shù).當個體靠近最優(yōu)情況,fgbest/fpi減小,算法的尋優(yōu)精度增強;當個體遠離最優(yōu)情況,fgbest/fpi增大,算法的全局搜索速度加快.文獻[10]中采用均勻分布的隨機數(shù)動態(tài)設(shè)置步長因子,服從[0,1]均勻分布的均值為0.5.故在后續(xù)實驗中令k=0.5,即:

(5)

2.2 GLbestCS算法

與CS算法相比,GLbestCS算法未引入新的操作,僅用適應(yīng)值更新步長比例因子α0i,因此認為GLbestCS與CS時間復(fù)雜度相近. 同時,GLbestCS算法的性能顯著更優(yōu),即更有效率. 因此,本文認為,GLbestCS 算法未增加算法整體的時間復(fù)雜度.

3 仿真結(jié)果

本文利用測試函數(shù)來評估GLbestCS算法的性能. 選擇Noman等[25]提出的20個基準函數(shù),在每個測試函數(shù)上獨立運行25次. 為了使誤差最小化,限制最大適應(yīng)值評估次數(shù)(MaxFES)為10 000×D(D為函數(shù)維度);發(fā)現(xiàn)概率pa的值取0.25;當D=10時,種群規(guī)模NP為30;當D取其他值時,令NP=D.

3.1 性能分析

表1所列為當D=30時,CS和GLbestCS算法在所有測試函數(shù)上的表現(xiàn). “AVGEr±SDEr”代表平均適應(yīng)值誤差和標準方差. 最后一行是基于α=0.05的Wilcoxon符號秩檢驗的統(tǒng)計結(jié)果,“+”代表GLbestCS算法的表現(xiàn)顯著優(yōu)于CS算法,“-”相反,“=”為兩者不存在明顯差異.

由表1可以看出,在函數(shù)Fsph、Fros、Fack、Fgrw、Fras、Fsch、Fsal、Fwht、Fpn1、Fpn2、F1、F2、F4、F5、F6、F9、F10上,GLbestCS算法的表現(xiàn)優(yōu)于CS算法;在函數(shù)F3、F7上則相反;僅在函數(shù)F8上兩者的表現(xiàn)近似. 同時,GLbestCS 算法在14個函數(shù)上表現(xiàn)更優(yōu),在5個函數(shù)上與CS算法近似,僅在1個函數(shù)上略差. 且GLbestCS算法在函數(shù)Fgrw上能夠取得全局最優(yōu)解. 圖1展示了CS和GLbestCS算法在測試函數(shù)中的一些有代表性的收斂過程. 可以看出,GLbestCS算法在前期有更快的收斂速度、在后期有更強的求精能力.

因此,可以認為,用全局-局部最優(yōu)適應(yīng)值動態(tài)設(shè)置步長比例因子是可行的,且能夠改善CS算法的性能.

圖1 CS和GLbestCS的收斂曲線Fig.1 The convergence curves of CS and GLbestCS

3.2 維數(shù)變化對算法性能影響分析

表2比較了CS和GLbestCS在不同維度的運行結(jié)果,可以看出GLbestCS算法的性能基本上穩(wěn)定地優(yōu)于CS算法.

表2 CS和GLbestCS求解測試函數(shù)的平均適應(yīng)值誤差(D=10 and D=50)Table 2 Average fitness error obtained by CS and GLbestCS for benchmark functions(D=10 and D=50)

3.3 與其他改進的CS算法比較分析

表3所列為VCS、BetaCS和GLbestCS算法在測試函數(shù)上的表現(xiàn). 表4的方法是Wilcoxon配對秩和檢驗[26],其中“R+”表示GLbestCS算法獲得的平均適應(yīng)值誤差排序總和比另一算法的更好,“R-”相反. 表5給出了Friedman檢驗[27]結(jié)果. 綜合而言,GLbestCS算法的性能優(yōu)于VCS和BetaCS算法.

表3 VCS、BetaCS和GLbestCS求解測試函數(shù)的平均適應(yīng)值誤差(D=30)Table 3 Average fitness error obtained by VCS,BetaCS and GLbestCS for benchmark functions(D=30)

表4 VCS、BetaCS和GLbestCS的Wilcoxon配對秩和檢驗(D=30)Table 4 Wilcoxon matched-pairs signed-rank test for VCS,BetaCS and GLbestCS(D=30)

表5 3個算法求解測試函數(shù)的平均Friedman檢驗秩(D=30)Table 5 Average ranking of three algorithms by the Friedman test for 20 functions(D=30)

3.4 對k值的討論

表6給出當k取值不同時GLbestCS算法在測試函數(shù)上取得的結(jié)果.

表6 GLbestCS求解測試函數(shù)的平均適應(yīng)值誤差(k=0.5,k=1 and k=1.1)Table 6 Average fitness error obtained by GLbestCS for benchmark functions(k=0.5,k=1 and k=1.1)

續(xù)表6Table 6 continued

可以看出,當k=0.5和k=1.1時算法的性能近似,均優(yōu)于k=1.0時.在表7中,部分情況下k=1.1的算法性能略優(yōu).由于個體靠近全局最優(yōu)時,方程(5)后半部分的比值變大,α0i的值逐漸變小.當k=0.5時,若當前個體達到全局最優(yōu),即fgbest/fpi=1時,α0i取得最小值-0.5,Lévy Flights隨機游走的方向改變,算法會繼續(xù)反向搜索. 故本文最終選擇了較優(yōu)的k=0.5.

表7 GLbestCS求解測試函數(shù)的平均Friedman檢驗秩(D=30)Table 7 Average ranking of GLbestCS by the Friedman test for 20 functions(D=30)

3.5 在其他算法上應(yīng)用的討論

將本文所提算法應(yīng)用于文獻[28]提出的CCS算法,命名為GLbestCCS算法. 表8和表9列出了CCS和GLbestCCS算法在D=30時的運行結(jié)果. 可以看出,GLbestCCS算法的性能顯著優(yōu)于CCS算法.

表8 CCS和GLbestCCS求解測試函數(shù)的平均適應(yīng)值誤差(D=30)Table 8 Average fitness error obtained by CCS and GLbestCCS for benchmark functions(D=30)

表9 CCS和GLbestCCS的Wilcoxon配對秩和檢驗(D=30)Table 9 Wilcoxon matched-pairs signed-rank test for CCS and GLbestCCS(D=30)

4 結(jié)論

本文采用最優(yōu)適應(yīng)值動態(tài)設(shè)置步長比例因子,并提出一種帶全局-局部最優(yōu)步長比例因子的布谷鳥搜索算法GLbestCS. 實驗結(jié)果證明,GLbestCS算法可有效地改善CS算法的性能. 當問題規(guī)模發(fā)生變化,GLbestCS算法仍然穩(wěn)定地優(yōu)于CS算法. 將該策略應(yīng)用于其他改進的CS算法,結(jié)果表明這種優(yōu)化仍然有效.