（电路与系统专业论文）基于粒子群优化算法的FIR数字滤波器的设计研究[电路与系统专业优秀论文].pdf

摘要 数字滤波器在数字信号处理的各种应用中发挥着十分重要的作 用，f i r 数字滤波器在满足一定对称条件下，可以实现线性相位，而 且稳定性好，因而f i r 数字滤波器获得了广泛的应用。它的优化设计 也一直受到广大学者和工程技术人员的关注。 粒子群优化算法模拟鸟群飞行觅食的行为，群体根据自己的速度 在解空闻中追随最优粒子进行搜索。粒子群算法收敛速度快、设置参 数少、简单易实现，在解决非线性优化问题方面有突出的表现，已成 为一种重要的优化工具。 本文基于粒子群优化算法理论，将粒子群优化算法应用于f i r 数 字滤波器的优化设计中，即将粒子群优化算法的优点与f i r 数字滤波 器的设计需求结合起来，借助粒子群优化算法寻找到较好的滤波器系 数，从而最大程度地逼近工程要求的幅频响应。本文首先介绍了粒子 群优化算法原理、数学描述、参数意义及各种模型。其次，分析了 f i r 数字滤波器原理及设计方法，并在指定技术指标下，应用粒子群 优化算法设计出一个高通滤波器，在m a t l a b 6 5 环境下进行仿真实验， 实验结果表明所设计的滤波器与传统优化算法所设计的滤波器相比， 通带波动小，阻带衰减大，滤波效果更优良。最后研究了粒子群算法 的参数对算法性能的影响。以算法理解的简单性、实现的简洁性为基 本思路，针对粒子在实际搜索过程中是非线性且高度复杂的现象，从 改变粒子群算法的参数出发，使惯性权重的变化受粒子运行态势的影 响，给出了一种动态改变惯性权重的粒子群优化算法，运用此算法设 计的高通滤波器，从在线性能、离线性能和各代群体最优适应度的性 能指标来看，算法收敛速度更快，鲁棒性更强。 关键词：f i r 数字滤波器粒子群优化算法动态改变惯性权重 a b s t r a c t d i g i t a l f i1 t e rp l a y a v e r yi m p o r t a n t r 0 1 ei nt h e a d d li c a t i o n so fd i g i t a ls i g n a l_ p r o e e s s i n g i nac e r t a i n a p p il c a t l o n s o i = d l g l t a is l g n a ip r o e e s s l n g i n ac e r t a l n s y l 嬲e t r yc o n d 主t 主o n s ，t h el i n e a rp h a s ec a nb ea c h 主e v e d ，a n dg o o d s t a b i1i t y ，a n dt h u sf i rd i g i t a lf i1 t e ra c c e s st oaw i d er a n g e o fi t s 毯p p l i e a t i o n i t so p t i 掇i z e dd e s i g n 黻e t h o dh a sb e e np a i d c l o s ea t t e n ti o 稳b y 越o s to fs c h o l a r sa n de n g i n e e r s 。 p s oa l g o r i t h ms i m u l a t e dt h ef o r a g i n gb e h a v i o ro ff l y i n g b i r d s g r o u p ss e a r e hf o l l o w i n gt h eb e s tp a r t i e l e sa e e 。r d i n gt o t h e i r s p e e di nt h es o l u t i o ns p a c e p s oa l g o r i t h mh a st h e a d v a n t a g e so ff a s tc o n v e r g e n c e ， 1 e s ss e to fp a r a m e t e r sa n de a s y t oa e h i e v e ，a 羚dh a so 毽t s t 氇辍d i 魏gp e r f o r 毽a n e ei na d d r e s s 主n g n o n l i n e a ro p t i m i z a t i o np r o b l e m ，w h i c hl e a dp s oa l g o r i t h mt o b e c o m ea ni 脚p o r t a n tt 0 0 1f o ro p ti m iz a ti o n b a s e do np a r t 主e l es 鬻a r 壤o p t i 毽主z 氇专i o 珏a 王g o r i t h 辍t h e o r y ，p s 0 a l g o r i t h n li su s e dt oo p t i m i z ed e s i g nt h ef i rd i g i t a lf i1 t e ri n t h is p a p e r ， t h a tis ， c o 加b i n i n gw it ht h ea d v a n t a g e so fp s 0 氇l g o r i t h 瓣a 羚d 乞h ed e s i g 魏r e 毽较i r e 毽e 辍t s 。ff i 装d i g 量专a lf i 王t e r ， w ec a nf i n db e t t e rf i l t e rc o e f f i c i e n t sw i t ht h eh e l po fp s 0 a l g o r i t h m ， i no r d e rt oa p p r o a c ht h ef r e q u e n c yr e s p o n s eo f e 魏g 主珏e e r 王疑gr e 毽疆主r e 氆e 琵t s 。 f 主r s t l y ， 墨h e p 帮e r i 魏t r 。d 驻e e st h e p r i n c i p l eo fp s oa l g o r i t h m ，m a t h 。m a ti c a ld e s c r i p ti o n ， t h e i l l m e a n i n go ft h ep a r a m e t e r sa n dv a r i o u sm o d e l s s e c o n d l y ，t h e d e s i g nt h e o r ya n dm e t h o d so ft h ef i rd i g i t a lf i l t e rh a v eb e e n a n a l y z e d u n d e rt h es p e c i f i e dt e c h n i c a li n d i c a t o r s ， a h i g h p a s sf i l t e rh a sb e e nd e s i g n e di nt h ea p p l i c a t i o no fp s o a l g o r i t h m ，w h i c hi ss i m u l a t e di nt h ee n v i r o n m e n to fm a t l a b 6 5 t h er e s u l t ss h o wt h a tt h eh i g h p a s sf i l t e rh a sb e t t e rf i l t e r i n g e f f e c ts u c ha ss m a l l e rp a s s b a n dr i p p l ea n db i g g e rs t o p b a n d a t t e n u a t i o nt h a nw h i c hd e s i g n e db yc o n d i t i o n a lo p t i m i z a t i o n a l g o r i t h m f i n a l1 y ，t h ep a p e rs t u d i e st h ei n f l u e n c eo np s o a l g o r i t h mp a r a m e t e r so np e r f o r m a n c e t ot h eb a s i ci d e a so fe a s y u n d e r s t a n da n ds i m p l ea c h i e v et ot h ea l g o r i t h m ，f o rt h e p h e n o m e n o no fn o n l i n e a ra n dh i g h l yc o m p l e xi nt h ea c t u a ls e a r c h p r o c e s sf o rp a r t i c l e sa n df r o mt h ec h a n g ei nt h ep a r a m e t e r so f p s o ，w ew a n t t h a tt h ei n e r t i aw e i g h tc h a n g e sw i t ht h er u n n i n g p o s t u r eo ft h ep a r t i c l e s s oap a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h mw h i c hd y n a m i cc h a n g ei nt h ei n e r t i aw e i g h ti sg i v e n t h ed e s i g n e dh i g h p a s sf i l t e ru s i n gt h i sa l g o r i t h mh a sf a s t e r c o n v e r g e n c ea n dm o r er o b u s tf r o mt h ep e r f o r m a n c ei n d ic a t o r so f o n 一1i n ep e r f o r m a n c e ，o f f 一1i n e p e r f o r m a n c ea n d t h eo p ti m a l f it n e s se a c hg e n e r a tio no ft h eg r o u p k e yw o r d s ：f i rd i g i t a lf i l t e rp a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h md y n a m i cc h a n g ei nt h ei n e r t i aw e i g h t 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标 明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：f 引侈写刎年6 月 2 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大 学。同意学校保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅。本人授权湖南师范大学可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密回。 ( 请在以上相应方框内打“ ”) 作者签名：f 到伊弓日期：矽7 年6 月2 ，日 导师签名：办i 专t日期：加夕年多月2 一日 基于粒子群优化算法的f i r 数字滤波器的设计研究 1 1 引言 第一章绪论弟一早珀t 匕 数字滤波器在数字信号处理的各种应用中发挥着十分重要的作 用，一般分为模拟滤波器和数字滤波器。数字滤波器是通过对抽样 信号进行数学运算处理，以得到期望的响应特性的离散时间系统。 从数字滤波器的实现方法上又可分为i i r ( i n f i n i t ei m p u l s e r e s p o n s e ) 数字滤波器和f i r ( f i n i t ei m p u l s er e s p o n s e ) 数字滤波 器。ii r 滤波器具有相位非线性的缺点，若需要线性相位，则要采用 全通网络进行相位校正。而f i r 滤波器的一个突出优点是：在满足 一定对称条件下，可以实现线性相位，而且因为其结构中只用到前 向路径从而使其具有固有的稳定性，因而f i r 滤波器获得了广泛的 应用。常用的f i r 数字滤波器设计方法有窗函数法和频率抽样法， 这两种方法简单易行，但不易精确的确定其通、阻带边界频率。很 多研究者在f i r 数字滤波器设计问题上做了大量的探索并提出了用 优化法来设计f i r 数字滤波器。其中雷米兹( r e m e z ) 交换算法是最标 准的优化算法，但它对设计指标不仅有频域上的要求，而且又有时 间响应的约束时，该算法就不再适用。采用加权最小二乘( w l s ) 算 法设计虽然容易实现，但需要计算高阶矩阵的逆，当滤波器的阶数 很高时，这个矩阵的求逆将出现困难瞳1 。遗传算法是一种全局最优方 法，但是遗传算法采用了选择、交叉和变异等操作，算法结构复杂， 运算量大，收敛速度慢口4 l 。 硕士学位论文 粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s 0 ) 5 h 8 1 是 一种全局优化进化算法，由e b e r h a r t 博士和k e n n e d y 博士发明。该 算法源于对鸟群捕食行为的研究，同遗传算法相比，p s o 算法没有许 多参数调整，采用浮点数编码，并且根据自己的速度来决定搜索， 因此一般情况下p s o 算法能更快的收敛于最优解。同时算法实现简 单，因此，它已经成为一种重要的优化工具。 1 2 课题背景及研究意义 数字滤波器是指输入和输出均为数字信号，通过一定运算关系 改变输入信号所含频率成分的相对比例或者滤除某些频率成分的器 件。数字滤波器具有稳定性高、精度高、设计灵活、实现方便等优 点，它不仅能完成模拟处理的大部分功能，满足滤波器对幅度和相 位特性的严格要求，而且还可以避免模拟滤波器无法克服的电压漂 移、温度漂移和噪声等问题，实现模拟处理由于成本、可靠性等原 因而无法具体实现的功能。 在实际的工程应用中，数字滤波器的设计实现，通常需要同时 满足多个技术指标或达到较高的精度，设计工作比较复杂，而且只 能是逼近工程应用的指标要求，所以，要提高滤波器的性能，设计 过程中必须要进行大量复杂的推导和计算，运算量非常庞大。可见， 正是由于数字滤波器设计中的复杂性和重要性，多年来人们一直在 探索着有效的设计方法。许多学者在数字滤波器的设计问题上作了 大量的研究工作，提出了些设计方法，其中非常重要的一类设计 基于粒子群优化算法的f i r 数字滤波器的设计研究 方法就是优化算法，它是在一定优化准则下，使设计的滤波器性能 达到最佳。因此也派生了各种领域的优化算法，如p a r k s m c c l e l l a n 算法，遗传算法，神经网络法等。随着数字技术的发展和广泛的应 用，数字滤波器的优化设计越来越受到人们的关注。 数字滤波器包括有限长冲激响应f i r 和无限长冲激响应ii r 数 字滤波器。后者可以利用模拟滤波器设计的结果，有大量的图表可 查，能用较少的阶数获得很高的选择特性，计算工作量小，效率高； 但是实现高效率的代价是相位的非线性，而且选择性越好，相位的 非线性越严重。前者有自己突出的优点，如系统总是稳定的，可以 具有严格线性相位，而同时可以具有任意的幅度特性，允许设计成 多通带或多阻带滤波器，这些都是i i r 系统难以实现的。因而f i r 滤波器获得了广泛的应用。优化技术在f i r 滤波器的设计中的应用 成为目前研究的一个课题。 粒子群优化算法是一种新的全局优化算法，算法模拟鸟群飞行 觅食的行为，通过鸟之间的集体协作使群体达到最优，它与遗传算 法类似，也是基于群体迭代，但没有交叉和变异算子，群体在解空 间中追随最优粒子进行搜索，算法初始化为一群随机粒子( 随机解) ， 然后通过迭代找到满意解或最优解。在每一次迭代中，粒子主要是 通过跟踪两个“极值 来更新自己：一是粒子本身所找到的最优解 ( 个体极值p a r t i c l eb e s t ，记作p b e s t ) ；二是整个种群目前所找到 的最优解( 全局极值9 1 0 b eb e s t ，记作曲e s t ) 。p s o 的优点在于收敛 速度快、设置参数少、简单易实现，算法本身具有深刻的智能背景， 既适合科学研究，又特别适合工程应用。粒子群算法在解决非线性 优化问题方面有突出的表现，已成为一种重要的优化工具。 滤波器的设计可以归结为一个最优化问题。在对p s o 算法分析 研究的基础上，进行数字滤波器设计，可以将p s o 算法的优点与f i r 数字滤波器的设计需求结合起来，借助p s o 算法寻找到更好的滤波 器系数，从而最大程度地逼近工程要求的幅频响应。此外，这种优 化方法具有一定的普遍适用性，还可以用来解决其它类似的优化问 题，是一项很有意义的研究工作。 1 3 国内外研究现状及存在问题 近半个世纪以来，滤波器设计的基本理论一直没有改变，现有 的技术都只支持一种滤波器实现方法，比如无源l c r 滤波器、有源 r c 滤波器、数字滤波器及开关电容滤波器，从指标要求到实际设计 的第一步，都基于许多前人的基础工作。后人提出的多种优化方法 也都是遵照前人的基本方法，在此基础之上进行优化设计阳1 。 从历史的角度来看，对设计线性相位f i r 数字滤波器来讲，首先 提出的方法是利用窗函数截短期望频率响应的傅里叶级数展开形式 的设计方法。而后，在2 0 世纪7 0 年代，又提出了频率取样方法和 c h e b y s h e v 逼近方法，后来，在实际的线性相位f i r 滤波器的设计中， 这两种方法成为非常普遍的方法n 0 l 。 窗函数设计方法的主要缺点是对在低通f i r 滤波器设计中比如通 带截止频率皱和阻带截止频率织，这样的关键参数缺少精度控制。通 常来说，通带截止频率啦和阻带截止频率织的值依赖于窗函数的类型 基于粒子群优化算法的f i r 数字滤波器的设计研究 及滤波器的长度。 频率抽样方法在窗函数的设计方法上面做了一些改进，它在频率 q = 2 刀后m 或q = 刀( 2 七+ 1 ) m 上指定耳( 国) 并且规定过渡带为2 万m 的 倍数。在频域上用d f t 或者用频率抽样实现f i r 滤波器时，这种方法 特别有吸引力。这些实现有吸引力的特点是耳( q ) 在除过渡带以外的 所有频率都是为o 或者为1 。 c h e b y s h e v 逼近方法对滤波器的技术指标提供总控制，因此，它 在后两种方法中是更为可取的一种。对于低通滤波器来讲，按照参数 啤、q 、i y l 和4 ，然后，对参数疋来优化滤波器。通常将逼近误差分 散在滤波器的通带和阻带上，在对一组给定的技术指标来讲，在最大 旁瓣最小化这个意义上，这种方法得到的滤波器结构是最佳的。 c h e b y s h e v 设计方法建立在r e m e z 变换算法的基础上，需要我们 指定滤波器的长度，关键频率吱和q 以及比值4 和色m 1 。然后，确定 满足这些技术指标的滤波器长度。尽管，没有根据这些参数确定滤波 器长度的简单公式，但是，已经提出了一些根据关键频率和通带波纹 及阻带波纹估计m 的近似方法。一个归功于k a i s e r 的特别简单的近 似公式是n 2 3 膨= ( 一2 0 l 0 9 1 0 ( 4 龟) 一1 3 ) ( 1 4 6 v ) ( 1 1 ) 优化算法是在一定准则下，使设计的滤波器性能最佳。由于用 来使计算机设计的滤波器和要求的频率响应之间的误差最小化的迭 代最优化技术的提出n 引，出现了很多基于该迭代优化技术的滤波器 设计方法，如p a r k s m c c l e l l a n 算法、神经网络法、遗传算法等等。 传统f i r 数字滤波器的优化设计中，以p a r k s m c c l e l l a n 算法为代 表，该方法能获得较好的通带和阻带性能，但是算法复杂，计算量 硕士学位论文 非常大。 人工神经网络具有很强的自适应、自学习能力，很多学者将神 经网络与f i r 数字滤波器的设计结合起来，取得了比较好的效果， 但是隐含层结点数的选取则比较困难。神经网络的隐含层结点过少 则无法获取信号的全部特征而导致逼近失败，过多则又会引起过度 训练，网络可能会记住信号中由于干扰而产生的多余的细微特征。 通常隐含层的选取只能以经验为依据m h l 6 1 。 遗传算法是一种模拟自然界生物进化的搜索算法，由于它简单 易行，鲁棒性强，尤其是不需要专门的领域知识而仅用适应度函数 作评价来指导搜索过程，从而使它的应用范围极为广泛，并且已在 众多领域得到了实际应用，取得了许多令人瞩目的成果，引起广大 学者和工程人员的关注，遗传算法适用于处理传统搜索方法难以解 决的非线性问题n ，设计的滤波器能得到全局最优解，它区别于其 它滤波器优化方法的重要特点是不需要量化过程n 副。但是遗传算法 用于滤波器的优化设计过程中，存在一些不足n 刚吖2 引，如搜索空间太 大、部分个体过分早熟使种群陷入局部极值点、收敛速度慢等问题。 p s o 算法结构简单，编码容易实现，运算速度快，需要调整的参 数少，是一种新的全局寻优算法。已有学者采用p s o 算法的线性递减 惯性权重( l i n e a r l yd e c r e a s i n gi n e r t i aw e i g h t ，l d w ) 的策略乜， 所设计的滤波器性能优良。但是p s 0 在实际搜索过程中是非线性的且 是高度复杂的，致使惯性权重的线性递减策略不能反映实际的优化搜 索过程。本文引入动态改变惯性权重的概念，使惯性权重因子的变化 受算法运行态势的影响，从而使所设计的f i r 数字滤波器全局收敛速 基于粒子群优化算法的f i r 数字滤波器的设计研究 度更快，性能更优良。 1 4 主要研究工作 ( 1 ) 将粒子群算法应用于f i r 数字滤波器的设计中，研究基于粒子 群优化算法的f i r 数字滤波器的设计。 ( 2 ) 分析粒子群算法中粒子的飞行速度，研究基于动态确定惯性权 重的粒子群优化算法的f i r 数字滤波器的设计。 1 5 内容安排 第1 章绪论，介绍了本文的研究意义和背景，并对国内外的f i r 数字滤波器的设计方法的研究现状进行了分析，最后对本文的主要研 究工作进行了介绍。 第2 章粒子群算法的概述，主要对粒子群算法的产生与发展，算 法描述及算法的改进做了介绍。 第3 章研究基于粒子群优化算法的f i r 数字滤波器的设计。对数 字滤波器的原理及基本设计方法进行了介绍，并将粒子群优化算法应 用于f i r 数字滤波器的设计中，给出设计实例进行仿真，从混频信号 的滤波效果可以看出此项研究的有效性。 第4 章对粒子群算法中粒子更新的速度进行研究，引入动态确定 惯性权重的概念，使惯性权重因子的变化受算法运行态势的影响，从 而使所设计的f i r 数字滤波器全局收敛速度更快，性能更优良。 第5 章对全文进行了总结并对未来工作进行展望。 硕上学位论文 第二章粒子群优化算法 2 1 粒子群算法的研究背景 大自然是开启人类智慧的老师。“师法自然 ，人类受到生物系 统、物理系统、社会系统等运行机制启发，建立和发展起一个个研 究工具来解决和攻克研究过程中遇到的困难。p s o 算法最早由 e b e r h a r t 和k e n n e d y 于1 9 9 5 年提出，它的基本概念源于对人工生命 ( a r t i f i c i a ll i f e ) 和鸟群捕食行为的研究。1 9 8 6 年，c r a i gr e y n o l d s 提出了b o l d ( b i r d o i d ) 模型乜2 i 。该模型用来模拟鸟类聚集飞行行为， 他提出了如下三个规则作为群体中每个个体的行动规则。 ( 1 ) 向背离最近的同伴的方向运动； ( 2 ) 向目的运动； ( 3 ) 向群体的中心运动。 在这个群体中每个个体的运动都遵循这三条规则，通过这个模 型来模拟整个群体的运动。p s o 算法的基本概念也是如此。不像遗传 算法等进化算法，p s 0 算法不依靠遗传算子来操作个体，比如选择算 子、交叉算子、变异算子等，而是依靠个体间的信息交换来达到整 个群体的共同演化。这些称为“群 ( s w a 瑚) 的无体积无质量的小微 粒，能够调整自身的运动轨迹，同时能够向着自己以前经历过的最 好位置和其他微粒曾经经历过的最好位置飞行。为了实现这个目的， 所有的微粒都具有记忆功能，能调整自身速度和记忆经历过的最好 位置。在一个最小化问题中，一个较好的位置意味着解空间的一个 基于粒子群优化算法的f l r 数字滤波器的设计研究 对应着目标函数值较小的点。 p s o 一经提出，立刻引起了进化计算等领域的学者们的广泛关 注，并在短短的几年时间里出现了大量的研究成果，形成一个研究 热点。己被“国际演化计算会议”( i e e e 工n t e r n a ti o n a lc o n f e r e n c e o ne v 0 1 u t i o n a r yc o m p u t a t i o n ，c e c ) 列为一个讨论的专题。 2 2 粒子群算法的原理 可以设想这样一个场景：一群鸟在随机搜寻食物，在这个区域 里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道自 己当前的位置离食物还有多远。那么找到食物的最优策略是什么 呢? 最简单有效的方法就是搜寻目前离食物最近的鸟的周围区域。 p s o 算法就从这种生物种群行为的特性中得到启发并用于求解 优化问题。在p s 0 算法中，如果我们把一个优化问题看作是在空中 觅食的鸟群，那么“食物”就是优化问题的最优解，而在空中飞行 的每一只觅食的“鸟”就是p s o 算法中在解空间中进行搜索的一个 “粒子”( p a r t i c l e ) 。粒子的概念是一个折衷的选择，它只有速度 和加速度用于调整本身的状态，没有质量和体积。“群”的概念来自 于人工生命业引，满足人工生命的五个基本原则心劓。因此p s o 算法也 可看作是对简化了的社会模型的模拟，这其中最重要的是社会群体 中的信息共享机制，它是推动算法的主要机制。 粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的 飞行经验和同伴的飞行经验来动态地调整。所有的粒子都有一个被 硕士学位论文 目标函数决定的适应度值( f i t n e s sv a l u e ) ，这个适应度值用于评价 粒子的“好坏”程度。每个粒子知道自己到目前为止发现的最好位 置p b e s t 。当前的位置p b e s t 就是粒子本身找到的最优解，这个可以 看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为 止整个群体中所有粒子发现的最好位置g b e s t ，g b e s t 是在p b e s t 中 的最好值，也是全局最优解，这个可以看作是整个群体的经验。每 个粒子使用下列信息改变自己的当前位置： ( 1 ) 当前位置； ( 2 ) 当前速度； ( 3 ) 当前位置与自己最好位置之间的距离； ( 4 ) 当前位置与群体最好位置之间的距离。 优化搜索正是在由这样一群随机初始化形成的粒子组成的一个 种群中，以迭代的方式进行的。 2 3 粒子群算法的数学描述 在每一次迭代中，粒子通过跟踪两个“极值”来更新自己 6 | ：第 一个极值就是粒子本身所找到的最优解p b e s t ；另一个极值是整个种 群目前找到的最优解g b e s t 。 粒子i 的位置为置= ( 薯。，t ：，) r ，速度为k = ( 。，k ：，) 7 ，个 体极值表示为只= ( 。，只：，) r ，可以看作是粒子自己的飞行经验。 全局极值表示为只= ( 乞。，只：，) r ，可以看作整个群体的飞行经验。 粒子就是通过自己的经验和群体经验来决定下一步的运动。对于第 1 n 基于粒子群优化算法的f i r 数字滤波器的设计研究 k + 1 次迭代，每一个粒子是按照下式进行变化的： 1 = 吃+ c i ，i ( p 甜一) + c j 眨( p 耐一) 2 1 ) 露1 = + 略1 ( 2 2 ) 式中f = 1 ，2 ，m ，其中m 是群体中粒子的总数。，i ，吃是 o ，1 区间生成的随机数。d = l ，2 ，为解空间的维数，即自变量的个 数。加速因子c i 和c 2 分别调节向p b e s t 和g b e s t 方向飞行的最大步长， 合适的c l 和c 2 可以加快收敛且不易陷入局部最优。最大速度y 眦决定 了粒子在问题空间搜索的力度，粒子的每一维速度都会被限制在 一屹一，+ 屹一 之间，假设搜索空间的第d 维定义为区间【一为一， + 吻一】，则通常屹一= 七畅一，o 1 后o 2 ，每一维都用相同的设置方 法2 副。 由上式可以看出，公式( 2 1 ) 主要通过三部分来计算粒子i 更新 的速度：粒子i 前一时刻的速度1 ，三，粒子i 当前位置与自己历史最 好位置之间的距离( 砌一毛) ，粒子i 当前位置与群体最好位置之间的 距离( 一) 。粒子通过公式( 2 2 ) 计算新位置的坐标。粒子移动原 理如图2 1 ，以二维空间为例描述了粒子根据公式( 2 1 ) 、( 2 2 ) 从 位置到位置右1 移动的原理： 图2 1 粒子移动原理 式( 2 1 ) 的第一部分称为动量部分，表示粒子对当前自身运动状 态的信任，为粒子提供了一个必要动量，使其依据自身速度进行惯性 运动搜索；第二部分称为个体认知部分，代表了粒子自身的思考行为， 鼓励粒子飞向自身曾经发现的最好位置；第三部分称为社会认知部 分，表示粒子间的信息共享与合作，它引导粒子飞向群体中的最优位 置。公式( 2 1 ) 的第一项对应多样化( d i v e r s i f i c a t i o n ) 的特点，第二 项、第三项对应于搜索过程的集中化( ( i n t e n s i f i c a t i o n ) 的特点，因 此这三项之间的相互平衡和制约决定了算法的主要性能。粒子就是通 过自己的经验和同伴中最好的经验来决定下一步的运动。 2 4 参数意义 ( 1 ) 粒子的长度n ：问题解空间的维数。 ( 2 ) 粒子种群大小m ：粒子种群大小的选择视具体问题而定，但是一 般设置粒子数为2 0 一5 0 。对于大部分的问题1 0 个粒子已经可以取得 很好的结果，不过对于比较难的问题或者特定的问题，也可以适当 基于粒子群优化算法的f i r 数字滤波器的设计研究 调整粒子的数量以取得更好的结果。 ( 3 ) 加速常数c 1 ，c 2 ：分别调节向p b e s t 和g b e s t 方向飞行的最大 步长，决定了粒子个体经验和群体经验对粒子运行轨迹的影响，反 映了粒子群之间的信息交流。当c 1 = o 时，则粒子没有了认知能力， 变为只有社会的模型( s o c i a 卜o n l y ) ： 略= 诟+ c 2 乞( 一) ( 2 3 ) 被称为全局p s o 算法粒子有扩展搜索空间的能力，具有较快的收敛 速度，但由于缺少局部搜索，对于复杂问题比标准p s o 更容易陷入 局部最优。当c 2 = 0 时，则粒子之间没有社会信息，模型变为只有 认知( c o g n i ti o n o n l y ) 模型： 略1 = 咭+ q ( 已一t ) ( 2 4 ) 被称为局部p s o 算法。由于个体之间没有信息的交流，整个群体相 当于多个粒子进行盲目的随机搜索，收敛速度慢，因而得到最优解 的可能性比较小。因此一般设置c l ：c 2 。这样，个体经验和群体经 验就有了相同重要的影响力，使得最后的最优解更精确。改变这些 常数会改变系统的“张力，较低的c l 、c 2 值使得粒子徘徊在远离 目标的区域，较高的c l 、c 2 值将产生陡峭的运动或越过目标区域。 s h i 和e b e r h a r t 建议，为了平衡随机因素的作用，一般情况下设置 c 1 = c 2 = 2 ，大部分算法都采用这个建议。 ( 4 ) 粒子的最大速度：粒子的速度在空间中的每一维上都有一 个最大速度限制值v 傩，用来对粒子的速度进行限制，使速度控制在 【一屹一，+ 屹m 觚 的范围内，这决定问题空间搜索的力度，该值一般由 用户自己设定。v 眦是一个重要的参数，如果值太大，则粒子们 也许会飞过优秀区域；另一方面如果值太小，则粒子们可能无法 对局部最优区域以外的区域进行充分的探测。实际上，它们有可能 会陷入局部最优，而无法移动足够远的距离跳出局部最优达到空间 中更佳的位置。这种限制可以达到防止计算溢出、决定问题空间搜 索的力度的目的。 ( 5 ) r l ，r 2 ：是介于 o ，1 之间的随机数，增加了粒子飞行的随机 性。 ( 6 ) 迭代终止条件：一般设为最大迭代次数g m a x 、计算精度万或最 优解的最大停滞步数g 。 2 5 算法步骤 s t e p l ：初始化粒子群：给定群体规模m ，解空间维数n ，随机产生每 个粒子的位置x i 、速度v i ； s t e p 2 ：评价每个微粒的适应度； s t e p 3 ：对每个微粒，将其适应值与其经过的最好位置p b e s t 作比较， 如果较好，则将其作为当前的最好位置p b e s t ； s t e p 4 ：对每个微粒，将其适应值与其经过的最好位置g b e s t 作比较， 如果较好，则将其作为当前的最好位置g b e s t ； s t e p 5 ：根据( 2 1 ) 、( 2 2 ) 式调整微粒速度和位置； s t e p 6 ：未达到结束条件则转s t e p 2 。迭代终止条件根据具体问题一般 选为最大迭代次数g m a x 或( 和) 微粒群迄今为止搜索到的最优 4 基于粒了群优化算法的f l r 数字滤波器的设计研究 位置满足预定最小适应阈值。 2 6 加入惯性权重的粒子群模型 1 9 9 8 年s h i 等人在进化计算的国际会议上发表了一篇论文a m o d i f i e dp a r t i c l es w a mo p t i m i z e r 对前面的公式( 2 1 ) 进行了 修正口1 。引入惯性权重因子。 略1 = 碱+ c l ，i ( 砌一) + 乞眨( 一) ( 2 5 ) 缈非负，称为惯性因子。公式( 2 2 ) 和( 2 5 ) 被视为标准p s o 算法。 初始时，s h i 将缈取为常数，后来实验发现，动态缈能够获得比固定 值更好的寻优结果。动态可以在p s o 搜索过程中线性变化，也可根 据p s o 性能的某个测度函数动态改变。目前，采用较多的是s h i 建 议的线性递减权值策略。 缈= 一( ( 一) g 蛳) g ( 2 6 ) g 嘲为最大进化代数，缈。为初始惯性权值，缈山为迭代至最大代数 时惯性权值。典型取值国。= o 9 ，缈山= o 4 。缈的引入使p s o 算法 性能有了很大提高，针对不同的搜索问题，国可以调整全局和局部 搜索能力，也使得p s o 算法能成功的应用于很多实际问题。 权重因子缈使粒子保持着运动惯性，使其具有扩展搜索空间的 趋势，有能力探索新的区域。如果国= o ，则速度只取决于当前位置 和历史最好位置，速度本身没有记忆功能。假设一个粒子正好处在 全局最好位置，它将保持静止，其他粒子则飞向它的最好位置和全 局最好位置的加权中心，粒子将收缩到当前全局最好位置。在加上 硕士学位论文 第一部分后，粒子有扩展搜索空间的趋势，这也使得国的作用表现 为针对不同的搜索问题，调整算法的全局和局部搜索能力的平衡。国 较大时，具有较强的全局搜索能力；缈较小时，有较强的局部搜索 能力。恰当的选取算法的参数值可以改善算法的性能。 2 7 粒子群算法的改进 粒子群算法自提出以来，就以简单的计算形式，较少的参数设 置和良好的算法性能吸引了大批学者的关注，并被广泛应用于各个 领域。 人们对粒子群优化算法进行了各种各样的改进。但综合起来看， 主要是从参数、公式改进以及与其它算法的混合这几方面来进行。 前面我们也提到，粒子群优化算法中的参数不是很多，主要有 粒子种群数m ，最大速度，惯性权重缈，加速常数c 1 和c 2 。前 二个参数通常可以采用数值实验的方法来确定它的大致范围，后三 个参数直接影响粒子运行的轨迹，对算法的效果有着直接的影响， 对于这三个参数的选择研究得更多一些。 ( 1 ) 基于惯性权重国的改进 初始时，s h i 将惯性权重取值定为常数，后来实验发现，动态的 惯性权重能够取得比固定值更好的寻优结果。于是s h i 提出了线性 递减权重( l d w ) 策略，在算法初期国取值较大，有利于粒子探索未 知的区域，扩大搜索空间。在算法后期，收敛的情况下，缈取值较 小，有利于微调对最优区域周围的搜索，从而提高搜索的精度。典 基于粒子群优化算法的f i r 数字滤波器的设计研究 型取值为= o 9 ，= o 4 。但是还有两个缺点：一是迭代初期局 部搜索能力较弱，即使初始粒子已经接近于全局最优点，也往往会 被错过；而在迭代后期，则因全局搜索能力变弱，容易陷入局部极 值。二是最大迭代次数g 。较难预测，从而将影响算法的调节功能。 2 0 0 1 年s h i 又提出用模糊规则乜刚动态的修改功的值和随机惯性权重 ( r 1 w ) 取值策略。陈贵敏等眩铂在l d w 的基础上，又给出了三种非线性 的惯性权重递减策略，发现对于多数连续优化问题，凹函数递减策 略优于线性策略，而线性策略优于凸函数策略。 ( 2 ) 基于加速常数c 1 和c 2 的改进 加速常数c l 和c 2 代表了粒子向自身极值p b e s t 和全局极值 g b e s t 推进的随机加速权值。小的加速常数值，可以使粒子在远离目 标区域内振荡；而大的加速常数值则可使粒子迅速向目标区域移动， 甚至又离开目标区域。 c 1 = o ，则粒子没有认知能力，比标准算法更容易陷入局部极点。 c 2 = o ，则粒子之间没有社会信息共享，得到最优解的概率非常 小。 s h i 和e b e r h a r t 建议，为了平衡随机因素的作用，一般设c 。= c 2 = 2 2 8 | 后来c 1 e r c 推导出c i = c 2 = 2 0 5 2 9 1 r a t n a w e e r a 等3 们采用了根据 迭代次数来动态地修改加速因子的方法，即： c l = c i ，+ 酽万幸( c l 。一q ，) 鲫眦 c 2 = c 2 。+ g 阴幸( c 2 。一c 2 。) 矽拧一 ( 2 7 ) ( 2 8 ) 其中，c l 。，c 2 。分别为卟乞的终值，c l ，、岛，分别为q 、c 2 的初始值 硕士学位论文 模拟实验结果表明，当q 由2 1 5 线性递减至o 1 5 ，岛由o 1 5 线性 递增至2 1 5 时，算法所获的适应值最优。但是，这些研究也仅仅局 限于部分问题的应用，无法推广到所有问题当中。 ( 3 ) 进化公式的改进 对于进化公式的改进，主要是针对速度更新公式进行的，位置 更新公式保持不变。王存睿等口妇用个体平均极值取代算法中的个体 极值，使得粒子可以利用更多其他粒子的有用信息，在收敛精度和 收敛的稳定性方面优于标准的粒子群算法。吴亮红b 2 1 等针对全局最 优模型收敛速度快、局部搜索能力强但鲁棒性差和局部最优模型全 局搜索能力强、鲁棒性好但收敛速度慢的特点，提出了一种复合两 种模型的粒子群算法。速度更新公式为： = 毗+ q ，i ( p 。一劫) + 吃( c j ( p 甜一勃) ) + c j ( 尸鲥一勤) ( 2 9 ) 其中，c l = 2 ，c 2 + c 3 = 2 ，一般要求c 2 随进化的进行减小，相应的c 3 就会增加，即随着进化的进行逐渐减小p b e s t 的作用而增强g b e s t 的作用，使得算法的全局搜索能力和收敛能力有了一定程度的提高。 但是这些算法只是对于某些测试函数有比较高的性能在具体应用的 过程当中，都需要具体问题具体分析。 基于粒了群优化算法的f l r 数字滤波器的设计研究 第三章基于粒子群优化算法的 f l r 数字滤波器的设计 3 1 数字滤波器原理及设计方法 3 1 1 数字滤波器的原理 数字滤波器是对一个数字信号按照一定的要求进行运算，然后 以数字形式输出的系统。数字信号经过处理之后以数字形式输出， 这种处理叫做数字滤波。输出只与过去以及现在的输入有关的数字 滤波器，称为有限冲激响应( f i r ) 数字滤波器数字滤波器的原理 如图3 1 所示 x ( 以 l - 乃( 刀) 图3 1 数字滤波器原理框图 其时域输入输出关系为： 写成差分方程表达式为： 其系统函数为： y ( 以) y ( 订) = ( m ) x ( 以一朋) ( 3 2 ) 日( z ) = ( ，z ) z 一“ ( 3 3 ) 系