一種改進的人工蜂群算法優(yōu)化的支持向量機

李紀麟 謝霖銓

（江西理工大學，江西 贛州 341000）

一種改進的人工蜂群算法優(yōu)化的支持向量機

李紀麟 謝霖銓

（江西理工大學，江西 贛州 341000）

為了改善現(xiàn)有支持向量機（Support Vector Machine）的機器學習效果依賴于參數(shù)選擇，而參數(shù)選擇通常依賴于經(jīng)驗的問題，在現(xiàn)有基礎(chǔ)上，本文結(jié)合一種稱為骨架人工蜂群算法（Bare-bones Artificial Bee Colony）的改進的人工蜂群算法對支持向量機的2個參數(shù)進行優(yōu)化，并對該優(yōu)化結(jié)果進行試驗。試驗結(jié)果表明，改進的支持向量機的準確率、識別速度均優(yōu)于原本的支持向量機。

支持向量機；人工蜂群算法；參數(shù)優(yōu)化

支持向量機（Support Vector Machine，SVM）是一種監(jiān)督式的機器學習方法，能非常成功地處理回歸問題（時間序列分析問題）和分類問題等諸多問題，并可推廣用于預測和綜合評價等領(lǐng)域［1］。支持向量機經(jīng)過多年的發(fā)展，已經(jīng)出現(xiàn)了多種改進算法，使得其性能有了很大的改進［2］。文獻［3-5］通過實驗證實核函數(shù)的參數(shù)的正確選擇對于SVM的性能有著至關(guān)重要的影響。現(xiàn)在通常使用的核函數(shù)是RBF核函數(shù)［4-8］。SVM的參數(shù)選擇實際上是一個優(yōu)化問題。截至目前，SVM的參數(shù)選擇包括如下方法：經(jīng)驗選擇法、交叉驗證法、網(wǎng)格搜索法、貝葉斯法等［7］。近年來，隨著包括模擬退火算法（Simulate Annealing Algo?rithm，SA）［9］、遺傳算法（Genetic Algorithm，GA）［10］、粒子群優(yōu)化算法（Particle Swarm Optimization Algorithm，PSO）［11］和人工蜂群算法（Artificial Bee Colony Algorithm，ABC）［12］等優(yōu)化算法的發(fā)展，已有學者采用上述算法來優(yōu)化選擇SVM的參數(shù)［4，7，13］。

骨架人工蜂群算法（Bare-bones Artificial Bee Colony，BBABC）是一種改進的人工蜂群算法［14］。該種算法相比原始的ABC及其他的優(yōu)化算法，有更好的收斂精度和收斂速度。本文使用BBABC對使用徑向基函數(shù)（Radial Ba?sis Function，RBF）作為核函數(shù)的SVM的2個參數(shù)進行優(yōu)化，并對優(yōu)化的結(jié)果進行試驗，取得了較好的效果。

1 人工蜂群算法

人工蜂群算法是一種啟發(fā)式群體智能優(yōu)化算法。該算法的基本思想是通過模擬蜂群中個體之間的分工和信息交流，相互協(xié)作尋找蜜源的過程。與經(jīng)典的優(yōu)化方法相比，ABC算法對目標函數(shù)和約束幾乎沒有要求，在搜索過程中基本不利用外部信息，僅以適應度函數(shù)作為進化的依據(jù)，即是使用“生成+檢驗”的方式［12］，這種方式十分適合用于解決NP完全問題。ABC算法具有操作簡單、控制參數(shù)少、搜索精度較高和魯棒性較強的特點［15-17］。Karaboga等［16］指出與遺傳算法、差分演化算法（Differen?tial Evolution，DE）和粒子群優(yōu)化算法相比較，ABC算法的求解質(zhì)量相對較好。

Bare-Bones人工蜂群算法（BBABC，又稱BABC或BCABC）［14］是一種新型的基于ABC的改進算法。該算法針對原始ABC具有較強的搜索性能和較弱的收斂性，引入了移動距離參數(shù)自適應，基于適應度的最近鄰，以及在跟隨蜂階段引入高斯搜尋方程這三種方式來提高算法的收斂性。通過結(jié)合這三種方式，該算法能夠極大地提升ABC的收斂性，從而提升ABC的性能。

1.1 人工蜂群算法的基本原理

1.1.1 群體智能模型的組成。對于一個給定的優(yōu)化問題，ABC算法使用一個模擬蜂群尋找更好的食物源的群體智能模型來尋找該優(yōu)化問題的解。這個群體智能模型由3種類型的蜜蜂及食物源組成。具體的定義如下。

