胡曉朋, 田雨波, 許永秀, 李雙雙

(江蘇科技大學(xué) 電子信息學(xué)院,鎮(zhèn)江 212003)

現(xiàn)實(shí)生活中存在著各種各樣的最優(yōu)化問(wèn)題,解決實(shí)際中復(fù)雜、多變的最優(yōu)化問(wèn)題成為研究者們研究的熱點(diǎn)．長(zhǎng)期以來(lái),人們受到大自然和生活的啟發(fā),一直在不斷探索并研究最優(yōu)化方法．在該領(lǐng)域中,具有重要意義的算法主要包括了遺傳算法[1]、粒子群優(yōu)化算法[2]等．類(lèi)電磁機(jī)制(electromagnetism-like mechanism,EM)算法是由S.I.Birbil和S.C.Fang于2003年提出的一種智能優(yōu)化算法[3]．與其它算法相比,EM算法表現(xiàn)出極其強(qiáng)大的全局搜索能力，其優(yōu)化思想是模擬電磁場(chǎng)中帶電粒子之間的吸引-排斥機(jī)制,尋優(yōu)機(jī)制簡(jiǎn)單、收斂速度快．近年來(lái)國(guó)內(nèi)外學(xué)者在資源分配[4]、醫(yī)學(xué)診斷[5]、電磁學(xué)[6]等領(lǐng)域?qū)ζ溥M(jìn)行了廣泛的應(yīng)用研究．但是,標(biāo)準(zhǔn)EM算法的后期,種群中的帶電粒子出現(xiàn)“聚集”現(xiàn)象,此時(shí)算法易陷入局部極小值．

為此,文中提出了一種改進(jìn)的類(lèi)電磁機(jī)制(improved electromagnetism-like mechanism,IEM)算法,即引入早熟的判斷和處理機(jī)制,對(duì)陷入早熟狀態(tài)的帶電粒子,迭代時(shí)以一定的概率選中進(jìn)行小波變異,進(jìn)而克服EM算法在搜索后期易陷入局部最優(yōu)的缺陷．

1 類(lèi)電磁機(jī)制(EM)算法

利用EM算法求解無(wú)約束函數(shù)優(yōu)化問(wèn)題的步驟如下:

(2) 局部搜索．對(duì)當(dāng)前xbest進(jìn)行局部搜索．一旦找到優(yōu)于xbest的粒子則停止搜索,否則需完成預(yù)先設(shè)定的迭代次數(shù),并且保持種群不變．

(3) 計(jì)算電荷量和合力．EM算法中,電荷量的計(jì)算公式為:

i=1, 2,…,m

(1)

之后,計(jì)算每個(gè)粒子所受的合力．仿照庫(kù)侖定律的定義方式,帶電粒子xi所受合力的計(jì)算公式如下:

(2)

(4) 移動(dòng)粒子．對(duì)于當(dāng)前帶電粒子xi(i=1, 2,…,m),將其沿著受力方向移動(dòng)．

(3)

式中：λ∈(0,1)為隨機(jī)數(shù)．移動(dòng)過(guò)程中,其可行移動(dòng)范圍由向量RNG=(v1,v2,…,vD)給出．向量RNG的分量表示對(duì)應(yīng)的朝上下邊界移動(dòng)的可行范圍．且有

(4)

如果移動(dòng)后的粒子目標(biāo)函數(shù)值更優(yōu),則用新粒子替換當(dāng)前粒子,否則保持不變．這樣更新了種群中全部帶電粒子的位置后,EM算法的迭代也完成了一次．

2 改進(jìn)的類(lèi)電磁機(jī)制(IEM)算法

2.1 早熟判斷與處理機(jī)制

類(lèi)電磁算法運(yùn)行到后期,帶電粒子容易出現(xiàn)“聚集”現(xiàn)象,導(dǎo)致收斂陷于停滯．文獻(xiàn)[7]給出了算法發(fā)生早熟收斂的判斷依據(jù):當(dāng)平均粒距Dis<α，且種群的適應(yīng)度方差δ2

