基于人工蜂群算法的改進(jìn)研究與實(shí)現(xiàn)

廉德勝, 徐曉鐘, 孫 璐

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

基于人工蜂群算法的改進(jìn)研究與實(shí)現(xiàn)

廉德勝, 徐曉鐘*, 孫 璐

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

參數(shù)的選擇直接影響著最小二乘支持向量機(jī)(LSSVM)的泛化性能和回歸效驗(yàn),是確保LSSVM優(yōu)秀性能的關(guān)鍵.為了解決以上問題,對人工蜂群算法(ABC)進(jìn)行了改進(jìn),引入新解越界處理方法,研究了一種基于雙種群策略的蜂群算法,同時提出提出一種運(yùn)行時參數(shù)調(diào)整方法,然后驗(yàn)證優(yōu)化后的算法IIABC的準(zhǔn)確性與健壯性.燃?xì)饣貧w分析采用平均絕對百分比誤差(MAPE)作為IIABC算法基準(zhǔn)方法,實(shí)驗(yàn)結(jié)果表明基于IIABC-LSSVM預(yù)測結(jié)果比IABC-LSSVM有著更高的準(zhǔn)確性.

最小二乘支持向量機(jī); 人工蜂群算法; 穩(wěn)健性; 平均絕對百分比誤差

0 引 言

在燃?xì)忸A(yù)測研究方面,迄今為止有很多方法被提出,比如傳統(tǒng)分析法、趨勢外推法、回歸分析法、時間序列分析法、時間序列預(yù)測法[1]、人工神經(jīng)網(wǎng)絡(luò)、專家系統(tǒng)、灰色預(yù)測、組合預(yù)測法等等.

2002年,一種基于SVM的新的預(yù)測方法——最小二乘支持向量機(jī)(LSSVM)被提出[2],作為SVM的變體,LSSVM包含了SVM算法的優(yōu)點(diǎn),同時用等式約束代替了不等式約束,求解優(yōu)化問題時,用線性方程組代替二次規(guī)劃問題,因此,這種方法大大簡化了標(biāo)準(zhǔn)SVM的處理過程,并且得到了廣泛的應(yīng)用.

在LSSVM中,存在2個待優(yōu)化參數(shù),即正則化參數(shù)γ,以及核函數(shù)參數(shù)δ2,參數(shù)的選擇對算法的性能起著非常重要的作用,選擇不合適的參數(shù)會導(dǎo)致LSSVM回歸模型過度擬合或擬合不足.因此,隨機(jī)選擇參數(shù)會使傳統(tǒng)經(jīng)驗(yàn)主義方法變得效率低下,將會導(dǎo)致不準(zhǔn)確的實(shí)驗(yàn)結(jié)果,即便如此,傳統(tǒng)人工選擇在參數(shù)調(diào)整方面仍占有一席之地.

研究表明:除了人工選擇方法,在LSSVM參數(shù)調(diào)整中存在2種基本的方法:基于網(wǎng)格搜索的交叉驗(yàn)證(CV)和基于理論技術(shù)方法[3].例如,基于CV-LSSVM的時間序列短期氣象預(yù)測案例[4]運(yùn)用的便是CV算法.但CV需要窮舉搜索特征空間,計(jì)算量過大,實(shí)際操作困難.第二種基于理論分析法包括進(jìn)化算法(EA)、群體智能技(SI).作為EA算法的一個分支,遺傳算法(GA)廣泛應(yīng)用于LSSVM參數(shù)優(yōu)化,除了GA算法,粒子群優(yōu)化算法(PSO)也有著廣泛的應(yīng)用.2005年,提出一種新的群體智能優(yōu)化算法——人工蜂群算法(ABC),該算法具有控制參數(shù)少,簡單靈活,易于實(shí)現(xiàn)等優(yōu)點(diǎn).即便如此,該算法仍有很大的提升空間,相關(guān)文獻(xiàn)表明,算法本身容易陷入局部最優(yōu)的情況.本文作者旨在把改進(jìn)后的ABC應(yīng)用到LSSVM回歸分析中,進(jìn)而提高泛化能力.

