基于自適應遺傳算法FIR數字濾波器優化設計

摘 要:FIR數字濾波器優化設計的目標是對濾波器理想性能的逼近。遺傳算法是一種模仿生物進化過程的全局優化概率搜索算法，它提出了一種求解復雜系統優化問題的通用框架，且不依賴于問題的領域和種類，在此將自適應的遺傳算法應用于FIR數字濾波器的優化設計，通過評價種群的“早熟度”來自適應調整交叉率和變異率，提高了遺傳算法的搜索效率。計算機仿真結果證明，該算法能夠獲得滿意的濾波器性能。

關鍵詞:FIR濾波器;優化設計;自適應遺傳算法;早熟度

中圖分類號:TP274文獻標識碼:B

文章編號:1004-373X(2010)02-143-04

Optimized FIR Filter Design Based on Self_adaptive Genetic Algorithm

HUANG Meng，TANG Lin，ZHEN Yu，ZHANG Jie

(91635 Army，Beijing，102249，China)

Abstract:The goal of optimized FIR filter design is approaching to the ideal performance of IIR filter.Genetic algorithm is an optimal probability search algorithm，imitating the process of biology evolution，which has proposed an universal method to solve optimized problems of complex system，independent of domain and kind of problems.The proposed algorithm applying self_adaptive genetic algorithm to optimized IIR filter design，and adjusting cross probability and mute probability self_adaptively by evaluating premature convergence degree to improve search efficiency of genetic algorithm.The simulation results demonstrate that the proposed algorithm can achieve satisfying capability of filter.

Keywords:FIR filter;optimized design;self_adaptive genetic algorithm;premature convergence degree

在現代信號處理和電子應用技術領域，FIR數字濾波器因具有穩定性和線性相位兩大優點而得到了廣泛的應用。FIR數字濾波器的設計方法主要有窗函數法、頻率采樣法、切比雪夫逼近法，這些方法的最終目的是對理想濾波器理想性能的逼近，而不可能真正做到理想濾波器的幅頻響應，正基于此，多年來許多專家學者在數字濾波器的優化設計問題上做了大量的研究工作，在一定優化準則下，提出了一些設計方法，如Caratheodory_Fejer(CF)法[1]，神經網絡(Neural Network)法[2]，最小P誤差法[3]以及模型擬合頻率響應法[4]等。這些優化算法各長，它們在數字濾波器的設計中都取得了較好的設計效果，也為數字濾波器的設計打開了新的思路。

遺傳算法是一種模仿生物進化過程的全局優化概率搜索算法，它提出了一種求解復雜系統優化問題的通用框架，且不依賴于問題的領域和種類，因此在諸多領域得到了廣泛的應用。但是標準的遺傳算法存在兩個重大的缺陷:早熟和收斂速度慢。這里提出了一種自適應調整遺傳參數的遺傳算法，并用其實現了FIR數字濾波器的優化設計，仿真結果說明了算法的有效性。

1 FIR數字濾波器及優化設計

1.1 FIR數字濾波器的頻率特性

有限沖激響應數字濾波器(FIR)的輸出僅取決于有限個過去的輸入和現在的輸入，用x(i)，y(i)分別表示其輸入和輸出，FIR濾波器可以表示為[5]:

y(i)=∑N-1j=0h(j)x(i-j)(1)

式中:h(i)(實數)為FIR的沖激響應，顯然:

h(i)=h(i)， 0≤i≤N-1

0，N

即FIR的沖激響應只有有限N個，稱N為FIR的階次。

對于N階線性相位FIR濾波器，其單位沖激響應h(i)為實數，且以對稱中心α=(N-1)/2對稱的，即有以下約束關系:

h(i)=±h(N-1-i)(3)

1.2 FIR濾波器優化設計準則

設一個FIR數字濾波器的理想頻率響應為:

Hd(jω)=Hd(ω)e-jθ(ω)， ω∈[-π，π](4)

式中:Hd(ω)≥0，若用一個N階的FIR頻率響應來逼近它，設其沖激響應為h(i)，i=0，1，2，…，N-1，那么其頻率響應可表示為:

