張俊杰 仰繼連

（1.洛陽師范學院物理與電子信息學院，洛陽，471022；2.清華大學電子工程系，北京，100084）

引 言

有限沖激響應(yīng)（Finite impulse response，F(xiàn)IR）數(shù)字濾波器在語音、譜分析等數(shù)字信號處理領(lǐng)域有著廣泛的應(yīng)用。本質(zhì)上FIR數(shù)字濾波器的優(yōu)化設(shè)計問題是一個多變量求極值的過程。這些年來其優(yōu)化設(shè)計一直受到研究人員的廣泛關(guān)注。在過去的幾十年里發(fā)展了大量針對FIR數(shù)字濾波器優(yōu)化設(shè)計的方法，如混合整數(shù)線性規(guī)劃法［1］、有界分支技術(shù)［2－4］、模擬退火算法［5］、遺傳算法［6］等。

20世紀90年代初期，Dorige等人［7］通過模擬真實蟻群覓食時尋求最短路徑的原理提出了螞蟻算法（Ant algorithm，AA），這是一種新型的基于種群演化的啟發(fā)式優(yōu)化算法。該算法是一種本質(zhì)并行的優(yōu)化算法，具有魯棒性強、易于和其他算法結(jié)合以及適于并行處理等優(yōu)異性能，因此自問世以來就受到了廣泛的研究，已成功應(yīng)用于有源濾波器比例積分 （Proportion integration，PI）參數(shù)優(yōu)化［8］、自適應(yīng)抗干擾天線［9］、模型參數(shù)估計［10］、FIR數(shù)字濾波器優(yōu)化設(shè)計［11－12］等領(lǐng)域。螞蟻算法本身涉及參數(shù)較多，將其應(yīng)用到不同領(lǐng)域時為了具有更好的算法性能，必須考慮如何合理地綜合配置這些參數(shù)。近年來研究人員從不同方面進行了螞蟻算法參數(shù)配置的研究和總結(jié)，主要分為兩個方面：基于經(jīng)典的旅行商問題（Traveling salesman problem，TSP）的仿真研究［13－18］和基于具體領(lǐng)域的應(yīng)用研究［19－20］?？傮w上這些研究和總結(jié)仍是以TSP問題為測試平臺，這就給具體應(yīng)用領(lǐng)域中螞蟻算法的參數(shù)選取帶來一些指導上的不便，因此需要考慮螞蟻算法在具體應(yīng)用領(lǐng)域的參數(shù)選取基礎(chǔ)上，希望能夠得到相對一般的參數(shù)選取指導原則。

針對基于螞蟻算法的FIR數(shù)字濾波器優(yōu)化設(shè)計模型，本文對其中不同參數(shù)的作用和影響作了理論上的分析，研究了相關(guān)參數(shù)的最佳配置，并進一步推導出一般的參數(shù)配置公式，這將有利于螞蟻算法的拓展和應(yīng)用推廣。

1 基于螞蟻算法的優(yōu)化設(shè)計

具有嚴格線性相位的N階FIR數(shù)字濾波器的頻率響應(yīng)函數(shù)可表示為

式中：G（ω）為濾波器的增益，θ（ω）為相位響應(yīng)。不失一般性，本文僅討論奇數(shù)長度偶對稱低通濾波器的情形，相應(yīng)的最小最大準則下優(yōu)化設(shè)計問題可表述為

式中：D（ω）表示期望的濾波器幅度響應(yīng)；Ω表示設(shè)計所需考慮的頻帶；W（ω）表示頻帶加權(quán)函數(shù)，一般為非負的常量值；h表示濾波器系數(shù)組成的向量。

對頻帶Ω進行離散化，記離散點集合｛ωi｜i＝1，2，…，M｝，則式（2）有如下形式

一般而言，在濾波器設(shè)計中選擇M≥4N即可保證足夠的精度。

