融合正弦余弦的蝙蝠算法

韓斐斐 劉升 王興凡

文章編號(hào)： 2095-2163（2018）03-0122-06中圖分類(lèi)號(hào)： 文獻(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)目：

作者簡(jiǎn)介：

通信作者：

收稿日期： 引言

優(yōu)化問(wèn)題廣泛存在于科學(xué)研究和工程優(yōu)化等領(lǐng)域，傳統(tǒng)的優(yōu)化方法已經(jīng)不能滿(mǎn)足解決復(fù)雜優(yōu)化問(wèn)題的需要。受自然界生物群體智能行為和自然界進(jìn)化規(guī)律的啟發(fā)，國(guó)內(nèi)外學(xué)者們提出了多種基于仿生學(xué)的群體智能優(yōu)化算法，如蟻群算法（Ant Colony Algorithm，ACA）[1]來(lái)自于蟻群尋找食物的行為，螞蟻根據(jù)信息素的濃度選擇覓食路徑；粒子群算法（Particle Swarm Optimization， PSO）[2]的基本思想來(lái)源于鳥(niǎo)群的信息交流和覓食行為；入侵雜草優(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]、文本聚類(lèi)[7]等領(lǐng)域。

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

1蝙蝠算法BA

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

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

（2）蝙蝠在位置xi以速度vi隨意飛行，以固定頻率fi、可變化波長(zhǎng)λ和響度A0搜索食物；同時(shí)根據(jù)目標(biāo)距離來(lái)調(diào)整發(fā)射出的脈沖波長(zhǎng)（或頻率），在靠近食物時(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)解。

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

At+1i=αAti（5）

rt+1i=r0i1-exp-γt（6）其中，ε∈[-1，1]是一個(gè)服從均勻分布的隨機(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)簡(jiǎn)單、魯棒性好、容易實(shí)現(xiàn)，利用正弦函數(shù)和余弦函數(shù)的性質(zhì)迭代以達(dá)到尋找最優(yōu)解的目的。算法中幾個(gè)關(guān)鍵的參數(shù)提升了其尋優(yōu)性能，有效地平衡了“局部開(kāi)發(fā)”和“全局探索”。在SCA中，隨機(jī)生成一個(gè)含有N個(gè)個(gè)體的初始種群Pt={Xti}，其中Xti=xti1，xti2，…，xtij，…，xtid， j=1，2，…，d； i=1，2，…，N，N為種群大??；d為待優(yōu)化函數(shù)所含決策變量的個(gè)數(shù)，即維數(shù)；t代表當(dāng)前進(jìn)化代數(shù)。

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

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個(gè)個(gè)體；xti代表第t次循環(huán)下第i個(gè)個(gè)體；x*是適應(yīng)度值最優(yōu)的個(gè)體；r1是控制搜索方向的參數(shù)；r2是控制搜索距離的參數(shù)；r3是一個(gè)隨機(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ì)算每個(gè)蝙蝠個(gè)體的適應(yīng)度值及最佳位置x*while（終止準(zhǔn)則不滿(mǎ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)過(guò)進(jìn)化的蝙蝠位置不是直接進(jìn)入下一次迭代，而是對(duì)種群中個(gè)體的位置進(jìn)行正弦、余弦操作，得到新的蝙蝠位置，再進(jìn)入（t+1）次迭代。由于正弦余弦算法利用正弦函數(shù)和余弦函數(shù)值的變化來(lái)達(dá)到尋優(yōu)的目的，且正弦（余弦）函數(shù)值的大小是在[-1，1]之間，因此將正弦余弦融合到BA中，可以有效提升BA的收斂速度。另外，SCA有幾個(gè)關(guān)鍵的參數(shù)，r1指引著個(gè)體搜索的方向，r2控制著個(gè)體尋優(yōu)的移動(dòng)距離，因此在SCABA中，蝙蝠個(gè)體的搜索距離和方向能夠被控制并朝向最優(yōu)個(gè)體，這降低了個(gè)體尋優(yōu)的盲目性，提高了個(gè)體尋優(yōu)的效率。SCABA將正弦余弦算法和蝙蝠算法各自的優(yōu)點(diǎn)充分融合，使算法不僅具有強(qiáng)大的全局尋優(yōu)能力，同時(shí)也具有強(qiáng)大的局部搜索能力，其運(yùn)行步驟描述如下：[WT5HZ][ST5HZ]Step 1[WT5BZ][ST5BZ]初始化SCABA的各個(gè)參數(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）更新蝙蝠個(gè)體的速度和位置，產(chǎn)生新一代個(gè)體，并計(jì)算其適應(yīng)度；[WT5HZ][ST5HZ]Step 3[WT5BZ][ST5BZ]如果隨機(jī)數(shù)rand1>ri，則從當(dāng)前種群的最優(yōu)解集中選擇一個(gè)解，使用式（4）通過(guò)施加擾動(dòng)，產(chǎn)生新個(gè)體xnew來(lái)替代當(dāng)前解；[WT5HZ][ST5HZ]Step 4[WT5BZ][ST5BZ]若隨機(jī)數(shù)rand2>Ai且f（xnew）

由表2可以看出，對(duì)于6個(gè)測(cè)試函數(shù)，無(wú)論是簡(jiǎn)單的單峰函數(shù)，還是存在大量局部極值的非線(xiàn)性多峰函數(shù)，本文提出的融合正弦余弦的蝙蝠算法（SCABA）最優(yōu)解、最差解、平均值及標(biāo)準(zhǔn)方差的精度均明顯高于基本蝙蝠算法（BA）和采用機(jī)動(dòng)飛行的蝙蝠算法（MFBA）。對(duì)于函數(shù)f2，存在找到最優(yōu)解的情況，對(duì)于函數(shù)f1，f3，f4，f5，f65個(gè)函數(shù)，最多相差47個(gè)數(shù)量級(jí)，這充分證明了改進(jìn)算法的尋優(yōu)精度和魯棒性比其它2種算法有很大程度的提高。為了更直觀比較SCABA與其它2種算法的尋優(yōu)性能，圖1給出了3種算法在6個(gè)測(cè)試函數(shù)上的收斂曲線(xiàn)，為了更方便對(duì)收斂曲線(xiàn)進(jìn)行觀察，對(duì)函數(shù)的最優(yōu)值取以10為底的對(duì)數(shù)。從圖1可以看出，SCABA具有更高的收斂精度，能夠在較短的時(shí)間內(nèi)接近于理論最優(yōu)值，并且收斂速度快，f1，f2，f3，f4，f55個(gè)函數(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個(gè)函數(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é)束語(yǔ)針對(duì)BA存在收斂精度低、尋優(yōu)速度慢、易陷入局部最優(yōu)等的不足，本文提出了一種融合正弦余弦的蝙蝠算法—SCABA，在算法迭代后期，對(duì)種群中蝙蝠個(gè)體的位置進(jìn)行正弦、余弦操作，得到新的蝙蝠位置。通過(guò)對(duì)6個(gè)測(cè)試函數(shù)的測(cè)試，仿真結(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)研究?jī)?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算法的文本聚類(lèi)[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è)車(chē)間調(diào)度問(wèn)題[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]裴宇航，劉景森，李煜. 一種動(dòng)態(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ī)動(dòng)飛行的蝙蝠算法[J]. 計(jì)算機(jī)應(yīng)用研究， 2014， 31（10）：2962-2964.[ZK）][FL）]