基于精英反向?qū)W習(xí)的混沌蝙蝠算法?

郭 旭 賀興時(shí) 高 昂

（西安工程大學(xué)理學(xué)院 西安 710048）

1 引言

蝙蝠算法（Bat Algorithm，BA）作為一種模擬蝙蝠回聲定位行為的新型元啟發(fā)式優(yōu)化算法被廣泛應(yīng)用于多目標(biāo)優(yōu)化，以及諸多經(jīng)典的全局工程優(yōu)化問(wèn)題［1～3］。BA結(jié)構(gòu)簡(jiǎn)單、參數(shù)少、魯棒性強(qiáng)，但本身也存在著容易陷入局部最優(yōu)、算法執(zhí)行后期的尋優(yōu)精度不足等問(wèn)題。文獻(xiàn)［4～7］分別提出了將BA同和聲搜索算法、模擬退火算法、遺傳算法以及差分進(jìn)化算法相結(jié)合的混合啟發(fā)式算法，不同程度上提高了算法的收斂速度與搜索精度。此外，劉長(zhǎng)平等針對(duì)基本蝙蝠算法收斂精度低和易早熟，采用levy飛行搜索策略來(lái)模擬蝙蝠的捕食行為，使得該算法有效地避免了局部極值的吸引［8］。張宇楠、盛孟龍等人分別將自適應(yīng)步長(zhǎng)、自適應(yīng)變異策略引入蝙蝠算法，從而使算法在后期獲得更高精度的解［9～10］。孫文捷、劉長(zhǎng)平等分別將基于Fuch映射和邏輯自映射的混沌算法引入到蝙蝠算法中，有效地結(jié)合了蝙蝠算法的全局優(yōu)化能力和混沌算法的局部搜索能力［11～12］。而關(guān)于蝙蝠算法的理論性分析，李枝勇等將蝙蝠算法簡(jiǎn)化到一維的單個(gè)蝙蝠，定義了速度和位置更新的兩種模式，利用特征方程的方法分別對(duì)其進(jìn)行了收斂性分析［13］。盛孟龍等基于隨機(jī)搜索算法的全局收斂性判斷準(zhǔn)則對(duì)蝙蝠算法的收斂性進(jìn)行分析［14］。

為了更好地控制蝙蝠算法的探測(cè)和開發(fā)能力，克服基本蝙蝠算法缺點(diǎn)，引入精英反向?qū)W習(xí)機(jī)制，通過(guò)對(duì)比精英蝙蝠的當(dāng)前解與反向解，選取較優(yōu)秀個(gè)體進(jìn)入下一次迭代，加快算法收斂速度。同時(shí)，在迭代中對(duì)蝙蝠位置進(jìn)行混沌擾動(dòng)，增加種群多樣性，這在一定程度上能有效地提高了算法的全局搜索能力和搜索精度。

2 基本蝙蝠算法

蝙蝠借助其特有的“聲吶系統(tǒng)”在黑暗的環(huán)境中躲避細(xì)如發(fā)絲的障礙物并捕食獵物［15～17］。蝙蝠算法即是模擬蝙蝠生物學(xué)行為并進(jìn)行優(yōu)化的一種基于群體進(jìn)化的算法。

首先在可行解空間隨機(jī)初始化種群，即確定個(gè)體的初始位置和初始速度，其中位置用來(lái)表示問(wèn)題的解，通過(guò)評(píng)價(jià)群體，找出群體最優(yōu)位置，然后分別按式（1）～（3）更新個(gè)體的飛行速度和位置：

根據(jù)生物學(xué)機(jī)理可知，在搜尋獵物過(guò)程中，蝙蝠初始階段發(fā)出的超聲波脈沖音強(qiáng)大而頻率低，有助于在更廣泛的空間搜索，發(fā)現(xiàn)獵物后，就逐漸減小脈沖音強(qiáng)，同時(shí)增加脈沖發(fā)射次數(shù)，以利于精確掌握獵物的空間位置，用式（4）和（5）來(lái)模擬這種搜索特點(diǎn)。

算法1 Bat Algorithm

初始化蝙蝠種群位置xi(i=1，2，…，n)和速度vi

初始化頻率 fi，脈沖發(fā)生率ri，音量Ai

While（t＜最大迭代次數(shù)）

通過(guò)調(diào)整頻率產(chǎn)生新的解

根據(jù)式（1）～（3）更新速度和位置

if（rand＞ri）

從最優(yōu)解集中選一個(gè)解

在選擇的最優(yōu)解周圍產(chǎn)生一個(gè)局部解

end if

通過(guò)隨機(jī)飛行得到一個(gè)新解

if（rand＜Aif(xi)＜f(x*)）

接受這個(gè)新解

