基于自適應(yīng)遺傳算法FIR數(shù)字濾波器優(yōu)化設(shè)計

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

關(guān)鍵詞:FIR濾波器;優(yōu)化設(shè)計;自適應(yīng)遺傳算法;早熟度

中圖分類號: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

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

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

1 FIR數(shù)字濾波器及優(yōu)化設(shè)計

1.1 FIR數(shù)字濾波器的頻率特性

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

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

式中:h(i)(實數(shù))為FIR的沖激響應(yīng)，顯然:

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

0，N

即FIR的沖激響應(yīng)只有有限N個，稱N為FIR的階次。

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

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

1.2 FIR濾波器優(yōu)化設(shè)計準則

設(shè)一個FIR數(shù)字濾波器的理想頻率響應(yīng)為:

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

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

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設(shè)置一個權(quán)重系數(shù)αp≥0(p=0，1，2，…，P-1)。那么描述H(jω)逼近Hd(jω)的加權(quán)均方誤差可近似寫成:

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

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

2 自適應(yīng)遺傳算法

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

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

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

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

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

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

D=Ftmax-tmax(10)

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

根據(jù)種群“早熟”程度的指標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根據(jù)D取值的不同而動態(tài)地自適應(yīng)調(diào)整:當種群個體趨于離散(即D變大)時，Pc增大、Pm減小，種群開發(fā)優(yōu)良個體能力增強;當種群個體趨于收斂(即D變小)時，Pc減小、Pm增大，種群產(chǎn)生新個體能力增強。

3 基于自適應(yīng)遺傳算法的FIR數(shù)字濾波器優(yōu)化設(shè)計

3.1 編碼

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

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

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

3.2 適應(yīng)度函數(shù)

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

f=1/E2(14)

3.3 選擇算子

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

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

3.4 交叉算子

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

圖1 兩點交差法

3.5 變異算子

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

3.6 實現(xiàn)步驟

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

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

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

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

式中，αp為通帶權(quán)重系數(shù);αt為過渡權(quán)重系數(shù);αs為阻帶權(quán)重系數(shù)。

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

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

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

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

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

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

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

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

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

圖2 FIR低通濾波器設(shè)計結(jié)果

5 結(jié) 語

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

參考文獻

[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]王小華，何怡剛，彭玉樓.神經(jīng)網(wǎng)絡(luò)在4型FIR高階多通帶濾波器的自適應(yīng)優(yōu)化設(shè)計研究[J].湖南大學學報，2004，31(20):66-69.

[3]殷瑞，萬國龍.數(shù)字信號處理[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]程佩青.數(shù)字信號處理教程[M].北京:清華大學出版社，1995.

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

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

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

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

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