基于Fuch映射的混沌蝙蝠算法

孫文捷， 張惠珍， 張 健， 趙 坤

（上海理工大學(xué) 管理學(xué)院，上海 200093）

近十幾年內(nèi)炙手可熱的遺傳算法、神經(jīng)網(wǎng)絡(luò)、模擬退火算法、蟻群算法、微粒群算法等［1］，都是受自然規(guī)律和生物群體智能行為的啟發(fā)而提出，其在廣泛的科學(xué)和工程技術(shù)領(lǐng)域內(nèi)顯示了其獨特的能力和應(yīng)用效果.但是，這類算法在求解復(fù)雜問題時，也暴露出其固有的一些缺陷，如算法易陷入局部極值，求解精度不高，而且許多算法的理論基礎(chǔ)較薄弱，沒有形成統(tǒng)一的算法框架，仍有許多問題有待研究.受蝙蝠回聲定位行為的啟發(fā)，Yang［2］于2010年提出一種新型的元啟 發(fā) 式 算 法——蝙 蝠 算 法（bat－inspired algorithm BA）.已有研究表明，BA 在某些方面將粒子群算法、遺傳算法和和聲算法的主要優(yōu)點進(jìn)行了良好的結(jié)合，并且粒子群算法和和聲算法可以認(rèn)為是蝙蝠算法在經(jīng)過適當(dāng)簡化后的一種特殊情況.因此，BA 較其它算法具有發(fā)揮更大作用的潛能［2－3］.混沌是一種普遍的非線性現(xiàn)象，具有遍歷性、隨機性與確定性相統(tǒng)一、對初始值變化敏感等特點［4］.由于遍歷性可使搜索過程避免陷入局部極小，因此，混沌搜索已成為一種非常有效的優(yōu)化算法.針對傳統(tǒng)混沌優(yōu)化方法中優(yōu)化結(jié)果對搜索初始值要求極高以及搜索效率較低的問題，傅文淵等［5］提出一種自適應(yīng)折疊混沌優(yōu)化方法——Fuch映 射，與Logistic映 射［6］、Chebyshev映 射［7］和Tent映射［8］相比，F(xiàn)uch映射具有更強的混沌特性.針對基本蝙蝠算法搜索效率低和較易陷入局部最優(yōu)的缺點，本文在基本蝙蝠算法中引入了Fuch映射，設(shè)計了一種基于Fuch映射的蝙蝠算法——Fuch混沌蝙蝠算法（FCBA）.算法循環(huán)過程中：一方面，通過混沌遍歷頻率變化區(qū)間，使得蝙蝠的速度能得到充分變化；另一方面，在蝙蝠所發(fā)射的脈沖速率還不太高時，利用Fuch映射對局部最優(yōu)解的鄰域進(jìn)行混沌遍歷搜索，使其跳出局部最優(yōu)解.通過求解基準(zhǔn)測試函數(shù)對FCBA與BA 的尋優(yōu)能力和搜索效率進(jìn)行比較.結(jié)果表明，與基本蝙蝠算法相比，F(xiàn)CBA 具有全局搜索能力強和收斂速度快的優(yōu)點.

1 蝙蝠算法

1.1 蝙蝠的回聲定位能力

蝙蝠是一種神奇的動物，有高級的回聲定位能力.微型蝙蝠靠一種聲納，也稱為回聲定位器，來探測獵物，避免障礙物，在黑暗中找到它們的棲息地.這些蝙蝠發(fā)出響亮的聲音脈沖，然后聆聽從周圍的物體反彈回來的回聲，利用雙耳的時間差及回聲的響度變化去建立周圍環(huán)境的三維場景.

大多數(shù)蝙蝠用短波、調(diào)頻信號對一個音階橫掃，而另一些蝙蝠則更經(jīng)常使用固定頻率的定位信號.它們的信號帶寬變化取決于物種，并經(jīng)常通過使用更多諧波來提高，但是它們探測獵物和避免障礙的原理都是基于回聲定位的聲學(xué)原理.研究顯示：蝙蝠發(fā)出的脈沖頻率通常為25～150kHz.由聲音在空氣中的速度v＝340m／s及超聲波在頻率f 下的波長λ＝v／f 可知：蝙蝠發(fā)出的脈沖波長λ在2～14mm之間，這樣的波長類同于它的獵物的大小.此外，蝙蝠發(fā)出在超聲波范圍內(nèi)的聲波，其響度能達(dá)到110dB，且響度可以從搜索獵物時的最高變化到靠近獵物時的最小.

1.2 蝙蝠運動的數(shù)學(xué)描述

1.2.1 蝙蝠的速度更新和位置更新

