基于改進蜂群算法優化的支持向量機研究與應用

朱范炳， 陳 澤， 張 翔

（信陽學院大數據與人工智能學院， 河南 信陽 464000）

0 引 言

支持向量機［1］（Support Vector Machine， SVM）是一種應用廣泛的機器學習方法，其基礎是Vapnik［2］創立的統計學習理論。 可以解決小樣本和非線性的實際問題，現已廣泛應用于智能故障診斷［3］、圖像識別［4］、負荷預測［5］等領域。 在使用支持向量機進行分類時，模型參數的選擇對分類準確率影響很大。 如何選擇模型參數以優化模型的性能是支持向量機研究領域的一個熱點問題。 目前常用的模型參數優化方法有遺傳算法［6］、高斯函數［7］、模擬退火算法［8］、粒子群優化算法［9］等。 在優化過程中，上述方法都不同程度地進入局部最優解，導致分類模型的性能不能最大化。 文獻［10］提出了一種多維更新的人工蜂群算法，該方法很好地保持了挖掘搜索寬度和深度上的平衡，有效地避免了問題陷入局部最優解，但求解方法采用全維搜索策略會大大增加時間成本。

基于以上分析，本文提出一種進一步改進人工蜂群算法的方法，通過選擇最優的搜索方向，在保證搜索精度的同時，能夠降低算法的時間復雜度。 基于RBF 核函數，采用改進的人工蜂群算法對支持向量機模型參數進行優化。 本文首先通過在標準數據集上的分類實驗，驗證改進人工蜂群算法優化支持向量機的有效性；然后通過人體活動數據分類識別，說明所提方法的實用性；最后得出結論。

1 人工蜂群算法分析與改進

1.1 基本人工蜂群算法

人工蜂群算法［11-12］（ Artificial Bee Colony Algorithm， ABC）是Karaboga 等學者于2005 年提出的一種仿生計算算法，主要應用于函數極值優化問題。 該算法模仿了蜂群的覓食行為，并將蜜蜂分為3 種不同的工作類型：采蜜蜂、觀察蜂和偵察蜂。 采蜜蜂、觀察蜂分別占蜜蜂總數的一半，一個蜜源對應一只蜜蜂。 蜜源優劣由適應度值評價，一個蜜源有最大開采次數。 算法通過迭代搜索蜜源，進行目標問題解的尋優，能夠以較大的概率找到全局最優解。

人工蜂群算法的基本原理：設有N個蜜源｛x1，x2，…，xN｝，每個蜜源xi（i＝1，2，…，N） 有D個分量，即待優化問題的解空間包含N個可行解，每個可行解是D維向量。 設定蜂群循環搜索的最大次數和每個蜜源的可重復開采次數，同一蜜源開采超過可重復開采次數則放棄該蜜源。 人工蜂群算法包括以下階段：

（1）蜂群的初始化階段：利用式（1）對任一解的任一分量進行全局隨機初始化：

其中，xidmin和xidmax分別表示可行解空間第d維分量的上下限，rand（0，1） 為［0，1］之間的隨機數。

（2）采蜜蜂搜索階段：采蜜蜂在初始蜜源鄰域，通過式（2）搜索產生一個新解，作為候選蜜源進行開采：

其中，j∈｛1，2，…，N｝，j≠i表示在N個蜜源中隨機選取一個不同于xi的蜜源，rand（- 1，1） 是在［-1，1］之間均勻分布的隨機數，決定采蜜蜂更新位置的擾動幅度。 計算新解的適應度fiti評價蜜源質量，在vi和xi之中采用貪婪策略進行選擇。

（3）觀察蜂跟隨階段：所有采蜜蜂完成搜索后，采蜜蜂會把解的信息及適應度分享給觀察蜂。 觀察蜂通過選擇概率Pi決定每只采蜜蜂被跟隨的概率：

或者

觀察蜂通過輪盤賭策略選擇采蜜蜂跟隨。 如果采蜜蜂對應蜜源的選擇概率值較大，則會被更多的觀察蜂跟隨，即適應度較大的蜜源附近會有更多的觀察蜂進行搜索，蜜源對應解的鄰域搜索范圍更廣。若新解的適應度比之前的好，觀察蜂將會更新解；反之，觀察蜂會將之前的解保留，同時解的迭代搜索次數會加1。

