基于灰狼优化算法的孪生支持向量回归机

沈葛亮,顾斌杰,潘 丰

(江南大学 轻工过程先进控制教育部重点实验室,江苏 无锡 214122)

近年来,由Jayadeva等人提出的孪生支持向量机(Twin support vector machine,TSVM)在图像处理、特征选择、入侵检测等领域得到了广泛应用[1-4]。TSVM将训练样本分为两类,相当于求解优化问题时样本个数减半。与传统的支持向量机[5]相比,TSVM的分类性能得到了提升,并且计算复杂度下降,训练时间仅为传统支持向量机的1/4[6]。

实际中,参数选择是TSVM的关键问题之一,不同的参数会严重影响分类和回归的结果。针对孪生支持向量分类机的参数选择问题,虽然传统的网格寻优方法能通过设定固定步长在一定范围内搜索得到最优解,但是其计算复杂度高,运行效率低,在样本数较大时性能欠佳。为此,Jayadeva等人提出了孪生支持向量分类机的核选择方法,为分类问题中核参数的选择提供了一种可行方法[7]。为了避免参数选择的盲目性,人们开始尝试利用群智能算法优化参数。丁世飞等人提出了基于粒子群优化算法的孪生支持向量分类,提高了分类精度[8]。之后,他们又提出了基于果蝇优化算法的孪生支持向量分类,通过果蝇优化算法寻找孪生支持向量机的惩罚参数,分类结果和运行效率均优于粒子群算法[9]。

针对孪生支持向量回归机参数选择问题的研究报道还不多见。灰狼优化算法(Grey wolf optimization,GWO)是一种模仿自然界狼群捕猎行为的新兴智能算法,它利用领导机制和位置更新机制寻找最优值[10]。在此基础上,Mirjalili等人提出了多目标灰狼优化算法,可用于寻优多个参数[11]。灰狼优化算法及其改进算法已经被证明具有更合理的全局最优搜索机制,运行稳定,收敛速度快,结构简单,通用性强,适用于各种参数寻优[12-16]。

为此,本文研究利用GWO算法优化孪生支持向量回归机的惩罚参数,提出了一种基于灰狼优化算法的孪生支持向量回归机(Twin support vector regressionbased on grey wolf optimization algorithm,GWOTSVR)。GWOTSVR将均方根误差和平均绝对误差作为GWO的适应度函数,利用灰狼优化算法的位置更新机制在定义域内寻找最优的适应度函数值,最终经过有限次数迭代后得到最优的惩罚参数。

1 孪生支持向量回归机

孪生支持向量回归机(Twin support vector regression,TSVR)的思想是将训练数据集分成两部分,分别选择合适的损失函数,构建出两个不平行的决策函数[17]。

f1(x)=(w1,x)+b1

(1)

f2(x)=(w2,x)+b2

(2)

式中:x∈Rn,w1,w2是权重向量,b1,b2是偏置,(·,·)表示内积。

为了使预测效果最好,需要找到最优决策函数,可通过求解如下原始问题得到

(3)

(4)

式中:‖·‖表示L2范数,C1,C2是惩罚参数,ε1,ε2>0是常数,ξ,θ是松弛向量,e是m×1维单位列向量。

通过引入拉格朗日乘子δ,η,根据Karush-Kuhn-Tucker(KKT)条件得到如下对偶形式

(5)

(6)

式中:G=[Ae],h1=y-ε1e和h2=y+ε2e,式(5)和式(6)的最优解分别为

(7)

(8)

当解出f1(x)和f2(x)后,决策函数如下

(9)

在非线性情况下,可通过引入核函数映射到高维空间进行求解。输入矩阵A∈Rm×n变为K(A,AT),式(1)和式(2)变为

f1(x)=K(xT,AT)w1+b1

(10)

f2(x)=K(xT,AT)w2+b2

(11)

相应的决策函数与式(9)类似。

2 本文算法

2.1 灰狼优化算法

灰狼优化算法是一种基于模仿灰狼领导层次和狩猎机制提出的元启发式优化算法,适用于具有未知搜索空间的寻优问题。灰狼族群分为4个等级,从高到低依次记为α,β,γ,τ,其中α,β,γ是领导阶层,各个阶层分工明确,互相协作。灰狼算法的整个优化过程就是α,β,γ,τ的位置更新过程,分成如下3个阶段:

第一阶段:根据狼群包围猎物机制,在建立数学模型时表示为

D=|E·Xp(t)-X(t)|

(12)

X(t+1)=Xp(t)-L·D

(13)

式中:Xp(t)表示更新后的α,β,γ狼三个等级的最优位置,X(t)表示所有可能解,即当前狼群的位置,L和E表示t时刻位置更新的系数,计算方式如下

L=2a·r1-a

(14)

E=2·r2

(15)

式中:a的值根据迭代次数的增加从2线性减小到0,r1和r2是[0,1]之间的随机数。

在包围过程中,狼群的位置根据当前更新的α,β,γ3个等级的位置不断进行调整,目的是寻找到最优的猎物位置。

第二阶段:在捕猎过程中,由α,β,γ3个等级主导寻找方向,向猎物位置靠近,其位置按照如下方式计算

Dα=|E1·Xα-X|X1=Xα-L1·Dα

Dβ=|E2·Xβ-X|X2=Xβ-L2·Dβ

(16)

Dγ=|E3·Xγ-X|X3=Xγ-L3·Dγ

(17)

根据以上公式得到α,β,γ的最优位置后,其他狼就可以据此进行位置更新,X(t+1)是更新后α,β,γ的位置。α,β,γ的位置更新过程如图1所示。

第三阶段:攻击猎物,确定猎物位置,通过|L|的大小来确定是否找到猎物位置,而L的值在[-a,a]之间。当|L|≤1,算法收敛,可以得到猎物位置。

2.2 GWOTSVR算法步骤

本文中灰狼优化算法的适应度函数fit依次设置为均方根误差(Root mean square error,RMSE)和平均绝对误差(Mean absolute error,MAE),另一方面也是作为评价算法预测性能的性能指标,RMSE和MAE分别按如下方法计算

(18)

(19)

利用GWO算法分别迭代搜索最小的均方根误差和平均绝对误差,从而确定孪生支持向量回归机的最优惩罚参数C1和C2。

基于灰狼优化算法的孪生支持向量回归机算法的具体步骤如下:

步骤1设置种群规模population,最大迭代次数M,参数取值上下界,需要优化参数的个数,初始迭代次数l=0;

步骤2将灰狼种群分成α,β,γ共3个等级,每个等级的狼群位置设置为(0,0),令每个等级的狼群适应度函数值fitα,fitβ,fitγ均为无穷大,按照下式初始化惩罚参数C1,C2

c1=rand(population ,1)×(ub-lb)+lb

c2=rand(population ,1)×(ub-lb)+lb

(20)

步骤5判断是否遍历c1,c2,若没有,转到步骤3;否则,转到步骤6;

步骤6根据式(16)计算灰狼群每个个体位置,由式(17)计算最优的惩罚参数C1,C2;

步骤7判断是否遍历每个灰狼个体,若没有,转到步骤6,否则,转到步骤8;

步骤8若l>M,则寻优结束,输出最优惩罚参数C1,C2;否则l=l+1,转步骤2。

3 仿真实验

3.1 实验设计与参数设置

仿真实验分别在线性和非线性情况下验证GWOTSVR算法的预测性能,并突出GWOTSVR算法在缩短寻优时间上的优势。仿真软件采用的是Matab2017a,所有的仿真实验均在内存为4GB的联想G50笔记本上运行。实验中采用UCI数据库中的Container、Airfoil、Yacht、Residential_Building、Real_estate、Boston、Akbilgic、Enb2012和Concrete共9个基准测试数据集,如表1所示。

表1 基准测试数据集

实验中将在每个基准测试数据集中随机不重复选取一半样本用于训练,另一半样本用于测试。设置GWOTSVR算法的种群大小为10,最大迭代次数为100,惩罚参数C1和C2的取值范围为[0.01,100],孪生支持向量回归机中的ε1=ε2=0.1。