(5)

另外,粒子的位置決定粒子的適應(yīng)度，可用所有粒子適應(yīng)度的動(dòng)態(tài)變化去判別種群的現(xiàn)狀(是否過(guò)于聚集導(dǎo)致早熟收斂),對(duì)其進(jìn)行實(shí)時(shí)監(jiān)控．群體適應(yīng)度方差為：

(6)

式中：m為種群大小,fi為粒子i的適應(yīng)度．favg為當(dāng)前所有粒子的平均適應(yīng)度,F為歸一化因子,由式(7)確定:

(7)

群體適應(yīng)度方差表示的是粒子間的聚散程度．算法迭代次數(shù)增加,不同粒子的適應(yīng)度越來(lái)越接近,δ2也會(huì)變?。?dāng)δ2

2.2 小波變異策略

小波是目前數(shù)學(xué)和工程學(xué)科中一個(gè)快速發(fā)展的領(lǐng)域[8]．其中,Morlet小波由于其更為精確、更高分辨率的譜估計(jì),已經(jīng)被廣泛應(yīng)用于各領(lǐng)域．相對(duì)于其他改進(jìn)的EM算法中使用的高斯變異[9]和柯西變異[10],Morlet小波函數(shù)產(chǎn)生正負(fù)數(shù)的概率是相同的,因此更能有效地在可行域內(nèi)進(jìn)行搜索．

文獻(xiàn)[11]給出基于小波變異的粒子群優(yōu)化算法．通過(guò)小波變異,粒子偏離當(dāng)前位置,大大豐富了已有的搜索信息,使粒子有機(jī)會(huì)向更優(yōu)的搜索區(qū)域移動(dòng)．引用以下變異公式對(duì)EM算法中的帶電粒子進(jìn)行變異:

(8)

(9)

式中：當(dāng)a=1時(shí),Morlet小波函數(shù)的99%的能量都包含在[-2.5,2.5]區(qū)間中,所以φ取值范圍區(qū)間為φ∈[-2.5a,2.5a]中的偽隨機(jī)數(shù)．a(chǎn)為尺度參數(shù),其計(jì)算公式為:

(10)

式中：ξwm為單調(diào)遞增函數(shù)的形狀參數(shù),gwm為a的上限值,t為當(dāng)前迭代次數(shù),T為最大迭代次數(shù)．

2.3 IEM算法步驟

IEM實(shí)現(xiàn)步驟如下:

步驟1 設(shè)置相關(guān)參數(shù),種群粒子初始化．

步驟2 局部搜索．

步驟3 根據(jù)式(1)和式(2)計(jì)算每個(gè)粒子的電荷量qi及所受合力Fi．

步驟4 根據(jù)式(3)更新粒子位置．

步驟5 根據(jù)粒子的適應(yīng)度函數(shù)值,計(jì)算平均粒距Dis和種群的適應(yīng)度方差δ2,并判斷Dis<α且δ2

步驟6 按概率對(duì)粒子位置進(jìn)行小波變異．

步驟7 判斷算法是否達(dá)到最大迭代次數(shù),若滿(mǎn)足則輸出全局最優(yōu)位置和其適應(yīng)度值,算法結(jié)束;否則返回步驟2．

IEM算法流程如圖1．

圖1 IEM算法流程Fig.1 Flowchart of IEM algorithm

2.4 數(shù)值驗(yàn)證實(shí)驗(yàn)

為了驗(yàn)證IEM算法的優(yōu)越性,將其與遺傳算法(genetic algorithm,GA)、粒子群(particle swam optimization，PSO)算法以及標(biāo)準(zhǔn)EM算法進(jìn)行對(duì)比．選取7個(gè)經(jīng)典高維測(cè)試函數(shù)作為測(cè)試對(duì)象[12]，其初始化信息如表1，涉及單峰、多峰、無(wú)窮極小、非凸病態(tài)等多種特性,能有效地考察算法的執(zhí)行能力．

