一種自適應混沌蜂群優化算法研究?

馬濟喬 李 越 華明宇 許立海

（中國人民解放軍63602部隊 酒泉 735000）

1 引言

近年來，在優化領域中出現了一種新的隨機搜索方法—蜂群算法，它具有全局尋優能力強的優點，被廣泛應用于優化問題。文獻［1］設計了一種混沌局部搜索算子，提高了算法的尋優效率；文獻［2］提出了一種基于改進人工蜂群算法的盲信號分離方法。文獻［3～6］將人工蜂群算法應用到支持向量機的優化中，并取得了很好的優化效果。

雖然人工蜂群算法在優化領域取得了很好的成績，但是其在快搜索到全局最優值時，樣本的多樣性減少，搜索速度減慢，容易陷入局部最優值。為此，本文提出一種自適應混沌蜂群算法，在不影響蜂群算法全局尋優的同時，提高蜂群全局的尋優速度并克服蜂群算法容易陷入局部最優的不足，通過對測試函數尋優結果的對比分析，驗證了該算法的優越性。

2 蜂群算法的基本原理

2.1 蜂群算法

蜜蜂屬于群居昆蟲，單個個體的行為通常比較簡單，但是群體卻表現出了極其復雜的行為。在實際生活中，蜜蜂可以在任何環境下，以一種非常高的效率獲取食物，而且它們能夠隨著環境的變化而改變覓食行為和交流方式。蜂群算法與求解最優問題的對應關系如表1所示。

表1 蜂群算法與求解最優值的關系

在蜂群算法中，蜜源的位置代表了所求優化問題的可行解，蜜源的豐富程度表示可行解的質量。首先初始化N個蜜源（可行解）Xi（i=1，2，…N），每個蜜源將會吸引一個引領蜂，所以N蜜源吸引N個引領蜂，而引領蜂所在的位置即為蜜源的位置。蜜源的個數不會隨著迭代過程的進行而改變。引領蜂在舞蹈區將蜂源的信息同跟隨蜂共享，會吸引大量的跟隨蜂前去采蜜，跟隨蜂的數量和蜜源的適應度有密切的關系，蜜源的適應度越大則被吸引過來的跟隨蜂越多。跟隨蜂將會依據選擇概率來決定去哪個蜜源采蜜，當跟隨蜂到達蜜源之后，對蜜源進行一次鄰域搜索，然后對每個跟隨蜂所搜索的位置進行對比，在引領蜂所對應的跟隨蜂中找到最好的蜜源，并與以前引領蜂所探索的蜜源進行對比，如果比以前的蜜源好，則新位置作為新的蜜源，由引領蜂開采；否則，繼續開采原來的蜜源，并記錄開采次數。以上過程完成了一次迭代，然后所有的蜜源再次吸引引領蜂進行新的一輪開采。當同一個蜜源被開采的次數超過限定的次數后，如果解得質量還沒有得到改善，此時采集該蜜源的引領蜂變成偵查蜂，并且偵查蜂隨機的在解空間中產生一個新的蜜源來代替原來的蜜源。

現實生活中蜜蜂的采蜜過程如圖1所示。

圖1 蜜蜂采蜜過程

蜜蜂的采蜜過程可以簡單地描述如下［7］。

以蜜源1為例，引領蜂采集完花蜜，來到蜂巢的某個區域卸下花蜜之后，將有三種選擇。

1）直接放棄原來開采的蜜源，成為偵查蜂，如圖1中的UF、S路線。

2）在擺尾舞區，引領蜂通過“擺尾舞”與跟隨蜂分享蜜源的相關信息，根據蜜源的適應度吸引一定數量的跟隨蜂前去采蜜，如圖1中的EF1路線。

3）卸下花蜜之后，引領蜂不再招募其他的蜜蜂，繼續回到原來的蜜源采蜜，如圖1中的EF2路線。

在實際生活中，大多數蜜蜂在一次采蜜完成之后都會選擇到擺尾舞區招募更多的跟隨蜂去蜜源采蜜。為了使算法簡單，這里直接選取EF1路線，即引領蜂回到擺尾舞區招募跟隨蜂去蜜源采蜜。

假如已經發現了蜜源1和2，蜜蜂有兩種選擇。

1）開始沒有蜜源信息的情況下，作為偵查蜂在蜂巢附近隨機的尋找蜜源，按照圖1中的S路線進行。