实验选取网格优化的孪生支持向量回归机(Grid twin support vector regression,GridTSVR)、基于粒子群算法的孪生支持向量回归机(Twin support vector regression based on particle swarm optimization,PSOTSVR)[18]、基于布谷鸟搜索算法的孪生支持向量回归机(Twin support vector regression based on Cuckoo search,CSTSVR)[19]、基于遗传算法的孪生支持向量回归机(Twin support vector regression based on genetic algorithm,GATSVR)[20-23]与GWOTSVR算法进行比较。为了保证实验的公平性,本文将GridTSVR算法的惩罚参数C1和C2的取值范围设置为与GWOTSVR算法相同。设置遗传算法种群大小为2,编码长度为10,交叉概率0.6,变异概率0.001,最大迭代次数为100;设置粒子群算法两个学习因子φ1=φ2=0.5,种群大小为10,最大迭代次数为100,惩罚参数C1和C2的取值范围为[0.01,100];设置布谷鸟算法种群大小为10,最大迭代次数为100,切换概率为0.25,levy指数为1.5,步长缩放因子为0.01。

3.2 实验结果与分析

3.2.1 线性结果

经过20次实验,得到的RMSE和MAE的平均值如表2所示。在线性情况下,GWOTSVR算法在基准数据集上RMSE和MAE的结果共有11个最优,CSTSVR算法的RMSE和MAE结果共有3个最优,GATSVR算法的RMSE和MAE结果共有3个最优,GridTSVR算法仅有1个最优结果。说明在线性情况下,GWOTSVR的综合预测性能更佳。

表2 线性情况下的实验结果

GridTSVR算法、PSOTSVR算法、CSTSVR算法、GATSVR算法和GWOTSVR算法的寻优时间对比实验结果如图2所示。由图2可以看出,GridTSVR算法的寻优效率低,原因是GridTSVR是在搜索范围内按照固定步长依次搜索,寻优过程机械重复;而PSOTSVR算法、CSTSVR算法、GATSVR算法与GWOTSVR等群智能算法则根据适应度函数自动更新寻优方向,寻优过程得到改进,寻优时间显著缩短。PSOTSVR算法需要设置的参数比GWOTSVR算法多,参数设置不准确将直接降低算法的预测性能;GATSVR算法结构较为复杂,需要经过选择,交叉,变异等过程,算法的寻优过程较为复杂,因此寻优时间相对较长;CSTSVR算法需要用levy飞行增强寻优性能,因而增加了算法的运行时间。GWOTSVR算法与本文其他智能算法相比,所需要设置的参数较少,结构相对简单,且收敛速度快,易实现,资源占用少,寻优时间最短。

3.2.2 非线性结果

选取多项式K(x,y)=[1+(x,y)]2作为核函数。与线性情况一样,选择RMSE和MAE作为性能评价指标,经过20次试验,得到RMSE和MAE的平均值,结果如表3所示。

从表3可以看出,非线性情况下,GWOTSVR算法与GATSVR算法各有7个实验结果最优,CSTSVR算法有3个实验结果最优,GridTSVR仅有1个实验结果最优;而GWOTSVR算法与GATSVR算法相比,GWOTSVR算法有10个实验结果优于GATSVR算法,1个相同,说明GWOTSVR算法的综合预测性能优于GATSVR算法。因此,在非线性情况下,GWOTSVR算法的综合预测性能更佳,寻优性能更好。

非线性情况下,GridTSVR,PSOTSVR,CSTSVR,GATSVR和GWOTSVR 5种算法在不同训练集下的寻优时间如图3所示。

从图3可以看出,由于引入了核函数,将数据映射到高维空间,相同数据集上的寻优时间与线性情况相比均有所增加。但是,群智能算法的寻优时间均比网格寻优少,尤其当训练样本个数增加时,群智能算法寻优时间优势显著。而GWO算法由于结构简单,算法稳定性强,收敛速度快,易实现,所需的寻优时间仍然比PSOTSVR,CSTSVR,GATSVR 3种智能算法少,可以在最短的时间内寻找到最优解。

综上所述,本文研究的GWOTSVR算法无论在线性还是非线性情况下,均能够找到合适的惩罚参数,且预测性能优于传统的网格寻优算法。与其他智能算法相比,GWOTSVR算法综合预测性能较好。更为重要的是,GWOTSVR算法所需要的寻优时间在线性和非线性情况下均小于其他算法。

4 结论

为了解决孪生支持向量回归机的参数选取问题,本文提出了GWOTSVR算法。该算法将均方根误差和绝对平均误差作为灰狼优化算法的适应度函数,通过有限次数迭代完成了对孪生支持向量回归机惩罚参数C1和C2的寻优。与现有算法相比,GWOTSVR算法具有更好的预测性能,能在最短的时间内搜索到最优参数。