表1 測(cè)試函數(shù)基本信息度Table 1 Information of benchmark functions

分別用GA算法、PSO算法、標(biāo)準(zhǔn)EM算法和IEM算法優(yōu)化上述7個(gè)測(cè)試函數(shù),算法獨(dú)立運(yùn)行30次,記錄30次優(yōu)化后的最優(yōu)適應(yīng)值(best fitness,BF)、平均最優(yōu)適應(yīng)值(mean best fitness,MBF)及標(biāo)準(zhǔn)差(standard deviation,SD)．具體參數(shù)設(shè)置為:維度30,種群數(shù)量50,最大迭代次數(shù)1 000,搜索范圍列于表1,GA算法遺傳算子分別為比例選擇、單點(diǎn)交叉和單點(diǎn)變異,設(shè)交叉概率為0.7,變異概率為0.1;PSO算法設(shè)權(quán)重為1,學(xué)習(xí)因子c1=c2=2;IEM算法設(shè)小波變異概率pm=0.2,形狀參數(shù)ξwm=0.5,尺度參數(shù)的上限值gwm=1 000．

從表2最優(yōu)適應(yīng)值和平均最優(yōu)適應(yīng)值可以看出,對(duì)于Sphere函數(shù)、Schwefel函數(shù)、Griewank函數(shù)和Ackley函數(shù),IEM算法求解的精度均提高了8個(gè)數(shù)量級(jí)以上．對(duì)于非凸病態(tài)函數(shù)Rosenbrock函數(shù),其他算法都陷入早熟,只有IEM算法找到了理想的解，IEM算法在Quadratic函數(shù)的求解精度上有一個(gè)數(shù)量級(jí)的提高．對(duì)于Rastrigrin函數(shù),IEM算法甚至多次找到它的全局最優(yōu)值．另一方面,標(biāo)準(zhǔn)差值反映出算法穩(wěn)定性的信息,因此，4種算法中IEM算法穩(wěn)定性最好．

表2 測(cè)試函數(shù)仿真結(jié)果對(duì)比Table 2 Comparison of the optimization for benchmark functions

3 FIR數(shù)字濾波器的設(shè)計(jì)

3.1 FIR數(shù)字濾波器介紹

設(shè)N階FIR數(shù)字濾波器的單位取樣響應(yīng)為h(0),h(1),…,h(N-1),其傳遞函數(shù)可表示為[13]:

(11)

取z=ejω,則濾波器的頻率響應(yīng)為:

(12)

若設(shè)FIR數(shù)字濾波器理想頻率響應(yīng)為|Hd(ejω)|,則在離散點(diǎn){ωi|i=1, 2,…,M}上,所設(shè)計(jì)濾波器的幅度|H(ejω)|與理想濾波器的幅度|Hd(ejω)|的誤差平方和為:

(13)

將式(12)代入式(13),可得：

(14)

FIR濾波器要選取濾波器系數(shù)h(0),h(1),…,h(N-1)使目標(biāo)函數(shù)E最小，可以用EM算法來(lái)求解．采用式(14)作為FIR濾波器設(shè)計(jì)的適應(yīng)度函數(shù)．即:

(15)

顯然Fitness值越小,得到的濾波器性能就越好．算法運(yùn)行結(jié)束后,適應(yīng)度值最小的帶電粒子所對(duì)應(yīng)的參數(shù)值就是需要求解的濾波器系數(shù)．

3.2 FIR數(shù)字濾波器仿真實(shí)例

