方群　王慧

摘要：函數(shù)優(yōu)化是算法應用中的基本問題，蜂群算法作為遺傳算法與生物種群習性特征相結(jié)合的新算法，比較適合于此類問題的求解。本文首先對蜂群算法進行了簡單的描述，設計出基于蜜蜂婚配過程的計算機實現(xiàn)的同等模型。使用實例測試蜂群算法的運行效果，并將其結(jié)果與基本遺傳算法的結(jié)果進行比較。實驗結(jié)果表明，蜂群算法全局搜索能力強，具有較快較好的發(fā)現(xiàn)最優(yōu)解的能力。

關鍵詞：蜂群算法；遺傳算法；函數(shù)優(yōu)化

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2016）19-0149-03

Bee Colony Algorithm for Function Optimization

FANG Qun， WANG Hui

（ Bengbu Navy Petty Office Academy，Bengbu 233012， China）

Abstract： Function Optimization is a basic problem in algorithm application. Bee Colony Algorithm is a combines generation algorithm and biological characteristics new algorithm. It is best of solution function optimization problem. A simple description of Bee Colony Algorithm is being in the article front. The corresponding model based bees marriage of computer is designed by us. The result of Bee Colony Algorithm is text by the function example. The experiment results show that using this algorithm in function optimization has better ability of global search and discovering best solution .

Key words：bee colony algorithm； generationalgorithm； function optimization

在人工智能的遺傳算法領域中，有許多算法是通過對一些社會性昆蟲的模擬而產(chǎn)生的，通過模擬螞蟻的行為而產(chǎn)生的蟻群算法就是基于群體的成功的優(yōu)化算法，此方法在解決許多復雜的組合問題中是成功的，研究和發(fā)展的前景也很好[1]。眾所周知，蜜蜂和螞蟻都是智能程度很高的物種，但目前為止，還很少有人試圖模擬蜜蜂的生活過程并將其中好的智能模式運用于優(yōu)化和搜索之中。在本文中，我們就介紹和分析這種發(fā)展于蜜蜂的婚配過程的蜂群算法。

遺傳算法是在達爾文的進化論和孟德爾的遺傳學基礎上提出的一種優(yōu)化求解算法。它通過對原始的基因組進行編碼，再選擇、交叉、變異等操作，進行整體性的信息交換，依據(jù)適者生存的原則，逐步淘汰種群差的特性。遺傳算法在函數(shù)優(yōu)化問題上取得比較好的效果[2]。

本文提出了一種通過模擬蜜蜂的婚配過程而產(chǎn)生的基于二進制編碼的蜂群算法。并在函數(shù)優(yōu)化問題上進行了仿真實驗，實驗結(jié)果證實了蜂群算法的有效性和可行性。

1 蜜蜂種群特點

蜂群算法是受到對蜜蜂的婚配行為的研究的啟發(fā)而提出的一種搜索優(yōu)化算法[3]。為了清楚地說明蜂群算法的原理，我們先大概地介紹一下蜜蜂的種群特點及婚配過程。

蜜蜂作為一種社會性昆蟲，有嚴格的社會分工，每個普通的蜜蜂群體都是由蜂后、雄蜂、工蜂和幼蜂組成。在蜜蜂的種群中，雌性的成蜂有蜂后和工蜂，蜂后代表著主要的具有繁殖能力的個體，并且專職于產(chǎn)卵，工蜂專職于幼蜂的撫育但有時也產(chǎn)卵。雄性的成蜂只有雄蜂，它是整個群體的警衛(wèi)和父親。但是與其他物種所不同的是：雄蜂的精子是單倍體，也就是說在精子中對下一代的基因起作用的遺傳物質(zhì)只有一般細胞的一半。幼蜂發(fā)育于受精的或未受精的卵細胞，前者可能發(fā)育成蜂后或工蜂，而后者則將發(fā)育成為未來的雄蜂。蜂后在婚飛的過程中完成精子的采集。蜂后在空中起舞就標志著婚飛的開始，隨后跟隨蜂后而來的雄蜂就與其在空中進行交配。在一次典型的婚飛中，每只蜂后要與7到20只雄蜂交配。在每次交配中，雄蜂的精子到達蜂后的受精囊并聚集在那兒以形成整個群體的基因池。每次當一只蜂后要產(chǎn)下一顆受精卵時，它隨機地從受精囊中挑出精子使之與卵子結(jié)合。[4]

上面我們大概介紹了蜜蜂婚配的過程及特點，下面我們將進一步分析蜜蜂的婚配過程，并以它為基礎，加以適當?shù)母纳疲O計出適合計算機實現(xiàn)的算法描述。

2 本文求解函數(shù)優(yōu)化的步驟

2.1 編碼

