蜂群算法在函數(shù)優(yōu)化問題中的應(yīng)用

方群　王慧

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

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

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

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

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

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

1 蜜蜂種群特點(diǎn)

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

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

上面我們大概介紹了蜜蜂婚配的過程及特點(diǎn)，下面我們將進(jìn)一步分析蜜蜂的婚配過程，并以它為基礎(chǔ)，加以適當(dāng)?shù)母纳?，設(shè)計(jì)出適合計(jì)算機(jī)實(shí)現(xiàn)的算法描述。

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

2.1 編碼

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

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

chrom[n][0]= 0110110100 x1

chrom[n][1]= 1101001011 x2

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

2.2 選擇與交叉

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

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

P（D0，D1） = （1）

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

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

prob（Q，D）= （2）

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

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

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

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

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

2.3變異和災(zāi)變

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

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

3 算法實(shí)例測試

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

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

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

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

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

4 總結(jié)

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

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

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

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

參考文獻(xiàn)：

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

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

[3] 高尚，楊靜.群智能算法及其應(yīng)用[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.