整體退火遺傳算法用于FIR濾波器的頻率采樣設(shè)計(jì)

1、第24卷第4期増刊儀器儀表學(xué)報(bào)2003年8月FIR劉從新吉培榮曾維魯 (三峽大學(xué)電氣信息學(xué)院宜昌443002)整體退火遺傳算法(WAGA)是一種新的遺傳算法.它將退火機(jī)制引入選擇算子并允許父代加入競(jìng)爭(zhēng)便遺傳算法更 加穩(wěn)健、高效。本文將WAGA應(yīng)用到F1R濾波器的頻率采樣設(shè)計(jì)對(duì)過(guò)渡帶樣本的取值進(jìn)行了優(yōu)化仿真結(jié)果表明用該方法 設(shè)計(jì)的濾波器有良好的頻率特他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期増刊儀器儀表學(xué)報(bào)2003年8月 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 第24卷第4期増刊儀器儀表學(xué)報(bào)2003年8月頻率采樣技

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

6、序列.它是原序 列的近似所以其頻率特性也將逼近原來(lái)的序列。對(duì)于 一個(gè)理想的的頻率特性H d (/).其單位樣值響應(yīng)為H (n)對(duì)在單位圓上作N等份得到H(k),對(duì)H(k)進(jìn)廳 IFFT變換得到有限長(zhǎng)h (n),設(shè)H (z)是其系統(tǒng)函數(shù). 則：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儀器儀表學(xué)握第24卷4(k)=卜2“嚴(yán)k= 0,.

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

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

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

10、目標(biāo)函數(shù)E= max(|6|)5為阻帶最大波動(dòng)個(gè) 體i的適應(yīng)度定義為：f(i)= 1/6i=0,M M為群體的規(guī)模 (8)3 3141設(shè)當(dāng)前群體為p-從中隨機(jī)地選擇n個(gè)個(gè)體作為 父代群體4體“的適應(yīng)度函數(shù)為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變異運(yùn)算中采用基本位運(yùn)算即0變?yōu)?. 1變?yōu)?0：交叉采用不定點(diǎn)交叉，交叉點(diǎn)|0.21),具體值隨機(jī) 產(chǎn)生。3 5遺傳算法的運(yùn)疔參數(shù)主要包括群體大小、變異概

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

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

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

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

15、ved, 466儀器儀表學(xué)扭第24卷個(gè)樣本在k為8, 9. 10及k為53. 54. 55處。在這里. 為了滿足濾波器的戳止恃性我們選擇k= & 9. 53. 54 設(shè)置過(guò)渡帶采樣值假設(shè)用4表示過(guò)渡帶樣本的 值.OCt.ChOCLCl.則頻域抽樣的幅度響應(yīng)為：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)其后的運(yùn)算過(guò)程如圖2 所示。(2)遺傳計(jì)算(選擇最優(yōu)秀的個(gè)體得到最優(yōu)解) 首先設(shè)置幾個(gè)運(yùn)行參數(shù)M = 100, pc= Q 9. pm= 0. 145, generat

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

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

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

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

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