基于渦流搜索算法的支持向量機分類模型

李學貴 許少華 李 娜 張 強

(1.東北石油大學計算機與信息技術學院，黑龍江 大慶 163318；2.山東科技大學計算機科學與工程學院，山東 青島 266590；3.大慶油田化工有限責任公司東昊分公司，黑龍江 大慶 163312；4.新疆油田公司勘探開發研究院，新疆 克拉瑪依 834000)

基于渦流搜索算法的支持向量機分類模型

李學貴1許少華2李 娜3張 強4

(1.東北石油大學計算機與信息技術學院，黑龍江 大慶 163318；2.山東科技大學計算機科學與工程學院，山東 青島 266590；3.大慶油田化工有限責任公司東昊分公司，黑龍江 大慶 163312；4.新疆油田公司勘探開發研究院，新疆 克拉瑪依 834000)

提出一種將渦流搜索算法用于支持向量機參數選取的新算法，利用該算法不必遍歷搜索空間內所有的參數點即可找到全局最優解。給出了具體的算法流程，并進行了仿真。仿真實驗結果表明渦流搜索算法是選取SVM參數的有效方法。

渦流搜索算法 支持向量機 參數優化 單解優化算法

許多現實生活中的優化問題由于本身性質比較復雜,精確優化方法常常不能解決這些問題[1]。因此,使用近似算法就成為解決這類問題的替代方案。元啟發式算法是一類不依賴具體問題的解決方案，更具有通用性，更適用大量不同的優化問題。元啟發式算法能在合理的時間內得到近似最優解,但不能保證解的最優性。元啟發式算法分為單解元啟發算法和群解元啟發算法兩種類型[2]。單解元啟發算法在任意時間都基于單解,包括基于啟發式局部搜索算法，例如模擬退火(SA)[3]、迭代局部搜索(ITS)[4]、向導局部搜索(GLS)[5]、隨機搜索(RS)[6]和可變鄰域搜索[7]。群解元啟發算法首先構建一些解，然后逐步迭代更新直至滿足終止條件，群解元啟發算法又分為兩類：進化算法和群智能算法。進化算法基于自然選擇機制,根據適應度從種群中選出最佳個體，然后采用一些遺傳算子產生后代。進化算法的典型代表是遺傳算法(GA)[8]和差分進化(DE)[9]。群智能算法的靈感源自于一些動物(螞蟻、蜜蜂、魚及鳥等)的集體行為，通過間接傳播媒介進行協作在決策空間中移動[1]。蟻群優化算法(ACO)[10]和粒子群優化算法(PSO)[11]是群智能算法的典型代表。

渦流搜索算法(Vortex Search，VS)是最近提出的一種新型元啟發式單解優化算法,渦流算法靈感源自攪動液體產生的渦流現象，可以提供搜索行為的探索和開發之間良好的平衡，該方法通過使用一種自適應步長調整方案的搜索行為模擬渦流現象，具有操作簡單和搜索能力強的突出優點[12]。渦流算法的搜索能力超過了單解的模擬退火算法、模式搜索算法和群解的人工蜂群算法。支持向量機(Support Vector Machine，SVM)是基于結構風險最小化原則建立的一種機器學習模型，具有較為完備的統計理論基礎，對于小樣本集合的學習問題有著良好的適應性[13,14]。支持向量機的參數決定了其學習性能和泛化能力。筆者提出一種基于渦流搜索算法的支持向量機分類預測模型，將渦流搜索算法用于支持向量機的參數優化，可以不必遍歷搜索空間內所有參數點便可找到全局最優解。

1 渦流搜索算法①

渦流搜索算法通過使用一種自適應步長調整方案的搜索行為模擬渦流現象。在初始階段,算法提供高效的探索行為，而當算法收斂到局部解附近時,則開始進一步的局部開發,使當前解向著最優解逐步逼近。渦流搜索算法操作簡單且搜索能力強，不需要設置過多參數，只需考慮迭代次數、候選解集大小及搜索空間上下界等參數。

1.1生成初始解

首先考慮一個二維優化問題，二維空間的渦流現象可以通過多個嵌套圓來模擬。渦流的最外圈最先被選為搜索空間的中心，推廣到d維空間中,初始的搜索中心μ0可用下式計算：

