改進(jìn)的布谷鳥搜索算法對(duì)支持向量機(jī)參數(shù)優(yōu)化

顧佳鑫，賀興時(shí), 劉 青

(西安工程大學(xué) 理學(xué)院， 陜西 西安 710048)

0 引 言

1995年，CORTES等學(xué)者基于VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原則(SRM)，提出了支持向量機(jī)理論，將需要處理的分類問題轉(zhuǎn)化為凸二次規(guī)劃問題[1]。目前,已被廣泛應(yīng)用到智能交通[2]、金融預(yù)測[3]、生物醫(yī)學(xué)和圖像處理[4]等領(lǐng)域。

雖然SVM具有訓(xùn)練速度快和精確度高的優(yōu)點(diǎn)，但SVM的性能受模型參數(shù)懲罰因子C和核函數(shù)的參數(shù)σ的影響[5]。因此，如何選擇這2個(gè)參數(shù)是SVM研究的熱點(diǎn)和難點(diǎn)。傳統(tǒng)的SVM參數(shù)優(yōu)化方法為網(wǎng)格搜索法、實(shí)驗(yàn)法、交叉驗(yàn)證法[6]和梯度下降法[7]。網(wǎng)格法和實(shí)驗(yàn)法耗時(shí)長；交叉驗(yàn)證法計(jì)算量大，難以實(shí)現(xiàn)2個(gè)以上的參數(shù)選取；梯度下降法對(duì)初始值選擇敏感，實(shí)驗(yàn)結(jié)果誤差大。因此，設(shè)計(jì)高效的參數(shù)尋優(yōu)方法是目前的研究重點(diǎn)。

群智能算法在參數(shù)優(yōu)化方面具有較強(qiáng)的并行處理能力，同時(shí)具有全局尋優(yōu)的優(yōu)點(diǎn)，故常用于SVM的參數(shù)優(yōu)化[8]。具有代表性的為粒子群算法(PSO)[9]、人工魚群算法(AFSA)[10]、人工蜂群算法(ABC)[11]、螢火蟲算法(FA)[12]、蝙蝠算法(BA)[13]、花授粉算法(FPA)[14]和布谷鳥搜索算法(CS)[15]等。

針對(duì)原始布谷鳥搜索算法易陷入局部最優(yōu)解、收斂速度慢、求解精度低的問題，宋慶慶等將混沌序列引入到布谷鳥搜索算法中來初始化鳥窩位置，增加布谷鳥種群多樣性[16]；陳程等提出了動(dòng)態(tài)權(quán)重改變自適應(yīng)概率的雙重搜索布谷鳥算法(DECS)，通過在尋優(yōu)過程中引入的新型步長因子以及記憶策略，實(shí)現(xiàn)算法雙重搜索模式的能力[17]；張珍珍等將多階段動(dòng)態(tài)擾動(dòng)引入到布谷鳥搜索算法中，并提出融合正弦余弦和種群初始化策略的布谷鳥算法[18-19]。該算法提高了求解精度，具有更好的優(yōu)化性能。但上述文獻(xiàn)都沒有提到改進(jìn)后布谷鳥搜索算法的應(yīng)用問題。

為了提高原始布谷鳥搜索算法的尋優(yōu)能力，本文提出改進(jìn)的布谷鳥搜索算法(GFCS)：用動(dòng)態(tài)發(fā)現(xiàn)概率P代替固定發(fā)現(xiàn)概率Pa，自適應(yīng)地調(diào)整布谷鳥萊維飛行的步長控制因子α，在布谷鳥隨機(jī)游走更新公式中改進(jìn)動(dòng)態(tài)慣性權(quán)重w*；利用GFCS算法優(yōu)化SVM的懲罰因子C和核函數(shù)參數(shù)σ解決SVM參數(shù)選擇盲目的問題，并和傳統(tǒng)的SVM、粒子群算法優(yōu)化SVM、螢火蟲算法優(yōu)化SVM和布谷鳥搜索算法優(yōu)化SVM進(jìn)行比較。

1 支持向量機(jī)

