一種自適應(yīng)混沌蜂群優(yōu)化算法研究?

馬濟(jì)喬 李 越 華明宇 許立海

（中國(guó)人民解放軍63602部隊(duì) 酒泉 735000）

1 引言

近年來(lái)，在優(yōu)化領(lǐng)域中出現(xiàn)了一種新的隨機(jī)搜索方法—蜂群算法，它具有全局尋優(yōu)能力強(qiáng)的優(yōu)點(diǎn)，被廣泛應(yīng)用于優(yōu)化問(wèn)題。文獻(xiàn)［1］設(shè)計(jì)了一種混沌局部搜索算子，提高了算法的尋優(yōu)效率；文獻(xiàn)［2］提出了一種基于改進(jìn)人工蜂群算法的盲信號(hào)分離方法。文獻(xiàn)［3～6］將人工蜂群算法應(yīng)用到支持向量機(jī)的優(yōu)化中，并取得了很好的優(yōu)化效果。

雖然人工蜂群算法在優(yōu)化領(lǐng)域取得了很好的成績(jī)，但是其在快搜索到全局最優(yōu)值時(shí)，樣本的多樣性減少，搜索速度減慢，容易陷入局部最優(yōu)值。為此，本文提出一種自適應(yīng)混沌蜂群算法，在不影響蜂群算法全局尋優(yōu)的同時(shí)，提高蜂群全局的尋優(yōu)速度并克服蜂群算法容易陷入局部最優(yōu)的不足，通過(guò)對(duì)測(cè)試函數(shù)尋優(yōu)結(jié)果的對(duì)比分析，驗(yàn)證了該算法的優(yōu)越性。

2 蜂群算法的基本原理

2.1 蜂群算法

蜜蜂屬于群居昆蟲(chóng)，單個(gè)個(gè)體的行為通常比較簡(jiǎn)單，但是群體卻表現(xiàn)出了極其復(fù)雜的行為。在實(shí)際生活中，蜜蜂可以在任何環(huán)境下，以一種非常高的效率獲取食物，而且它們能夠隨著環(huán)境的變化而改變覓食行為和交流方式。蜂群算法與求解最優(yōu)問(wèn)題的對(duì)應(yīng)關(guān)系如表1所示。

表1 蜂群算法與求解最優(yōu)值的關(guān)系

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

現(xiàn)實(shí)生活中蜜蜂的采蜜過(guò)程如圖1所示。

圖1 蜜蜂采蜜過(guò)程

蜜蜂的采蜜過(guò)程可以簡(jiǎn)單地描述如下［7］。

以蜜源1為例，引領(lǐng)蜂采集完花蜜，來(lái)到蜂巢的某個(gè)區(qū)域卸下花蜜之后，將有三種選擇。

1）直接放棄原來(lái)開(kāi)采的蜜源，成為偵查蜂，如圖1中的UF、S路線(xiàn)。

2）在擺尾舞區(qū)，引領(lǐng)蜂通過(guò)“擺尾舞”與跟隨蜂分享蜜源的相關(guān)信息，根據(jù)蜜源的適應(yīng)度吸引一定數(shù)量的跟隨蜂前去采蜜，如圖1中的EF1路線(xiàn)。

3）卸下花蜜之后，引領(lǐng)蜂不再招募其他的蜜蜂，繼續(xù)回到原來(lái)的蜜源采蜜，如圖1中的EF2路線(xiàn)。

在實(shí)際生活中，大多數(shù)蜜蜂在一次采蜜完成之后都會(huì)選擇到擺尾舞區(qū)招募更多的跟隨蜂去蜜源采蜜。為了使算法簡(jiǎn)單，這里直接選取EF1路線(xiàn)，即引領(lǐng)蜂回到擺尾舞區(qū)招募跟隨蜂去蜜源采蜜。

假如已經(jīng)發(fā)現(xiàn)了蜜源1和2，蜜蜂有兩種選擇。

