基于改進(jìn)人工蜂群算法的支持向量機(jī)時(shí)序預(yù)測*

劉 棟, 李 素, 曹志冬

(1.北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院 食品安全大數(shù)據(jù)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室,北京 100048; 2.中國科學(xué)院 自動化研究所 復(fù)雜系統(tǒng)管理與控制國家重點(diǎn)實(shí)驗(yàn)室,北京 100190)

0 引 言

支持向量機(jī)(support vector machine,SVM)[1]，有效克服了非線性、過學(xué)習(xí)和局部極小值等問題;在眾多領(lǐng)域的理論分析和實(shí)際應(yīng)用中取得巨大成功，一度被公認(rèn)為是機(jī)器學(xué)習(xí)領(lǐng)域的最佳算法。核參數(shù)尋優(yōu)對于SVM具有決定性影響，現(xiàn)有優(yōu)化方法[3～5]仍存在難以規(guī)避的問題。相比其他智能算法，人工蜂群[6](artificial bee colony ,ABC) 算法獨(dú)有角色分工轉(zhuǎn)換機(jī)制能平衡算法的全局和局部搜索，較大程度地?cái)[脫局部最優(yōu)，增大全局最優(yōu)解的獲取機(jī)率，且算法易實(shí)現(xiàn)、搜索精度高、控制參數(shù)少、魯棒性強(qiáng)，但受限于自身進(jìn)化方式和選擇策略，實(shí)際應(yīng)用中有待進(jìn)一步加強(qiáng)[6，7]。粒計(jì)算是海量信息處理的一種新的計(jì)算范式，使大數(shù)據(jù)背景下復(fù)雜性、模糊性問題及滿意近似解的研究逐漸成型，如模糊信息?；碚揫8](theory of fuzzy information granulation,TFIG)。

本文通過改進(jìn)各分工蜂群的搜索機(jī)制進(jìn)行SVM參數(shù)尋優(yōu)，并引入信息?；夹g(shù)進(jìn)行上證指數(shù)變化趨勢和變化空間的建模預(yù)測來證明所提出方法的優(yōu)越性。

1 支持向量回歸

(1)

(2)

式中K(xi,x)為核函數(shù)，在線性不可分的情況下引入。

2 經(jīng)典ABC算法

設(shè)原問題解空間維數(shù)是D，j∈{1,2,…,D}。搜索開始，引領(lǐng)蜂根據(jù)式(3)進(jìn)行領(lǐng)域搜索并更新食物源位置

vij=xij+φ(xij-xkj)

(3)

式中j為隨機(jī)整數(shù)，k∈{1,…,NP}且k≠i，代表從NP個(gè)食物源中隨機(jī)選取一個(gè)不等于i的食物源，φ～U(-1,1)決定xij鄰域的取值范圍。當(dāng)新食物源Vi=[vi1,…，vij]優(yōu)于Xi，貪婪選擇將Vi代替Xi；否則，保持Xi不變。待所有引領(lǐng)蜂已完成搜索和更新，立即進(jìn)入信息交換區(qū)以搖擺舞的方式分享食物源信息。跟隨蜂根據(jù)既得食物源信息，參照一定概率Pi并按輪盤賭來選擇跟隨引領(lǐng)蜂，首先在區(qū)間[0,1]上生成一個(gè)服從均勻分布的隨機(jī)數(shù)r，若Pi>r，按式(3)進(jìn)行鄰域搜索，并以與引領(lǐng)蜂相同的貪婪選擇策略確定要保留的食物源(或解)

(4)

式中fiti為解的適應(yīng)度值評價(jià)，通常為最小化優(yōu)化問題

(5)

3 基于改進(jìn)ABC算法的TFIG-SVR框架

3.1 經(jīng)典ABC算法的改進(jìn)

(6)

(7)

3.2 TFIG-SVR技術(shù)優(yōu)越性的理論推導(dǎo)

