采用動(dòng)態(tài)雙子群策略改進(jìn)的灰狼算法及其在心電信號識別中的應(yīng)用?

劉繼忠謝毓順徐文斌鄧家誠李繼發(fā)丁亞飛

(南昌大學(xué),南昌市醫(yī)工結(jié)合研究重點(diǎn)實(shí)驗(yàn)室,江西 南昌330031)

近20年以來,元啟發(fā)式算法(meta-euristic algorithm)迅速發(fā)展,它是源自于自然現(xiàn)象的啟發(fā),并結(jié)合計(jì)算智能的機(jī)制求解復(fù)雜的優(yōu)化問題最優(yōu)解的方法,包括遺傳算法(Genetic Algorithm,GA)[1]、模擬退火算法(Simulated Annealing,SA)[2]、粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法[3]、差分進(jìn)化(Differential Evolution,DE)算法[4]、布谷鳥搜索(Cuckoo Search,CS)算法[5]等。

灰狼優(yōu)化算法(GWO)是Mirjalili[6]于2014年提出的一種新型的元啟發(fā)式算法。GWO算法與傳統(tǒng)的PSO算法相比,其設(shè)置參數(shù)較少,編程難度小,且GWO算法本身并不依賴于參數(shù)的設(shè)置[7]。但GWO算法在求解高維度、多模態(tài)復(fù)雜函數(shù)問題時(shí),容易陷入局部最優(yōu)和出現(xiàn)早熟收斂現(xiàn)象。針對這些缺點(diǎn),國內(nèi)外學(xué)者提出了一些改進(jìn)方法。龍文等人[8]在灰狼優(yōu)化算法中引Powell局部搜索方式,有效提高了算法局部搜索能力。張悅等[9]在灰狼個(gè)體的適應(yīng)度中引入了自適應(yīng)調(diào)整策略和位置更新策略,提升了算法運(yùn)行速度。Heidari和Pahlavani[10]提出一種高效的GWO算法用于處理全局優(yōu)化問題,該算法利用Lévy飛行策略增強(qiáng)算法的全局勘探能力,引入貪婪選擇算子加快收斂速度。Long等[11]分析了GWO算法的個(gè)體位置更新方程由全局最優(yōu)解引導(dǎo)產(chǎn)生新個(gè)體,提出了一種修改個(gè)體位置更新方程以增強(qiáng)GWO算法的全局勘探能力。本文為了解決灰狼算法易陷入局部最優(yōu)的缺點(diǎn),將雙子群策略引入GWO以改進(jìn)GWO算法,并將其應(yīng)用到SVM中,建立DDGWO-SVM模型,獲取最優(yōu)核參數(shù)和懲罰參數(shù)。并將改進(jìn)后的SVM模型應(yīng)用于心電信號識別中,提升了心電信號識別率,驗(yàn)證了該改進(jìn)算法的尋優(yōu)特性。

1 支持向量機(jī)基本原理

支持向量機(jī)(Support Vector Machine,SVM)是建立在統(tǒng)計(jì)學(xué)理論基礎(chǔ)上的一種分類方法。依據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則[12],通過選擇的核函數(shù)將輸入空間映射到高維特征空間,在高維空間構(gòu)造最優(yōu)分類超平面,并使分類間隔最大。以上問題等價(jià)于求解不等式約束條件下的二次規(guī)劃問題。

式中:C為懲罰因子,ε為松弛因子。對式(1)引入Lagrange乘子αi(i＝1,…,n)將該凸二次規(guī)劃問題轉(zhuǎn)化為對偶形式。

通過求解以上優(yōu)化問題可以得到?jīng)Q策函數(shù):

式中:K(xi,x)為核函數(shù),常見核函數(shù)有線性核函數(shù)、多項(xiàng)式核函數(shù)等。本文選取泛化能力較強(qiáng)RBF核函數(shù),其表達(dá)式如下:

根據(jù)以上推演過程可知,SVM模型的核函數(shù)參數(shù)g和懲罰因子C的不同取值,對SVM的分類性能有著重要影響。

2 灰狼算法