假設(shè)搜索空間為D 維，第i只蝙蝠在第t次進(jìn)化時的位置和速度分別為和，則在第t＋1次進(jìn)化時，其位置和速度可分別更新為和，即

式中，F(xiàn)i，F(xiàn)max和Fmin為第i只蝙蝠在當(dāng)前時刻發(fā)出的聲波的頻率、聲波頻率的最大值和最小值；β為隨機數(shù)，β∈［0，1］；x＊為當(dāng)前最優(yōu)解.

對于大小為n 的蝙蝠群體，可以從中選擇一只蝙蝠（解），并更新該蝙蝠相應(yīng)的位置，即在被選擇解的附近產(chǎn)生一個新解

該過程可被理解為局部搜索過程.其中，xold為從當(dāng)前最優(yōu)解集中隨機選擇的一個解，At為當(dāng)前代前i只蝙蝠的平均響度；ε為隨機向量ε∈［－1，1］D.

1.2.2 響度和脈沖發(fā)射

蝙蝠實際捕獵過程中，其聲波響度A（i）隨著與獵物距離的減小而不斷減弱，但脈沖發(fā)射速率R（i）隨著與獵物距離的減小而逐漸提高.蝙蝠i脈沖的響度A（i）和發(fā)射速率R（i）可更新為

其中，0＜α＜1和λ＞0均為常量.A（i）＝0時意味著蝙蝠i剛剛發(fā)現(xiàn)一只獵物，暫時停止發(fā)出任何聲音.不難發(fā)現(xiàn)t→∞，At（i）→0，Rt（i）＝R0（i）.

上述現(xiàn)象反映在實際算法中，即隨著響度的不斷減弱和脈沖速率的不斷提高，蝙蝠以一定的概率進(jìn)行局部搜索和接受新解；但是，進(jìn)行局部搜索的概率隨著脈沖速率的不斷提高而降低，接受新解的概率隨著響度的不斷減弱而降低.這既反映了蝙蝠的實際捕獵情況，也有助于加快算法收斂，并在算法運行初期能夠跳離局部最優(yōu).

基本蝙蝠算法中，蝙蝠的速度和位置的更新策略和標(biāo)準(zhǔn)粒子群算法更新速度和位置的策略有些相似之處.雖然從某種程度上來講，蝙蝠算法可視為標(biāo)準(zhǔn)粒子群優(yōu)化和由響度和脈沖速率控制的集中局部搜索的一種均衡組合.但是，與其它仿生類智能優(yōu)化相似，基本蝙蝠算法仍有容易陷入局部最優(yōu)的不足之處.

2 Fuch映射

Fuch映射是一種新型的一維離散映射，其表達(dá)式為

其中，xn≠0，n∈Z＋.文獻(xiàn)［5］對Fuch映射的不動點特性和Lyapunov指數(shù)［9］進(jìn)行了深入研究，并計算得到Fuch映射的Lyapunov指數(shù)λ 為2.165.與傳統(tǒng)的混沌映射（如Logistic映射、Chebyshev映射和Tent映射）相比，F(xiàn)uch映射有如下優(yōu)勢［5］：

a.Fuch映射具有更強的混沌特性，給定微小的初始值變化，混沌映射產(chǎn)生的輸出是完全不同的，并且系統(tǒng)輸出毫無規(guī)律；

b.映射相比于Logistic映射和Tent映射在解空間內(nèi)具有更加均衡的遍歷性；

c.考察遍歷整個系統(tǒng)解空間的混沌迭代次數(shù)時，F(xiàn)uch映射與傳統(tǒng)有限折疊混沌映射相比具有更小的迭代次數(shù)，能更好地實現(xiàn)混沌尋優(yōu)；

d.Fuch映射的不動點為超越數(shù)，若初始值不為0，則該映射產(chǎn)生的混沌不收斂于有理數(shù)不動點，表明在初始值不為0的情形下均能產(chǎn)生混沌.

Fuch映射有不因初值設(shè)置不當(dāng)而陷入不動點（局部最優(yōu)）的優(yōu)點.因此，將Fuch映射引入基本蝙蝠算法，其可以不依賴蝙蝠初始搜索的精度，對局部最優(yōu)解的鄰域進(jìn)行混沌遍歷搜索.

3 基于Fuch映射的蝙蝠算法

3.1 頻率變化區(qū)間的混沌搜索

