108 2017，53（17） Computer Engineering and Applications 计算机工程与应用 ⦾网络、通信与安全⦾ 采用改进遗传算法优化 FIR 数字滤波器设计 孙田雨，史 峥 SUN Tianyu, SHI Zheng 浙江大学 电气工程学院，杭州 310027 College of Electrical Engineering，Zhejiang University，Hangzhou 310027，China SUN Tianyu, SHI Zheng. Research on design of FIR filter based on improved genetic algorithm. Computer Engi- neering and Applications, 2017, 53（17）：108-111. Abstract: The optimal design of finite impulse response filter can be abstracted into a problem of calculating the extremum of multidimensional continuous function, so it can be solved by genetic algorithm. Because the traditional genetic algo- rithm is easy to fall into local solution, it proposes a new strategy to improve the algorithm in the probability and operator of crossover and mutation, and it proves to be feasible by trial function. Under the Least Squares（LS）, Minimax（MM） and Minimum Mean Square Error（MMSE）criteria, it realizes the optimized design of digital FIR low pass filters based on the improved genetic algorithm. The experimental results show that the filters designed under different optimality criteria have good performance, and the versatility and effectiveness of the improved genetic algorithm are proved as well. Key words: digital filter; improved genetic algorithm; crossover and mutation; optimized design 摘 要：FIR 数字滤波器的最优化设计可以抽象成一个多维连续函数求极值的问题，因此可以采用遗传算法求解。 针对传统遗传算法存在的容易早熟收敛的问题，提出一种改进策略，从交叉变异的概率和算子两方面对算法进行改 进，并通过测试函数验证了改进策略的可行性。分别在最小二乘（LS）、最大误差最小化（MM）和均方误差最小化 （MMSE）准则下，采用改进遗传算法进行 FIR 数字低通滤波器最优化设计，实验结果显示在不同优化准则下设计的 滤波器都表现出了良好的性能，证明了改进算法的通用性和有效性。 关键词：数字滤波器 ；改进遗传算法 ；交叉变异 ；优化设计 文献标志码：A 中图分类号：TP202+.7 doi：10.3778/j.issn.1002-8331.1603-0399 1 引言 FIR 数字滤波器具有系统总是保持稳定，易于实现 线性相位这两个突出的优点，因而被广泛地应用于信号 采集、数据测量、图像处理等领域 [1-2]。传统的 FIR 数字 滤波器设计方法包括窗函数法和频率采样法两种，这两 种方法具有原理简单，易于实现的优点，但设计出来的 滤波器并不具有最优的特性，因而很少应用在实际的滤 波器设计当中。常用的 FIR 数字滤波器设计最优化准 则包括最小二乘（LS）准则[3]，均方误差最小化（MMSE） 准则[4]以及最大误差最小化（MM）准则[5]等。同时随着 工程中对滤波器的要求越来越高，其优化模型也越来越 复杂，采用传统算法难以精确求解，因而国内外许多研 究员引入智能算法进行求解。 遗传算法（Genetic Algorithm，GA）是一类常见的 智能算法，它具有鲁棒性好、求解时不依赖问题的具体 领域等优点，在调度分配、机器学习、人工智能等领域均 有所应用[6-7]。传统的遗传算法存在着收敛速度慢，容易 陷入到局部最优解等缺点，针对这些问题，文献[8]从编码 方式出发，提出一种新的 Gray 混沌编码方式，文献[9-11] 分别从不同的角度对遗传算子进行改进，均在一定程度 上改善了算法的寻优性能。本文提出了一种新的改进 策略，并将改进后的算法应用到 FIR 数字滤波器的最优 作者简介：孙田雨（1991—），男，硕士研究生，研究方向：数字信号处理，E-mail：764159414@qq.com；史峥（1967—），男，副教授，硕 士生导师，研究方向：集成电路 CAD。 收稿日期：2016-03-29 修回日期：2016-05-25 文章编号：1002-8331（2017）17-0108-04 CNKI 网络优先出版：2016-08-10, http://www.cnki.net/kcms/detail/11.2127.TP.20160810.1057.076.html 计算机工程与应用www.ceaj.org