1.1.1.1 食物源。ABC算法中的食物源是連續(xù)或離散的解空間中的點。對于每一個點i，定義一個函數(shù)fit（xi）作為評價該點處蜜源的標準，這個標準也稱為適應值。

ABC算法把蜂群分為2個部分，2種蜜蜂分別使用不同的策略來尋找新的食物源。將蜂群劃分的方式通常是50%為雇傭蜂，50%為跟隨蜂。

1.1.1.2 雇傭蜂（Employed Bees）。蜂群的兩種分類的其中一種是雇傭蜂。雇傭蜂尋找新的食物源的方式是在現(xiàn)有食物源的基礎(chǔ)上進行開采，在這個過程中可能雇傭跟隨蜂或不雇傭；雇傭跟隨蜂的過程即是“雇傭蜂”這個名字的由來。

1.1.1.3 跟隨蜂（Onlooker Bees）。蜂群的另一個部分是跟隨蜂。顧名思義，跟隨蜂的任務是選擇一個雇傭蜂并和該雇傭蜂一起對雇傭蜂所處的蜜源進行開發(fā)。

1.1.1.4 偵察蜂（Scout Bees）。雇傭蜂在認為一個蜜源沒有繼續(xù)開采的價值時（通常認為該蜜源已陷入局部最優(yōu)的情況），他就會轉(zhuǎn)變?yōu)閭刹旆洳⒃谌炙阉饕粋€新的蜜源。偵察蜂在選擇了一個新的蜜源之后將會重新轉(zhuǎn)變?yōu)楣蛡蚍洹?/p>

1.1.2 ABC算法的過程。對于一個解空間的維度為D的問題，ABC算法的過程如下。

1.1.2.1 初始化。首先將雇傭蜂視為偵察蜂，為每一個雇傭蜂在解空間內(nèi)隨機分配一個食物源xi。分配的方式如下：

xid=Ld+rand（0，1）×（Ud-Ld）（1）

式（1）中，Ld表示搜索空間的第d維下限；Ud表示搜索空間的第d維的上限，d∈［1，D］∩N*。；xid表示第i個雇傭蜂在第d個維度的位置；rand（0，1）是［0，1］內(nèi)的隨機數(shù)。上述公式表示初始化時，將任何一個雇傭蜂的任何一個維度都完全隨機生成，即是將雇傭蜂隨機放在解空間中的任何一點上。

1.1.2.2 雇傭蜂對食物源進行搜索。雇傭蜂首先對自身所在的食物源在某個維度上相對另一個雇傭蜂所在位置上的鄰域進行一次搜索。如果搜索到的新解xi′的適應度值Fiti′優(yōu)于之前保留的適應度值Fiti，則將雇傭蜂移動到新解的位置，否則保持原解的位置不變。當所有的雇傭蜂搜索完畢時，將根據(jù)蜜源所在的位置和質(zhì)量傳達給跟隨蜂。雇傭蜂搜索新解的方式如下：

1.1.2.3 跟隨蜂對食物源進行搜索。雇傭蜂給出每一個食物源及其適應度之后，跟隨蜂對每一個食物源的選擇概率進行計算，計算出的食物源的概率如下：

在算出概率之后，跟隨蜂通過輪盤賭的方式對該食物源進行選擇。在選中食物源之后，跟隨蜂和雇傭蜂一樣通過公式（2）對食物源進行開發(fā)。跟隨蜂在尋找到新的食物源，而且證明了食物源的適應度值好于原食物源之后，將把食物源的位置報告給雇傭蜂，雇傭蜂移動到新的食物源。

1.1.2.4 決定偵察蜂。在雇傭蜂及跟隨蜂的搜索過程中，每一次對一個食物源進行搜索而沒有更新，則對該蜜源記錄一個值triali。如果蜜源Xi經(jīng)過limit次搜索而沒有進行更新，則認為該蜜源陷入了局部最優(yōu)，該蜜源將會被放棄，占據(jù)該蜜源的雇傭蜂將會轉(zhuǎn)變?yōu)閭刹旆?。偵察蜂在搜索空間使用公式（1）隨機產(chǎn)生一個新的蜜源代替原蜜源Xi。

在ABC算法中，解的適應度評價包括許多種方式，其中應用較廣泛的是根據(jù)式（4）進行計算：

