融合正弦余弦的蝙蝠算法

韓斐斐 劉升 王興凡

文章編號： 2095-2163（2018）03-0122-06中圖分類號： 文獻標志碼： A

摘要： 關鍵詞： （School of Management Shanghai University of Engineering Science， Shanghai 201620， China）

Abstract： Bat Algorithm （BA） is a novel random search optimization algorithm. In order to overcome the shortcomings of slow convergence speed and poor optimization accuracy of bat algorithm， bat algorithm （SCABA） based on sine cosine is proposed， In the later iteration， the sine cosine operation is introduced to update the current individual position of the bat， thereby enhancing the diversity of the population， avoiding the algorithm getting into the local optimum and enhancing the global optimization ability of the algorithm. The improved algorithm， MFBA and basic BA are tested by six standard test functions. The simulating results show that the improved algorithm is feasible and effective. Compared with the basic BA algorithm， the convergence precision and robustness have been greatly improved .

Key words：

基金項目：

作者簡介：

通信作者：

收稿日期： 引言

優化問題廣泛存在于科學研究和工程優化等領域，傳統的優化方法已經不能滿足解決復雜優化問題的需要。受自然界生物群體智能行為和自然界進化規律的啟發，國內外學者們提出了多種基于仿生學的群體智能優化算法，如蟻群算法（Ant Colony Algorithm，ACA）[1]來自于蟻群尋找食物的行為，螞蟻根據信息素的濃度選擇覓食路徑；粒子群算法（Particle Swarm Optimization， PSO）[2]的基本思想來源于鳥群的信息交流和覓食行為；入侵雜草優化（Invasive Weed Optimization，IWO）[3]算法模擬自然界中雜草的入侵繁殖、空間擴散和優勝劣汰法則；花授粉算法（Flower Pollination Algorithm ， FPA）[4]模擬異花授粉為全局尋優，自花授粉為局部尋優。群智能算法已成為了智能優化領域的研究熱點和重要研究方向，并廣泛應用于大數據處理[5]、組合優化[6]、文本聚類[7]等領域。

2010年，學者Yang提出了蝙蝠算法[8]，其模擬自然界中蝙蝠利用回聲定位機制尋找獵物的特性，是在特定理想化規則下簡化而來的一種全局優化算法。目前，BA作為一種新的群智能優化算法，已成功用于路徑規劃[9]、圖像壓縮[10]、生產調度[11]等問題中。蝙蝠算法模型簡單、算法參數少、通用性強，但也存在易陷入局部最優、收斂精度低、算法后期收斂速度慢等不足，針對這些不足，國內外眾多學者根據不同的改進策略對其進行改進，文獻[12]把差分進化算法中的變異、交叉、選擇機制應用于蝙蝠算法，使蝙蝠算法具有變異機制，增強了算法的尋優能力；文獻[13]把模擬退火算法和高斯擾動融入基本蝙蝠算法，使算法不僅具有較好的全局搜索能力，而且加快了算法的收斂速度；文獻[14]賦予蝙蝠個體以隨機的速度，同時利用速度糾正因子限制蝙蝠的移動步長，既提高了蝙蝠種群的多樣性，又使得算法具有自適應性。本文針對蝙蝠算法的不足，把正弦余弦算法中的正弦余弦操作應用于蝙蝠算法，從而避免種群個體陷入局部最優，增強算法全局尋優能力。對6個標準測試函數進行測試，仿真結果表明，改進后算法的收斂速度、尋優精度和魯棒性均有了明顯的提高。

1蝙蝠算法BA

蝙蝠一般在夜間活動，在黑暗中發出短促、頻率高的聲音脈沖，通過對接收到的聲波回聲進行分析來判別方向、避開阻礙物以及尋找食物的位置。隨著蝙蝠與搜索獵物的距離減小，為了捕食到獵物，脈沖的發射率不斷增加，發出聲音的響度不斷減小。蝙蝠通過發出和接收聲波回聲的時間差，來確定目標距離、目標方位及目標移動速度。將蝙蝠尋找食物過程理想化如下：

（1）所有的蝙蝠都利用回聲定位機制感知目標距離，且能夠區分食物與障礙物。

（2）蝙蝠在位置xi以速度vi隨意飛行，以固定頻率fi、可變化波長λ和響度A0搜索食物；同時根據目標距離來調整發射出的脈沖波長（或頻率），在靠近食物時調整發射脈沖的頻度γ，γ（0，1）。

（3）響度從最大值Amax變化到最小值Amin。

設蝙蝠在d維空間中搜索食物，在t-1時刻，蝙蝠i的位置和飛行速度分別為xt-1i和vt-1i，在t時刻，蝙蝠i的位置xti、速度vti更新公式如下：fi=fmin+fmax-fminβ（1）

vti=vt-1i+（xt-1i-x*）fi（2）

xti=xt-1i+vti（3）其中，fmin和fmax分別為蝙蝠發出聲波的最小和最大頻率，每只蝙蝠發射聲波的頻率初始值在范圍[fmin， fmax]內均勻隨機分布；β∈[0，1]是服從均勻分布的隨機變量；x*是蝙蝠種群中的全局最優解。