2）如果是在看到引領蜂的“擺尾舞”后，飛到擺尾舞區，被招募到蜜源去采蜜，按照圖1中的R路線進行。

2.2 基本流程

基本蜂群算法的步驟可以描述如下［8～12］。

1）隨機產生Sn個初始解，即隨機產生Sn個蜜源和引領蜂，每一個解 xi(i=1，2，…，Sn)都是一個D維向量，D是優化參數的個數；初始化各個參數，包括蜂群總數、蜜源被開采次數以及同一蜜源的開采極限等。

2）初始化之后，進入采蜜過程。每個蜜源對應一個引領蜂，由引領蜂招募跟隨蜂，跟隨蜂不斷地搜索蜜源，以此來更新引領蜂所處的位置，一次次迭代，直到達到算法終止條件為止。

3）計算每個蜜源的適應度，記錄并保留當前的最優解。引領蜂以一定的概率對記憶中的蜜源位置發生改變，進而找到新的蜜源，并且計算新蜜源的適應度。假如計算出來的適應度大于原蜜源的適應度，則引領蜂將新蜜源的位置代替原蜜源的位置。

4）判斷是否滿足終止條件，若沒有，則轉到步驟2）繼續執行；否則，輸出最優解，結束程序。蜂群算法的流程圖如圖2所示。

跟隨蜂選擇蜜源的概率計算公式為

式中 fi為第i個蜜源的適應度。

引領蜂和跟隨蜂對記憶中的原始解的鄰域進行搜索的公式為

如果蜜源經過一定次數循環后不能被改進，則放棄該蜜源所對應的解。該處的引領蜂變成偵查蜂，然后繼續尋找新的蜜源，其計算公式為

圖2 蜂群算法流程圖

3 自適應混沌蜂群算法

蜂群算法是群體智能算法中比較典型的一種，其自我改進能力和局部搜索能力較強，幾乎能滿足大部分的優化求解問題。相比遺傳和蟻群等智能算法，蜂群算法能很快的搜索到最優值，但是其在快搜索到全局最優值時，樣本的多樣性減少，搜索速度減慢，容易陷入局部最優值。為此，本文提出一種自適應混沌蜂群算法，在不影響蜂群算法全局尋優的同時，提高蜂群全局的尋優速度并克服蜂群算法容易陷入局部最優的不足。

3.1 混沌算法

混沌是一種看似比較凌亂，但實際卻是非常有規則的運動。混沌現象是確定性非線性系統中所特有的一種現象，不需要添加任何隨機因素便可以產生。一個混沌變量同隨機變量一樣，表現的很雜亂，但是它卻可以無重復地遍歷搜索空間內的所有狀態，并且表現出一定的規律性，其體現在變量由確定的迭代方程給出。正是因為混沌的這些特性，使得混沌蜂群算法易跳出局部最優解，是一種很好的搜索機制。

本文采用的Logistic映射就是一種典型的混沌模型，被廣泛應用于各個領域，其方程如下:

當變量a=4的，該模型就完全進入混沌狀態。

混沌算法搜索的步驟如下，

1）將n個初始值分別賦予式（），可以得到n個不同的混沌值。令x*為當前搜索的最優解，則g(x*)為當前最優適應值。

2）利用混沌變量進行搜索。

式中，pj和qj為常數且恒大于零。通過對其值的調整，可以把混沌變量的取值范圍轉換到與其對應的優化變量的取值范圍內。

根據下式計算性能指標量。

3）如果 g(k)＜g(x*)，則 x*=x(k)，循環達到指定的次數便結束；否則，轉到2）繼續進行循環。

混沌優化算法利用其特有的遍歷性，將混沌方法引入到優化變量中，使其進行混沌運動，將混沌運動的范圍限制在優化變量約束范圍內，這樣達到了搜索全局最優的目的。本文將混沌算法引入到基本的ABC算法中，利用混沌算法對蜂群進行初始，形成初始解，并將其應用到ABC算法的搜索后期，使其跳出局部最優解的范圍，從而使ABC算法快速找到全局最優解，提高了該算法的尋優性能。

3.2 自適應混沌蜂群算法的提出

1）混沌初始化