在基本的蝙蝠算法中，每只蝙蝠利用特有的回聲定位能力，測算出自己與當(dāng)前所求得的最優(yōu)解間的距離，并根據(jù)自動發(fā)出的脈沖頻率來調(diào)節(jié)自己的速度.但是脈沖頻率往往是從［Fmin，F(xiàn)max］中隨機取得，這很有可能使速度的變化落在某個局部的區(qū)間中，根據(jù)式（3）可知：特別是在蝙蝠很靠近所搜索到的當(dāng)前最優(yōu)解時，速度會被迫“停滯”，這就影響了蝙蝠的搜索效率.另一方面，在蝙蝠的脈沖發(fā)射速率不斷升高后，進(jìn)行鄰域搜索的機會將越來越小，這使得蝙蝠對所搜索到的初始解的依賴性加大，這很有可能使算法陷入局部最優(yōu).

為了改進(jìn)基本蝙蝠算法的上述不足之處，本文定義第i只蝙蝠在第t 次進(jìn)化時產(chǎn)生混沌變量，并利用其對頻率變化區(qū)間進(jìn)行混沌搜索

與式（1）相比，式（7）使得蝙蝠在靠近當(dāng)前最優(yōu)解的同時，其速度依然能得到充分變化.

3.2 局部最優(yōu)解鄰域的混沌搜索

基本蝙蝠算法中的局部搜索為：從現(xiàn)有的最佳解決方案中選擇一只蝙蝠后，每只蝙蝠的新位置在隨機游走中就近產(chǎn)生.為了進(jìn)一步改善基本蝙蝠算法的局部搜索功能，改善其容易陷入局部最優(yōu)的不足之處，使其能夠較快地求出所求問題的最優(yōu)解或滿意解，本文利用Fuch映射對基本蝙蝠算法的局部最優(yōu)解鄰域進(jìn)行混沌搜索，具體搜索步驟如下：

Step1 產(chǎn)生隨機數(shù)rand，若rand＞Ri，則進(jìn)行局部搜索，否則不進(jìn)行局部搜索；fnew 為蝙蝠初始位置所相應(yīng)的目標(biāo)函數(shù)值；

Step 2 確定以當(dāng)前最優(yōu)解x＊為中心的鄰域搜索半徑

式中，low 和upper 分別為變量的上下界.

Step 3 令第t次進(jìn)化中第i 只蝙蝠所產(chǎn)生的混沌變量為本次鄰域搜索的初始混沌變量k0；記總迭代次數(shù)為m，臨時變量為temp，為第i 只蝙蝠第t次進(jìn)化時所搜索到的新解.以最小化問題為例，混沌遍歷搜索過程為

3.3 Fuch混沌蝙蝠算法

為了使基本蝙蝠算法能夠跳出局部最優(yōu)，通過較小地迭代次數(shù)搜索到全局最優(yōu)解，本文不僅利用Fuch映射對頻率變化區(qū)間和局部最優(yōu)解鄰域進(jìn)行混沌搜索，而且在每次進(jìn)化迭代開始前對Fuch 映射的初值進(jìn)行賦值擾動，得到一種新型蝙蝠算法——Fuch混沌蝙蝠算法，簡記為FCBA.

假設(shè)求函數(shù)f（x）的最小值，算法最大循環(huán)次數(shù)為gen，蝙蝠種群大小為n，第i只蝙蝠的位置為xi，速度為vi，脈沖發(fā)射速率為Ri，脈沖響度為Ai，個體適應(yīng)值fitness（i）＝f（xi）.用于求解f（x）的FCBA算法的基本步驟可以概括如下：

對蝙蝠的頻率變化區(qū)間進(jìn)行混沌搜索，更新其速度和位置，并對蝙蝠的速度與位置進(jìn)行越界處理；

對局部最優(yōu)解的鄰域進(jìn)行混沌遍歷搜索

更新當(dāng)前最佳解x＊及其對應(yīng)的速率、脈沖發(fā)射速率、脈沖響度和脈沖頻率；

增大Ri，減小Ai；

鄰域搜索半徑ρ的確定方法已經(jīng)可以避免位置越界的發(fā)生，因此上述FCBA 算法中只對蝙蝠的初始搜索進(jìn)行位置糾偏.

4 仿真實驗

為測試算法的求解性能，本文利用基本蝙蝠算法和FCBA 算法對4個經(jīng)典函數(shù)優(yōu)化問題進(jìn)行求解.為了確保兩種算法具有可比性，使它們在相同的起點上進(jìn)行比較，計算過程中，不僅對兩種算法共有的絕大部分參數(shù)設(shè)定了相同的值（如表1所示），而且對兩種算法設(shè)置了相同的迭代次數(shù)，但對其求解精度沒有設(shè)置.

表1 參數(shù)設(shè)置Tab.1 Setting up of parameters value

表2給出了4個測試函數(shù)及其變量取值區(qū)間和全局最優(yōu)解.除函數(shù)f4（x）為單模函數(shù)，無局部最優(yōu)解，只有全局最優(yōu)解外，其它3個函數(shù)都是典型的多峰函數(shù)，有多個極小值，均較難優(yōu)化，常用來測試算法的全局尋優(yōu)能力.

