整體退火遺傳算法用于FIR濾波器的頻率采樣設計

1、第24卷第4期増刊儀器儀表學報2003年8月FIR劉從新吉培榮曾維魯 (三峽大學電氣信息學院宜昌443002)整體退火遺傳算法(WAGA)是一種新的遺傳算法.它將退火機制引入選擇算子并允許父代加入競爭便遺傳算法更 加穩(wěn)健、高效。本文將WAGA應用到F1R濾波器的頻率采樣設計對過渡帶樣本的取值進行了優(yōu)化仿真結果表明用該方法 設計的濾波器有良好的頻率特他FR濾波器整體退火遺傳算:法優(yōu)化采樣The Application of W hole Annealhg Genetic Algorithm h Desn ofFIR Filter with Frequency Samplhg TechniqueL

2、 iu Congx in J i Peirong Zeng W eilu (College cf Electrical Eng ineering & Inf onn at ion T echnohgy T h “e Gorges U diversity Y ichan 443002 China)Abstract W hole annealing genetic algoritlun (WAGA) is a new genetic algorithm It introduces annealing m echan isn to select operator and a lbw ancestor

3、 to take part in the competition, which m akes genetic algoritlun more robust and efficient In this paper, we app ly WA GA to design FIR filter w ith frequency sampling technique and optin ize samples value in transition band The sinulatbn experinents show that the filter has good frequency pertb nn

4、ancaKey words F R filter W hole annealing genetic algorithm Op tin ization Sampling 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 第24卷第4期増刊儀器儀表學報2003年8月 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 第24卷第4期増刊儀器儀表學報2003年8月頻率采樣技

5、術是一種設計FIR濾波器常常使用 的方法這種技術對于窄帶濾波器比較有效但是采用 該技術設計濾波器時存在著過渡帶采樣值如何確定的 問題。傳統(tǒng)的方法往往采用査表的方法但是査表法存 在著提供的數據不能保證最優(yōu)的問題.文獻罪表明遺 傳算法(Genetic A lgorithm .簡稱GA )的全局尋優(yōu)能力 可以克服査表法的不足利用遺傳算法搜索到的采樣 值優(yōu)于査表法。本文將張講社等人提出的一種新型遺 傳算法整體退火遺傳算2 FIR頻率采樣技術是基于頻率采樣理論的一種設計方 法。對于一個任意長的序列、對其頻譜H(k)進行N尊 份均勻抽樣利用傅立葉反變換得到一個有限長為7 的數列，這個序列是原周期序刊的主值

6、序列.它是原序 列的近似所以其頻率特性也將逼近原來的序列。對于 一個理想的的頻率特性H d (/).其單位樣值響應為H (n)對在單位圓上作N等份得到H(k),對H(k)進廳 IFFT變換得到有限長h (n),設H (z)是其系統(tǒng)函數. 則：N- 1H(Z) = h(n)乙“(1)N1H(k) = Yh(n)e j,Bk(2)H(k)= H(k)/“(3)H代表頻域的幅值。 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 464儀器儀表學握第24卷4(k)=卜2“嚴k= 0,.