（4）偵察蜂階段：所有觀察蜂完成跟隨搜索后，如果某一蜜源在被搜索最大開采次數后仍沒有被更新，則認為該蜜源已被開采枯竭，對應的解陷入局部最優。 相應的采蜜蜂和觀察蜂則會放棄該蜜源，轉換為偵察蜂模式，按照式（1）進行全局隨機搜索新蜜源。 這是人工蜂群算法跳出局部最優的有效手段。 然后返回到采蜜蜂的搜索階段，3 種蜜蜂依次工作，重復循環搜索，最終找到目標問題的最優解。

1.2 改進人工蜂群算法

基本人工蜂群算法中，采蜜蜂和觀察蜂隨機選擇蜜源的一個維度，按照式（2）進行搜索。 如果在這個維度上有更好的解，但下一次迭代隨機選擇另外一個維度，這可能會導致無法進一步開發當前維度更優的解，后因達到最大開采次數而放棄這個蜜源。 這會使算法錯過很多尋找全局最優解的機會，增加算法的收斂時間，也會影響最終解的精度。

為此，本文提出了一種改進的多維搜索策略。該方法在第一次迭代時搜索蜜源的每個維度進行貪婪選擇。 如果當前維度選擇成功，則在保留當前維度更新的基礎上，將該維度保存到外部文檔Dim中，然后進行下一個維度的選擇。 如果選擇失敗，更新將不會被保留，外部文檔也不會存儲該維度。 結合上述想法，本文將式（2）中隨機更新一個維度替換為同時更新Dim中的維度，即可得到新的更新公式如下：

其中，m表示Dim中保存維度的個數。

每次搜索迭代搜索都會進行貪婪選擇，將每個蜜源中有價值的維度存儲到Dim中。 在下一次迭代中，對Dim中存儲的維度執行上述操作。 多次迭代后，Dim存儲維度的數量將減少，說明算法進化搜索的方向更加明確，直至算法達到穩定收斂。

2 支持向量機參數選擇

支持向量機在面對非線性分類問題時，通過高維空間變換將非線性分類問題轉化為高維空間的線性分類問題，并引入拉格朗日函數來解決不等式約束下二次函數的極值問題。 在使用支持向量機進行數據分類之前，應選擇核函數類型、懲罰因子C和核函數參數［13］。 本文采用RBF 徑向基函數作為核函數，以RBF 核函數中的寬度參數g和懲罰因子C為優化目標。 為了說明懲罰因子C和參數g對模型性能的影響，表1 和表2 給出了不同參數下數據分類準確率。

表1 C＝2 分類結果隨g 值的變化Tab. 1 Change of classification results with g when C＝2

表2 g ＝2 分類結果隨C 值的變化Tab. 2 Change of classification results with C when g ＝2

懲罰因子C起到控制錯誤子樣本懲罰的作用，從而實現錯誤子樣本比例與算法復雜度之間的權衡。 當C較小時，支持向量機對誤差的容忍度較高，模型的精度會降低，但泛化能力增強。 當C較大時，模型的精度提高，但復雜度增加，泛化能力也降低。參數g決定了數據樣本在高維特征空間中的復雜度，稱為空間維數。 該維數決定在空間中可以構造的線性分類曲面的最大維數。 維數越高，線性分類面越復雜，經驗風險越小，置信范圍越大，反之亦然。 從表1 和表2 可以看出，懲罰因子C和參數g對分類準確率有顯著影響。 因此，為了得到性能較好的支持向量機，需要選擇合適的寬度參數g，并在確定的特征空間中尋找合適的懲罰因子C，使模型的擬合能力和泛化能力得到最佳的結合。

3 改進人工蜂群算法優化支持向量機參數

利用智能計算方法優化支持向量機需要設置適應度函數和尋優解空間。 由于使用算法對支持向量機進行優化的目的是為了獲得更高的分類準確率，所以本文用分類準確率來設計算法的適應度函數；由前文的分析可知，懲罰因子C和寬度參數g會對支持向量機的分類性能產生很大的影響。 因此，設定懲罰因子C和寬度參數g為優化參數。

為了驗證本文改進的人工蜂群算法的有效性和優越性，使用UCI 標準數據集中3 組數據集進行支持向量機的訓練和測試驗證。 使用的數據集名稱、樣本規模、維度信息，見表3。 本文設計了不同改進方法的人工蜂群算法優化支持向量機的縱向比較實驗和不同算法優化支持向量機的橫向比較實驗。

