嵌入粒子群優化算法的混合人工蜂群算法

楊琳 孔峰

(廣西工學院電子信息與控制工程系，廣西 柳州 545006)

0 引言

人工蜂群算法(artificial bee colony，ABC)具有控制參數少、計算簡潔、實現方便等特點，已成功應用于函數優化等場合［1-3］。該算法在神經網絡訓練［4］、濾波器設計［5］、網絡優化［6］、機器人路徑規劃［7］、生產調度［8］等工程領域中也取得了很好的優化效果。

與其他智能算法一樣，傳統ABC算法也存在早熟收斂、后期收斂速度變慢的缺點。本文將粒子群優化算法(particle swarm optimization，PSO)引入到傳統ABC算法中，對在預先設定的搜索次數內沒有更新的雇傭蜂，在其現有的位置上拓寬一個范圍，作為粒子群優化算法的搜索空間重新進行搜索。

經典函數的測試結果表明，改進后的算法在收斂速度和搜索精度上均優于傳統ABC算法。

1 人工蜂群算法簡介

在傳統ABC算法中［9-10］，蜂群的智能模型包括:食物源、雇傭蜂和非雇傭蜂，其中非雇傭蜂由觀察蜂和偵察蜂組成。在整個算法迭代過程中，蜂群對食物源的選擇遵循下述原則:食物源(解)被選中的概率取決于所含花蜜的數量，花蜜的數量決定了食物源(解)的優劣;雇傭蜂按照“貪婪”選擇的方式對搜索到的食物源(解)進行選擇;觀察蜂按照概率選擇食物源(解)。

對于全局優化問題，令:

設搜索空間為 D 維，Xi(xi1，xi2，...，xiD)∈S 表示第i個食物源的位置，求解最優解的具體步驟如下。首先，ABC算法生成含有N個食物源(解)的初始群體，每個解 Xi(i=1，2，...，N)是一個 D 維向量;然后蜜蜂對所有的食物源進行循環搜索，直到找到問題的最優解。

雇傭蜂和觀察蜂按照以下公式對食物源進行位置更新:

式中:i∈{1，2，...，N}、j∈{1，2，...，d}為隨機數，且i≠k(k為i鄰域的一個解);Rij∈［-1，1］為隨機數，用于控制xij鄰域的生成范圍。

觀察蜂通過觀看雇傭蜂跳搖擺舞的方式來判斷食物源的收益率，并按照食物源被選中的概率選擇收益率較高的食物源。

收益率通過收益度值表示，選擇概率Pi為:

式中:fiti為第i個解的適應度值。

此外，當某個解在預先設定的搜索次數內沒有更新時，為了防止該解陷入局部極值，偵查蜂根據式(4)隨機產生一個新解來替換該解。

式中:j∈{1，2，…，d}為d維解向量中的某個分量。

2 粒子群優化算法

粒子群優化算法［11-12］(PSO)是模擬鳥群在空間覓食過程中的遷移和群集對優化問題進行求解。

假設在D維空間中有S個粒子，第i個粒子的位置和速度分別為 Xi=(xi1，xi2，...，xiD)和 V=(vi1，vi2，...，viD)。該粒子所經歷的歷史最好位置為 P=(pi1，pi2，...，piD)，整個種群所經歷的最優位置表示為G=(gi1，gi2，...，giD)。

粒子根據以下公式更新其速度和位置:

式中:r1和r2為［0，1］之間的隨機數;c1和c2分別為局部加速因子和全局加速因子;w為慣性權重;k為迭代次數。

粒子的速度更新包括3個組成部分:①當前的速度狀態，即慣性部分;②個體粒子自身的經驗部分，即認知部分;③單個粒子與種群的協同，即社會部分。此外，為使粒子速度不至于過大，通常會設置速度上限Vmax。當Vi＞Vmax時，Vi=Vmax;當 Vi＜-Vmax時，Vi=-Vmax。

3 混合人工蜂群算法

ABC算法和PSO算法均屬于群體智能的啟發式優化算法。ABC算法具有很高的收斂速度，但對局部信息的考慮欠缺，容易陷入局部極值，后期收斂速度會變慢。而PSO算法具有較強的全局搜索性能，可以較好地探索求解區域。

在ABC算法中，某個解連續迭代的次數達到或者超過搜索次數后，相應的雇傭蜂轉為偵查蜂，并重新在整個參數范圍內隨機搜索尋找。由于沒有依據當前解的信息，因此導致新的偵察蜂性能不夠優越。

通過結合PSO算法，既考慮了當前的最優情況，又有全局的探索性，使新偵察蜂在一定范圍內進行了細致的尋找。此時偵察蜂性能卓著，保證了全局優化的順利進行。

混合人工蜂群(particle artificial bee colony，PABC)算法具體實現過程如下。

① 初始化種群。隨機產生 N個初始解xi(1，2，...，N)，其中個解與雇傭蜂一一對應。

②計算雇傭蜂所對應的食物源收益率，并按照式(1)對食物源的位置進行更新。

③雇傭蜂將食物源的信息傳遞給觀察蜂，觀察蜂按照式(3)隨機選擇食物源，并在該食物源的鄰域內搜索新食物源。

④對搜索到的新食物源進行收益率計算。若其值優于舊食物源，則對舊食物源的位置進行更新，并進入步驟⑤;反之繼續搜索。

⑤查看是否滿足設定的最終條件，若不滿足終止條件，則轉向步驟③、④;否則，跳出循環，輸出最終解。

達到搜索次數上限后，雇傭蜂轉為偵查蜂進行粒子群搜索的具體步驟如下。

①根據當前的解定義粒子群的搜索范圍;