灰狼優(yōu)化算法是通過模擬狼群的等級制度和捕食策略,以迭代的方式不斷尋找最優(yōu)值的一種群優(yōu)化算法[13]。灰狼嚴(yán)格遵守著一個(gè)社會(huì)支配等級關(guān)系,其等級制度形如圖1所示的金字塔式結(jié)構(gòu)。根據(jù)灰狼種群中每個(gè)個(gè)體的適應(yīng)度,將狼群中適應(yīng)度最好的三匹灰狼,依次標(biāo)記為α、β、δ,而剩余的灰狼標(biāo)記為ω,GWO算法的優(yōu)化過程主要由每代種群中的最好三個(gè)解來指導(dǎo)完成。

圖1 灰狼群體等級

①包圍獵物

灰狼群體圍捕獵物時(shí),需要確定獵物與灰狼之間的距離。它們對獵物的搜索行為可以通過如下公式進(jìn)行描述:

式中:Xp(t)表示第t代獵物的位置；X(t)表示第t代時(shí)灰狼個(gè)體的位置；常數(shù)C為擺動(dòng)因子,由式(7)決定,A為收斂因子,由式(8)決定:

式中:a在迭代過程中從2線性減小到0；r1和r2是取值在[0,1]之間的隨機(jī)向量。

②獵捕

在α狼的帶領(lǐng)下,β狼和δ狼逐漸靠近獵物,可以依靠這三者來估計(jì)獵物的位置,盡量靠近這三只灰狼,也就可能離目標(biāo)最近。對于每一只ω狼首先根據(jù)式(9)、(10)計(jì)算它們與α狼、β狼、δ狼的距離,然后由(11)綜合判斷灰狼向個(gè)體移動(dòng)的方向,ω狼個(gè)體的移動(dòng)方向由α狼、β狼、δ狼來決定。

式中:X1表示α狼位置,X2表示β狼位置,X3表示δ狼位置,C1,C2,C3是隨機(jī)向量。

當(dāng)灰狼停止攻擊獵物,捕獵行為結(jié)束,獲得最優(yōu)解。整個(gè)尋優(yōu)過程通過式(8)中的收斂因子A在迭代過程中由2線性地減少到0來完成。當(dāng)｜A｜>1時(shí),在較大范圍搜索獵物,對應(yīng)全局搜索；當(dāng)｜A｜≤1時(shí),灰狼開始襲擊獵物,對應(yīng)局部搜索。

3 改進(jìn)灰狼算法

標(biāo)準(zhǔn)的灰狼優(yōu)化算法中(GWO)在解決復(fù)雜優(yōu)化問題時(shí),整個(gè)灰狼群體只向最優(yōu)個(gè)體α狼靠近,種群迭代多樣性隨著迭代次數(shù)的增加逐漸減小,且如果該位置若不是全局最優(yōu),就會(huì)使算法陷入局部最優(yōu),出現(xiàn)早熟收斂的問題。實(shí)際上,種群在整個(gè)解空間中尋優(yōu)時(shí),全局最優(yōu)解通常存在于局部最優(yōu)的附近。適應(yīng)度較高的個(gè)體有著較好的局部搜索能力,能夠引導(dǎo)種群進(jìn)行更加細(xì)致的搜索；而適應(yīng)度較低的個(gè)體有著較好的全局搜索能力,能使種群避免陷入局部最優(yōu),故種群的進(jìn)化速度更大程度取決于比較落后的個(gè)體而不是較優(yōu)秀的個(gè)體。

本文借鑒文獻(xiàn)動(dòng)態(tài)雙子群協(xié)同進(jìn)化果蠅優(yōu)化算法中的動(dòng)態(tài)雙子群策略[14],提出一種動(dòng)態(tài)雙子群策略灰狼算法(Dynamic Double-subgroup Strategy GWO,DDGWO),在迭代過程中,分別計(jì)算當(dāng)前灰狼個(gè)體與α狼的距離Disti_best和當(dāng)代最差個(gè)體的距離Disti_worst,若Disti_best≤(Disti_worst)/2,則將灰狼個(gè)體劃分為以當(dāng)代最優(yōu)位置α狼為幾何中心的較優(yōu)子群；否則,將其劃分以當(dāng)代較差個(gè)體為中心的較差子群。根據(jù)兩個(gè)子群的特點(diǎn),采取不同的非線性收斂因子,以平衡局部搜索能力和全局搜索能力。