在優化算法中，種群初始化是非常關鍵的一步，因為初始種群將會決定尋優的速度以及解的質量。在沒有先驗知識的前提下，一般采用隨機初始化的方法產生初始解，這樣沒有充分利用解空間的信息，在一定程度上限制了求解的效率。為了使初始解充分利用解空間的信息，本文采用混沌算法產生初始解。在不改變初始解具有隨機性的前提下，充分利用解空間的信息，提高了蜂群的多樣性和搜索的遍歷性。利用混沌算法產生初始解的過程如下:

（1）隨機產生N個初始解，并將其映射到Logistic方程的定義域內；

（2）用Logistic方程進行迭代產生混沌序列；

（3）將產生的混沌序列映射回原來的定義域內；

（4）將兩類初始解進行排序，將適應度較優的解作為種群的初始解。

2）自適應搜索方程

在ABC中，引領蜂和跟隨蜂根據式（2）對記憶中解的鄰域進行搜索，從式中可以看出，跟隨蜂和引領蜂是隨機搜索，沒有方向和范圍，具有一定的盲目性，特別是到了后期，隨著搜索蜜源數量的增加，而搜索范圍沒有改變，導致搜索時間花費較長，收斂較慢。

在ABC中，搜索的新蜜源位置與以前蜜源的位置有一個差值?ij(xij-xkj)，在整個搜索過程中，這個差值都是隨機的，而在實際的搜索過程中，搜索后期，搜索的范圍將減小。為此，提出了自適應步長:

式中，?為隨機系數，取值為1.1～1.5；N為總的迭代次數；t為當前迭代次數。從式（4～7）中可以看出，隨著迭代次數的增加，步長在不斷的減小，達到了減小搜索范圍的效果，有利于提高算法的搜索效率。根據自適應步長，將式（2）改進為

3）混沌搜索過程

蜂群算法在尋優初期，可以快速地接近最優解，但是當進行到搜索后期時，解之間的相似性增強，差距變小，導致算法易陷入局部最優。因此，本文考慮將混沌算法應用到搜索后期，使其跳出局部最優。在搜索后期利用混沌算法在較優蜜源處進行搜索，具體步驟如下:

（1）將蜜源映射到Logistic方程的定義域內；

（2）用Logistic方程進行迭代產生混沌序列；

（3）將產生的混沌序列映射回原來的定義域內，計算其適應度，并與原來的解進行對比；

（4）將最優解保留，判斷是否達到結束條件。若滿足結束條件，則退出；否則轉步驟（2）。

3.3 人口分布尋優分析

將自適應算法和混沌算法引入到人工蜂群算法中，不僅克服了蜂群算法易陷入局部最優的缺點，而且提高了尋優的效率和解的質量。利用ABC算法和HABC算法分別對人口分布進行尋優，結果如圖3～6所示。從圖中可以看出，在算法初期，HABC算法產生的初始種群距最優解較近，分布也比較集中，從整個搜索過程來看，HABC算法搜索速度很快并且搜索到解的質量很高，在搜索進行到第14代時，基本完成了尋優。

圖3 ABC算法和AHABC算法第一代尋優對比

圖4 ABC算法和AHABC算法第三代尋優對比

圖5 ABC算法和AHABC算法第五代尋優對比

圖6 ABC算法和AHABC算法第十代尋優對比

4 仿真分析

4.1 測試函數

為了進一步驗證HABC算法的優越性，選擇以下四個函數來評價算法的性能［13～16］，函數詳細信息如表2所示。

Sphere函數是經典的單峰函數，其全局最優值為0，分布在（0，0）位置處，Sphere函數主要是測試算法的尋優精度；Rosenbrock函數的最優解為0，分布在x=[1，1，…1]處，用來監測算法的尋優速度；Rastrigin函數，全局最優值為0，分布在x=[0，0，…0]處；Griewank函數，當且僅當xi=0時，全局最小值為0。Rastrigin函數和Griewank函數是典型的多模態函數，搜索范圍廣泛，局部最優值多且分布散亂，全局最優值難于搜索，因此用來監測全局搜索能力和跳出局部最優值的能力。四個函數的三維圖如圖7所示。

表2 測試函數

圖7 測試函數

4.2 尋優性能分析

首先對人工分群算法和自適應混沌蜂群算法的參數進行設置，蜂群總數為1000，其中引領蜂和跟隨蜂各500，分別改變維數和迭代次數對以上四個測試函數進行分析。