1 最小二乘支持向量機(jī)

給定輸入xi,輸出yi,包含N個點(diǎn){xi,yi}的訓(xùn)練集,對于非線性回歸,目標(biāo)模型約束表達(dá)式為:

y(x)=wTφ(xi)+b+ei,i=1,2,…,n.

(1)

式中w為權(quán)重向量,b為偏差,ei為預(yù)測值與真實(shí)值之間的誤差.系數(shù)向量w與b可以通過最優(yōu)問題導(dǎo)出,公式如下:

(2)

式中r為規(guī)則化系數(shù).

對(2)式使用拉格朗日乘數(shù)法后:

(3)

式中,αi為拉格朗日乘子,平衡LSSVM模型復(fù)雜度的一個參數(shù).(3)式滿足KKT條件,并且分別對w,b,ei,αi求偏導(dǎo)置為0:

(4)

(5)

LSSVM回歸模型(1)最后變?yōu)?

(6)

式中α與b就是(5)式的解,對于(6)式核函數(shù)K的選擇有多種選擇,包括Radial Basis Function (RBF),Multilayer Perceptron (MLP),Quadratic Kernel.本文作者選擇RBF核函數(shù),表達(dá)式如下:

(7)

其中σ2為RBF調(diào)整參數(shù),另外一個γ為(2)式的規(guī)則化系數(shù).

2 人工蜂群算法求解最優(yōu)問題

2.1 人工蜂群算法

ABC算法是一個由蜂群行為啟發(fā)的算法,2005年由Karaboga小組[5]為優(yōu)化代數(shù)問題而提出.ABC包含3種蜜蜂:雇傭蜂(employed bees)、觀察蜂(onlooker bees)、偵查蜂(scout bees).其中雇傭蜂與觀察蜂數(shù)量等于蜂群個數(shù)的一半,每一個食物源對應(yīng)一個雇傭蜂.雇傭蜂職責(zé)為尋找食物源也即待最優(yōu)解,之后會對每一食物源的蜂蜜量進(jìn)行評估,然后與觀察蜂共享評估后的食物源,觀察蜂根據(jù)食物源的質(zhì)量去開采合適的食物源,觀察蜂會決定是否放棄當(dāng)前食物源,并且可以把對應(yīng)的雇傭蜂轉(zhuǎn)換成偵查蜂.偵查蜂的職責(zé)是在有價值的食物源(當(dāng)前最優(yōu)解)附近隨機(jī)產(chǎn)生最優(yōu)解.在人工蜂群算法中,假定解向量維數(shù)為D,其中D為待優(yōu)化參數(shù)的個數(shù).人工蜂群算法過程:

2.1.1 初始化階段

初始化食物源通過隨機(jī)解向量邊界取值:

(8)

(9)

2.1.2 雇用蜂階段

雇用蜂與偵查蜂個數(shù)相等,并且,與食物源一一對應(yīng).新解

vij=xij+φij(xkj-xij).

(10)

式中,φij在[-1,1]區(qū)間隨機(jī)取值,xkj為相鄰解,且k≠i.重新計(jì)算新解適應(yīng)度,比較xij與vij適應(yīng)度,取較大適應(yīng)度對應(yīng)的解.

2.1.3 觀察蜂階段

觀察蜂根據(jù)一定概率選擇食物源,概率公式由適應(yīng)度組成:

(11)

觀察蜂階段與雇用蜂相似,但是在雇用蜂階段每個食物源都會被訪問并做進(jìn)一步處理,而在觀察蜂階段只有被選擇的食物源才會使用(10)式產(chǎn)生新解.

2.1.4 偵查蜂階段