對SVM引入TFIG構(gòu)建TFIG-SVR，并進(jìn)行幾何論證：1)基于原始樣本空間進(jìn)行粒劃分并在每個(gè)粒上進(jìn)行支持向量訓(xùn)練,實(shí)現(xiàn)將非線性問題轉(zhuǎn)化為若干線性可分問題,來獲得一系列決策函數(shù)；2)這種學(xué)習(xí)策略增強(qiáng)了模型的泛化能力和擬合精度，有利于回歸預(yù)測[9，10]；如圖1，傳統(tǒng)SVR將整個(gè)樣本特征空間用一個(gè)連續(xù)回歸超平面F擬合，而GSVR則把特征空間劃分為一系列子空間,然后基于子空間構(gòu)建SVR來獲得回歸超平面F*，根據(jù)統(tǒng)計(jì)學(xué)及不敏感損失函數(shù)理論，F(xiàn)*相比F具有間隔更寬的超平面。因此，GSVR機(jī)制增強(qiáng)了模型的擬合精度，降低了算法時(shí)間復(fù)雜度，抑制過學(xué)習(xí)而獲得了更強(qiáng)的泛化能力，另外，擬合過程的可并行實(shí)現(xiàn)又進(jìn)一步提高了學(xué)習(xí)效率。其中，三角型模糊粒子可用于多決策性問題，因此,本文采用Pedrycz W所提出的三角形模糊集信息?；椒╗11]來構(gòu)建TFIG-SVM模型。

圖1 TFIG-SVR擬合示意

3.3 TFIG-SVR設(shè)計(jì)

文獻(xiàn)[2,3,9,10,12]表明：高斯核即徑向基核函數(shù)(radial basis function,RBF)，具有優(yōu)良的非線性擬合性能，其參數(shù)包括：σ表征核的寬度(核函數(shù)徑向作用范圍)；C控制分類或回歸超平面復(fù)雜程度和異常點(diǎn)數(shù)間的平衡，影響模型泛化性能；ε描述決策函數(shù)對預(yù)測誤差不敏感區(qū)域的寬度，即真實(shí)值與預(yù)測值的差落在預(yù)定區(qū)間內(nèi)，則認(rèn)為無損失；反之，則有損失。本文采用改進(jìn)ABC算法對SVR進(jìn)行參數(shù)優(yōu)化，并將SVR預(yù)測值的均方誤差作為目標(biāo)函數(shù)：minf(C,σ,ε)，得TFIG-SVR及其算法流程如圖2。

1)參數(shù)初始化。ABC算法基本參數(shù)設(shè)置、最大、最小慣性權(quán)重Wmax和Wmin以及適應(yīng)度函數(shù)如式(5)，fi為預(yù)測值與真實(shí)值的均方根誤差； SVR相關(guān)參數(shù)元組(C,σ,ε)。

2)引入Pedrycz W模糊粒化方法處理原始數(shù)據(jù)，使Low,Mean,Up為三角型模糊粒子的參數(shù),代表樣本數(shù)據(jù)變化趨勢的支撐下限、核和支撐上限。

3)利用改進(jìn)ABC算法進(jìn)行參數(shù)尋優(yōu)。將參數(shù)三元組(C,σ,ε)抽象為食物源，通過C，σ和ε取值重新初始化蜂群，使引領(lǐng)蜂和跟隨蜂按式(6)和式(7)搜索，并按經(jīng)典ABC算法步驟執(zhí)行和跳轉(zhuǎn)，直到滿足算法結(jié)束條件，來獲得最佳參數(shù)元組(C,σ,ε)best，嵌入SVR對?；瘮?shù)據(jù)進(jìn)行回歸預(yù)測。

圖2 基于改進(jìn)人工蜂群算法的TFIG-SVR

3.4 模型時(shí)間復(fù)雜度計(jì)算