7、NI 或者:(k)二 說+卜2“ 晉 k= 0,N1 (4) 由(1).(2)可得：T T勸(K)；?H (J) = H (z) |z= (其中H (e和Hd(/)有以下關系：在扌由樣頻率上的逼近二者間的偏差為零。(2) H (c)實際上是對H (k)進疔內插得到的。(3) 理想響應的波形越陡.二者之間的誤差就越 大。2 2目前主要有兩種方法i 一種是對逼近誤差不作 任何限制：另外一種就是改變過渡帶的采樣值努力使 阻帶中的波動6最小化是一種優(yōu)化算法。GA具有全 局尋優(yōu)的能力，但是現在大多數的GA收斂速度慢.不 能絕對保證不陷入局部極小，本文采用了文獻m中的 新遺傳算法來確定過渡帶的樣本值。3F

8、IR遺傳算法是一類群體搜索策略，所謂群體是指狀 態(tài)空間中的有限點集, b2,bn稱為一個群體O 其中任意一個點b= aiaiavai稱為一個染色體.而a. 則稱為基因。一般的遺傳算法是:首先產生一個父彳弋群體，然后 通過一定方向選擇出下一代群體.該群體又通過交叉. 變異產生新的群體該群體又作為父群體進彳亍迭代循 環(huán)O理論上證明遺傳算法能從概率意義上收斂于問題 的最優(yōu)解但在實踐中.遺傳算法會出現一些不近人意 的地方如易于出現早孰現象局部尋優(yōu)能力差。模擬 退火算法具有較強的同部尋優(yōu)能力這一點怡好是遺 傳算法所欠缺的兩者結合則可能產生出性能優(yōu)良的 新的全局搜索算法。整體退火遺傳算法就是將退火思 想引

9、入選擇算子.并允許父代參與竟爭的新型遺傳算 法。新算法所產生群體的每一個體都將以概率1收斂 到整體最優(yōu)解并有較快的收斂速度。3 2(1) 整體退火遺傳算法用于FIR濾波器的頻率采 樣設計過程中一個低通濾波器可以這樣表示：H.(k)= 1. 1 1, 1, lngN(0U, 1, 1, 1. 1”(0)表示7個0(6)1、0代表濾波器的幅度值,仃，t：代表過渡帶的樣 本值，用21個基因表示。1.S12的前的正負號要根據 采樣的點數和所設計濾波器的類型確定。(2) 解碼解碼值：X= (Xr- Xi) * k/(2- 1)+ Xi(7)X：右邊界x匸左邊界k:染色體代表的整數1：染色 體長度(3)

10、目標函數E= max(|6|)5為阻帶最大波動個 體i的適應度定義為：f(i)= 1/6i=0,M M為群體的規(guī)模 (8)3 3141設當前群體為p-從中隨機地選擇n個個體作為 父代群體4體“的適應度函數為f(i).wlpk,則w, 被選取的概率為：P(W,) = exp(f(i)AJ/5Jexp(f(j)Ak) (9) Tk為逐漸趨于0的退火溫度且Tp l/ln(+ 1), To= 100、1000、1500,，k= 1,2,3,3 4變異運算中采用基本位運算即0變?yōu)?. 1變?yōu)?0：交叉采用不定點交叉，交叉點|0.21),具體值隨機 產生。3 5遺傳算法的運疔參數主要包括群體大小、變異概

11、率、交叉概率、終止迭代數。運行參數對遺傳算法的求 解結果和求解效率都有一定的影響但目前尚無合浬 選擇它們的理論依據。在實際便用中往往要試算多次 才能確定出它們的合理范圍。(1) 初始群體規(guī)模M由于遺傳算法對M十分敏感二這就決定了如果 從單一的M出發(fā)就不太可能搜索到全局最優(yōu)解。& 演算中(pm= 0. 15.pt= 0.9.),筆者發(fā)現解的適應度隨 著M的變化呈現類似“周期”式波動如果在信息量充 足的M區(qū)段選取多個M進行搜索，就有可能找到全 局最優(yōu)解 所以本文進一步定義了M厲于一個集合. 即M 92,94,100.-s 114)o(2) 變異率“和交叉率p,的確定p.十分難以確定稍為不適就會產生

12、初始收斂, 一般要根據具體的問題來確定其取值。在本文中以 變異率能否使92 WM 114(偶數)中的大部分群體收 斂現最優(yōu)解作為其被選擇的依據在選擇中這種判斷 比較容易只要取出2-3個群體.比較各自在不同變 異率下的收斂趨勢然后取它們優(yōu)秀變異率的交集經 I994-2C10 China Academic Journal Electronic Publishing House. All rights reserved.466儀器儀表學扭第24卷過驗證，發(fā)現這個變異率能便得大部分群體收斂;交叉3 6 2軟件流程 1994-2010 China Academic Journal Electronic