孙田雨，史 峥：采用改进遗传算法优化 FIR 数字滤波器设计 2017，53（17） 109 化设计当中，最后通过实验对比验证了改进算法的可行 性和优越性。 2 FIR 数字滤波器的优化模型 2.1 FIR 数字滤波器建模 对于一个 N - 1 阶 FIR 滤波器，设其单位冲击响应 为 h(0),h(1),…,h(N - 1) ，则待求滤波器的频率响应为： H(ejω)= ∑ N - 1 h( )n e-jwn n = 0 当 h(n) 为实序数时，可将 H(ejω) 表示为： H(ejω) = H(ω)ejθ(ω) （1） （2） 其中，H ( )ω 为相位函数。 )ω 为滤波器的幅度函数，θ( 由于滤波器满足线性相位，有： h(n) = ±h(N - 1 - n) （3） 对于本文讨论的Ⅰ、Ⅱ类 FIR 数字滤波器，单位脉 冲响应满足 h(n) = h(N - 1 - n) ，可以求得滤波器的幅度 响应： N - 1 H ( )ω = ∑ ö ø÷ 2.2 FIR 数字滤波器优化准则 h(n)cosé æ ëê èç n - N - 1 2 n = 0 ù ω ûú （4） 设理想 FIR 数字滤波器的频率响应为： Hd(ejω)= Hd( （5） 在通带和阻带的频域范围内取 M 个离散点 {ωi|i = 1,2,…,M} ，那么对滤波器的优化准则可以做如下表示。 )ω e-jθ( )ω 最小二乘（LS）准则： E = ∑ w(ωi)[H(ωi) - Hd(ωi)]2 M i = 1 最大误差最小化（MM）准则： F = max{w(ωi)[H(ωi) - Hd(ωi)]} 均方误差最小化（MMSE）准则： )ejωi ( G = 1 | h( )n e-jωin - || | M ∑ M æ çç è | ||∑ | | Hd N - 1 n = 0 i = 1 （6） （7） （8） | 2 ö ÷÷ ø 由上可知，一维 FIR 数字滤波器的最优化设计可以 抽象成一个连续函数寻优问题，即选取一组合适的系数 h(n) (n = 0,1,…,N - 1) ，使式（6）~（8）取得最小值，因此 可以采用遗传算法求解上述问题。 3 传统遗传算法改进 3.1 对交叉变异概率的改进 交叉概率 Pc 和变异概率 Pm 是影响遗传算法性能 的关键因素。 Pc 决定了遗传算法的全局搜索能力，Pc 过小，则遗传算法的寻优能力不足，Pc 过大，则容易破 坏已经得到的优良个体。 Pm 决定了遗传算法的局部 寻优能力，如果 Pm 过小则不容易产生新的个体，Pm 过 大，遗传算法就退化成了一般的随机搜索算法。在传统 的遗传算法中，交叉概率和变异概率通常是固定的，其 值的选取一般是根据以往经验和多次实验得到，如果选 取不当，则导致算法寻优能力差，容易陷入到局部最优 解当中。为了解决这一问题，Srinivas 等人提出了一种 根据适应度函数动态调整交叉概率和变异概率的方 法[12]，调整公式为： k1( fmax - f ′ ì ïï fmax - favg í ïï k2, f ′ < favg î k3( fmax - f ì ïï fmax - favg í ïï k4,  f < favg î ,  f ′ ≥ favg , f ≥ favg Pm = Pc = ) ) 式中 fmax 和 favg 分别表示当代群体中的最大适应度和 平均适应度，f ′ 表示进行交叉的两个父代中较大的适 应度，f 表示变异个体的适应度。 （10） （9） 这种方法可以在一定程度上改进遗传算法的寻优 能力，但由公式可以看出，适应度越接近于最大适应度 值时，变异概率和交叉概率就会越小；而当适应度与最 大适应度值相等时，交叉概率和变异概率就会变为零。 这意味着在算法进化初期表现较优的个体几乎不会发 生变化，从而增加了遗传算法陷入局部最优解的可能 性，因此本文提出了一种新的改进策略：    ,  f ′ ≥ favg Pc1 1 f ′ - favg fmax - favg ö ÷÷ ø λ Pc = ì ï 2 + expæ ï çç í è ï ï Pc1, f ′ < favg î ì Pm1 ï ï í ï ï î 式中，Pc1 ∈ [ 2 + expæ çç è Pm1,  f < favg 0.8,0.9 ，Pm1 ∈ [ ] Pm = 1 λ f - favg fmax - favg （11） （12） ,   f ≥ favg ö ÷÷ ø 0.1,0.2 ，λ 取值为 5。 ] 这样，当适应度趋近于最大适应度值时，交叉概率 和变异概率会慢慢减小但不会等于零，既能保证种群中 的优良个体不会在进化时被轻易破坏，同时也使算法拥 有跳出局部最优解的能力。 3.2 对交叉变异算子的改进 3.2.1 交叉算子的改进 传统的遗传算法中对于满足交叉概率的两个父体 ï ) ì í î 一般采用线性交叉策略： i + ( 1 - α xt ) i + αxt 1 - α xt i + 1 为选中的两个父代，xt + 1 xt + 1 i = αxt i + 1 = ( xt + 1 其中，xt i ，xt 后生成的子代，α ∈[0,1] 。 i + 1 i + 1 ï （13） i ，xt + 1 i + 1 为交叉 通过这种交叉策略产生的子代个体只能位于两个 父代所确定的矩体之内，且子代个体间的距离不会大于 父代之间的距离[13]，这样种群的进化就会极大地受限于 计算机工程与应用www.ceaj.org

110 2017，53（17） Computer Engineering and Applications 计算机工程与应用 1.0 0.8 0.6 0.4 0.2 0 －0.2 －0.4 －0.6 －0.8 －1.0 e u l a v s s e n t i F 所产生的初代群体。本文对交叉算子做如下改进： i + ( ) i + 1 +(1 - α)xt ) 1 - α xt i + 1 i + αxt ) i + 1 ì ï í ï î i + 1 + αxt xt i - xt xt i + 1 - xt i = β( xt + 1 i + 1 = β( xt + 1 ]0,1 ,β ∈ [ 其中 α ∈ [ 则采用传统线性交叉策略。 ]0,1 且 β < α 。如果产生的子代越界， （14） 通过式（14）产生的子代个体大小不会仅限定在两 个父代之间，从而拓展了算法的搜索空间，更好地保证 了种群的多样性和算法的寻优能力。 3.2.2 变异算子的改进 变异算子的主要作用在于保持群体的多样性，传统 遗传算法的变异策略是对满足变异概率的个体产生一 个固定步长的变化，本文通过改进使产生变异个体的空 间能够进行自适应变化： {maxæ èç minæ èç i - u( )t xmax - xmin xt i + u( )t xmax - xmin xt 2 ö ,xmin , ø÷ } ö ø÷ ] ,xmax 2 ，[ （15） 1 - t/T b ) 其中，u( )t = 1 - a( 范围，T 为最大进化代数，t 为当前代数，a ∈ ( 取值为 3。 xmin,xmax 为种群个体大小的 )0,1 ，b 这样在算法进化初期满足变异概率的个体有一个 较大的变异步长，可以在保持种群多样性的同时加快算 法的搜索速度，而在算法后期逐渐减小变异步长提高算 法的局部寻优能力。 3.3 测试函数验证 为了验证改进策略的有效性，选取两个测试函数： f1( 2πx cos( )x,y = x2 + y2 - cos( 2πy ) ) 2 f2( -10 ≤ x,y ≤ 10 n - 1( )x = ∑ ) 100( 2 + ( i = 1 -2.048 ≤ xi ≤ 2.048 xi + 1 - x2 i （16） ) ) xi - 1 2 （17） f1 是一个复杂的多模函数，具有大量的局部极值点，最 小值为 - 1 ；f2 是多维函数（本文取 n = 100 ），最小值 为 0。分别采用传统遗传算法（GA）和改进算法（IGA） 对函数进行优化，设初始种群个体数为 100，对于传统算 法，设交叉变异概率为 0.8 和 0.005，对于改进算法，取 Pc1 = 0.8,Pm1 = 0.01,a = 0.5 ，优化函数 f1 时，取最大进化 代数为 80，优化函数 f2 时，取最大进化代数为 800。两 种算法运行 20 次的结果如表 1 和图 1 所示，可以看出改 进算法是有效的。 表 1 测试函数的优化结果 函数 f1( )x,y f2( )xi 算法 最优值 平均值 传统算法 改进算法 传统算法 改进算法 －0.997 872 －0.999 635 1.385E－08 0 －0.706 628 －0.963 554 3.979E－05 1.475E－09 GA IGA GA IGA 105 100 10－5 e u l a v s s e n t i F 0 10 20 30 40 50 60 70 80 Number of Iterations （a）函数 1 各代适应度值 10－10 0 400 300 200 700 100 Number of Iterations （b）函数 2 各代适应度值 500 600 800 图 1 两种算法在测试函数下各代适应度值 4 算法流程及实验 4.1 算法过程 基于改进遗传算法设计FIR数字滤波器的过程如下： （1）对遗传算法各项参数进行初始化。 （2）对待求滤波器系数进行编码，本文采用实数编 码策略。 （3）取式（6）~（8）的倒数作为适应度函数，并计算每 个染色体的适应度函数值。 （4）采用轮盘赌和最优个体保留的策略进行选择操作。 （5）根据本文提出的改进策略进行交叉、变异操作。 （6）计算新群体中染色体的适应度值，并保留最优 适应度和对应的最优个体。 （7）如果达到了预先设定的进化代数，则结束算法 并返回最优个体；否则转到步骤（4）继续执行算法。 4.2 仿真实验和结果分析 本文以低通数字滤波器为例，分别采用传统遗传算 法（GA）、经典自适应遗传算法（AGA）和提出的改进算 法（IGA）进行滤波器优化设计：对于传统算法，取交叉变 异概率分别为 0.9 和 0.1，对于自适应算法，取 k1、k2、k3、k4 分别为 0.7、0.8、0.5和 0.01，对于改进算法，初始参数与 3.3 节中一致。取初始种群为 200，最大进化代数为 1 000。 例 1 根据 MM 准则，设计一个 51 阶的 FIR 低通数 字滤波器，其通带频率为[0，0.4π]，阻带频率为[0.5π，π]， 通带加权函数值 wp(ω) = 1 ，阻带加权函数值 ws(ω) = 10 ， 设计结果如图 2 和表 2 所示。 B d / ) ( ω H 10 0 －10 －20 －30 －40 －50 －60 －70 －80 0 GA AGA IGA 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 ω/π 图 2 基于 MM 准则的 51 阶滤波器 计算机工程与应用www.ceaj.org

孙田雨，史 峥：采用改进遗传算法优化 FIR 数字滤波器设计 2017，53（17） 111 表 2 51 阶滤波器各算法优化结果 算法 阶数 通带波纹/dB 阻带衰减/dB 传统算法 自适应算法 改进算法 文献[14]算法 51 51 51 51 0.323 9 0.173 4 0.057 2 0.041 0 28.33 36.13 43.43 28.86 例 2 根据 LS 准则，设计一个 40 阶的 FIR 数字低通 滤波器，通带频率为[0，0.4π]，阻带频率为[0.5π，π]，通带 加权函数值 wp(ω) = 1 ，阻带加权函数值 ws(ω) = 1 ，设计 结果如图 3 和表 3 所示。 B d / ) ( ω H 10 0 －10 －20 －30 －40 －50 －60 －70 －80 0 GA AGA IGA 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 ω/π 图 3 基于 LS 准则的 40 阶滤波器 表 3 40 阶滤波器各算法优化结果 算法 阶数 通带波纹/dB 阻带衰减/dB 传统算法 自适应算法 改进算法 文献[14]算法 40 40 40 40 0.271 3 0.110 3 0.013 8 0.014 4 21.58 29.13 39.65 36.85 例 3 根据 MMSE 准则设计不同阶数的Ⅰ类 FIR 低 通 滤 波 器 ，要 求 通 带 频 域 为 [0，0.23π]，阻 带 频 域 为 [0.28π，π]，图 4 是本文设计结果与文献[15]设计结果的 对比。 GA AGA IGA 文献[15] 0.001 2 0.001 0 0.000 8 0.000 6 0.000 4 0.000 2 差 误 方 均 0 24 26 28 30 32 34 36 滤波器阶数 图 4 不同阶数下滤波器最小均方误差 采用遗传算法在不同优化准则下设计 FIR 数字滤 波器可以抽象为在[－1，1]的范围确定一组 h(n) 使式 （6）~（8）取得最小值，所求的结果越小，滤波器的最小阻 带衰减值越大，就表明所设计的滤波器性能越好。 例 1 中采用改进遗传算法在 MM 准则下设计的 51 阶滤波器的最小阻带衰减为 43.43 dB，在相同条件下， 采用传统算法设计结果为 28.33 dB，采用自适应算法设 计结果为 36.13 dB，文献[14]采用蚂蚁算法设计结果为 28.33 dB，均低于采用改进算法的设计结果；例 2 中采用 改进算法在 LS 准则下设计的 40 阶滤波器的最小阻带 衰减为 39.65 dB，在相同条件下，采用传统算法设计结 果为 21.58 dB，采用自适应算法设计结果为 29.13 dB，文 献[14]采用蚂蚁算法设计结果为 36.85 dB。这说明改进 算法能更好求得式（6）（7）的最小值，例 3 的仿真结果直 接表明了本文提出的改进算法在不同的阶数下对式（8） 都有更好的优化结果。 由此可以证明，本文提出的改进策略可以使遗传算 法拥有更好的寻优能力，在不同的优化准则下通过改进 算法设计的 FIR 数字滤波器都表现出了更好的性能。 5 结束语 针对 FIR 数字滤波器的最优化设计问题，本文提出 一种新的改进遗传算法进行求解，新算法从交叉变异的 概率和算子两个方面对传统遗传算法进行改进，具备了 更好的全局寻优能力，实验证明在不同优化准则下基于 改进遗传算法设计的滤波器都表现出了良好的性能，说 明本文提出的算法改进策略是可行且有效的。同时，结 合不同智能算法的寻优思想进行遗传算法改进，构成混 合式的遗传算法用以求解数字滤波器优化设计问题，是 下一步需要展开的工作。 参考文献： [1] 汪芙平，靳夏宁，王赞基 . 实现动态相量测量的 FIR 数字滤 波器最优设计[J]. 中国电机工程学报，2014，34（15）：2388- 2395. [2] 洪鹏，吴雄斌，张兰，等 . 高频地波雷达中可重构 FIR 滤波 器的设计[J]. 计算机仿真，2015，32（4）：21-25. [3] Ronald E C，Lawrence R R.Interpolation and decimation the of digital signals—a tutorial review[J].Proceeding of IEEE，1981，69（3）：300-311. [4] Howard D H.Digital filters with equiripple or minimax response[J].IEEE Transactions on Audio and Electroa- coustics，1971，19（1）：87-93. [5] 方伟，孙俊，须文波 . 基于自适应量子粒子群算法的 FIR 滤 波 器 设 计 [J]. 系 统 工 程 与 电 子 技 术 ，2008，30（7）：1378- 1381. [6] Futuna R，Curteanu S，Leon F.An elitist non-dominated sorting genetic algorithm enhanced with a neural network applied to the multi- objective optimization of a polysi- loxane synthesis process[J].Engineering Applications of Artificial Intelligence，2011，24（5）：772-785. [7] 童立军 . 病毒进化遗传算法的车辆调度优化模型[J]. 计算 机工程与应用，2015，51（15）：240-243. （下转 172 页） 计算机工程与应用www.ceaj.org