1）開(kāi)始沒(méi)有蜜源信息的情況下，作為偵查蜂在蜂巢附近隨機(jī)的尋找蜜源，按照?qǐng)D1中的S路線(xiàn)進(jìn)行。

2）如果是在看到引領(lǐng)蜂的“擺尾舞”后，飛到擺尾舞區(qū)，被招募到蜜源去采蜜，按照?qǐng)D1中的R路線(xiàn)進(jìn)行。

2.2 基本流程

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

1）隨機(jī)產(chǎn)生Sn個(gè)初始解，即隨機(jī)產(chǎn)生Sn個(gè)蜜源和引領(lǐng)蜂，每一個(gè)解 xi(i=1，2，…，Sn)都是一個(gè)D維向量，D是優(yōu)化參數(shù)的個(gè)數(shù)；初始化各個(gè)參數(shù)，包括蜂群總數(shù)、蜜源被開(kāi)采次數(shù)以及同一蜜源的開(kāi)采極限等。

2）初始化之后，進(jìn)入采蜜過(guò)程。每個(gè)蜜源對(duì)應(yīng)一個(gè)引領(lǐng)蜂，由引領(lǐng)蜂招募跟隨蜂，跟隨蜂不斷地搜索蜜源，以此來(lái)更新引領(lǐng)蜂所處的位置，一次次迭代，直到達(dá)到算法終止條件為止。

3）計(jì)算每個(gè)蜜源的適應(yīng)度，記錄并保留當(dāng)前的最優(yōu)解。引領(lǐng)蜂以一定的概率對(duì)記憶中的蜜源位置發(fā)生改變，進(jìn)而找到新的蜜源，并且計(jì)算新蜜源的適應(yīng)度。假如計(jì)算出來(lái)的適應(yīng)度大于原蜜源的適應(yīng)度，則引領(lǐng)蜂將新蜜源的位置代替原蜜源的位置。

4）判斷是否滿(mǎn)足終止條件，若沒(méi)有，則轉(zhuǎn)到步驟2）繼續(xù)執(zhí)行；否則，輸出最優(yōu)解，結(jié)束程序。蜂群算法的流程圖如圖2所示。

跟隨蜂選擇蜜源的概率計(jì)算公式為

式中 fi為第i個(gè)蜜源的適應(yīng)度。

引領(lǐng)蜂和跟隨蜂對(duì)記憶中的原始解的鄰域進(jìn)行搜索的公式為

如果蜜源經(jīng)過(guò)一定次數(shù)循環(huán)后不能被改進(jìn)，則放棄該蜜源所對(duì)應(yīng)的解。該處的引領(lǐng)蜂變成偵查蜂，然后繼續(xù)尋找新的蜜源，其計(jì)算公式為

圖2 蜂群算法流程圖

3 自適應(yīng)混沌蜂群算法

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

3.1 混沌算法

混沌是一種看似比較凌亂，但實(shí)際卻是非常有規(guī)則的運(yùn)動(dòng)?；煦绗F(xiàn)象是確定性非線(xiàn)性系統(tǒng)中所特有的一種現(xiàn)象，不需要添加任何隨機(jī)因素便可以產(chǎn)生。一個(gè)混沌變量同隨機(jī)變量一樣，表現(xiàn)的很雜亂，但是它卻可以無(wú)重復(fù)地遍歷搜索空間內(nèi)的所有狀態(tài)，并且表現(xiàn)出一定的規(guī)律性，其體現(xiàn)在變量由確定的迭代方程給出。正是因?yàn)榛煦绲倪@些特性，使得混沌蜂群算法易跳出局部最優(yōu)解，是一種很好的搜索機(jī)制。

本文采用的Logistic映射就是一種典型的混沌模型，被廣泛應(yīng)用于各個(gè)領(lǐng)域，其方程如下:

當(dāng)變量a=4的，該模型就完全進(jìn)入混沌狀態(tài)。

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

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

2）利用混沌變量進(jìn)行搜索。

