基于多維更新的改進(jìn)人工蜂群算法

朱范炳，張 翔

（信陽(yáng)學(xué)院 大數(shù)據(jù)與人工智能學(xué)院，河南 信陽(yáng) 464000）

0 引言

群體智能和仿生計(jì)算算法以其良好的通用性、容錯(cuò)性以及對(duì)初始解不敏感等優(yōu)點(diǎn)，成為優(yōu)化問(wèn)題的有效工具。最初是源于對(duì)群體組織和生物活動(dòng)行為的研究分析，繼之而來(lái)地就陸續(xù)提出了遺傳算法、差分進(jìn)化算法、粒子群算法和蟻群算法等經(jīng)典的智能算法。2005 年，Karaboga受蜂群自組織模型啟發(fā)，提出了人工蜂群算法（Artificial Bee Colony，ABC），并將其應(yīng)用于函數(shù)值優(yōu)化問(wèn)題中。相對(duì)其他智能算法而言，ABC 算法有著設(shè)置參數(shù)少、執(zhí)行簡(jiǎn)單、工程應(yīng)用性很強(qiáng)的特點(diǎn)。然而，作為一種新興的搜索優(yōu)化算法，其理論研究仍有待改進(jìn)和完善。文獻(xiàn)［3-4］分別引用大鄰域搜索和對(duì)比機(jī)制改進(jìn)算法信息共享時(shí)的全局性。文獻(xiàn)［5］提出用非線性遞減選擇策略代替輪盤(pán)賭策略。文獻(xiàn)［6-8］分別通過(guò)學(xué)習(xí)經(jīng)驗(yàn)、采蜜蜂搜索策略和偵察蜂搜索策略來(lái)改進(jìn)算法。文獻(xiàn)［9］引入差分進(jìn)化思想增加解的多樣性。這些改進(jìn)方法雖然在一定程度上降低了算法陷入局部最優(yōu)的可能，但是收斂速度和精度卻仍未達(dá)到令人滿意效果。在此基礎(chǔ)上，本文提出在解的搜索過(guò)程中，隨機(jī)選取多維同時(shí)更新的策略，改進(jìn)標(biāo)準(zhǔn)人工蜂群算法，加快算法收斂。

1 標(biāo)準(zhǔn)人工蜂群算法

人工蜂群算法是一種模擬蜜蜂采蜜、尋找優(yōu)良蜜源時(shí)的群體組織行為的仿生計(jì)算方法，是基于自由搜索的群體智能算法。通過(guò)迭代進(jìn)化，進(jìn)行目標(biāo)問(wèn)題解的尋優(yōu)，算法能夠以較大的概率找到全局最優(yōu)解。

人工蜂群算法的基本原理：設(shè)有個(gè)蜜源｛，，…，x｝，每個(gè)蜜源x（1，2，…，）有個(gè)分量，即待優(yōu)化問(wèn)題的解空間包含個(gè)可行解，每個(gè)可行解是維向量。設(shè)定蜂群循環(huán)搜索的最大次數(shù)和每個(gè)蜜源的可重復(fù)開(kāi)采次數(shù)，同一蜜源開(kāi)采超過(guò)可重復(fù)開(kāi)采次數(shù)則放棄該蜜源。標(biāo)準(zhǔn)的人工蜂群算法包括以下階段：

（1）蜂群的初始化階段。對(duì)于任一解x的任一分量x（1，2，…，）都進(jìn)行初始化，可表示為：

其中，x和x分別表示可行解空間第維分量的上、下限，（0，1）為［0，1］之間的隨機(jī)數(shù)。

（2）采蜜蜂搜索階段。采蜜蜂在初始階段的蜜源附近，通過(guò)式（2）搜索產(chǎn)生一個(gè)新解，作為候選蜜源進(jìn)行開(kāi)采。式（2）的數(shù)學(xué)表述可寫(xiě)為：

其中，∈｛1，2，…，｝，≠表示在個(gè)蜜源中隨機(jī)選取一個(gè)不同于x的蜜源，決定采蜜蜂更新位置的擾動(dòng)幅度。

計(jì)算新解的適應(yīng)度fit，并進(jìn)行適應(yīng)度大小評(píng)價(jià)，在v和x之中采用貪婪策略進(jìn)行選擇。最后，采蜜蜂會(huì)記錄蜜源信息和適應(yīng)度值。

（3）觀察蜂跟隨階段。所有采蜜蜂完成搜索后會(huì)把解的信息及適應(yīng)度分享給觀察蜂。觀察蜂通過(guò)選擇概率P決定每只采蜜蜂被跟隨的概率，對(duì)此可分別表示如下：

觀察蜂使用輪盤(pán)賭策略選擇采蜜蜂跟隨。如果采蜜蜂對(duì)應(yīng)蜜源的選擇概率值較大，就會(huì)被更多的觀察蜂跟隨，即適應(yīng)度較大的蜜源附近會(huì)有更多的觀察蜂搜索，蜜源對(duì)應(yīng)解的鄰域搜索范圍更廣。若新解的適應(yīng)度比之前的好，觀察蜂將會(huì)用新解更新上一次迭代的解；反之，觀察蜂會(huì)將之前的解保留，同時(shí)解的迭代搜索次數(shù)也會(huì)加1。

