劉天健

基于禁忌蝙蝠算法的支持向量機特征選擇和參數(shù)優(yōu)化

劉天健

（廣西大學(xué)計算機與電子信息學(xué)院，廣西 南寧 530004）

支持向量機是一種有良好發(fā)展前景的學(xué)習(xí)機器。針對支持向量機訓(xùn)練過程中特征選擇和參數(shù)優(yōu)化的問題，提出一種基于蝙蝠算法和禁忌搜索算法相結(jié)合的算法的支持向量機特征選擇和參數(shù)優(yōu)化算法。將禁忌搜索算法理論引入蝙蝠算法中，可以有效提高BA算法的收斂速度和精度，得到更優(yōu)的支持向量機模型。UCI標準數(shù)據(jù)集的分類實驗結(jié)果表明，與基本的網(wǎng)格搜索，遺傳算法等比較，TSBA算法可以獲得更高的分類準確率和更好的穩(wěn)定性。

支持向量機；蝙蝠算法；禁忌搜索算法；特征選擇；參數(shù)優(yōu)化

蝙蝠算法（BA）［1］是一種新的群智能優(yōu)化算法。相對于其他的算法，BA算法在有效性和準確性方面有明顯的提高。但是，蝙蝠算法的優(yōu)化性能還不是十分完善，存在易陷入局部最優(yōu)早熟收斂等問題。禁忌搜索算法（TS）作為一種智能搜索算法具有模擬人類智能的記憶機制，已被廣泛應(yīng)用于各類優(yōu)化領(lǐng)域并取得了理想的效果。TS通過采用禁忌策略來限制搜索過程陷入局部最優(yōu)，從而避免迂回搜索。

基于此，本文提出一種新的基于蝙蝠算法和禁忌搜索算法的混合算法TSBA算法。TSBA算法具有結(jié)合BA算法和TS算法的優(yōu)點，使其具有更好的搜索能力，并且可以避免陷入局部最優(yōu)，加快收斂速度，從而更好的優(yōu)化SVM分類器。最后以UCI數(shù)據(jù)庫案例作為本文的實驗數(shù)據(jù)，對其進行仿真實驗，仿真結(jié)果表明，基于禁忌蝙蝠算法優(yōu)化的SVM比傳統(tǒng)的分類算法有更高的分類精度和穩(wěn)定性。

1　相關(guān)工作

1.1支持向量機原理

支持向量機［2］源于統(tǒng)計學(xué)理論，其思想是在n維空間中找到一個分類超平面，在這個空間建立一個最優(yōu)分類超平面，將空間上的點分類。在分開的數(shù)據(jù)的超平面的兩邊有兩個互相平行的分類超平面，最優(yōu)分類超平面是多個平行超平面的距離最大值。SVM分類問題有兩類：線性可分與非線性可分。線性可分問題的定義是其訓(xùn)練集可以用一個超平面完全正確地進行分類的問題。對于非線性的情況，SVM的處理方法是選擇一個核函數(shù)，通過將數(shù)據(jù)映射到一個高維特征空間，在這個空間中構(gòu)造最優(yōu)分類超平面。

1.2支持向量機參數(shù)

在支持向量機中，懲罰因子值的大小代表這分類器對被誤劃分的點的重視程度，誤差懲罰因子的值越大，表明分類器對該噪聲點的重視程度越到，反之則越低。而核函數(shù)參數(shù)γ決定著樣本點經(jīng)映射后所在的高維特征空間區(qū)域中分布的復(fù)雜程度，核函數(shù)參數(shù)的改變意味著特征空間VC維的改變，VC維的大小決定著空間的置信范圍，最終影響結(jié)構(gòu)風(fēng)險范圍。

在SVM的眾多核函數(shù)中，RBF核函數(shù)是應(yīng)用最廣泛的核函數(shù)之一，且因為其只有兩個參數(shù)：懲罰因子C和核函數(shù)γ。所以只要能找到最優(yōu)化參數(shù)組（C，γ），就能使SVM具有最好推廣性。

2　混合蝙蝠算法的支持向量機參數(shù)優(yōu)化

2.1混合蝙蝠算法

蝙蝠算法實現(xiàn)簡單，但是其具有局部搜索能力弱，易陷入局部最優(yōu)點，進化后期收斂速度慢等缺陷。而禁忌搜索是人工智能的一種體現(xiàn)，是局部搜索領(lǐng)域的一種擴展。禁忌搜索最重要的思想是標記對應(yīng)已搜索的局部最優(yōu)解的一些對象，并在進一步的迭代搜索中盡量避開這些對象（而不是絕對禁止循環(huán)），從而保證對不同的有效搜索途徑的探索［3］。因此本文在基本蝙蝠算法中引入禁忌搜索思想，提高蝙蝠算法擺脫局部極值點的能力，提高基本蝙蝠算法的收斂速度和精度。

混合蝙蝠算法基本思想：

