陳偉利,陳國(guó)華

　　(湖南人文科技學(xué)院 數(shù)學(xué)與計(jì)量經(jīng)濟(jì)系,湖南 婁底 417000)

      摘要：針對(duì)基本蝙蝠算法存在的易陷入局部最優(yōu)、后期收斂速度慢等問(wèn)題，提出動(dòng)態(tài)雙子群擬梯度蝙蝠算法。該算法利用蝙蝠脈沖發(fā)射頻率將蝙蝠種群動(dòng)態(tài)地劃分為自由搜索種群和局部搜索種群兩個(gè)子群,在局部搜索子群中利用擬梯度方向指導(dǎo)蝙蝠搜索。為了驗(yàn)證算法的有效性，通過(guò)對(duì)4個(gè)基準(zhǔn)函數(shù)的實(shí)驗(yàn)測(cè)試，實(shí)驗(yàn)結(jié)果表明，該算法相對(duì)于基本蝙蝠算法具有較好的全局搜索能力和優(yōu)化精度。

　　關(guān)鍵詞：蝙蝠算法；擬梯度；基準(zhǔn)函數(shù)；最優(yōu)值

0引言

　　蝙蝠算法(Bat Algorithm, BA)是一種新穎的群智能優(yōu)化算法，是由劍橋大學(xué)學(xué)者 Yang Xinshe在2010年通過(guò)模擬蝙蝠的捕食行為而提出的一種優(yōu)化算法［1］。該算法將優(yōu)化問(wèn)題的解看作是搜索空間中的微蝙蝠，搜索最優(yōu)解的過(guò)程看成是微蝙蝠尋找食物的過(guò)程。在一定程度上粒子群優(yōu)化(PSO)算法和和聲搜索(HS)算法是BA的一種特殊情況，而B(niǎo)A也被證明比粒子群優(yōu)化算法和遺傳算法具有更高的搜索性能［2］。自蝙蝠算法提出以來(lái)，已成功地運(yùn)用于多種優(yōu)化問(wèn)題的解決，如多目標(biāo)優(yōu)化［3］、工程優(yōu)化［4］、聚類方法［5］、調(diào)度問(wèn)題［6］、經(jīng)濟(jì)負(fù)荷分配問(wèn)題［7］等。參考文獻(xiàn)［8］總結(jié)了蝙蝠算法取得的進(jìn)展，并提出了蝙蝠算法進(jìn)一步研究的主要方向。雖然蝙蝠算法在許多優(yōu)化問(wèn)題中取得了很好的效果，但其本身也存在后期收斂速度不快和易陷入局部最優(yōu)等缺點(diǎn)。針對(duì)蝙蝠算法的這些缺陷，許多學(xué)者提出了各自的改進(jìn)方法，如模糊蝙蝠算法［9］、混沌蝙蝠算法［10-11］、Lévy飛行蝙蝠算法［12-13］。在對(duì)蝙蝠算法的改進(jìn)中，多數(shù)學(xué)者集中在蝙蝠初始化和飛行方式的改進(jìn)上［10-15］，而對(duì)于改進(jìn)蝙蝠的局部搜索策略的算法相對(duì)較少，基于此，本文提出動(dòng)態(tài)雙子群擬梯度蝙蝠算法(PGBA)。通過(guò)仿真實(shí)驗(yàn)表明，與基本的BA相比，PGBA具有更好的尋優(yōu)能力和搜索精度。

1動(dòng)態(tài)雙子群擬梯度蝙蝠算法

　　1.1設(shè)計(jì)思想

　　蝙蝠算法能夠成功地解決很多問(wèn)題，但基本蝙蝠算法存在求解精度不高和收斂速度過(guò)慢的問(wèn)題。筆者通過(guò)記錄蝙蝠群體在飛行時(shí)的各種參數(shù)，并對(duì)參數(shù)進(jìn)行了簡(jiǎn)單統(tǒng)計(jì)分析發(fā)現(xiàn)，控制蝙蝠群體自由飛行和局部搜索分配的脈沖發(fā)射頻率更新速度較快，而響度的變化卻并不大，這直接導(dǎo)致蝙蝠在局部尋優(yōu)過(guò)程中由于飛行速度過(guò)快而不能很好地發(fā)現(xiàn)更優(yōu)解。因此，為了提高蝙蝠的局部搜索能力，必須改變蝙蝠的響度更新方式。此外蝙蝠在局部搜索時(shí)是在最優(yōu)解附近隨機(jī)生成一個(gè)解，既然局部搜索的目的是發(fā)現(xiàn)更好的解，那為什么不朝著最有利的方向搜索？受梯度在傳統(tǒng)算法中的高效性的啟發(fā)，本文引入擬梯度定義，用于指示函數(shù)的大致上升或下降的方向，指導(dǎo)蝙蝠的局部搜索。

