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

梁毛毛,肖 文,王李進(jìn),鐘一文

(1.福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院,福建 福州 350002) (2.福建農(nóng)林大學(xué)智慧農(nóng)林福建省高校重點(diǎn)實(shí)驗(yàn)室,福建 福州 350002)

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

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

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

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

1 布谷鳥算法

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

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

(1)

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

(2)

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

(3)

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

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

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

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

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

(4)

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

(5)

2.2 GLbestCS算法

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

3 仿真結(jié)果

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

3.1 性能分析

表1所列為當(dāng)D=30時(shí),CS和GLbestCS算法在所有測試函數(shù)上的表現(xiàn). “AVGEr±SDEr”代表平均適應(yīng)值誤差和標(biāo)準(zhǔn)方差. 最后一行是基于α=0.05的Wilcoxon符號(hào)秩檢驗(yàn)的統(tǒng)計(jì)結(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)近似. 同時(shí),GLbestCS 算法在14個(gè)函數(shù)上表現(xiàn)更優(yōu),在5個(gè)函數(shù)上與CS算法近似,僅在1個(gè)函數(shù)上略差. 且GLbestCS算法在函數(shù)Fgrw上能夠取得全局最優(yōu)解. 圖1展示了CS和GLbestCS算法在測試函數(shù)中的一些有代表性的收斂過程. 可以看出,GLbestCS算法在前期有更快的收斂速度、在后期有更強(qiáng)的求精能力.

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

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

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

表2比較了CS和GLbestCS在不同維度的運(yùn)行結(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 與其他改進(jìn)的CS算法比較分析

表3所列為VCS、BetaCS和GLbestCS算法在測試函數(shù)上的表現(xiàn). 表4的方法是Wilcoxon配對秩和檢驗(yàn)[26],其中“R+”表示GLbestCS算法獲得的平均適應(yīng)值誤差排序總和比另一算法的更好,“R-”相反. 表5給出了Friedman檢驗(yàn)[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配對秩和檢驗(yàn)(D=30)Table 4 Wilcoxon matched-pairs signed-rank test for VCS,BetaCS and GLbestCS(D=30)

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

3.4 對k值的討論

表6給出當(dāng)k取值不同時(shí)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

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

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

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

將本文所提算法應(yīng)用于文獻(xiàn)[28]提出的CCS算法,命名為GLbestCCS算法. 表8和表9列出了CCS和GLbestCCS算法在D=30時(shí)的運(yùn)行結(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配對秩和檢驗(yàn)(D=30)Table 9 Wilcoxon matched-pairs signed-rank test for CCS and GLbestCCS(D=30)

4 結(jié)論

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