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

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

（上海理工大學 管理學院，上海 200093）

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

1 蝙蝠算法

1.1 蝙蝠的回聲定位能力

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

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

1.2 蝙蝠運動的數學描述

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

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

式中，Fi，Fmax和Fmin為第i只蝙蝠在當前時刻發出的聲波的頻率、聲波頻率的最大值和最小值；β為隨機數，β∈［0，1］；x＊為當前最優解.

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

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

1.2.2 響度和脈沖發射

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

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

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

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

2 Fuch映射

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

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

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

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

c.考察遍歷整個系統解空間的混沌迭代次數時，Fuch映射與傳統有限折疊混沌映射相比具有更小的迭代次數，能更好地實現混沌尋優；

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

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

3 基于Fuch映射的蝙蝠算法

3.1 頻率變化區間的混沌搜索

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

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

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

3.2 局部最優解鄰域的混沌搜索

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

Step1 產生隨機數rand，若rand＞Ri，則進行局部搜索，否則不進行局部搜索；fnew 為蝙蝠初始位置所相應的目標函數值；

Step 2 確定以當前最優解x＊為中心的鄰域搜索半徑

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

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

3.3 Fuch混沌蝙蝠算法

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

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

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

對局部最優解的鄰域進行混沌遍歷搜索

更新當前最佳解x＊及其對應的速率、脈沖發射速率、脈沖響度和脈沖頻率；

增大Ri，減小Ai；

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

4 仿真實驗

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

表1 參數設置Tab.1 Setting up of parameters value

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

表2 4個標準測試函數Tab.2 4Benchmarkfunctions

算法運行環境為Windows 764 位操作系統，Intel處理器，2.40 GHZ，4 GB內存；仿真軟件為MatlabR2012a.

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

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

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

從圖1可知，與BA 相比，FCBA 能夠較快地收斂于全局最優解，其在較小的進化迭代次數內便可接近所測函數的理論全局最優解.

表3 FCBA 的算法尋優結果Tab.3 Results obtained byu singFCBA

表4 BA 的算法尋優結果Tab.4 Results obtained by using BA

圖1 目標函數隨循環次數的變化曲線Fig.1 Changing curve of the objective function value

5 結 論

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

［1］王凌.智能優化算法及其應用［M］.北京：清華大學出版社，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］李兵，蔣慰孫.混沌優化方法及其應用［J］.控制理論與應用，1997，14（4）：613－615.

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

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

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

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

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