本文將構(gòu)建網(wǎng)格搜索(gridsearch)[2]、粒子群優(yōu)化(PSO)算法[3]、遺傳算法(GA)[4]、蟻群優(yōu)化(ACO)算法[5]和人工蜂群算法的SVR模型(設(shè)為x-SVR表1作為對照實(shí)驗(yàn)，將SVR時(shí)間復(fù)雜度統(tǒng)一設(shè)為定值O(f(n))，那么x-SVR時(shí)間復(fù)雜度僅須比較其核心智能算法。其中采用文獻(xiàn)[2]中網(wǎng)格搜索算法，其時(shí)間復(fù)雜度可粗略估計(jì)為O(n3)。設(shè)NCircle為進(jìn)化代數(shù)，n為種群規(guī)模，D為決策變量的維數(shù)，當(dāng)n→D得表 1。其中，改進(jìn)ABC算法時(shí)間復(fù)雜度與D無關(guān)僅取決于n；如果n足夠大，低次冪項(xiàng)可忽略，那么改進(jìn)ABC算法與其經(jīng)典算法相比，幾乎不需要額外付出時(shí)間耗費(fèi)，另外，蟻群算法時(shí)間復(fù)雜度最高。

表1 x-SVR模型時(shí)間復(fù)雜度比較

4 實(shí)例應(yīng)用與分析

收集上證指數(shù)1990年12月19日～2016年1月14日所有交易數(shù)據(jù)，包括收盤指數(shù)、指數(shù)最高值、指數(shù)最低值、當(dāng)日交易量、當(dāng)日交易額，預(yù)測后續(xù)5個(gè)交易日收盤指數(shù)的變化趨勢和變化空間如表2。

表2 2016年1月15日至2016年1月21日上證實(shí)際收盤指

4.1 實(shí)驗(yàn)參數(shù)設(shè)定

1)gridsearch-SVR的懲罰參數(shù)C和核參數(shù)γ的設(shè)定，學(xué)術(shù)界并未明確限定，但C過高會陷入過學(xué)習(xí)，所以,本實(shí)驗(yàn)設(shè)定為[-8,8]和[-8,8](取以2為底的冪指數(shù)值)，步距為1，相當(dāng)于進(jìn)化兩代；2)考慮到樣本數(shù)據(jù)規(guī)模較大，將PSO-SVR、ABC-SVR、改進(jìn)ABC-SVR、GA-SVR和ACO-SVR相同參數(shù)設(shè)置為：種群進(jìn)化代數(shù)為200，種群規(guī)模為20，損失函數(shù)ε的取值范圍為(0,1]，核函數(shù)相關(guān)參數(shù)γ的取值范圍為(0,1]，罰參數(shù)C的取值范圍(0,100]，其余參數(shù)均按算法最優(yōu)性能設(shè)定；3)權(quán)重參數(shù)設(shè)定，最大慣性權(quán)重Wmax和最小慣性權(quán)重Wmin參照文獻(xiàn)[13]設(shè)定。

4.2 實(shí)驗(yàn)結(jié)果分析

將引入TFIG的PSO-SVR、ABC-SVR、改進(jìn)ABC-SVR、GA-SVR和ACO-SVR用于上證收盤指數(shù)預(yù)測，得到x-SVR模型2016年1月15日～21日收盤指變化空間結(jié)果如表 3。改進(jìn)ABC-SVR預(yù)測所得收盤指數(shù)變化空間與表2中實(shí)際收盤指數(shù)最為接近，其次是PSO-SVR，ABC-SVR，GA-SVR，gridsearch-SVR，ACO-SVR表現(xiàn)最差，甚至產(chǎn)生了支撐預(yù)測空間支撐下限大于支撐上限的預(yù)測錯誤。

表3 x-SVR模型最終預(yù)測結(jié)果比較

上限參數(shù)Up是證券收盤指數(shù)預(yù)測最為核心的評價(jià)指標(biāo)，由圖3上限參數(shù)Up預(yù)測值的均方根誤差隨進(jìn)化代數(shù)的變化可看出，ACO-SVR產(chǎn)生的誤差值最大，預(yù)測精度不高，相比其他預(yù)測模型存在較大差距，說明蟻群算法不適合連續(xù)型時(shí)間序列預(yù)測與分析。改進(jìn)ABC-SVR均方根誤差最小，預(yù)測精度最高，其次依次為PSO-SVR，ABC-SVR，GA-SVR。在收斂速率上，PSO-SVR在算法早期率先達(dá)到穩(wěn)定狀態(tài)，但后期收斂速率變慢；GA-SVR相對于其他算法明顯早熟，進(jìn)化40代后進(jìn)入成熟狀態(tài)，對新空間的探測能力極為有限，且模型不穩(wěn)定，易陷入局部最優(yōu)；而改進(jìn)的ABC-SVR和ABC-SVR初期算法進(jìn)化過程相似，但改進(jìn)ABC-SVR比ABC-SVR收斂速度更快，預(yù)測精度更高，且更早成熟。

圖3 上證收盤指數(shù)預(yù)測迭代

