韓斐斐 劉升 王興凡

文章編號： 2095-2163（2018）03-0122-06中圖分類號： 文獻(xiàn)標(biāo)志碼： A

摘要： 關(guān)鍵詞： （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：

基金項(xiàng)目：

作者簡介：

通信作者：

收稿日期： 引言

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

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

1蝙蝠算法BA

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

（1）所有的蝙蝠都利用回聲定位機(jī)制感知目標(biāo)距離，且能夠區(qū)分食物與障礙物。

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

（3）響度從最大值A(chǔ)max變化到最小值A(chǔ)min。

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

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

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

對于局部搜索，在[0，1]之間產(chǎn)生一個隨機(jī)數(shù)rand1，如果rand1>ri，則對當(dāng)前最優(yōu)解按式（4）進(jìn)行隨機(jī)擾動，產(chǎn)生一個新解xnew，并對新解做越界處理。產(chǎn)生一個隨機(jī)數(shù)rand2，如果rand2>Ai且f（xnew）

At+1i=αAti（5）

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

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

2.1正弦余弦算法

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

首先，計(jì)算種群中每個個體的適應(yīng)度值，根據(jù)適應(yīng)度值的大小對種群中個體進(jìn)行排序，并記錄當(dāng)前最優(yōu)個體及其位置，在每一次迭代中，種群個體位置更新如下：

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

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

參考文獻(xiàn)[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ìn)文，虞慧群. 仿生蚊子追蹤算法[J]. 計(jì)算機(jī)學(xué)報(bào)，2014，37（8）：1794-1808.

[7] 喬瑩瑩，宋威，馬偉. 基于GA優(yōu)化QPSO算法的文本聚類[J]. 計(jì)算機(jī)應(yīng)用研究，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]姚妮，李紅嬋. 基于混合蝙蝠算法的多目標(biāo)柔性作業(yè)車間調(diào)度問題[J]. 微電子學(xué)與計(jì)算機(jī)，2017，34（3）：25-29，34.

[12]肖輝輝，段艷明. 基于DE算法改進(jìn)的蝙蝠算法的研究及應(yīng)用[J]. 計(jì)算機(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]裴宇航，劉景森，李煜. 一種動態(tài)調(diào)整慣性權(quán)重的自適應(yīng)蝙蝠算法[J]. 計(jì)算機(jī)科學(xué)，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ī)動飛行的蝙蝠算法[J]. 計(jì)算機(jī)應(yīng)用研究， 2014， 31（10）：2962-2964.[ZK）][FL）]