基于混沌機(jī)制的人工蜂群算法優(yōu)化的支持向量機(jī)分類器

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

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

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

關(guān)鍵字：人工蜂群算法，支持向量機(jī)，參數(shù)優(yōu)化，混沌機(jī)制，錦標(biāo)賽選擇策略

中圖分類號：TP311?文獻(xiàn)標(biāo)識碼：A??文章編號：黑龍江省長江學(xué)者后備計劃（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?引言

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

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

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

2?引入混沌機(jī)制的ABC算法

2.1?ABC算法優(yōu)化原理

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

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

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

1、種群初始化

在取值范圍內(nèi)按（1）隨機(jī)產(chǎn)生一個包含SN個個體的初始種群。

，

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

式中，表示初始種群中的第i個個體，它的維數(shù)n為優(yōu)化參數(shù)的個數(shù);rand（）表示在區(qū)間[0，1]上產(chǎn)生的隨機(jī)數(shù)。

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

2、引領(lǐng)蜂階段

引領(lǐng)蜂的數(shù)量等于食物源的一半，即SN/2，表示初始種群中適應(yīng)度值較優(yōu)的一半個體，與食物源的位置相對應(yīng)。引領(lǐng)蜂隨機(jī)選取食物源進(jìn)行交叉搜索，按式（2）對食物源進(jìn)行更新，即產(chǎn)生一個新解。

（2）

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

3、跟隨蜂階段

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

4、偵查蜂階段

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

經(jīng)過引領(lǐng)蜂、跟隨蜂和偵查蜂三個階段的搜索之后，整個種群進(jìn)化到下一代，這個過程反復(fù)循還直至達(dá)到最大迭代次數(shù)MaxCycles或者誤差達(dá)到預(yù)定的范圍之內(nèi)時結(jié)束算法。

2.2?基于混沌機(jī)制的ABC算法

1、混沌初始化

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

（5）計算i=i+1，如果i大于種群個數(shù)SN，則結(jié)束，否則返回（2）繼續(xù)循環(huán)。

經(jīng)過以上步驟就可以產(chǎn)生SN個初始種群。

2、錦標(biāo)賽選擇策略

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

3?基于混沌機(jī)制的人工蜂群算法優(yōu)化的SVM分類器

3.1?SVM原理

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

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

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

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

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

利用式（5）產(chǎn)生混沌初始種群（即懲罰因子C和核函數(shù)參數(shù)σ的初值），將懲罰因子C和核函數(shù)參數(shù)σ的初值寫入SVM模型，并對訓(xùn)練樣本進(jìn)行訓(xùn)練分類，準(zhǔn)確率即為ABC的適應(yīng)度值，記錄最好的適應(yīng)度值和對應(yīng)的參數(shù)值。

2、引領(lǐng)蜂按式（2）搜索更新，計算適應(yīng)度值，若新食物源的適應(yīng)度值優(yōu)于搜索前，則代替先前的食物源。

3、跟隨蜂根據(jù)錦標(biāo)賽選擇策略選擇食物源，并按式（2）在食物源附近進(jìn)行搜索新的食物源。計算新食物源的適應(yīng)度值，若新食物源的適應(yīng)度值優(yōu)于搜索前，則代替先前的食物源。

4、判斷是否存在需要放棄的食物源。如果某個食物源進(jìn)過Limit次循環(huán)之后沒有改變，則放棄該食物源，同時對應(yīng)的引領(lǐng)蜂變異為偵查蜂，按式（5）產(chǎn)生新的食物源。

5、迭代次數(shù)Cycles=Cycles+1，若Cycles達(dá)到最大迭代次數(shù)MaxCycles或分類準(zhǔn)確率達(dá)到設(shè)定精度結(jié)束算法，輸出最優(yōu)值;否則返回步驟2。

3.3實驗仿真與結(jié)果分析

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

表1?測試數(shù)據(jù)集說明

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

表2??三種算法的分類測試結(jié)果

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

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

4、結(jié)?語

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

參考文獻(xiàn)：

[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]?楊志民，劉廣利.不確定性支持向量機(jī)原??理及應(yīng)用[M].北京：科學(xué)出版社，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]?劉春波，王鮮芳，潘?豐.?基于蟻群優(yōu)化算法的支持向量機(jī)參數(shù)選擇及仿真[J].?中南大學(xué)學(xué)報：自然科學(xué)版，?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]?史忠值.知識發(fā)現(xiàn).北京：清華大學(xué)出版社，2002，203-207.

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

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

783-789.