對于局部搜索，在[0，1]之間產生一個隨機數rand1，如果rand1>ri，則對當前最優解按式（4）進行隨機擾動，產生一個新解xnew，并對新解做越界處理。產生一個隨機數rand2，如果rand2>Ai且f（xnew）

At+1i=αAti（5）

rt+1i=r0i1-exp-γt（6）其中，ε∈[-1，1]是一個服從均勻分布的隨機數；At=是在t時刻所有蝙蝠的平均響度；r0i為初始速率；α和γ是常數；α（0，1），γ（0，+∞）。

2融合正弦余弦的蝙蝠算法SCABA

2.1正弦余弦算法

2016年，格里菲斯大學教授Mirjalili提出正弦余弦算法（Sine and Cosine Algorithm，SCA）[15]，其結構簡單、魯棒性好、容易實現，利用正弦函數和余弦函數的性質迭代以達到尋找最優解的目的。算法中幾個關鍵的參數提升了其尋優性能，有效地平衡了“局部開發”和“全局探索”。在SCA中，隨機生成一個含有N個個體的初始種群Pt={Xti}，其中Xti=xti1，xti2，…，xtij，…，xtid， j=1，2，…，d； i=1，2，…，N，N為種群大小；d為待優化函數所含決策變量的個數，即維數；t代表當前進化代數。

首先，計算種群中每個個體的適應度值，根據適應度值的大小對種群中個體進行排序，并記錄當前最優個體及其位置，在每一次迭代中，種群個體位置更新如下：

xt+1i=xti+r1*sinr2*r3*x*-xti，r4<0.5

xti+r1*cosr2*r3*x*-xti，r4>0.5（7）

xt+1i代表第t+1次循環下的第i個個體；xti代表第t次循環下第i個個體；x*是適應度值最優的個體；r1是控制搜索方向的參數；r2是控制搜索距離的參數；r3是一個隨機慣性權重；r4的大小決定下一代進行余弦操作或者正弦操作，具體計算如下：r1=a-a*〖SX（〗t〖〗maxt〖SX）〗； r2=rand（0，2π）；r3=rand（0，2）；r4=rand（0，1）[JY]（8）SCA偽代碼算法設計隨機生成初始種群計算每個蝙蝠個體的適應度值及最佳位置x*while（終止準則不滿足）for i=1 to nfor k=1 to d根據式（8）計算參數r1，r2，r3，r4的值if r4<0.5根據式（7）中正弦部分更新位置else根據式（7）中余弦部分更新位置end forend forend while[BT5]2.2融合正弦余弦的蝙蝠算法SCABA在本文提出的混合正弦余弦算法的蝙蝠算法中，算法迭代后期，經過進化的蝙蝠位置不是直接進入下一次迭代，而是對種群中個體的位置進行正弦、余弦操作，得到新的蝙蝠位置，再進入（t+1）次迭代。由于正弦余弦算法利用正弦函數和余弦函數值的變化來達到尋優的目的，且正弦（余弦）函數值的大小是在[-1，1]之間，因此將正弦余弦融合到BA中，可以有效提升BA的收斂速度。另外，SCA有幾個關鍵的參數，r1指引著個體搜索的方向，r2控制著個體尋優的移動距離，因此在SCABA中，蝙蝠個體的搜索距離和方向能夠被控制并朝向最優個體，這降低了個體尋優的盲目性，提高了個體尋優的效率。SCABA將正弦余弦算法和蝙蝠算法各自的優點充分融合，使算法不僅具有強大的全局尋優能力，同時也具有強大的局部搜索能力，其運行步驟描述如下：[WT5HZ][ST5HZ]Step 1[WT5BZ][ST5BZ]初始化SCABA的各個參數，在d維空間中隨機生成初始種群蝙蝠的位置xi，其中i=1，2，…，n，同時計算相應蝙蝠的適應度，隨機產生脈沖發射的速率R0和聲音響度A0，并把群體中的最優蝙蝠初始位置作為x*的初值；[WT5HZ][ST5HZ]Step 2[WT5BZ][ST5BZ]根據式（1）～（3）更新蝙蝠個體的速度和位置，產生新一代個體，并計算其適應度；[WT5HZ][ST5HZ]Step 3[WT5BZ][ST5BZ]如果隨機數rand1>ri，則從當前種群的最優解集中選擇一個解，使用式（4）通過施加擾動，產生新個體xnew來替代當前解；[WT5HZ][ST5HZ]Step 4[WT5BZ][ST5BZ]若隨機數rand2>Ai且f（xnew）

