基于多維更新的改進人工蜂群算法

朱范炳，張 翔

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

2 改進的人工蜂群算法

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

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

3 改進算法驗證及結(jié)果分析

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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