基于混沌機制的人工蜂群算法優化的支持向量機分類器

劉霞+張姍姍+胡銘鑒+龐永貴

（1.2.?東北石油大學?電氣信息工程學院，黑龍江?大慶163318;3.?新疆石油勘探設計研究院，新疆?克拉瑪依?834000;4.?大慶物探一公司，黑龍江?大慶?163357）

摘要：支持向量機的分類性能在很大程度上取決于其相關參數的選擇，為了改善支持向量機的分類準確率，本文采用基于混沌機制的人工蜂群算法對其參數進行優化。在傳統人工蜂群算法的基礎上，采用Logistic混沌映射初始化種群和錦標賽選擇策略，進一步提高人工蜂群算法的收斂速度和尋優精度。該方法采用分類準確率作為適應度函數，利用人工蜂群算法對支持向量機的懲罰因子和核函數參數進行優化。通過對多個標準數據集的分類測試，證明基于混沌機制的人工蜂群算法優化的支持向量機分類器能夠獲得更高的分類準確率。

關鍵字：人工蜂群算法，支持向量機，參數優化，混沌機制，錦標賽選擇策略

中圖分類號：TP311?文獻標識碼：A??文章編號：黑龍江省長江學者后備計劃（2012CJHB005）

Artificial?colony?algorithm?based?on?chaotic?mechanism?optimization?of?support?vector?machine?classifier

LIU?Xia1，ZHANG?Shan-shan2，HU?Ming-jian3，PANG?Yong-gui4

（1.2.Northeast?Petroleum?University?Electrical?information?engineering?institute，Heilongjiang?Daqing?163318;3.Xinjiang?Design?Institute，China?Petroleum?Engineering，Xinjiang?Karamay?834000;4.Daqing?Gepphysical?Exploration?Company?of?NO.1，Heilongjiang?Daqing?163357）

Abstract：?The?classification?performance?of?support?vector?machine?（SVM）?to?a?large?extent?depends?on?the?selection?of?its?parameters，?in?order?to?improve?the?classification?accuracy?of?support?vector?machine?（SVM），?using?Artificial?bee?colony?algorithm?based?on?chaotic?mechanism?to?optimize?the?parameters?in?this?paper.?On?the?basis?of?the?traditional?artificial?colony?algorithm，?using?the?Logistic?chaotic?mapping?initialization?population?and?tournament?selection?strategy，?further?improve?the?artificial?colony?algorithm?convergence?speed?and?optimization?precision.The?method?adopts?the?classification?accuracy?as?fitness?function，?using?artificial?colony?algorithm?of?support?vector?machine?（SVM）?penalty?factor?and?the?kernel?function?parameter?optimization.?By?standard?data?sets?with?the?classification?of?the?test，?prove?that?artificial?colony?algorithm?based?on?chaotic?mechanism?optimization?of?support?vector?machine?classifier?can?achieve?higher?classification?accuracy.

Keywords：?Artificial?colony?algorithm，?Support?vector?machine?（SVM），?parameters?optimization，?Chaotic?mechanism，?Tournament?selection?strategy

1?引言

支持向量機（Support?Vector?Machines，?SVM）是以統計學習理論為基礎，針對有限樣本的一種通用學習方法，能有效解決小樣本、高維數、非線性等問題[1-3]。因而被廣泛應用在故障診斷、安全檢測、圖像處理等領域。由于模型參數包括懲罰因子C、核函數類型和核函數參數的選擇會嚴重影響最終的分類結果[4]，因此在利用SVM進行分類時，需要研究的熱點問題就是如何通過選擇模型參數以獲取最優分類結果。