支持向量機(jī)的原理是建立一個(gè)分類超平面作為決策面，使得正類和負(fù)類樣本間隔最大化。將大小為l的訓(xùn)練樣本集{(xi,yi),i=1,2,…,l}分為2類：如果xi∈Rn屬于第1類，則標(biāo)記(yi=1)為正；如果xi∈Rn屬于第2類，則標(biāo)記(yi=-1)為負(fù)。其中Rn為樣本空間的維數(shù)[1]?？汕蟮米顑?yōu)分類超平面：

(1)

式中：w為超平面法向量；b為閾值；C為懲罰因子；ξi為松弛變量；φ(xi)為映射函數(shù)。引入Lagrange函數(shù),得到式(1)的對(duì)偶問題：

(2)

求解式(2)得到最優(yōu)分類函數(shù)：

(3)

式中：ai(i=1，2,…,l)T為Lagrange乘子，K(xi,xj)=φ(xi)Tφ(xj)為核函數(shù)。本文采用徑向基核函數(shù)作為SVM模型的核函數(shù)，表達(dá)式為

K(xi,xj)=exp(-‖xi-xj‖2/2σ2)

其中σ為核函數(shù)參數(shù)。

2 布谷鳥搜索算法及改進(jìn)

2.1 原始布谷鳥搜索算法

布谷鳥搜索算法起源于布谷鳥孕育雛鳥的行為。一些布谷鳥在生產(chǎn)時(shí)會(huì)將自己的蛋放入百靈鳥、黃鶯等宿主鳥的巢中，讓它們代替自己喂養(yǎng)雛鳥。當(dāng)宿主鳥發(fā)現(xiàn)鳥蛋來源不明，就會(huì)拋棄這些外來的鳥蛋或者重新筑巢。為了模擬布谷鳥的孕育雛鳥行為，YANG等提出了以下3條理想規(guī)則[20]：

1) 布谷鳥一次只產(chǎn)下一個(gè)蛋，并隨機(jī)選擇鳥窩來孵化；

2) 最好的鳥窩將被保留到下一代；

3) 可選擇的鳥窩數(shù)量N是固定的,宿主鳥發(fā)現(xiàn)外來鳥蛋的概率Pa∈[0,1]。

基于以上3個(gè)理想狀態(tài)，YANG等采用式(4)更新下一代鳥窩位置[20]:

i=1,2,…,N

(4)

(5)

式中：α0為常數(shù)，一般取0.01;xb為當(dāng)前最優(yōu)解。

L(λ)～μ=t-λ(1<λ≤3)

(6)

由式(6)可知，布谷鳥在尋窩過程中，其飛行路徑變化為帶有重尾的概率分布，使得布谷鳥飛行路徑表現(xiàn)出了萊維飛行的本質(zhì)，即在尋優(yōu)路徑中頻繁的短步長偶爾會(huì)出現(xiàn)長步長。采用式(7)計(jì)算萊維隨機(jī)數(shù)[21]：

(7)

式中：μ和v服從標(biāo)準(zhǔn)正態(tài)分布；β=1.5，

結(jié)合式(4)～(7)，CS算法通過萊維飛行采用式(8)更新鳥窩位置：

(8)

(9)

2.2 改進(jìn)的布谷鳥搜索算法(GFCS)

2.2.1 動(dòng)態(tài)調(diào)整發(fā)現(xiàn)概率

在原始布谷鳥算法中，用固定的發(fā)現(xiàn)概率Pa=0.25控制全局搜索和偏好隨機(jī)游走，不利于全局搜索和局部搜索之間的平衡。本文提出動(dòng)態(tài)發(fā)現(xiàn)概率P代替固定發(fā)現(xiàn)概率Pa提高算法尋優(yōu)性能

(10)

式中：t為當(dāng)前迭代的次數(shù)；T是最大迭代次數(shù)。P隨t的變化如圖1所示。

圖 1 動(dòng)態(tài)發(fā)現(xiàn)概率變化Fig.1 Change of dynamic discovery probability

由圖1可以看出，動(dòng)態(tài)發(fā)現(xiàn)概率P在[0.1,0.4]之間隨迭代次數(shù)不斷增大。迭代前期以較小的P進(jìn)行全局搜索;隨著迭代過程的進(jìn)行，P不斷增大，直至迭代后期；當(dāng)P相對(duì)較大時(shí)，幫助算法在靠近全局最優(yōu)解時(shí)進(jìn)行局部精細(xì)搜索，提高算法的運(yùn)算精度和搜索效率。

