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

(南昌大學,南昌市醫(yī)工結合研究重點實驗室,江西 南昌330031)

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

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

1 支持向量機基本原理

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

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

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

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

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

2 灰狼算法

灰狼優(yōu)化算法是通過模擬狼群的等級制度和捕食策略,以迭代的方式不斷尋找最優(yōu)值的一種群優(yōu)化算法[13]?；依菄栏褡袷刂粋€社會支配等級關系,其等級制度形如圖1所示的金字塔式結構。根據(jù)灰狼種群中每個個體的適應度,將狼群中適應度最好的三匹灰狼,依次標記為α、β、δ,而剩余的灰狼標記為ω,GWO算法的優(yōu)化過程主要由每代種群中的最好三個解來指導完成。

圖1 灰狼群體等級

①包圍獵物

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

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

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

②獵捕

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

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

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

3 改進灰狼算法

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

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

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

圖2 非線性收斂因子

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

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

DDGWO算法流程如下:

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

②遍歷當前種群灰狼,計算適應度值；

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

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

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

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

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

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

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

4 實驗分析

4.1 DDGWO算法性能測試

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

表1 標準測試函數(shù)

表2 算法實驗結果

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

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

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

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

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

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

圖3 5種類型心電信號

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

表3 小波分量于頻帶范圍對應關系

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

式中:Edi為第di尺度細節(jié)系數(shù)能量,Eai為第i層小波分解的近似系數(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ā)式算法具有一定隨機性,在相同試驗環(huán)境下,各算法模型分別獨立運行10次,并進行對比分析,具體如表4所示。

表4 各算法模型10次獨立試驗分類結果

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

5 結論

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