將濾波器的無限精度系數(shù)h（k）用二進制進行編碼，表示為I1I2I3…，其中Ii∈｛0，1｝。引入字長的限制條件，假設(shè)字長為b（包含符號位），則此時h（k）表示為I1I2…Ib－1?？紤]到｜h（k）｜≤1，再引入比例因子S＝2b－1，將系數(shù)以整數(shù)形式表示，有

因此優(yōu)化設(shè)計中系數(shù)的定義域范圍為

即為濾波器優(yōu)化設(shè)計的系數(shù)空間。

設(shè)sij為螞蟻i在搜索過程中取值為j時式（3）的計算結(jié)果，則啟發(fā)因子定義如下

在t時刻螞蟻i選取j值的狀態(tài)轉(zhuǎn)移概率可表示為

式中：τij（t）為t時刻螞蟻i在系數(shù)空間中的信息素強度；p表示螞蟻i選擇的可能值集合；α，β分別表示信息素強度和啟發(fā)因子在系數(shù)尋優(yōu)中的相對重要性。

隨著時間的推移，以前積累的信息素會因揮發(fā)而逐漸減少，用參數(shù)ρ表示信息素的揮發(fā)程度。所有螞蟻完成一次尋優(yōu)后，信息素強度根據(jù)式（8，9）進行調(diào)整

式中：Q為常量，體現(xiàn)信息素的反饋作用。

優(yōu)化設(shè)計中，采用F（h）作為目標函數(shù)，利用螞蟻算法優(yōu)化設(shè)計得到一組系數(shù)，求解它的最小值，以達到技術(shù)指標的要求。為了提高算法效率，可根據(jù)技術(shù)指標在通帶和阻帶施加適當?shù)募s束，以避免在一些性能較差點附近搜索。

2 算法參數(shù)的配置

2.1 參數(shù)影響分析

從尋優(yōu)機制不難看出，螞蟻算法中對性能有著直接或間接影響的參數(shù)有m，α，β，ρ，Q和τij（0）。本文中，算法模型設(shè)定螞蟻數(shù)量等于需要優(yōu)化的濾波器系數(shù)個數(shù)，因而不考慮m的配置情況。算法中其他參數(shù)之間是相互關(guān)聯(lián)的，有著復雜的關(guān)系，它們的取值對算法的性能和收斂性有著重要的影響。

α，β作為信息素強度和啟發(fā)因子不同重要性的體現(xiàn)，關(guān)鍵是看二者的比值，因而不妨在算法中設(shè)定α＝1，只需改變β值即可實現(xiàn)二者不同重要性的對比。如果β＜1，則信息素對螞蟻的尋優(yōu)影響較大，算法陷入局部信息最優(yōu)的可能性增大；反之，則陷入局部啟發(fā)因子最優(yōu)的可能性較大。

ρ對算法的全局搜索能力及其收斂速度有著直接的影響。如果過大，則信息素揮發(fā)得太快，不利于信息的正反饋，雖然此時能提高算法的全局搜索能力，但會使收斂性降低；反之，若其過小，則以前尋優(yōu)到的值被再次選擇的可能性增大，算法陷入局部最優(yōu)的可能性增大，影響了解的質(zhì)量。

Q作為反饋量，其值越大，正反饋作用越強，算法的收斂性越高，但同時也會使得搜索空間減小，陷入局部最優(yōu)的可能性加大；反之，若其值過小，則會產(chǎn)生類似于ρ過大時的結(jié)果。因而Q對算法性能的影響有賴于其他參數(shù)的配置。

τij（0）取值和參數(shù)Q有著密切的聯(lián)系，因為反饋量的大小都是相對于已有的信息素強度而言。雖然信息素強度隨時間而變化，但初始信息素強度對它有著直接的影響，進而影響著算法的性能。