(1)

其中，Lupper和Llower都是d維向量，分別代表d維搜索空間的上界和下界。

1.2生成候選解

在渦流算法中,臨近解集Ct(s)通過高斯分布在d維空間中心μ向量附近隨機產生，t代表迭代次數，初始為0。初始候選解集Ct(s)={s1,s2,…,sk,…,sn}(k=1,2,3,…,n)通過以μ0為中心的高斯分布隨機產生,n代表候選解集中解的個數。高斯分布的一般形式如下：

(2)

其中，x是d×1維隨機變量,μ是d×1維樣本均值(渦流中心)向量,Σ是協方差矩陣。假如Σ對角元素相等而且非對角元素都為0，分布產生的形狀將是球形,因此協方差矩陣Σ可以通過下式計算：

Σ=σ2·Id×d

(3)

其中，σ2為高斯分布的方差，Id×d是d×d單位向量矩陣。高斯分布的初始均方差可以通過下式計算：

(4)

其中,初始均方差σ0也可以看作在二維優化問題中渦流外圈的初始半徑r0。算法搜索初始階段弱化局部性是必要的，所以初始半徑r0可以選擇一個較大的值。因此，初始步驟通過設置大半徑的最外圈實現了搜索空間的全覆蓋。

1.3當前解更新

在選擇階段，從C0(s)中選擇一個最好的候選解s′替換當前解μ0，前提是候選解必須在搜索空間邊界內才能被選擇，超出邊界范圍的解將變換進入到邊界內，計算公式如下：

(5)

其中，k=1,2,…,n，i=1,2,…,n，rand是一個符合均勻分布的隨機數。將最佳解作為搜索空間的新中心，縮減新的圈的半徑r1，圍繞新的中心周圍產生新的候選解集C1(s)，在候選解集C1(s)中評價所選的最優解s′。若最優解s′優于到目前為止的最優解,則更新最優解。接下來將最好解作為縮減半徑后的第3個圈中心,重復上述過程直至滿足終止條件。

渦流搜索算法相對比較簡單，不同于以往的單解算法，它使用了極少的內存量，而且使用了一個額外的步驟來在迭代時進行搜索半徑縮減。半徑縮減過程可以看作是一種自適應步長調整過程，搜索過程是算法成功的關鍵。

1.4搜索半徑縮減

在渦流搜索算法中,每一步迭代采用不完全伽馬函數的逆函數來縮減半徑的值，如下式：

(6)

其中，λ>0為隨機變量；α>0為形狀參數,相當于搜索的分辨率，取值范圍[0,1],隨著每次迭代搜索的分辨率也應該被矯正，所以α在搜索過程中按下式計算：

(7)

為確保在開始階段實現搜索空間的全覆蓋,選擇α0=1,t為當前迭代數,Imax為最大迭代數。每步迭代渦流半徑按下式更新：

σt=σ0(1/λ)γ(λ,αt)

(8)

文獻[12]指出,當λ=0.1時,搜索性能最好。這種更新方法可使搜索半徑在前半部分線性縮小，側重于全局探索,后半部分指數縮小，側重于局部開發，從而可較好地實現探索與開發之間的平衡。

2 渦流搜索算法支持向量機分類模型

2.1支持向量機

支持向量機是一種基于結構風險最小化原則建立的機器學習模型[13,14]，具有較為完備的統計理論基礎，對于小樣本集合的學習問題有著良好的適應性。支持向量機的基本思想是：首先，在線性可分情況下，在原空間尋找兩類樣本的最優分類超平面。在線性不可分的情況下，加入了松弛變量進行分析，通過使用非線性映射將低維輸入空間的樣本映射到高維屬性空間使它變為線性情況，在該特征空間中尋找最優分類超平面，通過使用結構風險最小化原理在屬性空間構建最優分類超平面，使分類器得到全局最優。支持向量機分類模型如圖1所示。

圖1 支持向量機分類模型

支持向量機的學習過程可轉化為優化問題，給定訓練樣本集(xi,yi)，i=0,1，…，l,x∈Rn，y∈{±1}，超平面記為(w·x)+b=0。尋找最優超平面，即：

s.t.yi[(wT·φ(xi))+b]≥1-ξi