H(jω)=∑N-1i=0h(i)e-jiω， ω∈[-π，π](5)

由上式可得:

Hd(jω)=Hd(ω)cos φ(ω)-jHd(ω)sin φ(ω)(6)

H(jω)=∑N-1i=0h(i)cos(iω)+j∑N-1i=0h(i)sin(iω)(7)

在[-π，π]上取P個頻率采樣點ωp(p=0，1，2，…，P-1)，并且為每一個ωp設置一個權重系數αp≥0(p=0，1，2，…，P-1)。那么描述H(jω)逼近Hd(jω)的加權均方誤差可近似寫成:

E2=1A∑P-1p=0αp∑N-1i=0h(i)cos(iωp)-Hd(ωp)cos φ(ωp)2 +

∑N-1i=0h(i)sin(iωp)-Hd(ωp)sin φ(ωp)2≥0(8)

式中:

A=∑P-1p=0αp(9)

如果采樣點ωp的數量足夠多且間隔足夠小，那么式(8)精確地表達了H(jω)與Hd(jω)的加權均方誤差。顯然，如果E2為0，那么所設計的FIR的頻率響應應在ωp(p=0，1，2，…，P-1)點上，幅頻響應和相頻響應兩方面嚴格地等于Hd(ωp)和φ(ωp)。由于N有限，E2不可能為0，任務在于尋找一種有效的算法使E2盡量小。由式(8)可知，αp取值的大小表達了對其對應的ωp點的重視程度，αp取值越大則要求在ωp附近頻域內H(jω)越嚴格地逼近Hd(jω)。

綜上所述，一維實數FIR數字濾波器優化設計問題就是尋找一組h(i)使式(8)的值盡可能小。

2 自適應遺傳算法

遺傳算法自提出以來，因其具有很強的解決問題的能力和廣泛的適應性，因而近年來滲透到研究與工程的各個領域，取得了良好的效果。但在實際應用中，基本遺傳算法也逐漸暴露出一些缺陷，這些缺陷主要集中在兩個方面:早熟和收斂速度慢[6，7]。

所謂早熟是指遺傳算法收斂于局部最優值，而非全局最優值的現象。這往往是由于在算法搜索的初期階段，種群中出現了某些超級個體，這些超級個體的適應值很高，隨著進化過程的進行，它們會很快占據整個種群，導致種群缺乏多樣性而陷入局部極值。由于遺傳算法從本質上而言是一種隨機搜索優化算法，所以當待求解問題規模較大或問題較復雜時，搜索空間往往非常龐大，于是導致遺傳算法的收斂速度很慢。

選擇合適的遺傳算子執行概率，是遺傳算法能否收斂到最優解的關鍵之一。遺傳算法的參數中交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關鍵所在，直接影響算法的收斂性，Pc越大，新個體產生的速度就越快。然而Pc過大時遺傳模式被破壞的可能性也越大，使得具有高適應度的個體結構很快就會被破壞;但是如果Pc過小，會使搜索過程緩慢，以致停滯不前。對于變異概率Pm，如果過小，就不易產生新的個體結構;如果過大，那么遺傳算法就變成了純粹的隨機搜索算法。針對不同的優化問題，需要反復試驗來確定Pc，Pm，這是一件繁瑣的工作，而且很難找到適應于每個問題的最佳值。

在傳統的遺傳算法中，交叉概率Pc、變異概率Pm與種群進化過程無關，從始至終都保持定值。近年來的研究表明，交叉概率和變異概率的選取對系統性能有重要的影響。用不變的Pc和Pm來控制遺傳進化，很容易導致“早熟”，降低算法的搜索效率。目前，調整遺傳算法控制參數較好的方法是動態自適應技術，其基本思想是使Pc，Pm在進化過程中根據種群的實際情況，隨機調整大小，目前這方面已有大量的研究[8，9]。具體做法為:當種群趨于收斂時，減小Pc、增大Pm，即降低交叉的概率，提高變異的概率，以保持種群的多樣性，避免“早熟”;當種群個體發散時，增大Pc、減小Pm，即提高交叉的概率，降低變異的概率，使種群趨于收斂，增加算法的收斂速度。

