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

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

現實生活中存在著各種各樣的最優(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算法表現出極其強大的全局搜索能力，其優(yōu)化思想是模擬電磁場中帶電粒子之間的吸引-排斥機制,尋優(yōu)機制簡單、收斂速度快．近年來國內外學者在資源分配[4]、醫(yī)學診斷[5]、電磁學[6]等領域對其進行了廣泛的應用研究．但是,標準EM算法的后期,種群中的帶電粒子出現“聚集”現象,此時算法易陷入局部極小值．

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

1 類電磁機制(EM)算法

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

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

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

i=1, 2,…,m

(1)

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

(2)

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

(3)

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

(4)

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

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

2.1 早熟判斷與處理機制

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

(5)

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

(6)

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

(7)

群體適應度方差表示的是粒子間的聚散程度．算法迭代次數增加,不同粒子的適應度越來越接近,δ2也會變?。敠?

2.2 小波變異策略

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

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

(8)

(9)

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

(10)

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

2.3 IEM算法步驟

IEM實現步驟如下:

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

步驟2 局部搜索．

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

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

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

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

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

IEM算法流程如圖1．

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

2.4 數值驗證實驗

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

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

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

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

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

3 FIR數字濾波器的設計

3.1 FIR數字濾波器介紹

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

(11)

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

(12)

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

(13)

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

(14)

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

(15)

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

3.2 FIR數字濾波器仿真實例

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

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

(16)

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

(17)

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

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

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

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

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

4 結論

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

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

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