在遺傳算法的運行過程中，它不對所求問題的實際決策變量直接進行操作，而是對表示可行解的個體編碼施加選擇、交叉和變異等遺傳操作。將一個問題的可行解從其可行解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法稱為編碼[5]。典型的遺傳算法都采用二進制的編碼方式，在本文中我們也采用這種與自然界中的實際情況相對應的編碼方式。但是在多個變量的情況下，傳統(tǒng)的整體編碼是用一個一維數(shù)組來按順序存放所有的基因。這樣的編碼方式明顯地存在著問題：隨著自變量維數(shù)的增加或求解精度要求的提高，整個位串的長度會迅速地增加，這樣，整個位串的長度將變得難以忍受，不方便操作；此外，一旦位串過長，將不可避免地導致重復操作，而且由于位串過長，還會降低雜交和變異操作的結(jié)果，致使算法易陷于局部最優(yōu)或增加運行時間。

為了解決這些問題，我們采用一種改進的二進制編碼方式 ——獨立編碼方式。它將每個變量都相互獨立開來，采用多維的數(shù)組來表示多維的變量，用獨立編碼方式就表示為：x1=0110110100，x2=1101001011

chrom[n][0]= 0110110100 x1

chrom[n][1]= 1101001011 x2

實驗表明，獨立編碼較整體編碼具有良好的收斂性，能使函數(shù)較好地逼近于極值。原因主要在于當雜交和變異概率不變時，原始的整體編碼由于精度要求，導致位串過長，而其中相當大的一部分位串只表示小數(shù)點后的數(shù)值，所以若雜交和變異算子作用在這一部分上，則對數(shù)值的改變不大。而獨立編碼由于大大縮短了位串長度，所以使得雜交和變異算子有很大可能作用到代表小數(shù)點以前的數(shù)值位串上，致使自變量的數(shù)值有較大改變。這就能使算法有效地跳出局部最優(yōu)解陷阱，更好地接近全局最優(yōu)解。

2.2 選擇與交叉

蜂后以一定的速率穿梭于空間中的不同區(qū)域，并在各個區(qū)域內(nèi)隨機地與碰到的雄蜂進行交配。在婚飛的開始，給蜂后賦予一定量的能量，在能量消耗到零或某一限度時或在受精囊裝滿時返回蜂巢。

雄蜂提供給后代一半的基因，因此保證雄蜂的高適應度也有利于產(chǎn)生適應度較高的幼蜂。為此，我們使用一個模擬的退火算法[6]來對雄蜂進行選擇。按照退火算法的原理，令當前的雄蜂為 D0，隨機產(chǎn)生下一個用于交配的雄蜂為 D1，如果f （D1）≥f （D0）則D1被接受為當前雄蜂（f（D）表示雄蜂 D的適應度 ），準備與蜂后交配。否則 D1僅以概率：

P（D0，D1） = （1）

被接受。S（t）表示蜂后在t時刻的速率，隨著時間的推移，S（t）的值會越來越小，則接受不良個體的概率也就越來越小，所以總能保持雄蜂的高適應度。

雄蜂與蜂后交配的隨機率用下式表示：

prob（Q，D）= （2）

此處，prob（Q，D）是將D的精子加入到蜂后Q的受精囊的概率，也就是指交配成功的概率；⊿f（t）是 D的適應度f（D）與Q的適應度f（Q）的絕對差值；S（t）表示蜂后在t時刻的速率。

表面上看來這個函數(shù)有些類似退火算法，當蜂后在剛開始婚飛因而速率很大時或是雄蜂的適應度和蜂后的一樣高時，交配的概率很大。隨著時間的推移，蜂后的速率和能量以下面的方式衰減：

S（t+1）=α*S（t） （3）

E（t+1）=E（t）-r （4）

此處，α是一個因子， α∈[0，1]；r是每次轉(zhuǎn)移后能量的消耗量。

2.3變異和災變

自然界中的變異率是進化的動力，只有通過變異率才能使后代產(chǎn)生前代沒有的特性，為進化提供條件。同時變異率設置得是否合適對于算法的表現(xiàn)也有很大的影響。如果變異率太小則某位的有效基因可能經(jīng)過好多代的進化都不會出現(xiàn)，算法容易陷入局部解中；如果變異率設得太大則經(jīng)常變異容易丟失一些有效基因，反而倒喪失了啟發(fā)性而變得更像隨機搜索。一般情況下，變異率設在0.0001～0.1就比較合適了。

在自然界中，有時會因為環(huán)境的突然性的巨大變化而使物種發(fā)生很大的改變，這時原有的基因平衡被打破，創(chuàng)造出完全不同的染色體，生物的性狀發(fā)生很大的變化。將這種思想應用于我們的蜂群算法中，有利于進化跳出局部極值點，快速、準確地搜索出全局最優(yōu)解。但是，災變率的選擇也不是任意的，它應該根據(jù)具體的情況而合理地設定。多次實驗的結(jié)果表明：選擇災變率的標準是要在整個的進化過程中保證發(fā)生1到2次的災變。否則，若災變率設得太小，可能整個進化完成后都沒有發(fā)生一次災變，也就喪失了設置災變率的意義；若災變率太高，則多次的反復災變就很容易丟失經(jīng)過多代進化積累起來的有利基因組合。

