李学贵 许少华 李 娜 张 强

(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)