（1）采用基本的蝙蝠算法初始化相應(yīng)的群體位置、速度、響度等參數(shù)，既不改變蝙蝠算法初始化時所具有的隨機性本質(zhì)。用第一代群體的適應(yīng)度的最好值，作為當前解和全局最優(yōu)解，并將其添加到禁忌表。

（2）t代第i個個體的適應(yīng)度與1t-的第i個個體適應(yīng)度做比較。如果t代第i個個體的優(yōu)于當前全局最優(yōu)解，就用禁忌搜索算法的藐視準則，把1t-代第i個個體適應(yīng)度和當前全局最優(yōu)解替換成t代第i個個體的適應(yīng)度，并把t代第i個個體適應(yīng)度加入禁忌表。

如果t代第i個個體的適應(yīng)度優(yōu)于1t-代第i個個體的適應(yīng)度，并且不在禁忌表中，則把1t-代第i個個體的適應(yīng)度替換成t代第i個個體的適應(yīng)度并把該當代的適應(yīng)度加入禁忌表。

如果t代第i個個體的適應(yīng)度優(yōu)于1t-代第i個個體的適應(yīng)度，但是禁忌表中有該適應(yīng)度，則忽略此次更新的速度、響度、位置等，以此來幫助蝙蝠算法跳出局部最優(yōu)點，從而快速尋找到最優(yōu)解。

2.2禁忌蝙蝠算法的支持向量機參數(shù)優(yōu)化

本文中的SVM核函數(shù)采用的是RBF核函數(shù)，因為RBF核函數(shù)使SVM具備了線性與非線性的分類能力，并且SVM的分類能力主要受其參數(shù)核函數(shù)γ和懲罰因子C的影響。所以本文考慮核函數(shù)γ和懲罰因子C，并用該算法去優(yōu)化SVM。

基于禁忌蝙蝠算法的支持向量機參數(shù)優(yōu)化具體算法步驟如下：

（1）設(shè)置蝙蝠種群的規(guī)模、最大迭代次數(shù)、禁忌表的長度，搜索范圍。

（2）初始化禁忌表和蝙蝠算法的相關(guān)參數(shù)值，主要包括蝙蝠種群里每只蝙蝠的音量A和脈沖速率r及其速度向量v和位置向量x，以及蝙蝠的頻率f范圍。

（3）初始化蝙蝠種群所有個體的位置，每一個解的位置為γ、C。

（4）評估初始代各只蝙蝠的適應(yīng)度值，選出適應(yīng)度值最大的個體，更新禁忌表。

（5）更新每只蝙蝠的脈沖速率、速度和位置，更新公式如下：

其中，β是一個從0到1的隨機數(shù)；f是蝙蝠的脈沖頻率，其范圍根據(jù)處理的問題大小，在初始化時設(shè)定［fmin，fmax］；為種群進化t代后更新的速度，是進化t-1代后的速度；為種群進化t代后更新的位置，是進化t-1代后的位置；X*是種群中適應(yīng)度最高的蝙蝠個體的位置。并且可以根據(jù)所求解的問題類型，在固定iλ（或if）的同時改變if（或iλ）。

（6）生成一個隨機數(shù)rand，如果rrand＞，則對當前最優(yōu)解進行一個隨機的擾動，產(chǎn)生一個新的解后，對新解進行越界檢查，如果超出范圍則進行越界處理。

（8）生成一個隨機數(shù)rand，如果rand＜A ，且f（）＞f），并且f（）的值不存在禁忌表中，同時將相應(yīng)的對象加入禁忌表，并修改禁忌表中各對象的任期。則接受步驟（6）產(chǎn)生的新解，然后按如下公式對ir和iA進行更新：

（10）如未滿足結(jié)束條件，則重復(fù)步驟（5）至（9）。

（11）輸出全局最優(yōu)解。具體流程見圖1。

圖1　TSBA-SVM的SVM參數(shù)優(yōu)化流程圖

3　仿真研究

3.1數(shù)據(jù)源

為了驗證本文提出算法的有效性，本文采用UCI標準數(shù)據(jù)集中的7個真實的數(shù)據(jù)集，各數(shù)據(jù)集簡要介紹如表1所列。

表1　來自UCI的數(shù)據(jù)集及其描述

3.2算法的參數(shù)設(shè)置

TSBA-SVM算法的參數(shù)設(shè)置：種群規(guī)模20，進化代數(shù)100，禁忌表的長度為5。

懲罰因子以及核函數(shù)參數(shù)變化范圍的最小值一般是以2為底，取其冪指數(shù)的值，即，變化范圍的最大值同樣也是以2為底，取其冪指數(shù)的值，即

在本章的7個UCI數(shù)據(jù)集的分類測試中，懲罰因子以及核函數(shù)參數(shù)變化范圍的min值皆取-5，而max皆取+5，即0.03125≤C≤32，0.03125≤r≤32。

3.3結(jié)果與分析