1）Sphere函數尋優對比

首先在迭代次數相同維數不同的情況下，利用ABC算法和AHABC算法分別對Sphere函數進行尋優搜索，結果如表3所示。

表3 不同維數下Sphere函數的尋優結果

從上表中可以看出，隨著搜索維數的增加，人工蜂群算法和自適應混沌蜂群算法搜索的最優值都越來越接近函數的最優值0，但是，后者搜索的最優值明顯比前者要小很多，提高了算法的精度。圖8是在維數相同迭代次數不同的條件下兩種算法的搜索曲線。

從圖中可以看出，在對Sphere函數進行尋優過程中，ABC算法在迭代600次后開始收斂，而AHABC算法在480次后就開始收斂，表明AHABC算法的搜索速度明顯大于ABC算法，并且搜索到的最優值更接近函數的最優值。

圖8 Sphere函數的尋優曲線

2）Rosenbrock函數尋優對比

首先在迭代次數相同維數不同的情況下，利用人工蜂群算法和自適應混沌蜂群算法分別對Rosenbrock函數進行尋優搜索，搜索結果如表4所示。

表4 不同維數下Rosenbrock函數的尋優結果

從表中可以看出，在迭代次數相同維數不斷增加的情況下，兩種算法搜索的最優值都不斷遠離函數的最優值0，為了驗證算法的搜索速度，在維數相同迭代次數不同的條件下進行尋優，結果如圖9所示。

圖9 Rosenbrock函數的尋優曲線

從圖中看出，在對Rosenbrock函數進行尋優的過程中，ABC算法在迭代400次后開始收斂，而AHABC算法在迭代300次后開始收斂，收斂速度快于ABC算法。AHABC算法搜索到的最優值明顯比ABC算法搜索到的最優值更接近函數的最優值。

3）Rastrigin函數尋優對比

在迭代次數相同維數不同的情況下，兩種算法對Rastrigin的尋優結果如表5所示。

表5 不同維數下Rastrigin函數的尋優結果

從表中可以看出，兩種算法對Rastrigin的尋優結果同Rosenbrock函數類似，都是隨著維數的增加，搜索結果漸漸遠離函數的最優值0。兩種算法在維數相同迭代次數不同的條件下進行尋優，結果如圖10所示。

圖10 Rastrigin函數的尋優曲線

從圖中可以看出，在對Rastrigin函數進行尋優的過程中，兩種算法在迭代300次后都開始收斂，收斂速度相差不大，但是AHABC算法搜索到的最優值與函數的最優值更接近。

4）Griewank函數尋優對比

在迭代次數相同維數不同的條件下，利用人工蜂群算法和自適應混沌蜂群算法對Griewank函數進行搜索，結果如表6所示。

表6 不同維數下Griewank函數的尋優結果

從表中可以看出，隨著維數的增加，兩種算法搜索的最優值越來越接近函數的最優值0，但是，自適應混沌蜂群算法搜索的最優值更接近0，精確度更高。兩種算法在維數相同迭代次數不同的條件下進行尋優，結果如圖11所示。

圖11 Griewank函數的尋優曲線

從圖中可以看出，在對Griewank函數尋優的過程中，ABC算法在迭代400后開始收斂，而AHABC算法在迭代300次后開始收斂，收斂速度明顯快于ABC算法，并且AHABC算法搜索到的最優值更接近函數的最優值。

通過AHABC和ABC對四個函數的尋優結果表明:1）兩種優化算法搜索測試函數的最優值隨著維數的增加而變化；2）在空間維數相同的條件下，兩種優化算法搜索的最優值隨著迭代次數的增加而逐漸減小，最后保持某一固定值不變；3）通過對測試函數的尋優結果不難發現，AHABC算法的搜索速度要快于ABC算法，搜索精度也明顯大于ABC算法。

5 結語

本文在人工蜂群優化算法的基礎上，提出了一種新的優化算法—自適應混沌蜂群算法。利用混沌算法初始化種群，提高了蜂群的多樣性和搜索的遍歷性；提出了一種自適應步長計算方法，提高了算法搜索后期的尋優速度，同時將混沌算法應用到后期蜜源的搜索中，防止算法陷入局部最優。通過對測試函數尋優結果的對比分析，驗證了該算法的優越性。