傳統(tǒng)灰狼算法通過調(diào)整收斂因子a使灰狼種群在全局和局部搜索之間進(jìn)行協(xié)調(diào)。標(biāo)準(zhǔn)灰狼算法的收斂因子a是呈線性遞減的,難以較好的協(xié)調(diào)全局與局部搜索能力。本文提出對較優(yōu)子群與較差子群采用不同的收斂因子,對于適應(yīng)度值較高的較優(yōu)子群,在迭代初期非線性收斂因子a1值快速減小,使得適應(yīng)度較高的灰狼快速向最優(yōu)解靠攏；迭代后期a1值緩慢下降以避免局部最優(yōu),a1如式(12)。而適應(yīng)度值較低的較差子群,迭代初期a2值緩慢下降使得適應(yīng)度較低的灰狼獲得更大的尋優(yōu)范圍；迭代后期快速下降完成收斂,a2如式(13)。收斂曲線如圖2所示,其中點(diǎn)劃線表示較優(yōu)子群的收斂曲線,虛線為較差子群收斂曲線,直線表示為標(biāo)準(zhǔn)灰狼算法的收斂曲線。

圖2 非線性收斂因子

標(biāo)準(zhǔn)灰狼算法的ω狼在進(jìn)行位置更新時(shí),是由α狼、β狼以及δ狼共同決定,三只狼都是起著等同的指導(dǎo)作用,其并沒有體現(xiàn)出α、β、δ狼在指導(dǎo)ω狼進(jìn)行位置更新時(shí)的所占的比重,這種等同的指導(dǎo)會(huì)使得算法整體收斂速度變得緩慢。

本文采用一種基于歐氏距離的位置更新策略,通過式(9)中Dα、Dβ、Dδ倒數(shù)的占比作為權(quán)重系數(shù),對灰狼個(gè)體位置進(jìn)行更新,具體公式見式(14)。

DDGWO算法流程如下:

①參數(shù)初始化,設(shè)置種群規(guī)模Sizepop,最大迭代次數(shù)Maxgen,初始化灰狼位置；

②遍歷當(dāng)前種群灰狼,計(jì)算適應(yīng)度值；

③找出灰狼群體中的α狼(最優(yōu)個(gè)體),以及適應(yīng)度最差的ω狼(最差個(gè)體),分別計(jì)算并保留α狼的坐標(biāo)Xa,Ya,以及最差位置ω狼的坐標(biāo)Xw,Yw；

④利用式(15),分別計(jì)算灰狼個(gè)體i與灰狼群體中最優(yōu)個(gè)體距離Disti_best以及最差個(gè)體距離Disti_worst:

⑤若Disti_best≤(Disti_worst)/2,則將灰狼個(gè)體i劃分到較優(yōu)子群,轉(zhuǎn)步驟⑥；否則,將灰狼劃分到較差子群,轉(zhuǎn)步驟⑦；

⑥較優(yōu)子群采用收斂因子a1及歐式權(quán)重,即式(12)、式(14),對灰狼個(gè)體位置更新；

⑦較差子群利用收斂因子a2及歐式權(quán)重,即式(13)、式(14),對灰狼個(gè)體位置更新；

⑧合并較優(yōu)子群與較差子群；

⑨進(jìn)入迭代尋優(yōu),重復(fù)執(zhí)行步驟②到步驟⑧直至當(dāng)前迭代次數(shù)等于最大迭代次數(shù)

4 實(shí)驗(yàn)分析

4.1 DDGWO算法性能測試

為測試DDGWO算法尋優(yōu)性能,以表1中6個(gè)標(biāo)準(zhǔn)函數(shù)為測試函數(shù),對本算法與標(biāo)準(zhǔn)GWO算法、基于LF改進(jìn)灰狼算法(LGWO)[10]、探索增強(qiáng)灰狼算法(EEGWO)[11]、改進(jìn)灰狼算法(IGWO)[15]、混合差分進(jìn)化灰狼(HGWO)算法[16]進(jìn)行對比測試。6個(gè)函數(shù)中F1～F3為單峰測試函數(shù),F4～F6為多峰測試函數(shù)。三種算法的參數(shù)設(shè)置如下:種群規(guī)模均設(shè)置為30,最大迭代次數(shù)均設(shè)為500。測試函數(shù)在上述參數(shù)設(shè)置的條件下,為了避免單次尋優(yōu)的偶然性分別獨(dú)立運(yùn)行30次實(shí)驗(yàn),取平均值和標(biāo)準(zhǔn)差作為最終測試結(jié)果,其中LGWO、EEGWO、HGWO算法結(jié)果直接來源于參考文獻(xiàn)[10－11,16],算法結(jié)果見表2所示。