在多數情況下，種群中不同個體的適應度不盡相同，因此可以用適應度分布的離散程度來表征種群的“早熟”程度。種群在進化過程中發生“早熟”的主要表現是:種群內適應度暫時最大的一些個體相互重復或趨同，使得它們有較大的概率參與下一代的選擇復制操作，且它們之間交叉后的子代也不會與父代有太大的變化，導致遺傳算法尋優過程十分緩慢，降低搜索效率。因此，要正確判斷一個種群是否會發生“早熟”主要看這個種群當前適應度最大的那些個體是否重復或相互趨同。“早熟”程度可以使用下面方法評價:

設第t代種群個體的平均適應度為t，t代種群中最優個體適應度為Ftmax，種群中個體適應度大于t的個體的平均適應度為tmax，那么可以用Ftmax與tmax之間的差值來評價種群的“早熟”程度:

D=Ftmax-tmax(10)

式(10)中，指標D用來表征種群的“早熟”程度。可以看出，當D增大時，種群趨于發散;D減小時，種群趨于相同。此方法只計算Ftmax與tmax的差值，不涉及適應度低于平均適應度的個體，從而避免了那些適應度較差個體對D的影響，更能反映種群中那些適應度較好的個體之間的趨同程度。

根據種群“早熟”程度的指標D，使得交叉概率Pc和變異概率Pm在進化過程中隨著D的變化而改變，如下式所示:

Pc=1/\\(11)

Pm=1-1/\\(12)

式中:k1，k2>0。Pc取值范圍在[0.5，1]之間，Pm的取值范圍在[0，0.5]之間。在進化過程中，Pc，Pm根據D取值的不同而動態地自適應調整:當種群個體趨于離散(即D變大)時，Pc增大、Pm減小，種群開發優良個體能力增強;當種群個體趨于收斂(即D變小)時，Pc減小、Pm增大，種群產生新個體能力增強。

3 基于自適應遺傳算法的FIR數字濾波器優化設計

3.1 編碼

遺傳算法中首先要完成的是對解的編碼，由于文中的問題是一個非線性函數的優化問題，故采用實數編碼技術。將染色體表示成如下向量:X=\\，x(i)∈[0，1]，i=0，1，2，…，N-1。其中:x(k)∈[0，1]，k=0，1，…，(N-1)/2，可由如下映射關系得到:

x(k)=\\/2(13)

式中:h(k)∈[-1，1]，k=0，1，…，(N-1)/2，其余的h(i)可由式(3)求得。

3.2 適應度函數

FIR數字濾波器的優化設計目標是使式(8)的值最小，因此使用式(8)的倒數作為適應度函數，即:

f=1/E2(14)

3.3 選擇算子

使用錦標賽選擇法和精英保留法相結合的選擇策略。錦標賽選擇法在選擇時先隨機在群體中選擇K個個體進行比較，適應度最好的個體將被選擇作為生成下一代的父體，參數K稱為競賽規模。這種選擇方式能使種群中適應度好的個體具有較大的“生存”機會。同時，由于它只使用適應度的相對值作為選擇的標準，而與適應度的數值大小不成直接比例，從而避免了超級個體的影響，在一定程度上避免了過早收斂和停滯現象的發生。

精英保留法即當前種群中適應度最好的個體不參加遺傳操作，直接復制到下一代，替換經交叉和變異操作產生的子種群中適應度最差的個體，其優點是在搜索過程中某一代的最優個體可不被遺傳操作所破壞，這樣可以保證遺傳算法以概率收斂到最優解。經驗證明，保留占種群總體2%～5%數量的個體，效果最為理想[10]。

3.4 交叉算子

交叉算子以概率Pc對兩個父個體進行隨機分割，然后再重新組合從而獲得兩個新個體。根據分割點的數量，可分為單點交叉或是多點交叉。其原理是每個父個體隨機選擇m個無重復的交叉點，在交叉點之間的變量間續地相互交換，產生兩條新的子個體，完成交叉操作。本文采用兩點交叉法，示意如圖1 所示。