增大 ri，減小 Ai（根據(jù)式（4）、（5）調(diào)整）

end if

排列蝙蝠并找到當(dāng)前最優(yōu)解

end while

3 精英反向混沌蝙蝠算法

3.1 精英反向?qū)W習(xí)

反向?qū)W習(xí)（Oppositition-based Learning，OBL）是計(jì)算智能中的一個(gè)新概念，已經(jīng)被證明是提高隨機(jī)搜索算法的搜索能力的一種有效方法［18］。OBL的基本思想是同時(shí)評(píng)估當(dāng)前解與反向解，選擇較好的解作為下一代的個(gè)體，該策略能夠有效地提高群體的多樣性，避免算法陷入局部最優(yōu)。

依據(jù)概率學(xué)原理，每個(gè)隨機(jī)產(chǎn)生的候選解相比它的反向解有50%的概率遠(yuǎn)離問(wèn)題最優(yōu)解［19］。由于全局最優(yōu)蝙蝠（即精英蝙蝠）是種群的引領(lǐng)者，一旦陷入局部最優(yōu)，將導(dǎo)致算法進(jìn)入“早熟”狀態(tài)。而對(duì)蝙蝠進(jìn)行反向?qū)W習(xí)將會(huì)在很大程度上避免此現(xiàn)象。此外，反向?qū)W習(xí)帶有一定的盲目性，加入精英策略，選擇精英個(gè)體，進(jìn)行反向?qū)W習(xí)，充分利用其特征信，在不過(guò)分增加計(jì)算量的基礎(chǔ)上，加快算法收斂速度。

3.2 混沌蝙蝠算法

混沌目前尚無(wú)嚴(yán)格定義，一般將有確定性方程得到的基本有隨機(jī)性運(yùn)動(dòng)狀態(tài)稱為混沌。Logistic映射就是一個(gè)典型的混沌系統(tǒng)，迭代公式如下：

式中，μ為控制參量，當(dāng) μ=4 ，0≤z0≤1時(shí)Logistic完全處于混沌狀態(tài)。本文將利用μ=4時(shí)的混沌特性，取式（6）的Logistic映射為混沌信號(hào)發(fā)生器。

基于混沌的蝙蝠算法對(duì)基本蝙蝠算法主要有兩方面的改進(jìn)。首先是利用混沌的遍歷性，產(chǎn)生初始群體：隨機(jī)產(chǎn)生一個(gè) d維向量 z1=(z11，z12，…，z1d)，且 z1i∈[0，1] ， i=1，2，…，d ，根據(jù)式（6）迭代生成 z2，z3，…，zn，將 zi，i=1，2，…，n 的各個(gè)分量載波到優(yōu)化變量的取值范圍：xij=Lb+(Ub-Lb)zij，i=1，2，…n ， j=1，2，…，d 作為初始種群。

其次，在迭代過(guò)程中，對(duì)蝙蝠位置進(jìn)行混沌擾動(dòng)：隨機(jī)產(chǎn)生一個(gè) d 維向量 u0=(u01，u02，…，u0d)，且 u0i∈[0，1] ， i=1，2，…，d ，根據(jù)式（6）迭代生成（t表示迭代次數(shù)）作為擾動(dòng)變量，用

代替蝙蝠的位置更新公式，即式（3）。

3.3 精英反向混沌蝙蝠算法

對(duì)于隨機(jī)優(yōu)化算法而言，探測(cè)能力和開發(fā)能力是最受關(guān)注的兩個(gè)問(wèn)題。本文利用混動(dòng)擾動(dòng)策略擴(kuò)大搜索區(qū)域，增加種群多樣性，避免陷入局部極值，提高算法的探測(cè)能力。但是混沌擾動(dòng)策略必將在一定程度上減緩算法的收斂進(jìn)程。而精英反向?qū)W習(xí)策略可有效地克服這一缺點(diǎn)，加快算法的收斂速度。算法描述如下：

算法2 EOCBA

執(zhí)行混沌及反向?qū)W習(xí)策略初始化蝙蝠種群位置xi(i=1，2，…，n)和速度 vi

初始化頻率 fi，脈沖發(fā)生率ri，音量Ai

While（t＜最大迭代次數(shù)）

If（rand＜p）

從當(dāng)前種群中選擇m個(gè)最好個(gè)體作為精英種群，進(jìn)行反向?qū)W習(xí)，形成較優(yōu)的下一代種群

else

通過(guò)調(diào)整頻率產(chǎn)生新的解

根據(jù)式（1）、（2）、（7）更新速度和位置

if（rand＞ri）

從最優(yōu)解集中選一個(gè)解

在選擇的最優(yōu)解周圍產(chǎn)生一個(gè)局部解end if

通過(guò)隨機(jī)飛行得到一個(gè)新解