實踐證明，支持向量機的分類準確率、懲罰因子以及核函數參數之間存在多峰值函數關系[5]，而梯度下降算法、遺傳（GA）算法、蟻群（ACO）算法及標準粒子群（PSO）算法這些目前常用的SVM參數優化方法，由于在尋優過程中會陷入局部最優解而使得分類效果不能達到最佳。2005年，Karaboga[6]提出了一種新的群集智能優化算法-----人工蜂群（Artificial?bee?colony，ABC）算法，并通過大量的標準函數測試證明[7，8]，ABC算法具有比傳統方法更佳的優化性能，它通過蜜蜂之間的分工合作，同時兼顧了精密搜索已知解域和擴展新解域，從而降低了算法陷入局部最優解的概率。

本文使用的支持向量機采用RBF核函數，利用基于混沌機制的人工蜂群算法對模型參數進行優化，通過對CUI數據庫中標準數據集的訓練和分類測試實驗證明，基于混沌機制的ABC算法能夠克服局部最優解，在一定程度上加快搜索速度，優化后的SVM具有更高的分類準確率，從而驗證了本文方法的可行性和有效性。

2?引入混沌機制的ABC算法

2.1?ABC算法優化原理

ABC算法模擬實際蜜蜂采蜜機制來處理函數的優化問題，人工蜂群分為以下三部分：引領蜂、跟隨蜂和偵查蜂。ABC算法在求解最優問題時，食物源的位置對應優化問題的可能解，每個食物源的花蜜量對應每個解的適應度值。

一個非線性函數最小值問題可以表示為：

min?f（X），XL≤?X≤XU，XL和XU分別是變量X取值的上界和下界，X=（x1，?x2，?x3…xn）?，n為變量的維數。利用ABC求解該最優問題的具體過程如下：

1、種群初始化

在取值范圍內按（1）隨機產生一個包含SN個個體的初始種群。

，

i=1，2…SN?????????????????????（1）

式中，表示初始種群中的第i個個體，它的維數n為優化參數的個數;rand（）表示在區間[0，1]上產生的隨機數。

對初始種群的一半計算適應度值及可行解的質量，記錄目前質量最好的解。

2、引領蜂階段

引領蜂的數量等于食物源的一半，即SN/2，表示初始種群中適應度值較優的一半個體，與食物源的位置相對應。引領蜂隨機選取食物源進行交叉搜索，按式（2）對食物源進行更新，即產生一個新解。

（2）

式中，k∈{1，2，?…SN/2}，j∈{1，2，?…n}，且k≠i，為[-1，1]之間的隨機數。計算新解的適應度值，如果新解的適應度優于舊解，那么就用新解代替舊解;反之，保留舊解。

3、跟隨蜂階段

跟隨蜂的數量跟引領蜂的數量是相等的，也是SN/2。跟隨蜂根據引領蜂搜索的信息，按照一個與適應度相關的概率來選擇一個食物源的位置，即解得位置，并像引領蜂一樣按式（2）對食物源進行更新，若新解的適應度值優于舊解，用新解替代舊解;反之保留舊解。跟隨蜂選擇食物源的概率公式為：

4、偵查蜂階段

經過引領蜂與跟隨蜂的搜索以后得到與初始種群相同大小的新種群，為了避免隨著種群的進化出現種群多樣性喪失過多的問題，人工蜂群算法模擬偵查蜂搜索潛在蜜源的生理行為，提出了一種特有的搜索方式——偵查蜂搜索。如果某一個體（解）連續“Limit”代沒有變化，與之對應的個體變異成偵查蜂，按式（2）搜索產生新個體，計算新個體的適應度值并與原個體比較，若優于原個體則代替原個體。

經過引領蜂、跟隨蜂和偵查蜂三個階段的搜索之后，整個種群進化到下一代，這個過程反復循還直至達到最大迭代次數MaxCycles或者誤差達到預定的范圍之內時結束算法。

2.2?基于混沌機制的ABC算法

1、混沌初始化

混沌看似混亂卻有著精致的內在結構，是非線性系統中特有并普遍存在的一種現象。隨機性、遍歷性和規律性是混沌最典型的特點，使得它能夠按照自身的某一“規律”不重復地遍歷給定范圍內的所有狀態。本文采用Logistic混沌映射來初始化種群。Logistic混沌映射的方程如下：