2.2.2 自適應(yīng)調(diào)整步長

針對(duì)原始布谷鳥搜索算法尋優(yōu)精度低的缺點(diǎn)，通過自適應(yīng)地調(diào)整布谷鳥萊維飛行的步長因子α,使得萊維飛行步長隨迭代的進(jìn)行不斷減小。在尋優(yōu)初期擁有較大的步長因子，從而擴(kuò)大算法前期的搜索空間，提高全局尋優(yōu)能力；在尋優(yōu)過程中，步長減小，提高算法局部搜索性能?；谏鲜龇治觯瑢⑹?7)的α0=0.01改成:

(11)

α0的變化如圖2所示。由圖2可以看出，α0的值隨著迭代次數(shù)非線性遞減。迭代前期α0的值較大，衰減速度較快，有利于提高算法全局尋優(yōu)能力，保證算法前期收斂速度快；迭代后期α0的值逐漸減小，衰減速度放緩，提高算法的局部搜索精度。從而將式(8)更新為：

(12)

圖 2 α0變化曲線Fig.2 Change of α0

2.2.3 動(dòng)態(tài)慣性權(quán)重的偏好隨機(jī)游動(dòng)

在原始布谷鳥算法的偏好隨機(jī)游動(dòng)環(huán)節(jié)中，采用固定上一代鳥窩位置的更新方式，見式(9)，容易造成算法在迭代后期陷入局部最優(yōu)值。本文在上一代鳥窩位置處引入動(dòng)態(tài)慣性權(quán)重w*，靈活地將上一代鳥窩位置與迭代過程動(dòng)態(tài)聯(lián)系起來。

(13)

式中：t為當(dāng)前迭代的次數(shù)；T是最大迭代次數(shù)。w*的變化如圖3所示。

圖 3 動(dòng)態(tài)慣性權(quán)重w*變化Fig.3 Change of dynamic inertia weight w*

通過圖3可以看出，w*在(0,1)之間隨迭代次數(shù)非線性遞減，即隨著迭代次數(shù)增加，w*逐步減小。在迭代前期，給上一代鳥窩位置賦予相對(duì)大的w*，使上一代鳥窩具有更大的作用能力與范圍，幫助布谷鳥算法在前期擴(kuò)大搜索空間，廣泛尋找全局最優(yōu)解；到迭代后期，算法接近最優(yōu)解時(shí)，對(duì)上一代鳥窩位置采用相對(duì)較小的w*，有效地削弱了上一代鳥窩的保留信息，幫助布谷鳥算法有效跳出局部最優(yōu)，使布谷鳥個(gè)體具有更好的局部尋優(yōu)能力。將式(9)更新為

(14)

3 GFCS算法對(duì)SVM參數(shù)優(yōu)化

GFCS算法在優(yōu)化SVM參數(shù)時(shí)，將待優(yōu)化的參數(shù)組合(C,σ)模擬為鳥窩，具體步驟如下：

1) 原始數(shù)據(jù)集為訓(xùn)練集和測試集，并進(jìn)行數(shù)據(jù)歸一化。數(shù)據(jù)歸一化公式為

(15)

式中：x、x*分別為歸一化前后的樣本值；xmax、xmin分別為樣本數(shù)據(jù)中的最大、最小值。

2) 初始化參數(shù)。包括布谷鳥種群規(guī)模、布谷鳥鳥窩的位置、最大迭代次數(shù)、步長因子，被發(fā)現(xiàn)概率Pa、參數(shù)取值上下界及自變量(懲罰因子C和核函數(shù)的參數(shù)σ)等。

3) 隨機(jī)分布鳥窩(C,σ)。采用式(16)作為布谷鳥鳥窩位置的適應(yīng)度函數(shù)，并計(jì)算鳥窩的適應(yīng)度值

(16)

式中：t為當(dāng)前迭代的次數(shù)；a(t)為第t次迭代分類準(zhǔn)確率。