式中，pj和qj為常數(shù)且恒大于零。通過(guò)對(duì)其值的調(diào)整，可以把混沌變量的取值范圍轉(zhuǎn)換到與其對(duì)應(yīng)的優(yōu)化變量的取值范圍內(nèi)。

根據(jù)下式計(jì)算性能指標(biāo)量。

3）如果 g(k)＜g(x*)，則 x*=x(k)，循環(huán)達(dá)到指定的次數(shù)便結(jié)束；否則，轉(zhuǎn)到2）繼續(xù)進(jìn)行循環(huán)。

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

3.2 自適應(yīng)混沌蜂群算法的提出

1）混沌初始化

在優(yōu)化算法中，種群初始化是非常關(guān)鍵的一步，因?yàn)槌跏挤N群將會(huì)決定尋優(yōu)的速度以及解的質(zhì)量。在沒(méi)有先驗(yàn)知識(shí)的前提下，一般采用隨機(jī)初始化的方法產(chǎn)生初始解，這樣沒(méi)有充分利用解空間的信息，在一定程度上限制了求解的效率。為了使初始解充分利用解空間的信息，本文采用混沌算法產(chǎn)生初始解。在不改變初始解具有隨機(jī)性的前提下，充分利用解空間的信息，提高了蜂群的多樣性和搜索的遍歷性。利用混沌算法產(chǎn)生初始解的過(guò)程如下:

（1）隨機(jī)產(chǎn)生N個(gè)初始解，并將其映射到Logistic方程的定義域內(nèi)；

（2）用Logistic方程進(jìn)行迭代產(chǎn)生混沌序列；

（3）將產(chǎn)生的混沌序列映射回原來(lái)的定義域內(nèi)；

（4）將兩類(lèi)初始解進(jìn)行排序，將適應(yīng)度較優(yōu)的解作為種群的初始解。

2）自適應(yīng)搜索方程

在ABC中，引領(lǐng)蜂和跟隨蜂根據(jù)式（2）對(duì)記憶中解的鄰域進(jìn)行搜索，從式中可以看出，跟隨蜂和引領(lǐng)蜂是隨機(jī)搜索，沒(méi)有方向和范圍，具有一定的盲目性，特別是到了后期，隨著搜索蜜源數(shù)量的增加，而搜索范圍沒(méi)有改變，導(dǎo)致搜索時(shí)間花費(fèi)較長(zhǎng)，收斂較慢。

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

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

3）混沌搜索過(guò)程

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

（1）將蜜源映射到Logistic方程的定義域內(nèi)；

（2）用Logistic方程進(jìn)行迭代產(chǎn)生混沌序列；

（3）將產(chǎn)生的混沌序列映射回原來(lái)的定義域內(nèi)，計(jì)算其適應(yīng)度，并與原來(lái)的解進(jìn)行對(duì)比；

（4）將最優(yōu)解保留，判斷是否達(dá)到結(jié)束條件。若滿(mǎn)足結(jié)束條件，則退出；否則轉(zhuǎn)步驟（2）。

3.3 人口分布尋優(yōu)分析

將自適應(yīng)算法和混沌算法引入到人工蜂群算法中，不僅克服了蜂群算法易陷入局部最優(yōu)的缺點(diǎn)，而且提高了尋優(yōu)的效率和解的質(zhì)量。利用ABC算法和HABC算法分別對(duì)人口分布進(jìn)行尋優(yōu)，結(jié)果如圖3～6所示。從圖中可以看出，在算法初期，HABC算法產(chǎn)生的初始種群距最優(yōu)解較近，分布也比較集中，從整個(gè)搜索過(guò)程來(lái)看，HABC算法搜索速度很快并且搜索到解的質(zhì)量很高，在搜索進(jìn)行到第14代時(shí)，基本完成了尋優(yōu)。

圖3 ABC算法和AHABC算法第一代尋優(yōu)對(duì)比

圖4 ABC算法和AHABC算法第三代尋優(yōu)對(duì)比

圖5 ABC算法和AHABC算法第五代尋優(yōu)對(duì)比