式（4）中，fi表示解的函數(shù)值。

ABC算法除上述對蜂群進行分類的方式外，還包括一些改進的方式。王慧穎等［18］提出了一種在蜂群中始終保持一定比例的雇傭蜂的方式對蜂群進行改進，取得了較好的效果。

1.2 Bare-bonesABC算法

ABC算法的一個很大的缺陷是其收斂速度過慢。對于解決某些極值點較少的問題，容易陷入局部最優(yōu)。假設某個解離極值點的距離足夠小，則基于ABC的機制，產(chǎn)生另一個離極值距離更小的解的概率則會變得非常低。為了針對這一點，Gao等［14］提出了一種稱為Bare-bones ABC的算法以解決該問題，該算法改進了如下3個方面。

①將公式（2）的ψ改變?yōu)橐粋€基于過往成功經(jīng)驗的自適應參數(shù)。ψ的值根據(jù)以下公式確定：

Ri則根據(jù)以下公式確定：

式（6）中，μR初值為0.5，而后每次迭代完將賦值為該次結(jié)果中成功取代了過往蜜源的蜜蜂對應的所有R的集合SR的平均值。

②將公式（2）的j由均勻分布的隨機數(shù)決定改為根據(jù)適應度進行評分確定：Si為第i個蜜源的評分，其算法為用蜜源的數(shù)量減去該蜜源的排名。j的選擇策略是根據(jù)Si的數(shù)值進行輪盤賭選擇。即對每個蜜源的選擇概率為：

③在跟隨蜂階段，把跟隨蜂選擇引領(lǐng)蜂的概率公式改為如下公式：

通過以上改進，BBABC比原始ABC在收斂性方面有了較大的改善。

2 支持向量機

SVM的工作原理是通過對樣本進行比較獲得一個分類超平面［17］。對于線性可分的兩類問題，其求得的是一條分離線或者是分類平面；而對于非線性可分情況的問題，則是先通過運用適當?shù)膬?nèi)積函數(shù)也就是核函數(shù)，將輸入空間中的輸入點信息映射到其他某個高維的空間中，使得輸入樣本在這里能線性可分，從而求出可分所對應的最優(yōu)線性分類面。所謂最優(yōu)指的是不同樣本之間的分類間隔最大，使得不同樣本能正確分開。

對于訓練樣本集{（x1，y1），（x2，y2），……，（xn，yn）}，其中xi∈Rn，yi∈{-1，1}，其中y=1的樣本稱為正例點，y=-1的樣本稱為負例點。將所求得的超平面記為w×x+b=0。若要使得正例點處于分類間隔一側(cè)，負例點處于另一側(cè)，則必有yi（w×xi+b）≥1。進而可知分類間隔為2/‖w‖。因而求最大超平面的問題就轉(zhuǎn)換為求解如下最小值問題：引入拉格朗日函數(shù)將公式（9）轉(zhuǎn)換為：

該問題的對偶問題為：

式（11）中，ai＜C，C稱為懲罰因子。求解該問題得最優(yōu)解a*=（a1*，a2*，……，an*）T，據(jù)此解得

對于非線性分類問題，則需要引入核函數(shù)代替樣本向量的內(nèi)積，將非線性空間映射到更高維的向量空間。目前使用范圍最廣的核函數(shù)為高斯徑向基函數(shù)（Radial Basis Function）：

如上所述，使用RBF作為核函數(shù)的支持向量機具有2個參數(shù)：懲罰因子C和RBF參數(shù)σ。王鵬等［4，5］實驗論證了這兩個參數(shù)的正確選擇對SVM的準確性具有重要影響。

3 通過BBABC進行參數(shù)選擇的支持向量機

如上文所述，支持向量機的參數(shù)選擇對其計算的準確性和泛化能力有重要影響。截至目前，支持向量機的參數(shù)選擇法主要包含：經(jīng)驗選擇法、交叉驗證法、網(wǎng)格搜索法、貝葉斯法以及包括SA、GA、PSO、ABC等優(yōu)化算法。其中，經(jīng)驗選擇法依賴于問題描述和使用者的經(jīng)驗，依賴于問題本身；交叉驗證法、網(wǎng)格搜索法等算法較為盲目，時間復雜度較高，收斂性較差。現(xiàn)有的優(yōu)化算法雖然具有一定的收斂性，但仍然稍顯不足。

通過使用支持向量機的分類準確率作為基礎(chǔ)計算適應度，則準確率越高，適應度越小。因此可以據(jù)此將BBABC和SVM相結(jié)合，算法步驟如下。