由表2可以看出，對于6個測試函數，無論是簡單的單峰函數，還是存在大量局部極值的非線性多峰函數，本文提出的融合正弦余弦的蝙蝠算法（SCABA）最優解、最差解、平均值及標準方差的精度均明顯高于基本蝙蝠算法（BA）和采用機動飛行的蝙蝠算法（MFBA）。對于函數f2，存在找到最優解的情況，對于函數f1，f3，f4，f5，f65個函數，最多相差47個數量級，這充分證明了改進算法的尋優精度和魯棒性比其它2種算法有很大程度的提高。為了更直觀比較SCABA與其它2種算法的尋優性能，圖1給出了3種算法在6個測試函數上的收斂曲線，為了更方便對收斂曲線進行觀察，對函數的最優值取以10為底的對數。從圖1可以看出，SCABA具有更高的收斂精度，能夠在較短的時間內接近于理論最優值，并且收斂速度快，f1，f2，f3，f4，f55個函數在迭代次數不到50次時，就能收斂到穩定的收斂精度，f6在迭代次數不到100次時，就能收斂到穩定的收斂精度。為了進一步驗證改進算法的可行性和有效性，在100維和500維下分別運行50次，并計算6個函數的最優值、最差值、平均值及標準差，從表3可以看出，SCABA在低緯度下的尋優精度跟在高緯度下的求解精度相差不明顯，不存在隨著優化函數維數的增加而陷入“維災難”的情況，這表明，在優化高維度的復雜函數時，SCABA也能呈現出良好的尋優性能。[FL）][PS韓斐斐1.EPS；S*2；X*2，BP#][HT6H][ST6HZ][WT6HX][WT5BZ][FL（2K2][BT4]4結束語針對BA存在收斂精度低、尋優速度慢、易陷入局部最優等的不足，本文提出了一種融合正弦余弦的蝙蝠算法—SCABA，在算法迭代后期，對種群中蝙蝠個體的位置進行正弦、余弦操作，得到新的蝙蝠位置。通過對6個測試函數的測試，仿真結果表明，SCABA具有較高的收斂速度和較好的優化精度，在很大程度上可避免陷入局部最優，具有較強的全局搜索能力。如何使改進算法表現出更優的尋優結果以及將改進算法應用到具體的領域，是下一步的重點研究內容。[HS2][HT5H]

參考文獻[HT][WT6B1][ST6BZ][HT6SS]

[1] [ZK（#〗[HJ*2] [JP3]Colorni A. Distributed Optimization by Ant Colonies[C]// European Conference on Artificial Life. The MIT Press， 1991.[JP]

[2] Kennedy J， Eberhart R. Particle swarm optimization[C]// IEEE International Conference on Neural Networks， 1995. Proceedings. IEEE， 2002，4：1942-1948.[3] [JP3]Mehrabian A R， Lucas C. A novel numerical optimization algorithm inspired from[JP] weed colonization[J]. Ecological Informatics， 2006， 1（4）：355-366.[ZK）][HT5SS][ST5BZ][WT5BZ][JY][FL）][WT6B1][ST6BZ][HT6SS]

[4] [ZK（#〗[HJ*2] Yang Xinshe. Flower pollination algorithm for global optimization[C]//LNCS 7445： Proceedings of the 11th Internation Conference on Unconventional Computation and Natural Computation， Orléan， France， Sep 3-7， 2012. Berlin， Heidelberg： Springer， 2012： 240-249.

[5] Cheng S， Zhang Q， Qin Q. Big data analytics with swarm intelligence[J]. Industrial Management & Data Systems， 2016， 116（4）：646-666.

[6] 馮翔，張進文，虞慧群. 仿生蚊子追蹤算法[J]. 計算機學報，2014，37（8）：1794-1808.

[7] 喬瑩瑩，宋威，馬偉. 基于GA優化QPSO算法的文本聚類[J]. 計算機應用研究，2014，31（10）：2912-2915.

[8] Yang X S. A New Meta-heuristic Bat-Inspired Algorithm[J]. Computer Knowledge & Technology， 2010， 284：65-74.

[9] Wang G G， Chu H C E， Mirjalili S. Three-dimensional path planning for UCAV using an improved bat algorithm[J]. Aerospace Science & Technology， 2016， 49：231-238.

[10]Karri C， Jena U. Fast vector quantization using a Bat algorithm for image compression[J]. Engineering Science & Technology An International Journal， 2016， 19（2）：769-781.

[11]姚妮，李紅嬋. 基于混合蝙蝠算法的多目標柔性作業車間調度問題[J]. 微電子學與計算機，2017，34（3）：25-29，34.

[12]肖輝輝，段艷明. 基于DE算法改進的蝙蝠算法的研究及應用[J]. 計算機仿真，2014，31（1）：272-277.[13]He X S， Ding W J， Yang X S. Bat algorithm based on simulated annealing and Gaussian perturbations[J]. Neural Computing & Applications， 2014， 25（2）：459-468. [14]裴宇航，劉景森，李煜. 一種動態調整慣性權重的自適應蝙蝠算法[J]. 計算機科學，2017，44（6）：240-244.[15][JP2]Mirjalili S. SCA： A Sine Cosine Algorithm for solving optimization problems[J]. Knowledge-Based Systems， 2016， 96：120-133.[JP][16]王文， 王勇， 王曉偉. 采用機動飛行的蝙蝠算法[J]. 計算機應用研究， 2014， 31（10）：2962-2964.[ZK）][FL）]