表2 4個標(biāo)準(zhǔn)測試函數(shù)Tab.2 4Benchmarkfunctions

算法運行環(huán)境為Windows 764 位操作系統(tǒng)，Intel處理器，2.40 GHZ，4 GB內(nèi)存；仿真軟件為MatlabR2012a.

表3和表4（見下頁）分別給出了4個測試函數(shù)利用基本蝙蝠算法和FCBA 算法的求解結(jié)果.

對比表3和表4中的數(shù)據(jù)，不難發(fā)現(xiàn)：FCBA 與BA 求解4個測試函數(shù)時，所耗費的計算時間相差并不很大，但FCBA 在尋優(yōu)精度上卻有著較大優(yōu)勢，尤其求解f2（x），f3（x）和f4（x）時，F(xiàn)CBA 在尋優(yōu)精度上的優(yōu)勢特別明顯，其求解結(jié)果在最好值、最劣值和平均值3方面均明顯優(yōu)于基本蝙蝠算法的計算結(jié)果.

給定相同的迭代次數(shù)，兩種算法所耗費的計算時間相差并不大.為了進(jìn)一步分析算法的收斂性能，圖1（見下頁）給出了兩種算法求解4個測試函數(shù)的迭代收斂曲線，圖1中（a），（b），（c）和（d）的橫坐標(biāo)表示進(jìn)化迭代次數(shù)gen，縱坐標(biāo)表示函數(shù)值f（x）.

從圖1可知，與BA 相比，F(xiàn)CBA 能夠較快地收斂于全局最優(yōu)解，其在較小的進(jìn)化迭代次數(shù)內(nèi)便可接近所測函數(shù)的理論全局最優(yōu)解.

表3 FCBA 的算法尋優(yōu)結(jié)果Tab.3 Results obtained byu singFCBA

表4 BA 的算法尋優(yōu)結(jié)果Tab.4 Results obtained by using BA

圖1 目標(biāo)函數(shù)隨循環(huán)次數(shù)的變化曲線Fig.1 Changing curve of the objective function value

5 結(jié) 論

將Fuch映射引入到基本蝙蝠算法中，設(shè)計了一種混沌蝙蝠算法.算法中，一方面，在蝙蝠的脈沖發(fā)射速率還不是很高，即蝙蝠還沒有很靠近獵物時，對局部最優(yōu)解的鄰域進(jìn)行混沌遍歷搜索，大大優(yōu)化了初始值的質(zhì)量與逼近全局最優(yōu)解的速度；另一方面，通過對局部最優(yōu)解的鄰域進(jìn)行混沌遍歷搜索，不僅有效地改善了蝙蝠初始搜索所得到的解，而且對基本蝙蝠算法的局部搜索功能進(jìn)行了很好的改進(jìn)，使其在較小的進(jìn)化迭代次數(shù)內(nèi)較快地收斂于全局最優(yōu)解或求得問題的滿意解.仿真結(jié)果表明：提出的混沌蝙蝠算法求解函數(shù)優(yōu)化問題時，在收斂速度和精度上均優(yōu)于基本蝙蝠算法，且具有一定的可行性和較好的尋優(yōu)能力.

［1］王凌.智能優(yōu)化算法及其應(yīng)用［M］.北京：清華大學(xué)出版社，2001.

［2］Yang X S.A new metaheuristic bat－inspired algorithm［J］.Nature Inspired Cooperative Strategies for Optimization，2010，284：65－74.

［3］Yang X S，Gandomi A H.Bat algorithm：a novel approach for global engineering optimization［J］.Engineering Computation，2012，29（5）：267－289.

［4］李兵，蔣慰孫.混沌優(yōu)化方法及其應(yīng)用［J］.控制理論與應(yīng)用，1997，14（4）：613－615.

［5］傅文淵，凌朝東.自適應(yīng)折疊混沌優(yōu)化方法［J］.西安交通大學(xué)學(xué)報，2013，47（2）：33－38.

［6］范九倫.分段Logistic混沌映射及其性能分析［J］.電子學(xué)報，2009，37（4）：720－725.

［7］石軍.基于Chebyshev映射的混沌特性及其性能分析［J］.現(xiàn)代電子技術(shù)，2008（23）：93－96.

［8］單梁，強浩，李軍，等.基于Tent映射的混沌優(yōu)化算法［J］.控制與決策，2005，20（2）：179－182.

［9］李小亭，蔡詩東.混沌和李亞普諾夫特征指數(shù)［J］.物理，1996，25（5）：282－285.