在偵查蜂階段,如果當(dāng)前食物源被訪問次數(shù)已超過上限limit,則放棄當(dāng)前食物源,雇用蜂轉(zhuǎn)變成偵查蜂,同時進(jìn)行一次隨機(jī)搜索,如(9)式.

2.2 基于自增種群與局部搜索蜂群算法

文獻(xiàn)[6]提出一種基于自增群體學(xué)習(xí)框架(ISL)與局部搜索過程的新人工蜂群算法變種(IABC-LS),ISL基本思想為:算法輸入包含小規(guī)模群體與新個體.新個體是在每次迭代完成后與最優(yōu)個體交互后產(chǎn)生的,當(dāng)一個新個體即食物源加入到整個環(huán)境后,新個體位置信息被表示為:

(12)

除了應(yīng)用ISL,對人工蜂群算法還有2個重要的修改,在雇用蜂與觀察蜂階段使用當(dāng)前最優(yōu)解替代相鄰解,對(10)式做出以下調(diào)整:

vij=xij+φij(xcbest,j-xij).

(13)

在偵查蜂階段,對新解使用以下公式產(chǎn)生:

(14)

其中,Rfactor代表新解與當(dāng)前最優(yōu)解的距離,公式雖然加了快尋優(yōu)過程,但是卻容易使算法陷入局部最優(yōu)的情況,所以,Rfactor與limit的使用是非常有必要的.IABC算法也可以在每次迭代過程中采用局部搜索(IABC-LS),IABC與IABC-LS在尋優(yōu)領(lǐng)域得到了廣泛的應(yīng)用.

2.3 改進(jìn)蜂群算法

IABC-LS算法雖然提高了ABC的準(zhǔn)確性,但是也使得算法本身復(fù)雜性進(jìn)一步增加,比如算法參數(shù)較多等[7].在此基礎(chǔ)上,對算法本身做了進(jìn)一步的改進(jìn),同時提出了一種動態(tài)參數(shù)調(diào)整方法.

IABC中,雇傭蜂階段使用當(dāng)前最優(yōu)解替代相鄰ABC中隨機(jī)選擇的食物源.為了進(jìn)一步提高算法收斂速度與準(zhǔn)確度,提出了一種基于當(dāng)前最優(yōu)解處理新解越界問題,對于越界的解采用以下處理:

vij=xij+random(-1,1)(xcbest,j-xij).

(15)

其中,xcbest,j為當(dāng)前最優(yōu)解.

IABC算法包含5個待調(diào)整參數(shù),其參數(shù)的選擇對算法的性能起著重要的作用,Rfactor一般設(shè)置較小值,會使算法誤入局部最優(yōu).因此算法運(yùn)行初期,Rfactor應(yīng)該比較大,隨著算法逐漸進(jìn)行,逐漸減小.基于以上問題提出了一種參數(shù)調(diào)整方法,有效地降低算法參數(shù)調(diào)整復(fù)雜度.

在算法運(yùn)行時動態(tài)調(diào)整Rfactor,

(16)

其中,t為初始值,sumSelect為在蜂群算法中對食物源訪問次數(shù)的總和,這樣可以保證在算法運(yùn)行時,隨著尋優(yōu)過程的進(jìn)行,Rfactor由大變小,即可滿足實(shí)際情況.

為了提高算法穩(wěn)健性,提出了一種基于雙種群蜂群算法,即在算法尋優(yōu)過程中并行采用兩個種群進(jìn)行尋優(yōu),尋優(yōu)過程相對獨(dú)立,但在每一迭代完成后,雙種群進(jìn)行一次信息交換,交換方式如下:

minp1=minp1+rn(maxp2-minp1).

(17)

其中,minp1,maxp2分別為雙種群當(dāng)前最優(yōu)解中最小解與最大解,rn為[0,1]之間的隨機(jī)數(shù).

2.4 基于改進(jìn)蜂群算法的LSSVM參數(shù)尋優(yōu)