　　定義給定某常數(shù)h，p維函數(shù)f(X)在點(diǎn)(x1,x2,…,xp)的相對(duì)于h的擬梯度向量定義為：

　　V=(v1,…,vp)

　　其中，vi=f(x1,x2,…,xi+h,…,xp)－f(x1,x2,…,xi,…,xp)。

　　1.2動(dòng)態(tài)雙子群擬梯度蝙蝠算法步驟

　　綜上所述，本文提出擬梯度蝙蝠算法的步驟如下：

　　（1）初始化蝙蝠種群參數(shù)(蝙蝠的位置、飛行頻率、飛行速度、脈沖發(fā)射頻率、響度)。

　?。?）計(jì)算每只蝙蝠的適應(yīng)度值，并得到最優(yōu)適應(yīng)度對(duì)應(yīng)的蝙蝠位置（bestx），記錄最優(yōu)適應(yīng)度值。

　?。?）生成隨機(jī)數(shù)，將蝙蝠種群分為脈沖發(fā)射頻率小于隨機(jī)數(shù)（記為第一類）和大于隨機(jī)數(shù)（記為第二類）兩類。

　?。?）自由飛行。對(duì)步驟（3）分出的第一類，按照基本蝙蝠算法進(jìn)行自由飛行。

　　（5）擬梯度局部搜索。對(duì)步驟（3）分出的第二類，首先令h=loudness,計(jì)算其擬梯度v,在最優(yōu)位置附近按擬梯度方向生成一個(gè)局部解，xnew=xbest－v 。

　　（6）如果局部搜索不能找到更優(yōu)解，視為響度太大搜索失敗，將該蝙蝠的響度更新為原先的α倍，即Anew=α×Aold。如果找到更優(yōu)解，則更新蝙蝠位置，保持響度不變。

　?。?）對(duì)自由飛行和局部搜索之后的蝙蝠種群，如果找到更優(yōu)解，則更新其脈沖發(fā)射頻率。更新方法為：rt+1i=r0i(1+e－γ×t)。

　?。?）對(duì)當(dāng)前蝙蝠重新排序，找到最優(yōu)蝙蝠所在位置，記錄最優(yōu)值。

　　（9）滿足結(jié)束條件（達(dá)到精度或最大迭代次數(shù)），轉(zhuǎn)至步驟（10），否則轉(zhuǎn)至步驟（3），進(jìn)行下一輪迭代。

　?。?0）輸出相關(guān)結(jié)果。

2仿真實(shí)驗(yàn)

　　為了驗(yàn)證本文提出的算法的有效性，本文從相關(guān)文獻(xiàn)中選取4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)(包括單峰和多峰函數(shù))進(jìn)行仿真實(shí)驗(yàn)。

　　這是一個(gè)多峰函數(shù)，在x*=(0,0,…,0)取得理論最小值0。

　　利用擬梯度蝙蝠算法對(duì)4個(gè)標(biāo)準(zhǔn)的測(cè)試函數(shù)進(jìn)行求解，并與基本的蝙蝠算法進(jìn)行比較。算法的參數(shù)設(shè)置如下：在標(biāo)準(zhǔn)蝙蝠算法中，頻率范圍為［0,1］,α=γ=0.9,蝙蝠數(shù)量為40，r0=0.1,響度初始化為隨機(jī)數(shù)，迭代次數(shù)為200次。擬梯度蝙蝠算法的參數(shù)設(shè)置與標(biāo)準(zhǔn)算法類似，僅改變脈沖發(fā)射頻率和響度調(diào)整幅度，即rate0=0.5,α=0.5。在上述參數(shù)設(shè)置下，每種算法運(yùn)行30次，將兩種算法的最優(yōu)結(jié)果、最差結(jié)果、平均結(jié)果和標(biāo)準(zhǔn)差統(tǒng)計(jì)如表1所示。 