if（rand＜Aif(xi)＜f(x*)）

接受這個(gè)新解

增大 ri，減小 Ai（根據(jù)式（4）、（5）調(diào)整）end if

排列蝙蝠并找到當(dāng)前最優(yōu)解

end if

end while

4 實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證本文提出的基于權(quán)重策略的蝙蝠算法的性能，選取8個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)（見(jiàn)表1）進(jìn)行仿真測(cè)試，并與基本算法對(duì)比。

4.1 測(cè)試函數(shù)與試驗(yàn)參數(shù)設(shè)置

蝙蝠算法中各參數(shù)取值尚無(wú)理論依據(jù)，本文所設(shè)置的參數(shù)值是根據(jù)經(jīng)驗(yàn)值來(lái)確定?；掘鹚惴ㄖ校N群規(guī)模N=30，個(gè)體i的最大脈沖頻度，最大脈沖音強(qiáng)A=0.75，脈沖音強(qiáng)衰減i系數(shù)α=0.9，脈沖頻度增加系數(shù)γ=0.04，最大迭代次數(shù)Nmax=1000，尋優(yōu)精度ε=10-5。在基于精英反向?qū)W習(xí)的混沌蝙蝠算法中，精英種群m=10，其余同上。測(cè)試函數(shù)如表1所示。

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

4.2 測(cè)試結(jié)果與分析

為克服算法的偶然性誤差，對(duì)每個(gè)測(cè)試函數(shù)，算法分別獨(dú)立運(yùn)行30次，圖1～8為本文改進(jìn)算法（EOCBA）與基本蝙蝠算法（BA）對(duì)8個(gè)測(cè)試函數(shù)的進(jìn)化曲線對(duì)比。算法性能統(tǒng)計(jì)結(jié)果見(jiàn)表2。

圖1 函數(shù) f1的數(shù)值進(jìn)化曲線

圖2 函數(shù) f2的數(shù)值進(jìn)化曲線

圖3 函數(shù) f3的數(shù)值進(jìn)化曲線

圖4 函數(shù) f4的數(shù)值進(jìn)化曲線

圖5 函數(shù) f5的數(shù)值進(jìn)化曲線

圖6 函數(shù) f6的數(shù)值進(jìn)化曲線

圖7 函數(shù) f7的數(shù)值進(jìn)化曲線

圖8 函數(shù) f8的數(shù)值進(jìn)化曲線

表2中最優(yōu)結(jié)果、平均結(jié)果及最差結(jié)果反映了BA和EOCBA對(duì)測(cè)試函數(shù) f1～f8所求解的質(zhì)量，改進(jìn)的算法均優(yōu)于原算法，特別是對(duì)測(cè)試函數(shù) f1、f3、f4、f5、f6。標(biāo)準(zhǔn)差反映算法的穩(wěn)定性，除 f2外，EOCBA均有較明顯優(yōu)勢(shì)。而對(duì) f2而言，30次測(cè)試BA算法均陷入一個(gè)局部極值，從而標(biāo)準(zhǔn)差極小，這并不能說(shuō)明算法性能優(yōu)越，而屬于“早熟”現(xiàn)象。尋優(yōu)成功率指算法達(dá)到尋優(yōu)精度的次數(shù)占實(shí)驗(yàn)總次數(shù)的比重，是算法性能比較的又一重要指標(biāo)，除測(cè)試函數(shù) f2、f8外，尋優(yōu)成功率均有所提高，特別是對(duì) f3～f6。平均迭代次數(shù)體現(xiàn)算法的尋優(yōu)速度，EOCBA在收斂速度上快于BA。

改進(jìn)的算法在尋優(yōu)精度、尋優(yōu)成功率和收斂速度方面均有所提高。算法性能的改善主要源于混沌擾動(dòng)以及精英反向?qū)W習(xí)保持了種群多樣性，同時(shí)，精英反向?qū)W習(xí)充分利用精英蝙蝠的特征信息，以較小的計(jì)算量為代價(jià)，加快了算法收斂速度。

表2 實(shí)驗(yàn)結(jié)果對(duì)比

5 結(jié)語(yǔ)

針對(duì)基本蝙蝠算法存在的后期收斂速度慢、易陷入局部極值的缺點(diǎn)，該算法引入精英反向?qū)W習(xí)策略，優(yōu)化迭代種群，同時(shí)，在迭代中對(duì)蝙蝠位置進(jìn)行混沌擾動(dòng)，增加種群多樣性，有效地提高了算法的全局搜索能力和搜索精度。但改進(jìn)的算法在一定程度上增加了算法復(fù)雜度，對(duì)混沌映射及精英種群的合理選取，并將新算法用于解決實(shí)際問(wèn)題，將是下一步的研究工作。