13、Publishing House. All rights reserved, 466儀器儀表學扭第24卷率一般取0.9o(3) To 和 generatbn 的確定筆者用C語育設計了一個用整體退火遺傳算法 優(yōu)化設計F1R濾波器的程序.其流程如圖lo 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 466儀器儀表學扭第24卷GAFilter圖1根據模擬退火的思想(開始八足夠髙，最后溫度 的T足夠低.這樣得到的解就有可能是最優(yōu)解J本 文中選擇T= 1000, 1500; gener

14、ation的選擇比較簡 單只要滿足在算法結束時T足夠低就可以了。3 6FIR濾波器的設計一采用頻率采樣法可由以下的 實例來給予說明。實例給定低通濾波器的技術指標:通帶邊緣頻 率w產0. 2TT阻帶邊緣頻率0. 3tk最大通帶波動 rP= 0. 4dB,最小阻惜衰減(X= 60dB.用頻率法設計一 個64階的FIR濾波器。3 6 1計算過程(1)濾波器的計算(產生個體的適應度)首先.Aw= 2說4,所以在0. 2tk w 0. 3tt中有3 1994-2010 China Academic Journal Electronic Publishing House. All rights reser

15、ved, 466儀器儀表學扭第24卷個樣本在k為8, 9. 10及k為53. 54. 55處。在這里. 為了滿足濾波器的戳止恃性我們選擇k= & 9. 53. 54 設置過渡帶采樣值假設用4表示過渡帶樣本的 值.OCt.ChOCLCl.則頻域抽樣的幅度響應為：Hr(k)= L 1, 1, L I. L 1,11,11.47(0),t2廠tl,- 1廠1廠1廠1廠1廠1 4k)=卜少鬻k= 0,63264然后由(3)式得到H(k)其后的運算過程如圖2 所示。(2)遺傳計算(選擇最優(yōu)秀的個體得到最優(yōu)解) 首先設置幾個運行參數M = 100, pc= Q 9. pm= 0. 145, generat

16、ion 340,T= 1000具體計算過程如下： 初始化M個染色體.K= K+ lo 對該代中的M個染色體譯碼TT(t.,h),分別 代入filter(TT)計算出每個染色體的適應度f(i)。 采用退火算子計算出每個個體被選擇的概率o 用賭輪法選擇M個父體o 對M個父體進行配對交叉，在交叉過程中以概 率進行變異操作。 比較新產生的群體的最優(yōu)個體和上的最優(yōu)個 體的適應度若更好，則繼續(xù)下一代操作若不及，則恢 復上一代的所有個體。 如果.KMgcncration則回到循環(huán)運算。反之， 則結束運算O實例1用頻率采樣技術設計一個低通濾波器. 技術指標同上節(jié)。取采樣點N=64。H.(k)= 1, 1. 1

17、, 1, 1. 1, 1, t.,t2,47(0),ti, -11,1,1,1,1用染色體的長度1= 32的二進制字符串對TT (ti. t：)進行編碼op= 0. 65n高阻帶 邊緣頻率W2C 0. 871；最大通帶波動Ap= 0.3dB,最小 阻帶衰減0(= 60dBo取采樣點N二64oHJk)= 10(0).t/2,9(l),s9(0)h 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 466儀器儀表學扭第24卷 1994-2010 China Academic Jour

18、nal Electronic Publishing House. All rights reserved, 466儀器儀表學扭第24卷4Xk) =1 642nK264k= 0, 63圖3 F1R帶通濾波器幅度響應曲線 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 466儀器儀表學扭第24卷用染色體的長度L= 32的二進制字符串對TT (th)進行編碼。 1994-2010 China Academic Journal Electronic Publishing House.

19、All rights reserved, 466儀器儀表學扭第24卷p戶 0.9, pn= 0. 16, generation 350, To= 1500 表2給出了 WAGA和文獻采用的GA對TT (tu h)進行優(yōu)化計算的部分結果。本文采用整體退火遺傳算法實現了對FIR濾波 器一頻率采樣法的優(yōu)化設計.仿真表明WAGA具有 交強的局部尋優(yōu)能力其應用改善了濾波器的性能為 我忙用遺傳算法設計濾波器提供了新的手段。 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 466儀器儀表學扭

20、第24卷 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 466儀器儀表學扭第24卷GAs 92 98100 102 104 106 108 110 114 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 466儀器儀表學扭第24卷 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 466儀器儀表學扭第24卷WAGA 1273 1273 1270 1258 1259 1273 1116 1256 1273GA 1268 1271 1273 1154 1273 1114 1267 1106 12613(92 M 114)GAs