（5）計算i=i+1，如果i大于種群個數SN，則結束，否則返回（2）繼續循環。

經過以上步驟就可以產生SN個初始種群。

2、錦標賽選擇策略

錦標賽是基于局部競爭機制的一種選擇策略，它的基本思想是在種群中隨機選出k個個體進行適應度值的比較，選擇適應度值較優的個體。參數k是競賽的規模，通常情況取默認值2。在ABC算法中，將第t代某個個體的適應度值與其它所有個體兩兩進行比較，對適應度值較優的個體授予一分，對每個個體重復這一過程，個體得分越高表示個體越優秀，被選擇的概率越大。這種方式根據種群個體間適應度值的關系進行選擇，與個體的適應度值無關，因此對適應值的正負沒有要求，從而提高優秀個體被選擇的概率，在一定程度上避免了比例選擇策略可能出現的過早收斂和停滯現象。

3?基于混沌機制的人工蜂群算法優化的SVM分類器

3.1?SVM原理

SVM分類的過程就是在空間找到一個滿足分類要求的最優分類超平面，該超平面在保證分類正確的基礎上，還能夠使兩類數據集間的距離最大。將SVM的學習過程轉化為優化問題，設有訓練樣本集{（xi，yi），i=1，2，?……l}，輸入xiRn，期望輸出yi{+1，-1}，其中+1，-1分別代表兩類的類別標識，則這個數據集的分類超平面可描述為wgx+b=0。尋找最優超平面的公式如下：

為核函數，其值受核函數參數σ的影響，目前常用的核函數主要有多項式核函數、徑向基函數、多層感知器和動態核函數等[9，10]。

綜上可知，尋找最優超平面的關鍵在于選擇最優核函數的前提下尋找最優的懲罰因子C和核函數參數σ，以使得SVM獲得最大分類正確率。

3.2?基于混沌機制的ABC-SVM算法流程

1、算法初始化，設定最大迭代次數MaxCycles、種群個數SN、維數D（由于需要優化的參數有兩個，所以D=2）、個體最大更新次數Limit、懲罰因子C和核函數參數σ的最大值（cmax，gmax）和最小值（cmin，gmin）。

利用式（5）產生混沌初始種群（即懲罰因子C和核函數參數σ的初值），將懲罰因子C和核函數參數σ的初值寫入SVM模型，并對訓練樣本進行訓練分類，準確率即為ABC的適應度值，記錄最好的適應度值和對應的參數值。

2、引領蜂按式（2）搜索更新，計算適應度值，若新食物源的適應度值優于搜索前，則代替先前的食物源。

3、跟隨蜂根據錦標賽選擇策略選擇食物源，并按式（2）在食物源附近進行搜索新的食物源。計算新食物源的適應度值，若新食物源的適應度值優于搜索前，則代替先前的食物源。

4、判斷是否存在需要放棄的食物源。如果某個食物源進過Limit次循環之后沒有改變，則放棄該食物源，同時對應的引領蜂變異為偵查蜂，按式（5）產生新的食物源。

5、迭代次數Cycles=Cycles+1，若Cycles達到最大迭代次數MaxCycles或分類準確率達到設定精度結束算法，輸出最優值;否則返回步驟2。

3.3實驗仿真與結果分析

為了驗證本文算法的有效性和優越性，采用UCI數據庫（http：//archive.ics.uci.edu/ml/）中的3個具有代表性的數據集Heart、Iris和Wine進行訓練和分類實驗，數據集詳細信息如表1所示。ABC算法的控制參數設置如下：食物源數量SN設為20，最大迭代次數MaxCycles設為1000，個體最大更新次數Limit設為50，懲罰因子的搜索范圍設為[0.1，100]，核函數參數的搜索范圍設為[0.01，1000]。

表1?測試數據集說明