一般來說，上述參數(shù)可通過反復試湊得到較好的組合，但若想徹底分析各參數(shù)組合的性能，則會因?qū)嶒灲M數(shù)的增加而變得不切實際。更重要的是，這些參數(shù)本質(zhì)上相互聯(lián)系，具有復雜的關(guān)系，僅取這些粗糙的值進行組合，難以找到參數(shù)的最佳組合，不利于提高算法的效率和收斂性。通過以上對算法參數(shù)的討論，本文推導出一種較為有效的參數(shù)配置基本公式。

2.2 參數(shù)配置公式推導

在螞蟻算法不同的應(yīng)用領(lǐng)域中，sij的定義會有所不同，但是在算法參數(shù)選擇和配置時，ρ和τij（0）可以根據(jù)經(jīng)驗設(shè)定，于是有

在本文的優(yōu)化設(shè)計中，根據(jù)技術(shù)指標在頻帶施加不同的約束，避免了在性能較差點附近的搜索。sij在系數(shù)為最優(yōu)解和舍入解時差別不是很大，因而可選取濾波器系數(shù)為舍入解時式（3）的計算結(jié)果作為sij的值，這可使得其他參數(shù)更容易控制。同時，根據(jù)算法的正反饋機制，在利用式（17）進行參數(shù)配置時還應(yīng)注意：不要在t比較小時就出現(xiàn)τij（t）?τij（0）的情況，也不要出現(xiàn)t足夠大時仍有τij（t）≈τij（0）的情況。只有根據(jù)實際問題進行合理的配置才能使算法具有更好的性能。

3 仿真結(jié)果分析

本文仿真實驗主要驗證螞蟻算法在FIR數(shù)字濾波器優(yōu)化設(shè)計中各個參數(shù)的不同配置對算法性能的影響以及參數(shù)配置公式對于參數(shù)選擇的指導意義。在優(yōu)化設(shè)計中本文算法的具體性能以及與其他算法的性能比較可以參見文獻［11］，其中在最小最大準則下本文算法與模擬退火算法相比在通帶衰減性能上有了明顯的提高，在最小平方準則下無論在通帶還是阻帶，本文算法設(shè)計的濾波器性能都比Tabu優(yōu)化算法有了較大的改進，在紋波約束最小平方準則下，本文算法和離散拉格朗日乘子法優(yōu)化設(shè)計所得的濾波器在阻帶最小衰減和通帶最大衰減效果幾乎一致，滿足了設(shè)計要求的技術(shù)指標，顯示了本文算法在復雜準則下優(yōu)化設(shè)計的良好性能。為了便于比較參數(shù)配置對算法性能的影響，本文不失一般性地在最小最大優(yōu)化準則下進行仿真實驗，使用MATLAB語言實現(xiàn)算法程序，所用硬件平臺為主頻2.40GHz的奔騰 Ⅳ處理器、256 MB內(nèi)存的PC。仿真實驗所用的FIR低通數(shù)字濾波器技術(shù)指標為：字長b＝8，階數(shù)N＝51，歸一化通帶頻率為［0，0.2］，阻帶頻率為［0.25，0.5］，通帶、阻帶加權(quán)函數(shù)分別為1和10。

仿真實驗中，螞蟻算法參數(shù)設(shè)置為：Q＝1，ρ＝0.3，τij（0）＝5，濾波器系數(shù)取舍入解時sij＝0.492 3，阻帶衰減為26.15dB。每組實驗方案運行10次，每次進行15次循環(huán)。阻帶最大衰減表示10次運行中阻帶衰減最大的情況，即優(yōu)化性能最好情況；阻帶最小衰減表示10次運行中阻帶衰減最小的情況，即優(yōu)化性能最差情況；阻帶平均衰減表示10次仿真實驗中阻帶衰減的平均值；阻帶衰減方差表示10次運行中阻帶衰減的穩(wěn)定性；平均時間表示10次仿真實循環(huán)。阻帶最大衰減表示10次運行中阻帶衰減最大的情況，即優(yōu)化性能最好情況；阻帶最小衰減表示10次運行中阻帶衰減最小的情況，即優(yōu)化性能最差情況；阻帶平均衰減表示10次仿真實驗中阻帶衰減的平均值；阻帶衰減方差表示10次運行中阻帶衰減的穩(wěn)定性；平均時間表示10次仿真實驗中運算時間的平均值。