3 算法實例測試

為了體現(xiàn)蜂群算法的效果，分析解決問題的有效性，本文使用Rosenbrock函數(shù)作為測試函數(shù)，并將結(jié)果與基本遺傳算法進行了比較，結(jié)果表明：蜂群算法能以較小的幼代數(shù)目、較小的進化代數(shù)得到比基本遺傳算法高得多的命中率搜索出最優(yōu)解。

在以下的測試中，基本遺傳算法的運行參數(shù)為：群體大?。篗=80；終止代數(shù)：T=200；交叉概率：Pc=0.6；變異概率：Pm=0.001。蜂群算法的運行參數(shù)為：群體大小：M=15；終止代數(shù)：T=60；變異概率：Pm=0.001；災變概率：Pd=0.002。Rosenbrock函數(shù)的全局最大值計算：

max f（ χ1， χ2 ）=100（ χ12 -χ2 ） 2 +（1-χ1） 2（-2.048≤χ1，χ2 ≤2.048） （5）

如圖 1所示，該函數(shù)有兩個局部極大點，分別是f（-2.048，2.048）=3897.73，和 f（-2.048，-2.048）=3905.93，其中后者為全局最大點。

由上面的測試結(jié)果可知，蜂群算法比基本遺傳算法能更快、更準確地收斂到全局最優(yōu)解，命中率較高。蜂群算法的性能明顯高于基本遺傳算法，能快速準確地搜索出全局最優(yōu)解，是生物模型與計算機模型的較好的結(jié)合，是對于遺傳算法的成功的改進。

4 總結(jié)

本文使用獨立的編碼方式使得染色體的變化不過多地局限于小數(shù)點后一些對結(jié)果影響不大的位，使染色體的變化在解的空間上能有較大的跨越，加快了向局部解收斂的速度。

災變的應用使算法能突發(fā)性地從局部最優(yōu)解跳出，重新選擇方向，向著全局最優(yōu)解的方向進化，使得算法能較準確地搜索出全局最優(yōu)解。

總體上說，蜂群算法是個與傳統(tǒng)的遺傳算法很不一樣的過程，它的結(jié)果只強調(diào)于每一代中的一個最優(yōu)個體，好像是針對性偏強，卻在反映物種多樣性上偏弱，但是正是因為它的針對性較強，將目標緊緊地盯住全局最優(yōu)解，所以才能快速、準確地搜索出全局最優(yōu)解。此外，該算法很靈活，在雄蜂的選擇、蜂后與雄蜂交配的概率、工蜂對幼蜂的撫育作用這些地方都可以針對不同的問題而使用不同的選擇標準或啟發(fā)函數(shù)，具有很大的發(fā)展空間。

而且蜂群算法中也存在著一般遺傳算法沒有出現(xiàn)過的特殊現(xiàn)象：一般的遺傳算法每代的平均適應度會隨著進化代數(shù)的疊加而不斷提高，而蜂群算法卻不一樣，它每代的平均適應度是不受代數(shù)影響的，有時可能保持好多代都不變，有時甚至會減小。而這種現(xiàn)象的產(chǎn)生也是由蜂群算法的特點所決定的。因為在進化到一定程度時，蜂后在不斷地進化，雄蜂也在不斷地進化，可能當前的蜂后和雄蜂都是當時最好的，所以它們可能是一代中許多幼蜂的父母或者甚至是以后好多代的父母，相同的基因產(chǎn)生的初始幼蜂當然相同，而且可能每個幼蜂經(jīng)過變異后的基因都不如當前的情況，所以蜂群就好像陷入了一個停滯不前的情況了，許多代的平均適應值都是一樣的。而平均適應度的減小則是因為蜜蜂的單倍體交叉特性，可能蜂后和雄蜂的適應度都是高的，可經(jīng)過單倍體交叉后，恰好雄蜂染色體中的有利基因被標記了，而蜂后在對應標記位上的基因是不利的，所以產(chǎn)生的幼代的適應度反而會降低。

參考文獻：

[1] 胡中華，趙敏.基于人工蜂群算法的機器人路徑規(guī)劃[J].電焊機，2009（39）：4.

[2] 丁海軍，李峰磊.蜂群算法在TSP問題上的應用及參數(shù)改進[J].中國科技信息，2008（3）.

[3] 高尚，楊靜.群智能算法及其應用[M].北京：中國水利水電出版社，2006：58-63.

[4] Karaboga D，Basturk B.Onthe performance of Artificial Bee Colony （ABC） algorithm[J].Applied Soft Computing Journal，2007（5）.

[5] MouloudKoudil， KarimaBenatchba. Using artificial bees to solve partitioning and scheduling problems in codesign[J].Applied Mathematics and Computation，2007：186.

[6] Afshar A， Bozorg Haddad O. Honey-bee mating optimization （HBMO） algorithm for optimal reservoir operation[J].Journal of the Franklin Institute，2007：344.