　　從表1可以看出，與基本蝙蝠算法(BA)相比，擬梯度蝙蝠算法(PGBA)明顯取得更好的尋優(yōu)結(jié)果。從最優(yōu)結(jié)果的角度看，BA在f1、f2、f4上都是成功的，但在f3上失敗。與參考文獻(xiàn)［15］中結(jié)果有差異，這里主要的原因在于種群的數(shù)量和迭代的次數(shù)設(shè)置不同； PGBA在4個(gè)函數(shù)上都取得成功，且其精度遠(yuǎn)遠(yuǎn)高于BA，尤其在函數(shù)f4上，其精度達(dá)到了10－16 。從平均結(jié)果看，PGBA在f3上表現(xiàn)欠佳，但仍遠(yuǎn)好于BA，而在其他函數(shù)上則取得了非常理想的結(jié)果。為了更清晰地對(duì)比BA和PGBA，圖1~圖4給出了兩種算法在4個(gè)函數(shù)上的收斂曲線對(duì)比圖。

　　通過(guò)兩種算法的收斂曲線對(duì)比圖，可以發(fā)現(xiàn)PGBA相對(duì)BA具有更好的尋優(yōu)能力，在函數(shù)f1和f2上，PGBA相對(duì)于BA不僅達(dá)到了更高的精度，而且在收斂速度上明顯要更快。而在f3和f4上，PGBA在開(kāi)始迭代時(shí)其收斂速度并沒(méi)有優(yōu)勢(shì)，但隨著迭代次數(shù)的增加，PGBA表現(xiàn)出了較強(qiáng)的局部挖掘能力。

3結(jié)論

　　針對(duì)基本蝙蝠算法收斂速度較慢和易陷入局部最優(yōu)的問(wèn)題提出了動(dòng)態(tài)雙子群擬梯度蝙蝠算法。該算法動(dòng)態(tài)地將基本蝙蝠種群劃分為自由搜索和局部搜索兩個(gè)不同的種群，在局部搜索種群中利用擬梯度方向指導(dǎo)蝙蝠的搜索。這一劃分既保證了算法的全局搜索能力，又提高了算法的局部搜索能力。實(shí)驗(yàn)表明，該算法具有較好的全局搜索能力和較高的搜索精度。

參考文獻(xiàn)

　?。?］ Yang Xinshe. A new metaheuristic batinspired algorithm［M］.Nature inspired cooperative strategies for optimization (NICSO 2010). Springer Berlin Heidelberg, 2010: 6574.

　?。?］ Yang Xinshe. Nature Inspired Metaheuristic Algorithms (2nd Edition)［M］. Frome, UK: Luniver Press, 2010: 97104.

　?。?］ Yang Xinshe. Bat algorithm for multiobjective optimization［J］.International Journal of BioInspired Computation, 2011, 3(5):267274.

　　［4］ Yang Xinshe, GANDOMI A H. Bat algorithm: a novel approach for global engineering optimization［J］. Engineering Computation, 2012, 29(5):267289.

　　［5］ KOMARASAMY G, WAHI A. An optimized kmeans clustering technique using bat algorithm［J］. European Journal of Scientific Research, 2012, 84(2):263273.

　　［6］ 盛曉華,葉春明. 蝙蝠算法在PFSP調(diào)度問(wèn)題中的應(yīng)用研究［J］. 工業(yè)工程,2013,16（1）:119124.

　?。?］ GHERBI Y A, BOUZEBOUDJA H, LAKDJA F. Economic dispatch problem using bat algorithm［J］. Leonardo Journal of Sciences, 2014, 13(24): 7584.

　　［8］ Yang Xinshe, He Xingshi. Bat algorithm: literature review and applications［J］. International Journal of BioInspired Computation, 2013, 5(3): 141149.

　　［9］ KHAN K, NIKOV A, SAHAI A. A fuzzy bat clustering method for ergonomic screening of office workplaces［M］. Third International Conference on Software, Seruices and Semantic Techdogies S3T 2011. Springer Berlin Heidelberg, 2011，101:5966.

　?。?0］ LIN J H, CHOU C W, YANG C H, et al. A chaotic Levy flight bat algorithm for parameter estimation in nonlinear dynamic biological systems［J］. Computer and Information Technology, 2012, 2(2): 5663.

　?。?1］ 劉長(zhǎng)平, 葉春明. 具有混沌搜索策略的蝙蝠優(yōu)化算法及性能仿真［J］. 系統(tǒng)仿真學(xué)報(bào), 2013, 25(6):11831188.

　　［12］ 劉長(zhǎng)平,葉春明. 具有Lévy飛行特征的蝙蝠算法［J］. 智能系統(tǒng)學(xué)報(bào),2013,8（3）:240246.