4) 比較適應(yīng)度值，保存當(dāng)前最小適應(yīng)度值及對(duì)應(yīng)的鳥窩位置xi。

5) 根據(jù)改進(jìn)后布谷鳥搜索式(12)、(14)更新鳥窩位置xi，并計(jì)算適應(yīng)度值。

6) 產(chǎn)生一組隨機(jī)數(shù)，與被發(fā)現(xiàn)概率Pa進(jìn)行比較：若隨機(jī)數(shù)小于被發(fā)現(xiàn)概率，則隨機(jī)改變鳥窩位置；否則，保持原鳥窩位置不變。更新后的鳥窩位置有可能超出解空間范圍，需要將其限制在解空間內(nèi)：

(17)

式中：xmin和xmax分別為解空間的最大值和最小值i=1,2,…,n。

7) 比較適應(yīng)度值，找到當(dāng)前最優(yōu)解并保留原最優(yōu)鳥窩位置。

8) 若達(dá)到最大迭代次數(shù)或滿足停止迭代條件，則轉(zhuǎn)至9)；否則轉(zhuǎn)至2)繼續(xù)迭代。

9) 輸出最小適應(yīng)度值并保留最優(yōu)鳥窩，即得到最優(yōu)參數(shù)組合(C,σ)。

10) 將輸出的最優(yōu)參數(shù)C,σ進(jìn)行SVM模型的訓(xùn)練和測試。

4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)在Matlab環(huán)境下實(shí)現(xiàn)，硬件配置為Windows 10操作系統(tǒng)，4 GiB內(nèi)存，1 TiB硬盤，i7-7500和3.1 GHz主頻CPU的計(jì)算機(jī)。

4.1 GFCS算法性能

為了分析GFCS算法的優(yōu)化性能，選擇6個(gè)常用的基準(zhǔn)測試函數(shù)進(jìn)行測試。其中Ackley、Rastrigin、Griewank為具有多個(gè)局部最小值的多峰函數(shù)，用于測試算法跳出局部極值，避免陷入局部最優(yōu)的能力；Schwefel's2.2、Sphere、Sum square為單峰函數(shù)，用于測試算法的優(yōu)化精度和收斂速度。所選擇的6種函數(shù)設(shè)置見表1。

本次實(shí)驗(yàn)將提出的GFCS算法與PSO算法[22]、FA算法[23]、CS算法[20]進(jìn)行比較。參數(shù)設(shè)置如表2，實(shí)驗(yàn)結(jié)果如圖4所示。

表 1 基準(zhǔn)測試函數(shù)Tab.1 Benchmark function

表 2 算法參數(shù)設(shè)置Tab.2 Algorithm parameter settings

(a) Ackley函數(shù)收斂曲線 (b) Rastrigin函數(shù)收斂曲線

(c) Griewank函數(shù)收斂曲線 (d) Schwefel′s2.2函數(shù)收斂曲線

(e) Sum square函數(shù)收斂曲線 (f) Sphere函數(shù)收斂曲線圖 4 不同算法在6種測試函數(shù)上收斂曲線Fig.4 Convergence curves of different algorithms on six test functions

4.2 GFCS算法優(yōu)化SVM參數(shù)實(shí)驗(yàn)

為了驗(yàn)證GFCS算法對(duì)SVM的參數(shù)優(yōu)化的有效性，選用徑向基核函數(shù)作為實(shí)驗(yàn)核函數(shù)，優(yōu)化對(duì)象為懲罰因子C和核函數(shù)的參數(shù)σ。采用UCI數(shù)據(jù)庫中的標(biāo)準(zhǔn)數(shù)據(jù)集測試模型性能，實(shí)驗(yàn)數(shù)據(jù)集描述如表3所示。

表 3 實(shí)驗(yàn)數(shù)據(jù)集描述Tab.3 Description of experimental data sets

從圖4可以看出：GFCS算法收斂速度、穩(wěn)定性和尋優(yōu)能力明顯高于PSO、FA、CS等算法，并且GFCS算法適應(yīng)度值最低。表明GFCS算法全局尋優(yōu)能力較強(qiáng)，不易陷入局部最優(yōu)解。