表1 標(biāo)準(zhǔn)測試函數(shù)

表2 算法實(shí)驗(yàn)結(jié)果

由表2中的6個(gè)測試函數(shù)的運(yùn)行結(jié)果來看,DDGWO算法在測試函數(shù)F1、F4、F6上均取得最優(yōu)解,并且在整體性能上明顯優(yōu)于標(biāo)準(zhǔn)的GWO算法。F1～F3單峰函數(shù)測試結(jié)果表示DDGWO算法無論是在平均值或均方差上,均明顯低于LGWO、GWO、HGWO和IGWO,相較于EEGWO的結(jié)果,兩算法在F2、F3上各有優(yōu)劣,均接近最優(yōu)解,結(jié)果表明DDGWO算法對于單峰函數(shù)有著極好的優(yōu)化精度。從F4、F5、F6多峰函數(shù)測試結(jié)果可以看出DDGWO算法獲得了較好的尋優(yōu)結(jié)果,表明相較于標(biāo)準(zhǔn)灰狼算法,在遇到局部極值時(shí)更容易跳出局部最優(yōu),與其他的GWO變體算法相比,只有EEGWO算法在函數(shù)F5上略勝與本文算法,但是在函數(shù)F6上DDGWO優(yōu)于EEGWO。

總體而言,通過對6個(gè)基準(zhǔn)測試函數(shù)的仿真實(shí)驗(yàn),與5種優(yōu)化算法作比較,實(shí)驗(yàn)結(jié)果驗(yàn)證了采用動(dòng)態(tài)雙子群策略能夠有效提高灰狼算法的性能,在大多數(shù)情況,相較于標(biāo)準(zhǔn)GWO算法和其他先進(jìn)的GWO變體算法,DDGWO有著更高的尋優(yōu)精度和尋優(yōu)穩(wěn)定性,能夠提供具有很高競爭力的優(yōu)化結(jié)果,為GWO算法的改進(jìn)提供了一種新的思路。

4.2 基于SVM的DDGWO算法心電信號識別分類

由于醫(yī)學(xué)數(shù)據(jù)涉及到個(gè)人隱私,因此目前能夠公開獲取到的心電數(shù)據(jù)數(shù)量不多。而善于處理小樣本的支持向量機(jī)(SVM)在處理心電信號問題上已經(jīng)獲得了不錯(cuò)的結(jié)果[17－18]。但是將SVM運(yùn)用于實(shí)際問題中時(shí),參數(shù)的選取對SVM的性能有著重大的影響,SVM的學(xué)習(xí)精度和泛化能力均取決于其參數(shù)優(yōu)化選擇。

為了進(jìn)一步驗(yàn)證本文提出的動(dòng)態(tài)雙子群策略灰狼算法的優(yōu)化性能,建立DDGWO-SVM模型,進(jìn)行心電異常信號識別。將算法與灰狼算法(GWO)、粒子群算法(PSO)和布谷鳥算法(CS)優(yōu)化的SVM參數(shù)尋優(yōu)識別算法性能進(jìn)行對比,并以分類正確率即識別率(Accuracy)作為評價(jià)指標(biāo)。

實(shí)驗(yàn)數(shù)據(jù)采用MIT-BIH標(biāo)準(zhǔn)心電數(shù)據(jù)庫[19]。取第一導(dǎo)聯(lián),以檢測到的R波峰之前的99個(gè)點(diǎn),之后的150個(gè)點(diǎn)作為一個(gè)完整的心拍,即每個(gè)波段包含250個(gè)采樣點(diǎn)。從MIT-BIH心電數(shù)據(jù)庫選取5類典型心電數(shù)據(jù):正常的心電信號(NB)、左束支傳導(dǎo)阻滯(LBBB)、右束支傳導(dǎo)阻滯(RBBB)、心房早期收縮(APC)、心室早期收縮(PVC)。5類心電數(shù)據(jù)每類選取300個(gè)樣本,共計(jì)選取1500個(gè)樣本；其中每類取200個(gè),共計(jì)1000個(gè)作為訓(xùn)練樣本集；其余500作為測試樣本集。5種類型心電信號具體如圖3所示。

