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

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

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

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

1 類電磁機制(EM)算法

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

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

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

i=1, 2,…,m

(1)

之后,計算每個粒子所受的合力．仿照庫侖定律的定義方式,帶電粒子xi所受合力的計算公式如下:

(2)

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

(3)

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

(4)

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

2 改進的類電磁機制(IEM)算法

2.1 早熟判斷與處理機制

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

(5)

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

(6)

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

(7)

群體適應度方差表示的是粒子間的聚散程度．算法迭代次數(shù)增加,不同粒子的適應度越來越接近,δ2也會變小．當δ2

2.2 小波變異策略

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

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

(8)

(9)

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

(10)

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

2.3 IEM算法步驟

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

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

步驟2 局部搜索．

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

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

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

步驟6 按概率對粒子位置進行小波變異．

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

IEM算法流程如圖1．

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

2.4 數(shù)值驗證實驗

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

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

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

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

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

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

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

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

(11)

取z=ejω,則濾波器的頻率響應為:

(12)

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

(13)

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

(14)

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

(15)

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

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

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

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

(16)

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

(17)

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

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

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

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

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

4 結論

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

(2) 將文中算法應用于高維測試函數(shù)的求解,結果表明該方法在應對高維復雜化問題時具備較強的開發(fā)能力．

(3) 相較標準EM算法,應用文中算法設計的FIR數(shù)字濾波器得到了更為滿意的仿真結果,說明其具有良好的參考價值．