將傳統SVM、ABC-SVM和基于混沌機制的ABC-SVM的測試結果進行比較，比較結果如表2所示。由這些實驗結果可以看出，ABC算法能夠兼顧全局最優解和局部最優解的搜索，對SVM進行參數優化后，可得到更高的分類正確率，而基于混沌機制的ABC算法能夠進一步提高支持向量機的分類準確率。

表2??三種算法的分類測試結果

三種算法進行3次試驗后得到的平均運行時間如表3所示，從表中的數據可以看出，對支持向量機進行參數優化，由于算法的復雜性增加從而使得運行時間增加，但是基于混沌機制的ABC算法優化的SVM在一定程度上縮短了運行時間，與傳統ABC優化的SVM比較表現出更好的收斂性，有效地降低了搜索運行時間。

表3?三種算法的運行時間對比

4、結?語

支持向量機模型參數的選擇在很大程度上影響支持向量機的分類準確率，為了找到最優的參數取值，采用人工蜂群算法優化支持向量機的方法，并在傳統蜂群算法的基礎上加入混沌思想及采用錦標賽選擇策略，提出基于混沌機制的人工蜂群算法優化的支持向量機分類器。算法中，把支持向量機的分類準確率當做人工蜂群算法的適應度函數，采用RBF核函數，利用人工蜂群算法優化支持向量機的懲罰因子C和核函數參數σ。通過對UCI標準數據及的分類實驗證明，基于混沌機制的人工蜂群算法具有較強的局部和全局搜索能力，在很大程度上克服了局部極值點的問題，其優化的支持向量機與傳統的支持向量機相比，具有更高的分類準確率，并對于文中測試的數據集而言，有效地縮短了搜索時間。在本文的研究過程中發現，在人工蜂群算法初始化過程中，一些控制參數是通過多次試驗得到較優的初值，因此，如何更快更有效地確定人工蜂群算法中的初始化參數對于進一步提高算法的效率有著不可忽視的作用。

參考文獻：

[1]?Vapnik?V?N.?The?nature?of?statistical?learning?[M].2nd?ed.?New?York：?Springer，?2000.

[2]?CRISTIANINI?N，?et?al.?An?introduction?to?support?vector?machines?and?other?kernel-based?learning?methods?[M].?Beijing：?Mechanical?industry?press，2005.

[3]?楊志民，劉廣利.不確定性支持向量機原??理及應用[M].北京：科學出版社，2007.

[4]?SHAO?Jun，?LIU?Jun-hua，?QIAO?Xue-guang，etal.Temperature?compensation?of?FBG?sensor?based?on?support?vector?machine[J].?Journal?of?Optoelectronics?Laser，2010，?21（?6）：?803-807.

[5]?劉春波，王鮮芳，潘?豐.?基于蟻群優化算法的支持向量機參數選擇及仿真[J].?中南大學學報：自然科學版，?2008，?39?（6）：?1309-1313.

[6]?Karaboga?D.?An?Idea?Based?on?Honey?Bee?Swarm?for?Numerical?Optimization[R].?TECHNICAL?REPORT-TR06，Erciyes?University?，?Engineering?Faculty?，Computer?Engineering?Department，2005.

[7]?Karaboga?D，Basturk?B.?A?powerful?and?efficient?algorithm?for?numerical?function?optimization：Artificial?bee?colony?（ABC）?algorithm[J].?Journal?of?Global?Optimiza-?tion，?2007，39（3）：459-471.

[8]?Karaboga?D，Basturk?B.?A?comparative?study?of?artificial?bee?colony?algorithm[J].?Applied?Mathematics?and?Computation，?2009，214（1）：108-132.

[9]?史忠值.知識發現.北京：清華大學出版社，2002，203-207.

[10]?Amari?S，Wu?S.Improving?support?vector?machine?classifier?by?modifying?kernel

functions.Neural?Networks，1999，?12（9）：

783-789.