圖3 5種類型心電信號

心電信號特征的提取采取小波變換法,與傳統(tǒng)的時(shí)域特征相比,小波變換的多分辨特性,能夠提取到更加有效的心電信息。MIT-BIH原始心電數(shù)據(jù)含有少量工頻干擾、肌電干擾、基線漂移三種噪聲。心電信號的主要頻率集中在100 Hz以下,而90%的心電信號能量集中在0.25 Hz～35 Hz之間[20]。本文使用Mallat算法對ECG信號進(jìn)行多尺度小波變換[21],采用對心電信號支撐性較好的‘bior2.4’小波進(jìn)行8層小波分解。ECG信號經(jīng)8層小波變換之后的頻帶范圍對應(yīng)關(guān)系如表3所示。

表3 小波分量于頻帶范圍對應(yīng)關(guān)系

肌電干擾、工頻干擾主要集中在第d1、d2尺度,而基線漂移位于第a8尺度。對含噪聲較多且有效心電信息偏少的d1、d2和a8尺度的子帶信號不做處理,提取并計(jì)算其余尺度(d3～d8)頻帶能量,定義各尺度能量比作為心電特征,共取6個(gè)頻帶能量比作為SVM的輸入特征向量,各尺度頻帶能量比具體計(jì)算方式見式(16)。

式中:Edi為第di尺度細(xì)節(jié)系數(shù)能量,Eai為第i層小波分解的近似系數(shù)能量。

設(shè)定各優(yōu)化算法參數(shù),其中CS算法的pa＝0.25。PSO算法的c1＝c2＝1.45,v＝0.9。DDGWO、CS、PSO、GWO算法的種群大小均為30,最大迭代次數(shù)為100,懲罰因子C與RBF核函數(shù)g的取值范圍均為[10＾(－4),10＾4]。由于啟發(fā)式算法具有一定隨機(jī)性,在相同試驗(yàn)環(huán)境下,各算法模型分別獨(dú)立運(yùn)行10次,并進(jìn)行對比分析,具體如表4所示。

表4 各算法模型10次獨(dú)立試驗(yàn)分類結(jié)果

由表4可以看出,由于GWO與PSO易陷入局部最優(yōu),雖然也能取得較好的識別率,但模型穩(wěn)定性較差。DDGWO-SVM模型相較于GWO-SVM和PSO-SVM模型,具有更好的識別率且識別穩(wěn)定性更高。雖然相較于CS-SVM模型提升較小,但由于布谷鳥算法的全局尋優(yōu)特性,算法收斂較慢,具體運(yùn)算中同等環(huán)境下CS-SVM模型的運(yùn)行時(shí)間為DDGWOSVM的兩倍左右。由此可以看出,本文提出的動(dòng)態(tài)雙子群策略灰狼算法能夠?qū)VM參數(shù)起到較好的優(yōu)化,并且以DDGWO為基礎(chǔ)所建立的DDGWOSVM模型對心電信號不但具有較高的識別率,且具有較高穩(wěn)定性。

5 結(jié)論

為了解決灰狼算法易陷入局部最優(yōu)的缺點(diǎn),本文將雙子群策略引入GWO算法,提出一種動(dòng)態(tài)雙子群策略灰狼算法,并用于SVM參數(shù)優(yōu)化以檢驗(yàn)其優(yōu)化性能?；?種函數(shù)的算法結(jié)果對比表明,與傳統(tǒng)的GWO以及其他先進(jìn)的GWO變體算法相比,DDGWO算法在單峰函數(shù)上具有優(yōu)異的尋優(yōu)能力,在多峰函數(shù)的尋優(yōu)中,遇到局部極值時(shí)能夠跳出局部最優(yōu),在大多數(shù)情況下?lián)碛懈叩膶?yōu)精度與更好的尋優(yōu)穩(wěn)定性,驗(yàn)證了所提出的DDGWO算法是有效的,進(jìn)而為GWO算法的改進(jìn)提供了一種新的思路。心電信號識別的對比實(shí)驗(yàn)結(jié)果表明,所提出的DDGWO算法能夠用在SVM參數(shù)優(yōu)化上,并且優(yōu)化后的SVM模型對心電信號不但具有較高的識別率,且具有較高穩(wěn)定性。