圖1和圖2顯示了其他參數(shù)滿足式（17）時，不同β值對算法性能的影響。從圖1中可以看出，β≥1時，整體上阻帶最大衰減、最小衰減及平均衰減都要好于β＜1時的情形，表現(xiàn)出在相同條件下算法具有更好的性能。觀察圖2可以看出，β≥1時平均運算時間總體上要小于β＜1時的情形，并且β≥1時其值越大，相應(yīng)地平均運算時間也越大且有增加的趨勢；當取值為整數(shù)時，平均運算時間相對較小。綜上，本文推薦在能獲得滿足技術(shù)指標解的情況下，β取1～5之間的整數(shù)。

表1和表2顯示了在根據(jù)仿真實驗選取綜合性能較好的組合α＝1，β＝2基礎(chǔ)上，其他參數(shù)的配置是否滿足式（17）對算法性能的影響。從表1可看出，此時阻帶衰減情況比較理想，且阻帶衰減方差波動較小，體現(xiàn)了算法良好的穩(wěn)定性。表2中組1，6和8的阻帶最小衰減相比濾波器系數(shù)取直接舍入解時性能要差，沒有達到優(yōu)化目的，說明此時算法失效；同時阻帶衰減方差較大且有很大波動，表明此時算法非常不穩(wěn)定。這說明式（17）對于參數(shù)的整體配置以及算法性能的提高有著積極的指導意義。

圖1 參數(shù)β對阻帶衰減的影響

圖2 參數(shù)β對運算時間的影響

近年來，一些研究將螞蟻算法應(yīng)用于自適應(yīng)抗干擾天線［9］、FIR數(shù)字濾波器優(yōu)化設(shè)計［12］等領(lǐng)域。這些應(yīng)用研究中同樣面臨選擇和配置螞蟻算法參數(shù)的問題。參考文獻［9］根據(jù)自適應(yīng)信號處理原理和最小均方誤差準則建立了數(shù)學模型，確定螞蟻算法所要優(yōu)化的目標函數(shù)。仿真實驗中根據(jù)經(jīng)驗在自適應(yīng)螞蟻算法中參數(shù)選取為Q＝40，ρ＝0.9，τij（0）＝1，α＝3，β＝1；文獻［12］構(gòu)造了一個優(yōu)化窗函數(shù)的改進型螞蟻算法，該算法將函數(shù)優(yōu)化問題中生成解的過程轉(zhuǎn)化為蟻群每前進一步就選擇一個十進制數(shù)字并以此來生成一個十進制串的過程。仿真實驗中有關(guān)參數(shù)取值為：Q＝0.8，ρ＝0.7，τij（0）＝0.01，α＝3，β＝3。將文獻［9，12］中選取的算法參數(shù)代入式（18）計算，結(jié)果相同。

表1 任意選取參數(shù)Q，ρ，τij（0）且滿足式（17）

表2 任意選取參數(shù)Q，ρ，τij（0）且不滿足式（17）

因為在螞蟻算法中信息素強度的更新需要進行多步，例如在文獻［9］中算法迭代了500次甚至2 000次，在文獻［12］中，算法迭代次數(shù)達到了1 000次，所以從量級的角度考慮，可以認為式（19）成立。通過上述分析可以看出，雖然在不同的應(yīng)用領(lǐng)域以及不同的優(yōu)化準則下，sij的選取和定義有所不同，但是不同參數(shù)的選取同樣一般地滿足式（18）和式（17），結(jié)果吻合，說明本文提出的參數(shù)配置公式對于參數(shù)選擇具有一定的指導意義。

4 結(jié)束語