圖1 兩點交差法

3.5 變異算子

變異就是根據一定的概率Pm，將個體染色體上某一位置上的基因進行攝動，使其產生突變。設父個體向量x=(x1，x2，…，xk)，則分量xi以概率Pm被選擇作為變異，設對xi進行變異，則其后代為x′=(x1′，x2′，…，xk′)，其中xi′以等概率取(1-r)xi或xi+(1-xi)r，r為[0，1]上的隨機數。

3.6 實現步驟

(1) 根據不同的頻段要求初始化αp。其中，權重系數αp的大小表達了設計FIR數字濾波器時，對與其對應的ωp附近頻域內逼近誤差的重視程度。在具體的設計中，αp是可以調整的，不同的αp取值將導致不同的設計結果。通常要求FIR數字濾波器應具有較好的阻帶特性，而對過渡帶沒有嚴格的要求，因此可令:

αp=αp=1，ωp在通帶

αt=0，ωp在過渡帶

αs≥1，ωp在阻帶

式中，αp為通帶權重系數;αt為過渡權重系數;αs為阻帶權重系數。

(2) 隨機產生初始種群，在區間[-2，2]中產生一組隨機數作為初始化種群，每個個體表示為染色體的基因編碼。

(3) 計算A=∑P-1p=0αp。

(4) 計算個體的適應度，并判斷是否符合優化準則。若符合，輸出最佳個體及其代表的最優解，并結束計算;否則保留適應度最好的個體，執行(5)。

(5) 在種群中使用錦標賽選擇法選擇兩條個體。

(6) 計算交叉概率Pc和變異概率Pm。

(7) 對選擇個體進行交叉和變異操作，產生新的個體。

(8) 重復(5)~(7)，直到新種群數量等于上一代種群數量，并返回(4)。

4 FIR數字濾波器仿真實例

設計一個階次N為49，ωp=0.4π，ωs=0.5π，φ(ω)=18ω的低通實數FIR數字濾波器，設定αp=1，αt=0，αs=5，初始種群100，最大進化代數為300，最后選擇出最優的結果如圖2所示。

圖2 FIR低通濾波器設計結果

5 結 語

針對遺傳算法存在的“早熟”和收斂速度慢的缺陷，設計了評價進化過程中種群的“早熟度”的方法，使交叉和變異概率根據“早熟度”的變化而自適應調整，提高了遺傳算法的收斂速度，并將其應用于FIR數字低通濾波器的優化設計，并進行了仿真實驗，實驗結果表明該算法能夠設計出性能較好的數字濾波器。

參考文獻

[1]JIN Weidong，Zhang Gexiang，Zhao Duo.Satisfactory Optimization Design of IIR Digital Filters\\.Journal of Southwest Jiaotong University，2005，13(1):23-27.

[2]王小華，何怡剛，彭玉樓.神經網絡在4型FIR高階多通帶濾波器的自適應優化設計研究[J].湖南大學學報，2004，31(20):66-69.

[3]殷瑞，萬國龍.數字信號處理[M].北京:清華大學出版社，2007.

[4]Shaw A K.Optimal Design of Digital IIR Filters by Model_fitting Frequency Response Data\\.1993IEEE Int.Symposium on Circuits and Systems\\.1993.

[5]程佩青.數字信號處理教程[M].北京:清華大學出版社，1995.

[6]李敏強，寇紀淞.遺傳算法的基本理論與應用[M].北京:科學出版社，2002.

[7]王小平，曹立明.遺傳算法——理論、應用與軟件實現[M].西安:西安交通大學出版社，2002.

[8]王成棟，張優云.基于實數編碼的自適應偽并行遺傳算法[J].西安交通大學學報，2003，37(7):707-710.

[9]史明霞，陶林波，沈建京.自適應遺傳算法的改進與應用[J].微計算機應用，2006，27(4):405-408.

[10]Mat Buckland.游戲編程中的人工智能技術[M].吳祖增，沙鷹，譯.北京:清華大學出版社，2006.