實(shí)驗(yàn)中，選取未優(yōu)化參數(shù)的SVM、基于粒子群算法的SVM(PSO-SVM) 、基于螢火蟲算法的SVM(FA-SVM)和基于布谷鳥搜索算法的SVM(CS-SVM)作為對(duì)比實(shí)驗(yàn)，與GFCS-SVM相比較。

參數(shù)設(shè)置如下：SVM的懲罰因子C和核函數(shù)的參數(shù)σ上界為100，下界為0.01；PSO算法速度上界為5，下界為-5，學(xué)習(xí)因子γ1=γ2=1.5；FA算法步長因子k=0.5，光強(qiáng)吸收系數(shù)r=1，最大吸引度h=0.2；CS算法被發(fā)現(xiàn)概率Pa=0.25，步長因子a0=0.01；GFCS算法動(dòng)態(tài)發(fā)現(xiàn)概率P∈[0.1,0.4]，自適應(yīng)步長因子a0∈[0,0.02]，慣性權(quán)重w*∈[0,1]。PSO、FA、CS和GFCS算法的種群規(guī)模N=30，最大迭代次數(shù)T=200。

通過各個(gè)算法在6個(gè)UCI數(shù)據(jù)集上的實(shí)驗(yàn)仿真，分析GFCS-SVM分類性能。圖5給出了GFCS算法優(yōu)化SVM參數(shù)后在不同數(shù)據(jù)集分類效果，表4給出各算法在不同數(shù)據(jù)集上尋找的最優(yōu)懲罰因子C和核函數(shù)的參數(shù)σ，表5給出各算法在不同數(shù)據(jù)集的分類準(zhǔn)確率。結(jié)合圖5和表5可以看出，GFCS-SVM在6個(gè)UCI數(shù)據(jù)集上都得到了最佳分類準(zhǔn)確率。因此，和傳統(tǒng)的SVM、原始群智能算法優(yōu)化SVM相比，GFCS算法優(yōu)化后SVM具有更好的分類效果。這是因?yàn)镚FCS-SVM全局尋優(yōu)和局部搜索最優(yōu)解能力增強(qiáng)，可以更精確地鎖定懲罰因子C和核函數(shù)的參數(shù)σ(見表4)，使得SVM分類準(zhǔn)確率提高。

(a) Heart-c數(shù)據(jù)集 (b) Ionosphere數(shù)據(jù)集

(c) Wine數(shù)據(jù)集 (d) Iris數(shù)據(jù)集

(e) Glass數(shù)據(jù)集 (f) Image-seg數(shù)據(jù)集圖 5 GFCS-SVM在不同數(shù)據(jù)集的分類結(jié)果Fig.5 Classification result of GFCS-SVM on different data sets

表 4 各算法在不同數(shù)據(jù)集上尋找的最優(yōu)參數(shù)

表 5 各算法在不同數(shù)據(jù)集上的分類準(zhǔn)確率

5 結(jié) 語

針對(duì)原始布谷鳥搜索算法存在的易陷入局部最優(yōu)、求解精度低,以及收斂速度慢等問題，從發(fā)現(xiàn)概率、步長因子和慣性權(quán)重等3個(gè)方面改進(jìn)原始算法，提出了GFCS算法。通過6個(gè)基準(zhǔn)測試函數(shù)的仿真，結(jié)果表明GFCS算法收斂速度快、有很強(qiáng)的穩(wěn)定性和尋優(yōu)能力。將GFCS算法應(yīng)用于SVM懲罰因子C和核函數(shù)的參數(shù)σ尋優(yōu)，避免了SVM參數(shù)選擇盲目性；通過在6個(gè)UCI數(shù)據(jù)集進(jìn)行測試，與未優(yōu)化參數(shù)的SVM、PSO-SVM、FA-SVM、CS-SVM相比，GFCS-SVM分類效果最好。因此，GFCS算法是有效的SVM參數(shù)優(yōu)化算法。未來可以將GFCS算法應(yīng)用于其他SVM模型，如最小二乘支持向量機(jī)、孿生支持向量機(jī)和非平行超平面支持向量機(jī)等，解決大規(guī)模數(shù)據(jù)分類問題。