②設置最大迭代次數Nmax，隨機初始化每個粒子的速度和位置;

③按照粒子群搜索方式更新粒子的個體最優值和全局歷史最優值;

④判斷是否達到迭代次數，如果沒有轉入步驟②，否則進入步驟⑤;

⑤用新食物源的位置更新原食物源的位置。

4 算法性能分析

為了驗證PABC算法的有效性，本文將PABC算法與基本ABC算法進行試驗比較。在仿真試驗中選取了3個經典測試函數進行測試。

Sphere函數是一個單模態函數，沒有局部極值，只有全局極值，主要用來測試函數的尋優精度和算法的執行能力。Griewank函數是一個復雜的非線性多模態函數，具有很多的局部極小值，通常一般算法都很難找到全局最優解，用來測試算法的全局搜索性能和避免早熟的能力。Rosenbrock函數是一個典型的復雜優化問題，在取值空間內走勢平坦，全局最優點恰好處于拋物線的波谷中，幾乎不可能收斂到全局最優點。一般情況下，Rosenbrock函數主要用來測試算法的收斂速度和執行能力。測試函數表達式、搜索空間和理論全局最優解如 表1所示。

表1 3個標準測試函數Tab.1 Three of the benchmark test functions

本文在固定的迭代次數下，通過采用比較測試函數的平均值、方差、最優值和最差值的方式對各算法進行評價。

算法參數設置如下:種群規模設置為100、雇傭蜂和觀察蜂各為50、測試函數的維數分別為50維和100維、迭代次數為1000。

在PABC算法中，PSO算法參數設置如下:種群規模為24、最大迭代次數為50、局部加速因子c1和全局加速因子c2各為2.0、慣性因子 w為0.8。對每個測試函數連續運行20次，求其平均值。

各函數在不同維數下的平均值、方差、最差值和最優值的比較如表2、表3所示。

表2 測試函數的仿真結果比較(50維)Tab.2 Comparison of the simulation results of benchmark functions(50 dimensions)

表3 測試函數的仿真結果比較(100維)Tab.3 Comparison of the simulation results of benchmark functions(100 dimensions)

Sphere、Griewank和Rosenbrock這3個標準測試函 數的平均適應度曲線如圖1～圖3所示。

圖1 Sphere函數的進化代數曲線Fig.1 The evolution algebra curves of Sphere function

5 結束語

針對人工蜂群算法易陷入局部極值和全局搜索性能不依賴于局部信息的問題，本文結合粒子群優化算法所具有的高效全局搜索性能，提出了基于粒子群優化算法的混合人工蜂群算法(PABC)［13-16］。改進的算法對陷入局部極值的個體使用粒子群搜索策略進行處理，使算法快速跳出局部最優，有效地減少了無用的迭代。試驗結果表明，PABC算法不但保持了基本ABC算法的運算特點，而且成功地解決了基本ABC算法易陷入局部收斂的問題。改進后的算法具有較強的全局收斂性，且優化能力顯著提高。

［1］Karaboga D.Technical Report-TR06［R］.Kayseri:Erciyes Universy，Engineering Faculty，Computer Engineering Department，2005.

［2］Karaboga D，Basturk B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony(ABC)algorithm［J］.Journal of Global Optimization，2007，39(3):459-471.

［3］Karaboga D，Basturk B.On the performance of artificial bee colony(ABC)algorithm［J］.Applied Soft Computing，2008，8(1):687-697.

［4］Karaboga D，Akayb B，Ozturk C.Artificial bee colony(ABC)optimization algorithm for training feed-forward neural network［C］//Proc of Modeling Decisions for Artificial Intelligence Conference，Berlin:Spring-Verlag，2007:318-319.

［5］Karaboga D.A new design method based on artificial bee colony algorithm for digital IIR filters［J］.Journal of the Franklin Institute，2009，346(4):328-348.

［6］Srinivasa R R，Narasimham S V L，Rama L J.Optimization of distribution network configuration for loss reduction using artificial bee colony algorithm［J］.International Journal of Electrical Power and Energy Systems Engineering，2008，10(2):709-715.

［7］胡中華，趙敏.基于人工蜂群算法的機器人路徑規劃［J］.電焊機，2009，39(4):93-96.

［8］李端明，程八一.基于人工蜂群算法求解不同尺寸工件單機批調度問題［J］.四川大學學報:自然科學版，2009，46(3):657-662.

［9］Karaboga D，Basturk B，Ozturk C.Artificial bee colony(ABC)optimization algorithm for solving constrained optimization［C］//Foundations of Fuzzy Logic and Soft Computing，2007:789-798.

［10］羅鈞，樊鵬程.基于遺傳交叉因子的改進蜂群優化算法［J］.計算機應用研究，2009，26(10):3716-3717.

［11］Kennedy J，Eberhart R.Particle swarm optimization［C］//Conf on Neural Networks，Perth，Australia，1995:1942-1948.

［12］Eberhart R，Kennedy J.A new optimizer using particle swarm theory［C］//Porceeding of the Sixth International Symposium on Micro Machine and Human Science，Nagoya，Japan，1995:39-43.

［13］鄭偉，劉靜，曾建潮.人工蜂群算法及其在組合優化中的應用研究［J］.太原科技大學學報:自然科學版，2010，31(6):467-470.

［14］胡中華，趙敏.基于人工蜂群算法的TSP仿真［J］.北京理工大學學報:工學版，2009，29(11):978-981.

［15］楊進，馬良.蜂群優化算法在車輛路徑問題中的應用［J］.計算機工程與應用，2010，46(5):214-216.

［16］肖永豪，余衛宇.基于蜂群算法的圖像邊緣檢測［J］.計算機應用研究，2010，27(7):2748-2749.