ξi≥0,i=0,1,…,n

(9)

其中，w為超平面的法向量；C為錯分樣本的懲罰因子,C>0;ξ為松弛變量；b為閾值,b∈R。

引入Lagrange函數，將二次規劃問題轉化為相應的對偶問題，即求：

(10)

其中，K(xi,xj)為核函數，受核函數參數的影響。

2.2支持向量機分類模型參數優化

在式(10)中K(xi,xj)核函數受核函數參數G影響。支持向量機求解問題的關鍵為在最優核函數下尋找最優的懲罰因子C和核函數參數G，以使正確分類率最大。因此，以C和G為對象在不同核函數類型下，C和G在一定范圍內取值，對于選定的C和G，把訓練集作為原始數據集計算此組C和G下訓練集驗證分類準確率，最終取訓練集驗證分類準確率最高的那組C和G作為最佳參數，懲罰系數C與核參數G的選擇過程實際上是一個優化搜索過程，如果采用傳統方法，很難獲得最優參數，采用元啟發式算法可以不必遍歷所有參數點，也能找到全局最優解，渦流搜索算法的特點十分適合于SVM參數優化，針對支持向量機的參數優化問題，筆者采用渦流搜索算法對SVM參數尋優。

2.3渦流搜索算法的SVM參數尋優算法

采用渦流搜索算法對SVM參數進行優化，需要對相關參數進行設置并對適應度函數進行定義。渦流搜索算法主要設置最大迭代數、候選解集大小和搜索空間上下界。由于優化SVM的主要目的在于獲得更高的正確分類率，因此采用訓練集進行交叉驗證下的正確分類率Vacc作為渦流搜索算法的適應度函數，基于渦流搜索算法的SVM參數尋優算法描述如下：

a. 初始化搜索中心μ0，初始化搜索半徑r0，初始化均方差σ0，最優解的適應度函數初始化無窮小，當前迭代步數t=0；

b. 圍繞搜索中心μt以搜索半徑rt高斯分布生成候選解集，假如有候選解值超出邊界范圍將變換進入到邊界內，采用式(5)進行變換；

c. 在候選解集C1(s)中評價一個解s′，若最優解s′優于到目前為止的全局最優解,則更新最優解，若s′的適應函數值與目前最優解相同并且懲罰因子C小于當前全局最優解的懲罰因子C，也更新最優解；

d. 將最佳解作為搜索空間新中心，縮減新的圈半徑rt+1，接下來將最好解作為縮減半徑后的圈中心，迭代步數t=t+1；

e. 判斷是否滿足終止條件，迭代步數t是否小于最大迭代步數Imax，滿足條件則轉到步驟b重復上述過程；

f. 迭代結束，輸出迄今為止的最優解S。

3 仿真實驗

為驗證筆者所提算法的有效性,選用了UCI數據庫中的Wine、Seeds和Iris 3個數據集進行仿真實驗，這些數據集的詳細信息見表1。實驗中將數據集的各屬性通過線性歸一化到區間[0,1]內，在劃分各數據的訓練樣本和測試樣本時，取一部分作為訓練數據，一部分作為測試數據。

表1 仿真實驗數據集

筆者將渦流搜索算法中的參數設置為：搜索鄰域解數10，最大迭代步數100，懲罰因子C的范圍[0,2],核函數參數σ取值范圍[0,2]。渦流搜索算法的適應度變化曲線如圖2所示，算法的最佳適應度是指每次迭代搜索的最大適應度的解，平均適應度是指每次迭代搜索解的所有鄰域解適應度的平均值，全局最佳適應度代表所有已搜索的最佳解的適應度。

仿真實驗對于3種數據集分別采用粒子群算法和網格搜索算法作為參比模型，支持向量機的核函數采用徑向基(RBF)核函數，搜索SVM的最優參數,然后利用搜索到的優化模型在測試樣本上進行測試，不同算法的實驗結果比較見表2。

圖2 渦流搜索算法優化迭代適應度變化曲線表2 仿真實驗結果