圖6 ABC算法和AHABC算法第十代尋優(yōu)對(duì)比

4 仿真分析

4.1 測(cè)試函數(shù)

為了進(jìn)一步驗(yàn)證HABC算法的優(yōu)越性，選擇以下四個(gè)函數(shù)來(lái)評(píng)價(jià)算法的性能［13～16］，函數(shù)詳細(xì)信息如表2所示。

Sphere函數(shù)是經(jīng)典的單峰函數(shù)，其全局最優(yōu)值為0，分布在（0，0）位置處，Sphere函數(shù)主要是測(cè)試算法的尋優(yōu)精度；Rosenbrock函數(shù)的最優(yōu)解為0，分布在x=[1，1，…1]處，用來(lái)監(jiān)測(cè)算法的尋優(yōu)速度；Rastrigin函數(shù)，全局最優(yōu)值為0，分布在x=[0，0，…0]處；Griewank函數(shù)，當(dāng)且僅當(dāng)xi=0時(shí)，全局最小值為0。Rastrigin函數(shù)和Griewank函數(shù)是典型的多模態(tài)函數(shù)，搜索范圍廣泛，局部最優(yōu)值多且分布散亂，全局最優(yōu)值難于搜索，因此用來(lái)監(jiān)測(cè)全局搜索能力和跳出局部最優(yōu)值的能力。四個(gè)函數(shù)的三維圖如圖7所示。

表2 測(cè)試函數(shù)

圖7 測(cè)試函數(shù)

4.2 尋優(yōu)性能分析

首先對(duì)人工分群算法和自適應(yīng)混沌蜂群算法的參數(shù)進(jìn)行設(shè)置，蜂群總數(shù)為1000，其中引領(lǐng)蜂和跟隨蜂各500，分別改變維數(shù)和迭代次數(shù)對(duì)以上四個(gè)測(cè)試函數(shù)進(jìn)行分析。

1）Sphere函數(shù)尋優(yōu)對(duì)比

首先在迭代次數(shù)相同維數(shù)不同的情況下，利用ABC算法和AHABC算法分別對(duì)Sphere函數(shù)進(jìn)行尋優(yōu)搜索，結(jié)果如表3所示。

表3 不同維數(shù)下Sphere函數(shù)的尋優(yōu)結(jié)果

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

從圖中可以看出，在對(duì)Sphere函數(shù)進(jìn)行尋優(yōu)過(guò)程中，ABC算法在迭代600次后開(kāi)始收斂，而AHABC算法在480次后就開(kāi)始收斂，表明AHABC算法的搜索速度明顯大于ABC算法，并且搜索到的最優(yōu)值更接近函數(shù)的最優(yōu)值。

圖8 Sphere函數(shù)的尋優(yōu)曲線(xiàn)

2）Rosenbrock函數(shù)尋優(yōu)對(duì)比

首先在迭代次數(shù)相同維數(shù)不同的情況下，利用人工蜂群算法和自適應(yīng)混沌蜂群算法分別對(duì)Rosenbrock函數(shù)進(jìn)行尋優(yōu)搜索，搜索結(jié)果如表4所示。

表4 不同維數(shù)下Rosenbrock函數(shù)的尋優(yōu)結(jié)果

從表中可以看出，在迭代次數(shù)相同維數(shù)不斷增加的情況下，兩種算法搜索的最優(yōu)值都不斷遠(yuǎn)離函數(shù)的最優(yōu)值0，為了驗(yàn)證算法的搜索速度，在維數(shù)相同迭代次數(shù)不同的條件下進(jìn)行尋優(yōu)，結(jié)果如圖9所示。

圖9 Rosenbrock函數(shù)的尋優(yōu)曲線(xiàn)

從圖中看出，在對(duì)Rosenbrock函數(shù)進(jìn)行尋優(yōu)的過(guò)程中，ABC算法在迭代400次后開(kāi)始收斂，而AHABC算法在迭代300次后開(kāi)始收斂，收斂速度快于ABC算法。AHABC算法搜索到的最優(yōu)值明顯比ABC算法搜索到的最優(yōu)值更接近函數(shù)的最優(yōu)值。