為進(jìn)一步對比x-SVR性能，基于主頻2.7 GHz實(shí)驗(yàn)平臺的MATLAB R2012b上運(yùn)行程序，得到x-SVR的實(shí)際運(yùn)行時(shí)間(s)和參數(shù)Up的預(yù)測平均絕對百分比誤差(MAPE)如表 4，x-SVR運(yùn)行時(shí)間與表1中對于x-SVR時(shí)間復(fù)雜度的公式推導(dǎo)結(jié)果完全吻合。如表4，智能算法中改進(jìn)ABC-SVR和PSO-SVR模型訓(xùn)練速率明顯快于ABC-SVR和GA-SVR；預(yù)測精度方面，改進(jìn)ABC-SVR進(jìn)化40代時(shí)就已經(jīng)明顯超過其他所有模型進(jìn)化200代所能夠達(dá)到的預(yù)測精度，且運(yùn)行時(shí)間和網(wǎng)格搜索接近；另外，網(wǎng)格搜索回歸精度與ABC-SVR接近，但運(yùn)行時(shí)間不到ABC-SVR的1/4，網(wǎng)格搜索算法擁有進(jìn)一步改進(jìn)的潛力，表明：大數(shù)據(jù)條件下，簡單模型往往具有更強(qiáng)的泛化能力和回歸效能，如網(wǎng)格搜索法。

表4 x-SVR模型效能對比

5 結(jié) 論

1)繼承經(jīng)典ABC算法技術(shù)優(yōu)勢，同時(shí)提高了其收斂速率和預(yù)測精度；2)所提出算法在進(jìn)化40代在回歸精度和預(yù)測性能上可以明顯超過其他智能算法，該方法對諸如關(guān)注效率和性能的數(shù)據(jù)樣本也具有良好的通用性和可借鑒性；3)能在一定程度上擺脫局部最優(yōu)和早熟限制，具有良好的泛化性能；4)與基線實(shí)驗(yàn)網(wǎng)格搜索模型相比，即使在算法時(shí)間耗費(fèi)方面，算法進(jìn)化40代達(dá)到可接受精度的前提下運(yùn)行時(shí)間與大規(guī)模樣本數(shù)據(jù)下的簡單模型接近，5)以模糊信息粒化技術(shù)進(jìn)行變化空間和趨勢預(yù)測，規(guī)避了復(fù)雜結(jié)構(gòu)數(shù)據(jù)難以追求問題最優(yōu)解及定量化精確描述的困局。

參考文獻(xiàn):

[1] Chapelle O,Vapnik V,Bousquet O,et al.Choosing multiple parameters for support vector machines[J].Machine Learning,2002,46:131-159.

[2] Ma X Y,Zhang Y B,Wang Y X.Performance evaluation of kernel functions based on grid search for support vector regression[C]∥The 7th International Conference on Cybernetics and Intelligent Systems & IEEE on Robotics,Automation and Mechatronics,2015:283-288.

[3] Xiao T J,Ren D,Lei S H,et al.Based on grid-search and PSO parameter optimization for support vector machine[C]∥The 11th World Congress on Intelligent Control and Automation,2014:1529-1533.

[4] 崔小勇,林 寧.基于遺傳模擬退火算法的無線傳感器網(wǎng)路由協(xié)議[J].傳感器與微系統(tǒng),2016,35(7):32-34.

[5] 倪 壯,肖 剛,敬忠良,等.改進(jìn)蟻群算法的飛機(jī)沖突解脫路徑規(guī)劃方法[J].傳感器與微系統(tǒng),2016,35(4):130-133.

[6] Basturk B,Karaboga D.An artificial bee colony(ABC)algorithm for numeric function optimization[C]∥Proceedings of IEEE Swarm Intelligence Symposium,Indianapolis,USA,2006:651-656.

[7] Karaboga D,Basturk B.A comparative study of artifieal bee colony algorithm[J].Applied Mathematics & Computation,2009,2(14):108-132.

[8] Zadeh L.Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[J].Fuzzy Sets Syst,1997,90:111-127.

[9] 徐 計(jì)，王國胤，于 洪.基于粒計(jì)算的大數(shù)據(jù)處理[J].計(jì)算機(jī)學(xué)報(bào),2015,38(8):1497-1517.

[10] Wang W J,Guo H S.Granular support vector machine based on mixed measure[J].Neurocomputing,2013,101(3):116-128.

[11] Pedrycz W.Knowledge-based clustering-fromdata to information granules[M].New Jersey:John Wiley & Sons,Inc,2005.

[12] Cheng X,Guo P.Short-term wind speed prediction based on support vector machine of fuzzy information granulation[C]∥25th Chinese Control and Decision Conference,CCDC 2013,2013:1918-1923.

[13] Nickabadi A,Ebadzadeh M M,Safabakhsh R.A novel particle swarm optimization algorithm with adaptive inertia weight[J].Applied Soft Computing,2011,11(4):3658-3670.