①預處理數(shù)據(jù)集，將數(shù)據(jù)集分為訓練集A和測試集B。Cycle=1。

②初始化ABC，并使用公式（1）生成NP個解，每個解xi（i∈［1，NP］∩N*）是一個二維向量（Ci，σi）。

For i=1…NP DO

③初始化SVM。使用SVM對訓練集A進行機器學習。對上一步的學習結(jié)果使用測試集B進行驗證，得到SVM的準確度，并根據(jù)公式（4）求得xi的適應度值。

④引領(lǐng)蜂階段。For i=1…NP DO，根據(jù)公式（6）生成Ri，根據(jù)公式（5）生成ψij，并根據(jù)公式（7）確定Xk。根據(jù)公式（3）生成解vi，并根據(jù)步驟③計算適應度fit（vi）。

if fit（vi）＜fit（xi），將vi代替xi，令trial=1，將Ri并入集合SR。else trial自增1。

⑤跟隨蜂階段。根據(jù)公式（3）計算pi，;令t=0，i=1。

表1 預測準確率對比

表2 支持向量數(shù)對比

表3 平均預測時間對比

while t≤NP do

if rand（0，1）＜pi，根據(jù)公式（8）產(chǎn)生新的Vi，據(jù)步驟③計算fit（vi）。

⑥偵察蜂階段。If max（triali）＞limit，重新將xi根據(jù)公式（1）替換為新解。令μR=mean（SR）。

⑦If Cycle＞MaxCycle終止循環(huán)輸出結(jié)果；否則，Cy?cle=Cycle+1，并返回步驟④。

4 試驗分析

4.1 數(shù)據(jù)來源

試驗使用加州大學歐文分校（University of Californi?aIrvine）提供的UCI數(shù)據(jù)集其中之一的Wine Quality數(shù)據(jù)集。該數(shù)據(jù)集包含產(chǎn)自北葡萄牙的葡萄牙青酒隨機取樣的4 898個樣本，每個樣本包含通過物理化學方式測量的密度、pH值、酒精度等12項特征。最終的質(zhì)量評級包含10個等級［19］。試驗前已將所有特征歸一至［0，1］區(qū)間。試驗分為2次，一次以前3/5的數(shù)據(jù)作為訓練集，后2/5的數(shù)據(jù)作為測試集。另一次以前4/5的數(shù)據(jù)作為訓練集，后1/5的數(shù)據(jù)作為測試集。

ABC的參數(shù)作如下設置：種群數(shù)為50，引領(lǐng)蜂數(shù)量為25，最大搜索次數(shù)設置為30,最大迭代次數(shù)為150。

4.2 對比和評價標準

在相同條件下，采用簡單隨機選擇變量值的SVM和原始ABC優(yōu)化的SVM進行對比試驗。性能評價指標為優(yōu)化速率、識別準確率和識別時間。識別準確率計算公式如下：式（14）中，Sc表示正確分類的樣本數(shù)，Sa表示樣本總數(shù)。

4.3 結(jié)果與分析

4.3.1 優(yōu)化速率和識別準確率對比。使用隨機數(shù)、ABC、BBABC算法對SVM參數(shù)進行優(yōu)化，優(yōu)化速率見圖1。使用優(yōu)化所得的參數(shù)建立識別模型，識別準確率見表1，支持向量數(shù)見表2。結(jié)果表明，使用BBABC的算法效率、支持向量數(shù)及識別準確率均優(yōu)于ABC算法。

相對于原始ABC SVM，BBABC-SVM的平均預測時間較少，識別速度較快。這主要由于BBABC-SVM減少了支持向量的數(shù)量，加快了算法的收斂速度。

圖1 優(yōu)化速率對比

4.3.2 識別時間對比。在實際運用中，許多應用需要保證實時性，因而預測速度也十分重要。為此，對上述數(shù)據(jù)的平均預測時間（單位s）進行仿真試驗，結(jié)果如表3所示。

5 結(jié)語

由上述優(yōu)化效果可見，使用BBABC優(yōu)化的SVM因為利用了BBABC的自適應機制向最優(yōu)解方向收斂，在時間上和識別準確率上均優(yōu)于使用ABC優(yōu)化的SVM，但識別準確率仍稍顯不足。這可能是由于兩方面的原因：一是由于支持向量機的優(yōu)化是一個多峰值的問題，算法可能由于早熟收斂陷入了局部最優(yōu)；二是分類樣本各類的分布不均勻。接下來的研究將圍繞避免早熟收斂、使算法跳出局部最優(yōu)的方向展開。

