郭 旭 賀興時 高 昂

（西安工程大學理學院 西安 710048）

1 引言

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

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

2 基本蝙蝠算法

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

首先在可行解空間隨機初始化種群，即確定個體的初始位置和初始速度，其中位置用來表示問題的解，通過評價群體，找出群體最優(yōu)位置，然后分別按式（1）～（3）更新個體的飛行速度和位置：

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

算法1 Bat Algorithm

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

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

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

通過調整頻率產生新的解

根據式（1）～（3）更新速度和位置

if（rand＞ri）

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

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

end if

通過隨機飛行得到一個新解

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

接受這個新解

增大 ri，減小 Ai（根據式（4）、（5）調整）

end if

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

end while

3 精英反向混沌蝙蝠算法

3.1 精英反向學習

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

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

3.2 混沌蝙蝠算法

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

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

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

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

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

3.3 精英反向混沌蝙蝠算法

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

算法2 EOCBA

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

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

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

If（rand＜p）

從當前種群中選擇m個最好個體作為精英種群，進行反向學習，形成較優(yōu)的下一代種群

else

通過調整頻率產生新的解

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

if（rand＞ri）

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

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

通過隨機飛行得到一個新解

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

接受這個新解

增大 ri，減小 Ai（根據式（4）、（5）調整）end if

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

end if

end while

4 實驗與結果分析

為驗證本文提出的基于權重策略的蝙蝠算法的性能，選取8個標準測試函數(shù)（見表1）進行仿真測試，并與基本算法對比。

4.1 測試函數(shù)與試驗參數(shù)設置

蝙蝠算法中各參數(shù)取值尚無理論依據，本文所設置的參數(shù)值是根據經驗值來確定。基本蝙蝠算法中，種群規(guī)模N=30，個體i的最大脈沖頻度，最大脈沖音強A=0.75，脈沖音強衰減i系數(shù)α=0.9，脈沖頻度增加系數(shù)γ=0.04，最大迭代次數(shù)Nmax=1000，尋優(yōu)精度ε=10-5。在基于精英反向學習的混沌蝙蝠算法中，精英種群m=10，其余同上。測試函數(shù)如表1所示。

表1 標準測試函數(shù)

4.2 測試結果與分析

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

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

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

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

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

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

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

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

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

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

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

表2 實驗結果對比

5 結語

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