在采用改進(jìn)后蜂群算法參數(shù)尋優(yōu)的LSSVM中,每一個食物源代表著一個可行解,采用核函數(shù)RBF,在回歸分析中包括2個參數(shù)γ,δ2,同樣地,每一個解的適應(yīng)度值通過平均絕對百分比誤差(MAPE)計(jì)算得到.將LSSVM模型計(jì)算嵌入到改進(jìn)后蜂群算法中,當(dāng)算法迭代完成后,將會得到最優(yōu)參數(shù),即MAPE越小,預(yù)測準(zhǔn)確度越高.

3 算法應(yīng)用與分析

3.1 改進(jìn)算法比較與分析

在IABC基礎(chǔ)之上做出進(jìn)一步改進(jìn),人工蜂群算法作為優(yōu)化算法,基準(zhǔn)函數(shù)的使用可以有效體現(xiàn)算法的準(zhǔn)確性,采用經(jīng)典Rastrigin作為適應(yīng)度評價函數(shù),并以此為對比,比較改進(jìn)蜂群算法(IIABC)與IABC.實(shí)驗(yàn)數(shù)據(jù)如下:最小種群為10,最大種群為50;limit=100;解向量維度為100;最大環(huán)循次數(shù)為2 500;實(shí)驗(yàn)結(jié)果如圖1所示.

圖1 IIABC實(shí)驗(yàn)圖

實(shí)驗(yàn)結(jié)果表明:基于雙總?cè)篒ABC算法準(zhǔn)確性以及穩(wěn)健性都要優(yōu)于IABC.同時表明,人工蜂群算法作為近年來新興起啟發(fā)式算法有著廣闊的應(yīng)用前景.

3.2 基于LSSVM算法比較與分析

3.2.1 樣本數(shù)據(jù)描述

采用上海市燃?xì)庳?fù)荷數(shù)據(jù)作為實(shí)驗(yàn)樣本,其中采用最小溫度、最大溫度、平均溫度以及天氣狀況作為樣本輸入,輸出為燃?xì)庳?fù)荷.對于實(shí)驗(yàn)數(shù)據(jù),其中80%作為訓(xùn)練樣本,其余20%作為測試樣本.

3.2.2 樣本歸一化與評價準(zhǔn)則

在進(jìn)行實(shí)驗(yàn)之前,對實(shí)驗(yàn)數(shù)據(jù)采用歸一化預(yù)處理,把每一個特征空間歸一化到[0,1]空間,這樣會避免數(shù)據(jù)最小值遠(yuǎn)遠(yuǎn)小于最大值.同時為了評價實(shí)驗(yàn)性能,通常采用2個準(zhǔn)則:MAPE與RMSE(Root Mean Square Percentage Error).采用MAPE作為評價準(zhǔn)則.

3.2.3 實(shí)驗(yàn)結(jié)果

IIABC-LSSVM使用LSSVM-Matlab Toolbox實(shí)現(xiàn),其中IIABC/IABC參數(shù)取值為:初始種群為20,最大總?cè)簽?0,D=2,limit=100;表1為采用以上數(shù)據(jù)的實(shí)驗(yàn)結(jié)果.從表1可以看出:使用IIABC-LSSVM作為預(yù)測模型得出γ=875.23和δ2=78.72.與之相關(guān)聯(lián)MAPE僅為10.2999%,與IABC-LSSVM相比更小,即IIABC-LSSVM預(yù)測模型準(zhǔn)確度大于IABC-LSSVM模型的準(zhǔn)確度.

表1 燃?xì)庳?fù)荷預(yù)測

4 總 結(jié)