數(shù)字濾波器采用文中所提出的算法進(jìn)行仿真實(shí)驗(yàn)設(shè)計(jì),由于高通濾波器設(shè)計(jì)過(guò)程類(lèi)似于低通濾波器,帶阻濾波器設(shè)計(jì)過(guò)程類(lèi)似于帶通濾波器,故此處僅設(shè)計(jì)低通濾波器和帶通濾波器．GA算法、PSO算法、EM算法與IEM算法分別運(yùn)行20次取平均值作為最后結(jié)果．具體參數(shù)設(shè)置如下:種群數(shù)量50,最大迭代次數(shù)1 000．GA算法遺傳算子分別為比例選擇、單點(diǎn)交叉和單點(diǎn)變異,交叉概率0.7,變異概率0.1;PSO算法中權(quán)重為1,學(xué)習(xí)因子c1=c2=2;IEM算法中小波變異概率pm=0.2,形狀參數(shù)ξwm=0.5,尺度參數(shù)的上限值gwm=1 000．例1中4種算法的仿真結(jié)果如圖2、3,例2中4種算法的仿真結(jié)果如圖4、5．

例1:設(shè)計(jì)一個(gè)階數(shù)N為21,阻帶最小衰減為20 dB的低通數(shù)字濾波器,技術(shù)指標(biāo)為:

(16)

例2:設(shè)計(jì)一個(gè)階數(shù)N為32,阻帶最小衰減為30 dB的帶通數(shù)字濾波器,技術(shù)指標(biāo)為:

(17)

圖2 FIR低通數(shù)字濾波器對(duì)數(shù)幅頻響應(yīng)Fig.2 Logarithmic amplitude-frequency curves of low pass FIR digital filters

圖3 FIR低通數(shù)字濾波器幅頻響應(yīng)Fig.3 Amplitude-frequency curves of low pass FIR digital filters

圖4 FIR帶通數(shù)字濾波器對(duì)數(shù)幅頻響應(yīng)Fig.4 Logarithmic amplitude-frequency curves of band pass FIR digital filters

圖5 FIR帶通數(shù)字濾波器幅頻響應(yīng)Fig.5 Amplitude-frequency curves of band pass FIR digital filters

由圖2可以看出,除了GA算法,其他3種算法設(shè)計(jì)的FIR低通數(shù)字濾波器的阻帶衰減都能滿(mǎn)足設(shè)計(jì)要求,但利用IEM算法設(shè)計(jì)的FIR低通數(shù)字濾波器的阻帶特性均勻變化,阻帶最小衰減比EM算法提高了近10 dB．由圖4可以看出,GA算法和PSO算法設(shè)計(jì)的FIR帶通數(shù)字濾波器未能達(dá)到設(shè)計(jì)指標(biāo),EM算法和IEM算法設(shè)計(jì)的FIR帶通數(shù)字濾波器表現(xiàn)良好,并且IEM算法對(duì)應(yīng)的阻帶最小衰減比EM算法略有提升．由圖3、5可以看出,IEM算法設(shè)計(jì)的FIR數(shù)字濾波器通帶波動(dòng)更小、比較平緩,阻帶的波紋幾乎為零,更接近理想濾波器．

4 結(jié)論

(1) 針對(duì)標(biāo)準(zhǔn)EM算法存在早熟收斂的缺陷,提出一種改進(jìn)的EM算法,引入早熟的判斷和處理機(jī)制,迭代時(shí)以一定的概率選中陷入早熟狀態(tài)的帶電粒子進(jìn)行小波變異,使其跳出局部最優(yōu)值．

(2) 將文中算法應(yīng)用于高維測(cè)試函數(shù)的求解,結(jié)果表明該方法在應(yīng)對(duì)高維復(fù)雜化問(wèn)題時(shí)具備較強(qiáng)的開(kāi)發(fā)能力．

(3) 相較標(biāo)準(zhǔn)EM算法,應(yīng)用文中算法設(shè)計(jì)的FIR數(shù)字濾波器得到了更為滿(mǎn)意的仿真結(jié)果,說(shuō)明其具有良好的參考價(jià)值．