本文在已完成的基于螞蟻算法的FIR數(shù)字濾波器優(yōu)化設(shè)計研究基礎(chǔ)上，對優(yōu)化設(shè)計中算法不同參數(shù)的作用、選取和影響進行了深入的分析和研究，簡化了影響算法性能的參數(shù)個數(shù)。在理論分析的基礎(chǔ)上，研究了相關(guān)參數(shù)的最佳配置，推導了參數(shù)配置的一般公式，在一系列仿真實驗的基礎(chǔ)上驗證了本文的參數(shù)選取原則的有效性，同時還分析了螞蟻算法在其他應(yīng)用領(lǐng)域中的參數(shù)設(shè)置，經(jīng)驗證也滿足本文所提出的參數(shù)選取原則，進一步表明本文的參數(shù)選取原則的可行性和有效性，為螞蟻算法在優(yōu)化問題中參數(shù)的科學配置提供了一定的參考。實驗過程中發(fā)現(xiàn)受濾波器技術(shù)指標和優(yōu)化準則的影響，選取的參數(shù)之間存在著較大的差異，波動性較大。如何改善和降低由濾波器技術(shù)指標和優(yōu)化準則對參數(shù)設(shè)置帶來的影響有待進一步深入的研究。

［1］ Kodek D M.Design of optimal finite word length FIR digital filters using integer programming techniques［J］.IEEE Trans Acoust，Speech，Signal Process，1980，28：304－308.

［2］ Lim Y C，Parker S R.Discrete coefficient FIR digital filter design based upon an LMS criteria［J］.IEEE Trans Circuits Syst，1983，CAS30：723－739.

［3］ Jaumard M，Minoux M，Siohan P.Finite precision design of FIR digital filters using a convexity property ［J］.IEEE Trans Acoust，Speech，Signal，Process，1988，36：407－411.

［4］ Cho N，Lee S U.Optimal design of finite precision FIR filters using linear programming with reduced constraints［J］.IEEE Trans Signal Process，1998，46：195－199.

［5］ Benvenuto B，Marchesi M.Digital filters design by simulated annealing［J］.IEEE Trans Circuits Syst，1989，36：459－460.

［6］ Gentili P，Piazza F，Uncini A.Efficient genetic algorithm design for power－of－two FIR filters，Proc［C］／／IEEE Int Conf Acoust，Speech and Signal Prcocess.［S.l.］：IEEE，1995：1268－1271.

［7］ Colorni A，Dorigo M，Maniczzo V.Distributed optimization by ant colonies［C］／／Proc of ECAL91－European Conference on Artificial Life.Paris，F(xiàn)rance：［s.n.］，1991：134－142.

［8］ 谷鑫.基于有功功率平衡和蟻群算法優(yōu)化PI參數(shù)的有源濾波器［D］.天津：天津大學電氣與自動化工程學院，2006.Gu Xin.Active power filter based on active power balance principle and ant colony algorithm optimized PI regulator［D］.Tianjin：Electrical Engineering ＆Automation，Tianjin University，2006.

［9］ 項建弘，郭黎利，王麗敏.基于復數(shù)蟻群算法的自適應(yīng)抗干擾天線［J］.數(shù)據(jù)采集與處理，2010，25（2）：143－147.Xiang Jianhong，Guo Lili，Wang Limin.Adaptive anti－jam array antenna based on complex ant colony algorithm［J］.Journal of Data Acquisition and Processing，2010，25（2）：143－147.

［10］曹蘭英，周曄，蘇曉陽.一種用于SAR圖像統(tǒng)計模型參數(shù)估計的蟻群算法［J］.數(shù)據(jù)采集與處理，2009，24（1）：78－81.Cao Lanying，Zhou Ye，Su Xiaoyang.ACA for statistical parameters estimation in SAR images［J］.Journal of Data Acquisition and Processing，2009，24（1）：78－81.