數據集主要參數網格搜索算法粒子群算法渦流搜索算法Iris懲罰因子C0.57430.36131.0027核函數參數G4.00009.30751.9880適應度1.000000.986841.00000正確分類率/%95.945993.243297.2973Seeds懲罰因子C3.03145.00902.8677核函數參數G2.29742.00002.5219適應度0.9038460.9038460.903846正確分類率/%97.169897.169897.1698Wine懲罰因子C0.4061264.9142001.642200核函數參數G0.50003.44481.6761適應度0.9746840.9887640.974684正確分類率/%96.629297.752898.8760

從表2的仿真實驗結果可以看出,采用渦流算法對SVM參數進行尋優所需計算量減少，而其正確分類率也優于基于網格搜索和粒子群算法。

4 結束語

支持向量機的參數是影響支持向量機分類精度的重要因素，參數的選擇決定了其學習性能和泛化能力，筆者將渦流搜索算法用于支持向量機參數優化，可以不必遍歷搜索空間內所有參數點便可找到全局最優解。仿真結果表明：渦流搜索算法是選取SVM參數的有效方法，經參數優化的支持向量機具有更高的分類精度，通過優化參數達到提高支持向量機分類精度的目的。

[1] Talbi E G.Metaheuristics:From Design to Implementation[M].New Jersey:Wiley & Sons,2009:323～325.

[2] Boussaid I,Lepagnot J,Siarry P.A Survey on Optimization Metaheuristics[J].Information Science,2013,237(7):82～117.

[3] Kirkpatrick S,Gelatt C D, Vecchi M P.Optimization by Simulated Annealing[J].Science,1983,220(5):671～680.

[4] Lourenco H R, Martin O, Stutzle T.Iterated Local Search:Framework and Applications[J].International Series in Operations Research & Management Science, 2010, 146(5): 363～397.

[5] Alsheddy A. Empowerment Scheduling: A Multi-objective Optimization Approach Using Guided Local Search[D]. Esse:University of Essex,2011.

[6] Rastrigin L A. The Convergence of the Random Search Method in the Extremal Control of a Many Parameter System[J].Autom Rem Control，1963，24(10):1337～1342.

[7] Hansen P,Mladenovic N, Perez J A M.Variable Neighbourhood Search:Methods and Applications[J].Annals of Operations Research,2010,175(1):367～407.

[8] Holland J H.Adaptation in Natural and Artificial Systems[M]. Ann Arbor: University of Michigan Press,1975:1～211.

[9] Storn R,Price K.Differential Evolution—A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces[M].Berkley:Int Computer Science Institute,1995:1～15.

[10] Dorigo M.Optimization,Learning and Natural Algorithms[D].Milano:Politecnico di Milano,1992.

[11] Kennedy J,Eberhart R C.Particle Swarm Optimization[C].Proceeding of IEEE International Conference on Neural Networks. New York:IEEE,1995:1942～1948.

[12] Berat D,Tamer O.A New Metaheuristic for Numerical Function Optimization:Vortex Search Algorithm[J].Information Sciences,2015,293(1):125～145.

[13] Vapnik V N.The Nature of Statistical Learning Theory[M].New York:Springer,1995.

[14] Vapnik V N，著,許建華,張學工,譯.統計學習理論[M].北京:電子工業出版社,2004.

ClassificationModelofSupportVectorMachineBasedonVortexSearchAlgorithm

LI Xue-gui1, XU Shao-hua2,LI Na3, ZHANG Qiang4

(1.SchoolofComputer&InformationTechnology,NortheastPetroleumUniversity,Daqing163318,China; 2.CollegeofComputerScienceandEngineering,ShandongUniversityofScience&Technology,Qingdao266590,China；3.DonghaoBranchCo.,DaqingOilfieldChemicalCo.,Ltd.,Daqing163312,China; 4.ResearchInstituteofExplorationandDevelopment,XinjiangOilfieldCompany,Karamay834000,China)

Applying the vortex search algorithm to SVM parameter selection was proposed, which searches for global optimal solution without going through all parameter points in the space. The concrete algorithm flow was presented and simulated to show that, the vortex search algorithm is an effective way for selecting SVM parameters.

vortex search algorithm, support vector machine,parameter optimization, single-solution optimization algorithm

TP183

A

1000-3932(2016)12-1291-05

2016-10-11(修改稿)

國家自然科學基金項目(61170132)；中國石油科技創新基金項目(2010D-5006-0302)