（4）偵察蜂階段。所有觀察蜂完成跟隨搜索后，如果某一蜜源在被搜索可重復(fù)開(kāi)采次數(shù)后仍未被更新，則認(rèn)為該蜜源已被開(kāi)采枯竭，對(duì)應(yīng)的解陷入局部最優(yōu)。相應(yīng)的采蜜蜂和觀察蜂就會(huì)放棄該蜜源，轉(zhuǎn)換為偵察蜂模式，進(jìn)行全局隨機(jī)搜索，尋找一個(gè)新的蜜源代替被舍棄的蜜源，這是人工蜂群算法跳出局部最優(yōu)的有效手段。重復(fù)循環(huán)搜索，最終找到目標(biāo)問(wèn)題的最優(yōu)解。

2 改進(jìn)的人工蜂群算法

標(biāo)準(zhǔn)人工蜂群算法中，采蜜蜂在更新解時(shí)采用的是逐維更新的策略，即搜索一個(gè)多維解時(shí)，每次只更新一個(gè)維度就會(huì)計(jì)算適應(yīng)度值，或者在每一代的搜索中只隨機(jī)選取一維更新，最后完成每一維的更新。當(dāng)函數(shù)維度不斷增加時(shí)，單維搜索算法在解的搜索過(guò)程中，對(duì)于在個(gè)別維度上出現(xiàn)較優(yōu)值而沒(méi)有得到繼續(xù)挖掘的解，有可能達(dá)到蜜源可重復(fù)開(kāi)采次數(shù)的搜索限制而被廢棄，之后由偵察蜂重新隨機(jī)搜索，這將會(huì)導(dǎo)致算法錯(cuò)過(guò)很多達(dá)到全局最優(yōu)的機(jī)會(huì)，增加了收斂時(shí)間，同時(shí)也影響了最終求解的精度。借鑒鄰域更新算子和主成分維度更新的想法，本文將公式（2）中更新一個(gè)維度替換為同時(shí)更新個(gè)不同維度，由不同優(yōu)化問(wèn)題的解的維度數(shù)而定，即得到新的更新公式（5）：

研究可知，這樣就可有效地避免單維更新的局限性，增加個(gè)別維度上出現(xiàn)的較優(yōu)解被繼續(xù)挖掘的概率，減少了收斂時(shí)間，加大了算法的搜索力度，提高了解的搜索空間。

3 改進(jìn)算法驗(yàn)證及結(jié)果分析

為了驗(yàn)證改進(jìn)人工蜂群算法的有效性，提升算法性能，本文采用Ackley、Griewank、Schaffer 和Sphere 4 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)做尋優(yōu)測(cè)試實(shí)驗(yàn)。

在實(shí)驗(yàn)中，蜜蜂的種群規(guī)模設(shè)置為40，算法的最大循環(huán)次數(shù)為3 000，蜜源的可重復(fù)開(kāi)采次數(shù)為300。對(duì)每個(gè)測(cè)試函數(shù)取解的維度30，每次結(jié)果由10 次實(shí)驗(yàn)平均所得，記錄10 次的均值和求取到最優(yōu)值的平均迭代次數(shù)。實(shí)驗(yàn)結(jié)果數(shù)據(jù)見(jiàn)表1。

表1 測(cè)試結(jié)果數(shù)據(jù)統(tǒng)計(jì)Tab.1 Data statistics of test results

由表1 中數(shù)據(jù)可知，對(duì)于不同的測(cè)試函數(shù)，收斂速度加快了大約為300～500 次迭代；特別是對(duì)于Schaffer 函數(shù)，其收斂速度加快了約1 000次迭代，且改進(jìn)算法的求解精度也有較為明顯的改善。

圖1～圖4 是4 個(gè)測(cè)試函數(shù)在標(biāo)準(zhǔn)ABC 算法和改進(jìn)的ABC 算法（IABC）尋優(yōu)過(guò)程中，函數(shù)的優(yōu)化值隨搜索迭代次數(shù)的變化趨勢(shì)。明顯地看出，改進(jìn)的ABC 算法優(yōu)化函數(shù)值變化曲線更加陡峭，變化趨勢(shì)幅度更大、更快，即改進(jìn)的人工蜂群算法收斂速度更快。

圖1 Ackley 測(cè)試函數(shù)結(jié)果對(duì)比圖Fig.1 Comparison diagram of Ackley

圖2 Griewank 測(cè)試函數(shù)結(jié)果對(duì)比圖Fig.2 Comparison diagram of Griewank

圖3 Schaffer 測(cè)試函數(shù)結(jié)果對(duì)比圖Fig.3 Comparison diagram of Schaffer

圖4 Sphere 測(cè)試函數(shù)結(jié)果對(duì)比圖Fig.4 Comparison diagram of Sphere

4 結(jié)束語(yǔ)

本文提出一種基于多維更新的改進(jìn)人工蜂群算法，即在解的搜索過(guò)程中，采取隨機(jī)選擇多個(gè)維度同時(shí)更新的策略。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的人工蜂群算法能夠顯著地加快算法的收斂速度，收斂值更加趨近測(cè)試函數(shù)的最優(yōu)值。