［11］仰繼連，曾以成，徐茂林.設(shè)計有限字長FIR數(shù)字濾波器的螞蟻算法［J］.數(shù)據(jù)采集與處理，2009，24（3）：375－379.Yang Jilian，Zeng Yicheng，Xu Maolin.Ant algorithm for designing finite wordlength FIR digital filters［J］.Journal of Data Acquisition and Processing，2009，24（3）：375－379.

［12］謝勝.蟻群算法在FIR數(shù)字濾波器設(shè)計中的應(yīng)用［D］.長春：吉林大學計算機科學與技術(shù)學院，2006.Xie Sheng.Ant colony algorithms for fir digital filters design ［D］.Changchun：College of Computer Science and Technology，Jilin University，2006.

［13］詹士昌，徐婕，吳俊.蟻群算法中有關(guān)算法參數(shù)的最優(yōu)選擇［J］.科技通報，2003，19（5）：381－386.Zhan Shichang，Xu Jie，Wu Jun.The optimal selection on the parameters of the ant colony algorithm［J］.Bulletin of Science and Technology，2003，19（5）：381－386.

［14］石立寶，郝晉.隨機攝動蟻群算法的收斂性及其數(shù)值特性分析［J］.系統(tǒng)仿真學報，2004，16（11）：2421－2424.Shi Libao，Hao Jin.The numerical characteristics analysis and convergence proof for ant colony optimization algorithm with random perturbation behavior［J］.Journal of System Simulation，2004，16（11）：2421－2424.

［15］盧輝斌，賈興偉，范慶輝.基本螞蟻算法中參數(shù)的討論與改進［J］.計算機工程，2005，31（20）：175－179.Lu Huibin，Jia Xingwei，F(xiàn)an Qinghui.Discussion and improvement for parameters of ant algorithm［J］.Computer Engineering，2005，31（20）：175－179.

［16］吳春明，陳治，姜明.蟻群算法中系統(tǒng)初始化及系統(tǒng)參數(shù)的研究［J］.電子學報，2006，34（8）：1530－1533.Wu Chunming，Chen Zhi，Jiang Ming.The research on initialization of ants system and configuration of parameters for different TSP problems in ant algorithm［J］.Acta Electronica Sinica，2006，34（8）：1530－1533.

［17］劉剛，郭旭紅，馮志華，等.蟻群算法在TSP中的仿真應(yīng)用及最優(yōu)參數(shù)選擇研究［J］.蘇州大學學報：工科版，2007，27（1）：56－59.Liu Gang，Guo Xuhong，F(xiàn)eng Zhihua，et al.Research on the optimal parameter selection of the ant colony system algorithm and its application in TSP［J］.Journal of Soochow University：Engineering Science Edition，2007，27（1）：56－59.

［18］章寶歌，杜呈欣.螞蟻數(shù)和α、β的設(shè)置在求解函數(shù)優(yōu)化中的影響［J］.計算機工程與應(yīng)用，2009，45（30）：40－44.Zhang Baoge，Du Chengxin.Configuration of parametersα，βand ants′number for function optimization［J］.Computer Engineering and Applications，2009，45（30）：40－44.

［19］范小寧，林焰，紀卓尚.迭代更新蟻群管路敷設(shè)系統(tǒng)參數(shù)的敏感性分析［J］.計算機工程，2007，33（15）：36－39.Fan Xiaoning，Lin Yan，Ji Zhuoshang.Sensibility analysis of parameters in ACO for solving ship pipe routing［J］.Computer Engineering，2007，33（15）：36－39.

［20］張瀟，王江晴.螞蟻算法在帶時間窗車輛路徑問題中的應(yīng)用及參數(shù)分析［J］.計算機工程與科學，2010，32（12）：134－136.Zhang Xiao，Wang Jiangqing.Application of the ant algorithm in the vehicle routing problem with time windows and its parameter analysis［J］.Computer Engineering ＆ Science，2010，32（12）：134－136.