整体退火遗传算法用于FIR滤波器的频率采样设计

1、第24卷第4期増刊仪器仪表学报2003年8月FIR刘从新吉培荣曾维鲁 (三峡大学电气信息学院宜昌443002)整体退火遗传算法(WAGA)是一种新的遗传算法.它将退火机制引入选择算子并允许父代加入竞争便遗传算法更 加稳健、高效。本文将WAGA应用到F1R滤波器的频率采样设计对过渡带样本的取值进行了优化仿真结果表明用该方法 设计的滤波器有良好的频率特他FR滤波器整体退火遗传算:法优化采样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滤波器常常使用 的方法这种技术对于窄带滤波器比较有效但是采用 该技术设计滤波器时存在着过渡带采样值如何确定的 问题。传统的方法往往采用査表的方法但是査表法存 在着提供的数据不能保证最优的问题.文献罪表明遗 传算法(Genetic A lgorithm .简称GA )的全局寻优能力 可以克服査表法的不足利用遗传算法搜索到的采样 值优于査表法。本文将张讲社等人提出的一种新型遗 传算法整体退火遗传算2 FIR频率采样技术是基于频率采样理论的一种设计方 法。对于一个任意长的序列、对其频谱H(k)进行N尊 份均匀抽样利用傅立叶反变换得到一个有限长为7 的数列，这个序列是原周期序刊的主值

6、序列.它是原序 列的近似所以其频率特性也将逼近原来的序列。对于 一个理想的的频率特性H d (/).其单位样值响应为H (n)对在单位圆上作N等份得到H(k),对H(k)进厅 IFFT变换得到有限长h (n),设H (z)是其系统函数. 则：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最小化是一种优化算法。GA具有全 局寻优的能力，但是现在大多数的GA收敛速度慢.不 能绝对保证不陷入局部极小，本文采用了文献m中的 新遗传算法来确定过渡带的样本值。3F

8、IR遗传算法是一类群体搜索策略，所谓群体是指状 态空间中的有限点集, b2,bn称为一个群体O 其中任意一个点b= aiaiavai称为一个染色体.而a. 则称为基因。一般的遗传算法是:首先产生一个父彳弋群体，然后 通过一定方向选择出下一代群体.该群体又通过交叉. 变异产生新的群体该群体又作为父群体进彳亍迭代循 环O理论上证明遗传算法能从概率意义上收敛于问题 的最优解但在实践中.遗传算法会出现一些不近人意 的地方如易于出现早孰现象局部寻优能力差。模拟 退火算法具有较强的同部寻优能力这一点怡好是遗 传算法所欠缺的两者结合则可能产生出性能优良的 新的全局搜索算法。整体退火遗传算法就是将退火思 想引

9、入选择算子.并允许父代参与竟争的新型遗传算 法。新算法所产生群体的每一个体都将以概率1收敛 到整体最优解并有较快的收敛速度。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为群体的规模 (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变为1. 1变为 0：交叉采用不定点交叉，交叉点|0.21),具体值随机 产生。3 5遗传算法的运疔参数主要包括群体大小、变异概

11、率、交叉概率、终止迭代数。运行参数对遗传算法的求 解结果和求解效率都有一定的影响但目前尚无合浬 选择它们的理论依据。在实际便用中往往要试算多次 才能确定出它们的合理范围。(1) 初始群体规模M由于遗传算法对M十分敏感二这就决定了如果 从单一的M出发就不太可能搜索到全局最优解。& 演算中(pm= 0. 15.pt= 0.9.),笔者发现解的适应度随 着M的变化呈现类似“周期”式波动如果在信息量充 足的M区段选取多个M进行搜索，就有可能找到全 局最优解 所以本文进一步定义了M厲于一个集合. 即M 92,94,100.-s 114)o(2) 变异率“和交叉率p,的确定p.十分难以确定稍为不适就会产生

12、初始收敛, 一般要根据具体的问题来确定其取值。在本文中以 变异率能否使92 WM 114(偶数)中的大部分群体收 敛现最优解作为其被选择的依据在选择中这种判断 比较容易只要取出2-3个群体.比较各自在不同变 异率下的收敛趋势然后取它们优秀变异率的交集经 I994-2C10 China Academic Journal Electronic Publishing House. All rights reserved.466仪器仪表学扭第24卷过验证，发现这个变异率能便得大部分群体收敛;交叉3 6 2软件流程 1994-2010 China Academic Journal Electronic

13、Publishing House. All rights reserved, 466仪器仪表学扭第24卷率一般取0.9o(3) To 和 generatbn 的确定笔者用C语育设计了一个用整体退火遗传算法 优化设计F1R滤波器的程序.其流程如图lo 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 466仪器仪表学扭第24卷GAFilter图1根据模拟退火的思想(开始八足够髙，最后温度 的T足够低.这样得到的解就有可能是最优解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)遗传计算(选择最优秀的个体得到最优解) 首先设置几个运行参数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个父体进行配对交叉，在交叉过程中以概 率进行变异操作。 比较新产生的群体的最优个体和上的最优个 体的适应度若更好，则继续下一代操作若不及，则恢 复上一代的所有个体。 如果.KMgcncration则回到循环运算。反之， 则结束运算O实例1用频率采样技术设计一个低通滤波器. 技术指标同上节。取采样点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)进行优化计算的部分结果。本文采用整体退火遗传算法实现了对FIR滤波 器一频率采样法的优化设计.仿真表明WAGA具有 交强的局部寻优能力其应用改善了滤波器的性能为 我忙用遗传算法设计滤波器提供了新的手段。 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