表3 UCI 測試數據集信息Tab. 3 The information of UCI test data sets

3.1 不同方法改進蜂群算法優化支持向量機參數

分別采用本文改進的人工蜂群算法（IABC）、文獻［10］提出的多維更新的人工蜂群算法（MABC）和基本人工蜂群算法（ABC）對支持向量機模型參數進行優化。 實驗結果由10 次實驗計算平均值所得。表4 記錄不同人工蜂群算法優化的支持向量機在不同數據集下的分類準確率，表5 記錄對應算法的運行時間。 由結果數據可以看出，本文改進人工蜂群算法優化的支持向量機在保證分類準確率的同時，能夠有效降低算法收斂時間。

表4 改進蜂群算法優化支持向量機分類準確率Tab. 4 Classification accuracy of SVM optimized by IABC %

表5 改進蜂群算法優化支持向量機運行時間Tab. 5 Running time of SVM optimized by IABCs

3.2 不同算法優化支持向量機參數

為了進一步驗證改進算法的性能，利用IABC算法與網格搜索算法（GS）、遺傳算法（GA）和粒子群算法（PSO）優化支持向量機的參數。 分別進行10 次實驗計算結果平均值。 表6 記錄的是4 種算法在不同數據集下的分類準確率。 由結果數據可以看出，對于不同樣本規模和維度的數據集，IABC 優化的SVM 模型都比其他算法具有更高的分類準確率。 因此，采用IABC 優化的SVM 模型將局部最優解的搜索與全局最優解的搜索結合起來，具有較好的收斂性。

表6 不同算法優化支持向量機分類準確率Tab. 6 Classification accuracy of SVM optimized by different algorithms%

4 實例分析

4.1 實驗方案設計

應用改進蜂群算法優化的支持向量機對人體活動的實測數據進行分類，驗證改進算法的實用性。數據采集過程中參與者需佩戴帶有加速度、溫度和高度傳感器的智能手表。 從加速度傳感器采集的數據包括X，Y和Z方向的加速度。 溫度和高度傳感器的數據包括參與者的體表溫度和佩戴手表距地面的距離。 采樣頻率設置為52 Hz，采集7 種不同的人體活動數據，數據的詳細內容見表7。

表7 人體活動數據信息Tab. 7 Activity data information

4.2 實驗與結果分析

在采集的人體活動數據中每類抽取100 組樣本，共計700 組；在支持向量機訓練和測試中，隨機抽取490 個樣本作為訓練集，其余210 個樣本作為測試集。 本文主要運用ABC 和IABC 算法對SVM模型參數進行優化，從而進行人體活動識別。 實驗中設置蜂群算法的種群規模為20，最大迭代次數為500。 ABC 和IABC 算法優化的SVM 模型分類準確率的迭代變化曲線分別如圖1 和圖2 所示。

圖1 ABC-SVM 分類準確率變化曲線Fig. 1 Classification accuracy curve of ABC-SVM

圖2 IABC-SVM 分類準確率變化曲線Fig. 2 Classification accuracy curve of IABC-SVM

由圖1 和圖2 可見，在算法迭代次數均為500的情況下，ABC 算法優化的SVM 模型（ABC-SVM）分類準確率收斂速度快，最高可達84.31%；IABC 算法優化的SVM 模型（IABC-SVM）分類準確率收斂速度較ABC-SVM 慢，但分類準確率最高可達85.73%，有顯著提高。 對上述實驗數據分別采用SVM、ABC-SVM、IABC-SVM 進行10 次分類實驗，計算分類準確率平均值記錄于表8 中。

表8 不同算法模型的分類準確率Tab. 8 Classification accuracy under different algorithms

5 結束語

支持向量機模型參數是影響分類精度的重要因素。 針對目前支持向量機訓練算法計算量大、運行時間長、分類準確率待提高的問題，本文提出了一種改進的人工蜂群算法對支持向量機參數優化的方法。 通過標準數據集的實驗表明，改進的人工蜂群算法優化的支持向量機模型提高了分類準確率，降低了算法收斂時間。 將該方法應用于實測的人體活動數據分類，獲得了良好的分類精度，說明改進人工蜂群算法優化的支持向量機具有較好的實際應用價值。