表2是TSBA-SVM算法與基本遺傳算法和網(wǎng)格搜索算法的實驗結(jié)果對比，按照折疊交叉確認法的K取10，對其中的若干個UCI數(shù)據(jù)集分別進行10次測試，然后去10次實驗最高分類正確率的平均數(shù)。

表2　TSBA-SVM算法與GA和GS算法的性分類正確率對比

由表2的實驗數(shù)據(jù)對比可見，本文算法的分類準確率都要略高于基本遺傳算法［4］和網(wǎng)格搜索算法［5］。

從表2的實驗結(jié)果來看，TSBA-SVM算法不僅分類準確率比基本遺傳算法的分類準確率略高，穩(wěn)定性略高于基本遺傳算法；而TSBA-SVM算法不僅分類準確率比網(wǎng)格搜索算法的準確率更高，而且穩(wěn)定性也高于網(wǎng)格搜索算法。說明TSBA-SVM算法不僅在分類準確率上高于GA算法和網(wǎng)格搜索算法，并且穩(wěn)定性上有很大提升。

表3是TSBA-SVM算法與文獻［6］的兩種改進算法CCBSS、GS-SVM算法的實驗結(jié)果對比，樣本數(shù)據(jù)按照訓(xùn)練數(shù)據(jù)占總樣本數(shù)據(jù)的50%，評價數(shù)據(jù)占25%，測試數(shù)據(jù)占25%，對于每個數(shù)據(jù)集，都分別測試30次，然后取30次實驗最優(yōu)分類正確率的平均值。

表3　TSBA-SVM與CCBSS和GS-SVM的分類正確率的對比

由表3的實驗數(shù)據(jù)對比可見，本文算法的分類準確率相比與CCBSS、GS-SVM分別提高了5.16%、2.73%、3.12%、3.97%，并且TSBA-SVM算法在群體規(guī)模和進化代數(shù)上都要優(yōu)于CCBSS、GS-SVM，由此可見TSBA-SVM算法的整體性能比CCBSS和GS-SVM算法有很大的優(yōu)勢。

4　結(jié)論

支持向量機的分類準確率與其參數(shù)的的選擇密不可分，利用RBF核函數(shù)的優(yōu)點，選取相對應(yīng)的參數(shù)，能在很大程度上提高支持向量機的學(xué)習(xí)能力。本文在保留了基本蝙蝠算法所具有的隨機性強、精確度高、魯棒性好等優(yōu)點的基礎(chǔ)上，結(jié)合禁忌搜索算法的仿人工記憶的特性，提出了一種基于禁忌蝙蝠算法的支持向量機支持向量機特征選擇和參數(shù)優(yōu)化。TSBA-SVM可以很好的解決BA算法容易陷入局部最優(yōu)、收斂速度慢的缺點。通過在7個數(shù)據(jù)集上進行實驗，實驗結(jié)果表明基于混合蝙蝠算法的支持向量機分類器比基本的網(wǎng)格搜索算法、基本遺傳算法、CCBSS算法和GS-SVM算法有更高的分類準確率和更好的穩(wěn)定性。

［1］ Yang X S.A new metaheuristic bat-inspired algorithm［M］// Nature inspired cooperative strategies for optimization（NICSO 2010）.Springer Berlin Heidelberg，2010：65-74.

［2］ Vapnik V N. The nature of statistical learning theory. Statistics for Engineering and Information Science［J］. Springer-Verlag，New York， 2000.

［3］ 董宗然，周慧.禁忌搜索算法評述［J］.軟件工程師，2010，（2）：96-98.

［4］ Coello C A C，Montes E M. Constraint-handling in genetic algorithms through the use of dominance-based tournament selection［J］.Advanced Engineering Informatics，2002，16（3）：193-203.

［5］ Hsu C W， Chang C C， Lin C J. A practical guide to support vector classification［R］.臺北：國立臺灣大學(xué)資訊工程學(xué)系，2003：1-12.

［6］ 蔣華榮，郁雪.應(yīng)用遺傳算法優(yōu)化子空間的SVM分類算法［J］.計算機科學(xué)，2013，40（11）：255-260.

Feature selection and parameter optimization for support vector machines based on Taboo bat algorithm

Support vector machine is a good development prospect of learning machine. Aiming at the problem of feature selection and parameter optimization of support vector machine in the training procedure， a novel approach based on the bat algorithm and tabu search algorithm for feature selection and parameter optimization of SVM is proposed. The tabu search algorithm theory into bat algorithm， BA can improve the convergence speed and precision to give better support vector machine model. The experimental results for UCI standard datasets show that compared with the basic GS， GA， TSBA-SVM algorithm can achieve higher classification accuracy and better stability.

Support vector machine； bat algorithms； tabu search algorithm； feature selection； parameter optimization

TP38

A

1008-1151（2016）02-0012-03

2016-01-11

劉天健（1990－），男，河北廊坊人，廣西大學(xué)計算機與電子信息學(xué)院碩士生，研究方向為高性能計算與網(wǎng)絡(luò)系統(tǒng)。