3）Rastrigin函數(shù)尋優(yōu)對(duì)比

在迭代次數(shù)相同維數(shù)不同的情況下，兩種算法對(duì)Rastrigin的尋優(yōu)結(jié)果如表5所示。

表5 不同維數(shù)下Rastrigin函數(shù)的尋優(yōu)結(jié)果

從表中可以看出，兩種算法對(duì)Rastrigin的尋優(yōu)結(jié)果同Rosenbrock函數(shù)類(lèi)似，都是隨著維數(shù)的增加，搜索結(jié)果漸漸遠(yuǎn)離函數(shù)的最優(yōu)值0。兩種算法在維數(shù)相同迭代次數(shù)不同的條件下進(jìn)行尋優(yōu)，結(jié)果如圖10所示。

圖10 Rastrigin函數(shù)的尋優(yōu)曲線(xiàn)

從圖中可以看出，在對(duì)Rastrigin函數(shù)進(jìn)行尋優(yōu)的過(guò)程中，兩種算法在迭代300次后都開(kāi)始收斂，收斂速度相差不大，但是AHABC算法搜索到的最優(yōu)值與函數(shù)的最優(yōu)值更接近。

4）Griewank函數(shù)尋優(yōu)對(duì)比

在迭代次數(shù)相同維數(shù)不同的條件下，利用人工蜂群算法和自適應(yīng)混沌蜂群算法對(duì)Griewank函數(shù)進(jìn)行搜索，結(jié)果如表6所示。

表6 不同維數(shù)下Griewank函數(shù)的尋優(yōu)結(jié)果

從表中可以看出，隨著維數(shù)的增加，兩種算法搜索的最優(yōu)值越來(lái)越接近函數(shù)的最優(yōu)值0，但是，自適應(yīng)混沌蜂群算法搜索的最優(yōu)值更接近0，精確度更高。兩種算法在維數(shù)相同迭代次數(shù)不同的條件下進(jìn)行尋優(yōu)，結(jié)果如圖11所示。

圖11 Griewank函數(shù)的尋優(yōu)曲線(xiàn)

從圖中可以看出，在對(duì)Griewank函數(shù)尋優(yōu)的過(guò)程中，ABC算法在迭代400后開(kāi)始收斂，而AHABC算法在迭代300次后開(kāi)始收斂，收斂速度明顯快于ABC算法，并且AHABC算法搜索到的最優(yōu)值更接近函數(shù)的最優(yōu)值。

通過(guò)AHABC和ABC對(duì)四個(gè)函數(shù)的尋優(yōu)結(jié)果表明:1）兩種優(yōu)化算法搜索測(cè)試函數(shù)的最優(yōu)值隨著維數(shù)的增加而變化；2）在空間維數(shù)相同的條件下，兩種優(yōu)化算法搜索的最優(yōu)值隨著迭代次數(shù)的增加而逐漸減小，最后保持某一固定值不變；3）通過(guò)對(duì)測(cè)試函數(shù)的尋優(yōu)結(jié)果不難發(fā)現(xiàn)，AHABC算法的搜索速度要快于ABC算法，搜索精度也明顯大于ABC算法。

5 結(jié)語(yǔ)

本文在人工蜂群優(yōu)化算法的基礎(chǔ)上，提出了一種新的優(yōu)化算法—自適應(yīng)混沌蜂群算法。利用混沌算法初始化種群，提高了蜂群的多樣性和搜索的遍歷性；提出了一種自適應(yīng)步長(zhǎng)計(jì)算方法，提高了算法搜索后期的尋優(yōu)速度，同時(shí)將混沌算法應(yīng)用到后期蜜源的搜索中，防止算法陷入局部最優(yōu)。通過(guò)對(duì)測(cè)試函數(shù)尋優(yōu)結(jié)果的對(duì)比分析，驗(yàn)證了該算法的優(yōu)越性。