［1］VN Vapnik.The Nature of Statistical Learning Theory［M］. New York：John Wiley and Sons，1998.

［2］丁世飛，齊丙娟，譚紅艷.支持向量機理論與算法研究［J］.電子科技大學學報，2011（1）：2-10.

［3］陳健飛，蔣剛，楊劍鋒.改進ABC-SVM的參數(shù)優(yōu)化及應用［J］.機械設計與制造，2016（1）：24-28.

［4］王鵬，郭朝勇，劉紅寧.基于支持向量機的槍彈外觀缺陷識別與分類［J］.計算機工程與科學，2016（9）：1943-1949.

［5］M Zuriani，Y Yuhanis，SK Siti.Enhanced artificial bee col?ony for training least squares support vector machines in commodi?ty price forecasting［J］.Journal of Computational Science，2014（5）：196-205.

［6］張博洋.支持向量機理論與應用研究綜述［J］.無線互聯(lián)科技，2015（19）：111-112.

［7］寧愛平，張雪英，劉俊芳.ABC-PSO算法優(yōu)化混合核SVM參數(shù)及應用［J］.數(shù)學的實踐與認識，2014（18）：158-165.

［8］古麗娜孜·艾力木江，孫鐵利，乎西旦.一種基于融合核函數(shù)支持向量機的遙感圖像分類［J］.東北師大學報（自然科學版），2016（3）：60-66.

［9］AG Khachaturyan，SV Semenovskaya，BK Vainshtein.Sta?tistical-Thermodynamic Approach to Determination of Structure Amplitude Phases［J］.Sov.Phys.Crystallography，1979（5）：519-524.

［10］AE Eiben，PE Raué，Z Ruttkay.Genetic algorithms with multi-parent recombination［A］//International Conference on Evo?lutionary Computation，1994：78-87.

［11］KennedyJ，Eberhart R.Particle Swarm Optimization［A］// IEEE International Conference on Neural Networks，1995：1942-1948.

［12］Dervis Karaboga.An Idea Based On Honey Bee Swarm for Numerical Optimization［D］.Erciyes：Erciyes University，2005.

［13］蔡麗霞，馬琰.基于ABC-SVM的考生行為自動識別［J］.計算機系統(tǒng)應用，2015（5）：129-134.

［14］W Gao，F(xiàn)TS Chan，L Huang，et al.Bare bones artificial bee colony algorithm with parameter adaptation and fitness-based neighborhood［J］.Information Sciences，2015（C）：180-200.

［15］D Karaboga，B Akay.A comparative study of artificial bee colony algorithm［J］.Applied Mathematics and Computation，2009（14）：108-132.

［16］D Karaboga，B Basturk.On the performance of artificial bee colony（ABC）algorithm［J］.Applied Soft Computing，2008（1）：687-697.

［17］秦全德，程適，李麗，等.人工蜂群算法研究綜述［J］.智能系統(tǒng)學報，2014（2）：127-135.

［18］王慧穎，王文彬.基于改進搜索策略的混合蜂群算法［J］.系統(tǒng)工程與電子技術(shù)，2014（10）：2094-2101.

［19］P Cortez，A Cerdeira，F(xiàn) Almeida，et al.Modeling wine preferences by data mining from physicochemical properties［J］. Decision Support Systems，2009（4）：547-553.

An Improved Artificial Bee Colony Algorithm Based on Support Vector Machine

Li JilinXie Linquan
（Jiangxi University of Science and Technology，Ganzhou Jiangxi 341000）

In order to improve the performance of existing support vector machine in machine learning that depends on the parameters of SVM,and the parameters always depend on the experience of the problem,based on the existing conclusion,an SVM that hybrid with an improved artificial bee colony algorithm called bare-bones artificial bee colo?ny algorithm was proposed to optimize the two parameters of SVM,and the optimized results were tested.The results showed that the improved SVM had better accuracy and recognition speed than the original support vector machine.

support vector machine；artificial bee colony algorithm；parameter optimizing

TP18

：A

：1003-5168（2017）03-0046-05

2017-02-16

李紀麟（1990-），男，碩士，研究方向：數(shù)據(jù)挖掘和智能算法；謝霖銓（1962-），男，教授，研究方向：數(shù)據(jù)挖掘。