本文作者利用LSSVM算法,針對參數(shù)的選擇問題,提出了一種基于IIABC的LSSVM參數(shù)優(yōu)化,實(shí)現(xiàn)了燃?xì)庳?fù)荷預(yù)測.具體工作如下:首先,為了進(jìn)一步提高IABC算法的準(zhǔn)確性與穩(wěn)健性,根據(jù)IABC基本原理,引入了新解越界處理方法,并研究了一種基于雙種群策略的蜂群算法,同時提出一種運(yùn)行時參數(shù)調(diào)整方法.其次,針對LSSVM參數(shù)優(yōu)化問題,將改進(jìn)后的IIABC應(yīng)用到LSSVM參數(shù)優(yōu)化,避免了參數(shù)選擇的盲目性,并為燃?xì)庳?fù)荷預(yù)測提供了理論依據(jù).最后,采用IABC參數(shù)選擇LSSVM和基于IIABC的LSSVM進(jìn)行實(shí)驗(yàn),通過比較驗(yàn)證了IIABC的優(yōu)化作用,并證明了本方法的優(yōu)越性.

[1] 唐舟進(jìn),任峰,彭濤,等.基于迭代誤差補(bǔ)償?shù)幕煦鐣r間序列最小二乘支持向量機(jī)預(yù)測算法 [J].物理學(xué)報,2014,63(5):050505.

Tang Z J,Ren F,Peng T,et al.A least square support vector machine prediction algorithm for chaotic time series based on the iterative error correction [J].Acta Physica Sinica,2014,63(5):050505.

[2] Suykens J A K,Gestel T V,Brabanter J D,et al.Least-squares support vector machines[M].Singapore:World Scientifics,2002.

[3] Afshin M,Sadeghian A,Raahemifar K.On efficient tuning of lssvm hyper-parameters in short-term load forecasting:a comparative study [C].Procedings of the IEEE Power Engineering Society General Meeting,Tampa:IEEE,2007.

[4] Mellit A,Massi Pavan A,Benghanem M.Least squares support vector machine for shortterm prediction of meteorological time series [J].Theory Application Climatology,2013,111(1):297-307.

[5] Karaboga D.An idea based on honey bee swarm for numerical optimization [R].Kayseri:Erciyes University,2005.

[6] Aydin D,Liao T J,Oca M A M D,et al.Improving performance via population growth and local search:the case of the artificial bee colony algorithm [C].International Conference on Artificial Evolution,2011,7401(6):85-96.

[7] Aydin D,?zy?n S,Yasar C.Artificial bee colony algorithm with dynamic population size to combined economic and emission dispatch problem [J].Electrical Power and Energy Systems,2014,54:144-153.

(責(zé)任編輯：包震宇)

Improvement and implementation of algorithmbased on artificial bee colony

Lian Desheng, Xu Xiaozhong*, Sun Lu

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

Selection of the hyper-parameters is critical to the performance of Least Squares Support Vector Machines (LSSVM),directly impacting the generalization and regression efficacy of the LSSVM.In order to solve the problem above,this paper based on ABC has done certain researches and improvement (IIABC) which have been applied to the LSSVM regression analysis.In this paper,the Artificial Bee Colony (ABC) Algorithm is improved,introducing a new cross processing method,studying a ABC based on double population policy,and putting forward a run-time parameter adjustment method,and then the robustness and accuracy of the optimized IIABC are verified.Experiment adopts MAPE as the benchmark IIABC algorithm for gas regression analysis,and shows that forecasting based on the IIABC-LSSVM is of higher accuracy than the IABC-LSSVM.

LSSVM; ABC; robustness; MAPE

2015-09-09

廉德勝(1990-),男,碩士研究生,主要從事機(jī)器學(xué)習(xí)方面的研究.E-mail:632953014@qq.com

導(dǎo)師簡介: 徐曉鐘(1968-),男,高級工程師,主要從事人工智能數(shù)據(jù)挖掘以及計(jì)算機(jī)軟件架構(gòu)設(shè)計(jì)方面的研究.E-mail:xxz_edu@shnu.edu.cn

TP 391.9

A

1000-5137(2017)02-0200-06

*通信作者