嵌入粒子群優(yōu)化算法的混合人工蜂群算法

楊琳 孔峰

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

0 引言

人工蜂群算法(artificial bee colony，ABC)具有控制參數(shù)少、計算簡潔、實現(xiàn)方便等特點，已成功應(yīng)用于函數(shù)優(yōu)化等場合［1-3］。該算法在神經(jīng)網(wǎng)絡(luò)訓(xùn)練［4］、濾波器設(shè)計［5］、網(wǎng)絡(luò)優(yōu)化［6］、機器人路徑規(guī)劃［7］、生產(chǎn)調(diào)度［8］等工程領(lǐng)域中也取得了很好的優(yōu)化效果。

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

經(jīng)典函數(shù)的測試結(jié)果表明，改進后的算法在收斂速度和搜索精度上均優(yōu)于傳統(tǒng)ABC算法。

1 人工蜂群算法簡介

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

對于全局優(yōu)化問題，令:

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

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

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

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

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

式中:fiti為第i個解的適應(yīng)度值。

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

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

2 粒子群優(yōu)化算法

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

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

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

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

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

3 混合人工蜂群算法

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

在ABC算法中，某個解連續(xù)迭代的次數(shù)達到或者超過搜索次數(shù)后，相應(yīng)的雇傭蜂轉(zhuǎn)為偵查蜂，并重新在整個參數(shù)范圍內(nèi)隨機搜索尋找。由于沒有依據(jù)當(dāng)前解的信息，因此導(dǎo)致新的偵察蜂性能不夠優(yōu)越。

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

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

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

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

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

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

⑤查看是否滿足設(shè)定的最終條件，若不滿足終止條件，則轉(zhuǎn)向步驟③、④;否則，跳出循環(huán)，輸出最終解。

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

①根據(jù)當(dāng)前的解定義粒子群的搜索范圍;

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

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

④判斷是否達到迭代次數(shù)，如果沒有轉(zhuǎn)入步驟②，否則進入步驟⑤;

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

4 算法性能分析

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

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

表1 3個標(biāo)準(zhǔn)測試函數(shù)Tab.1 Three of the benchmark test functions

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

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

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

各函數(shù)在不同維數(shù)下的平均值、方差、最差值和最優(yōu)值的比較如表2、表3所示。

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

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

Sphere、Griewank和Rosenbrock這3個標(biāo)準(zhǔn)測試函 數(shù)的平均適應(yīng)度曲線如圖1～圖3所示。

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

5 結(jié)束語

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

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

［8］李端明，程八一.基于人工蜂群算法求解不同尺寸工件單機批調(diào)度問題［J］.四川大學(xué)學(xué)報:自然科學(xué)版，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］羅鈞，樊鵬程.基于遺傳交叉因子的改進蜂群優(yōu)化算法［J］.計算機應(yīng)用研究，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］鄭偉，劉靜，曾建潮.人工蜂群算法及其在組合優(yōu)化中的應(yīng)用研究［J］.太原科技大學(xué)學(xué)報:自然科學(xué)版，2010，31(6):467-470.

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

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

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