（信号与信息处理专业论文）基于遗传算法的自适应噪声抵消研究.pdf

东南大学硕士研究生学位论文 摘要 针对传统的自适应噪声抵消算法存在容易陷入局部极值点和不易收敛的问题，本文利用 遗传算法的全局收敛特性构造了基于遗传算法的自适应噪声抵消系统，分别采用基于二值 编码和基于实数编码的遗传算法进行仿真。 根据仿真结果基于f i r 滤波器结构的系统虽然有着结构简单的优点，但当参考噪声 信道传输函数为a i m r 模型时，算法的搜索效果相对f i r 滤波器结构较差。因此本文采用了 i i r 滤波器结构的系统。 仿真结果显示，对于自适应噪声抵消问题直接采用实数编码的遗传算法与常用的基 于二进制编码的g a 相比可以提高解的精度和运算速度。针对遗传算法所存在的未成熟收敛 和局部搜索能力较差的问题，本文采用小生境技术以有效保持群体的多样性，避免了算法的 未成熟收敛。然后将遗传算法与基于梯度的算法相结合得到混合遗传算法仿真结果表明该 算法可以有效地提高算法的局部搜索能力，从而提高了算法的搜索精度和速度。 u n d x 交叉算子有着很好的全局搜索性能：单亲遗传算法可以解决“早熟收敛”问题：c g a 可以降低遗传算法对内存的要求。对这些算法的研究都有着各自的意义，本文将其应用到自 适应噪声抵消系统，并给出了相应的仿真结果 本文的最后探讨了遗传算法的并行化处理和硬件实现问题。 关键词：自适应滤波自适应噪声抵消遗传算法硬件实现 堑童叁堂堕堕茎竺兰垡笙塞 。 a b s t r a c t c o n s i d e r i n gt h el o c a le x t r e m u m sa n dc o n v e r g e n c ed i f f i c u l t yo ft h et r a d i t i o n a la d a p t i v en o i s e c a n c e l l a t i o na l g o r i t h m ( a n c a ) ，t h i sp a p e rp r o p o s e saa d a p t i v en o i s ec a n c e l l a t i o ns y s t e mb a s e d o nt h eg e n e t i c a i g o r i t h m 限制在l 以内就可以了 x ( ，2 ) _ ：x c 。、 c 0 y ( ，? ) 绘定自适应滤波器的滤波器结构，自适应算法就是指按照某种准则不断调整滤波器的参 数，以达到在所描述的准则下的误差最小 3 6 。设输入信号为x ( 七) ，所期望的参考信号为 d ( 七) ，输出信号为_ y ( 七) ，滤波器的参数为占( 七) 我们按照所选定的准则，设计一个适当 的目标函数或代价函数f ( - ) ，自适应算法逐步调整目( 七) 使目标函数f ( - ) 最小化，最终使 y ( 后) 逼近于d ( 七) ，此时滤波器的参数口( 七) 收敛于自适应滤波器参数的最优解吼由于目 标函数f ( ) 是x ( k ) 、d ( k ) 和y ( k ) 的函数，即f ( ) = f 【x ( 七) ，d ( 七) ，y ( 七) 】，因此目标函数 应具有以下两个性质： 1 非负性 ，i x ( ) ，d ( k ) ，_ y ( ) 】0 ，v x ( k ) ，d ( 忌) ，y ( k ) 2 最佳性 f i x ( k ) ，d ( 露) ，y ( 七) = r a i n ( f ( ) ) ，当y ( 七) = d ( 七) 时 1 3 1 自适应算法简介 自适应算法大体可分为以下几类，都有各自的特点 3 6 】。 一、基于w i d r o w 滤波理论的方法的l m s 算法。它基于最小均方误差准则，对平稳随机 信号进行滤波。主要缺点是收敛速度慢和对输入信号的相关矩阵特征值扩展度的变化较敏 感。 第5 页 东南大学硕士研究生学位论文 二、基于k a l m a n 滤波理论的方法。滤波器可以工作在平稳的或非平稳的环境。比起l m s 算法有极快的收敛速度，对特征值扩展度的变化不敏感，但因需要求解卡尔曼滤波问题的矩 阵公式，计算复杂度较大。 三、基于最小平方准则的方法。使加权误差平方和最小，如：r l s 算法，l s l 算法等。 四、基于神经网络理论的方法。神经网络是由大量的神经源相互连接而成的非线性网络 系统，具有很强的自适应、自学习、自组织能力，并行性、鲁棒性好。 1 3 2 自适应噪声抵消系统常用算法及其存在的问题 在自适应噪声抵消系统中应用的算法有l m s 算法 3 9 c 5 2 2 5 6 】、r l s 算法和神经网络方 法 5 1 2 5 4 。比较而言：r l s 算法的收敛速度要高于l m s 算法，但是l m s 的计算量大大小于 r l s ，易于实时实现。神经网络方法鲁棒性较好。 在实际应用中最为常见的为l m s 算法。它具有计算简单、易于实时实现的特点。 考虑自适应滤波器结构为横向滤波器，在输入信号和参考信号都是平稳随机信号的情况 下，所期望的响应信号与横向滤波器输出信号之间的均方误差是滤波器系数权矢量的各分量 的二次函数，均方误差曲面是一个中间下凹的超抛物面，有唯一的最低点。可以用梯度方法 沿着该曲面调节权矢量的各元素以得到均方误差的晟小值。 按照此最小均方误差准则，以瞬时值推导出梯度矢量的估计值，即得到最小均方误差算 法，即l m s 自适应算法。它为w i d r o w 和h o f f 于1 9 6 0 年所提出 3 2 ，具有如下权系数更新 公式( 1 2 1 ) ： “= + 睨= 一占( ) = + 2 9 n k 五( 1 3 1 ) 其中是权系数矢量，k 是输入信号矢量，占( ) = e ( e i 。) 为均方误差( m s e ) 函数，输 出误差气定义为d k 一吲五，破是所期望信号，为控制算法收敛速度和稳定性的步长 因子。在l m s 算法的实际应用中，梯度v 占( 峨) 通常用其估计值v 占( 巩) = 2 e k k 代替。 其中收敛步长j 不易确定过小则收敛慢，过大则导致较大的失调量。为了解决这个 问题有多种改进的算法被提出。 变步长算法开始取较大的步长以加速收敛，然后逐渐减小步长以保证收敛后有较小的失 调量。其性能优于l m s 算法，主要方法有归一化l m s 算法( n l m s ) 、解相关l m s 算法( d l m s ) 2 4 、 双符号自适应法 5 、变步长l m s n e w t o n 法e 2 0 、时变步长自适应算法( v s s ) e 2 2 2 等。 动量l m s 算法( m l m s 算法) 2 3 在权系数更新中增加一个动量调节因子口，权系数更新 公式则为( i 2 2 ) ： + l = 哌一u v s ( ) + 以一i ( 1 3 2 ) m l m s 算法具有平滑和快速收敛的特点，但其收敛速度的提高是以较大的失调量为代价的。 针对m s 算法失调量大的缺点，文献 3 3 给出了具有随机动量因子的s m l m s 算法，以减小 第6 页 东南大学硕士研究生学位论文 动量失调对算法的影响。 变换域l m s 算法 1 5 1 7 先对输入信号进行正交变换，以降低输入信号间的相关性，然 后用能量归一化使输入信号自相关矩阵的特征值集中于1 附近，从而加速白适应滤波器的收 敛速度。但是对输入信号的正交变换增加了算法的复杂性。 以上虽然对l m s 算法提出了多种改进算法，但都无法完全解决l m s 算法的收敛问题。而 且梯度估计本身上就是一种比较租糙的估计。若将其用于i i r 自适应滤波器的优化时，更是 无法解决由于局部极小值的存在而算法无法达到全局收敛的问题。 1 4 基于遗传算法的自适应噪声抵消 以l m s 算法为代表的传统的自适应算法存在容易陷入局部极值点和不易收敛的问题，为 了解决这个问题本文引入具有全局收敛特性的遗传算法构成新的自适应噪声抵消算法。 由j h o ll a n d 教授提出的遗传算法( g a ) 3 5 是一种借鉴生物界自然选择和自然遗传机 制的随机化搜索算法，这是一种全局收敛的算法，可以有效地应用于大规模搜索空间。其基 本流程为首先随机生成一组初始解，对其按一定规则编码。对已编码的个体计算其适应度； 然后根据适应度迭代进行选择、交叉、变异操作直至所得最优解满足要求或已达到停止条件。 图1 5 遗传算法的基本流程 给定某个具体的实际问题，根据所要达到的目标，我们定义一个目标函数，则我们的 目的就是要找到使这个目标函数达到最小或晟大( 根据目标函数的定义而定) 的解。遗传算 法里将所给定问题所对应的目标函数的解( 参数集) 按照一定规则的编码将之表示为个体 ( i n d i y i d u a l s ) ，一定数量的个体则组成了群体( p o p u l a t i o n ) ，各个体所对应的函数值叫做 适应度( f i t n e s s ) 。遗传算法从任一初始化的群体出发，通过随机选择( 淘汰适应度较差的 第7 页 东南大学硕士研究生学位论文 个体而使群体中优秀的个体有更多的机会生存到下一代) 、交叉( 体现了自然界种群体内个 体之间的信息交换) 和变异( 在群体中引入新的个体以确保群体的多样性) 等遗传操作，使 群体一代一代地进化到适应度更好的区域，直至找到最优解。其基本流程如图1 5 所示。 由图可见，遗传算法是一种群体性操作，其操作对象为群体中的所有个体。选择 ( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 构成了遗传操作的主要操作算子。遗传算 法的几个基本要素：参数编码；群体的初始化；适应度函数的设计( 即目标函数的选择) ； 遗传操作算子的设计；控制参数的确定，这些都直接影响遗传算法的搜索效率 相比于传统的搜索算法，遗传算法有着以下独特之处： 1 遗传操作的处理对象不是参数本身，而是对参数集进行了编码的个体。这一特点， 使得遗传算法的应用具有广泛性。 2 传统的搜索算法都是单点搜索算法，对于多峰分布的搜索空间容易陷入局部的极值 点而得不到全局最优解。而遗传算法是同时对多个个体进行处理，选择、交叉操作都是 全局性的操作，使得其具有较好的全局搜索性能，从而减小了陷入局部的极值点的可能。 同时。这使遗传算法具有并行性的特点。 3 标准的遗传算法的操作不需搜索空间的知识，其目标函数不要求连续、可微等条件， 甚至不要求有具体的函数形式，只需能够得到目标函数的结果数据，便可以求得全局极 值。因此这一特点使得遗传算法在有些实际应用有其独到之处。 4 遗传算法不是采取确定性的规则，而是采取概率的规则来指导它的搜索方向。不同 于一般的随机搜索方法的搜索方向是盲目的，遗传算法实际上是有着明确的搜索方向 的。 以上特点使得遗传算法具有使用简单、应用范围广、鲁棒性强和易于并行处理的特点。 其目标函数不要求连续、可微等条件，甚至不要求有具体的函数形式，只需能够得到目标函 数的结果数据，便可以求得全局极值。遗传算法已广泛地应用于控制、规划、设计、组合优 化、图像处理、信号处理、机器人及人工生命等诸多领域 1 3 1 6 2 7 3 4 。因此，应用遗 传算法来实现自适应噪声抵消系统，可以取得传统方法所无法达到的效果。 当然，将遗传算法应用到自适应噪声抵消系统。也还有一些问题需要解决。首先因为遗 传算法是对多个解同时进行操作，对每个解的评估都需要一个样本，而实际系统每一代只能 提供一个样本，因此需要构造适于遗传算法操作的系统结构。其次遗传算法本身也存在着一 些缺陷，主要是未成熟收敛和局部搜索能力差的问题。为了解决未成熟收敛问题，需要在编 码、适应度函数和遗传操作的设计中考虑相应对策。针对遗传算法局部搜索能力较弱的特点， 要对标准的遗传算法做进一步的改进，以改善遗传算法的局部搜索能力，进一步提高优化质 量与搜索效率。 第8 页 东南大学硕士研究生学位论文 1 5 小结 自适应噪声抵消就是让受到污染的信号经过一个自适应滤波器，抑制其中的干扰和噪声 并保留信号能量，以提高传递和接收的信号的信噪比。自适应滤波器由参数可调的数字滤波 器和自适应算法两部分组成。 参数可调的数字滤波器的形式可以分为两类基本结构，一类为非递归的横向结构的自适 应滤波器，另一类为自适应递归滤波器。 自适应算法有基于w i d r o w 滤波理论的l m s 算法、基于k a l m a n 滤波理论的方法、基于最 小平方准则的r l s 算法。l s l 算法等方法以及基于神经网络理论的方法。在自适应噪声抵消 系统中晟常用的算法为l m s 算法，其计算量小，易于实时实现。但是l 惦算法的收敛步长 不易确定，过小则收敛慢过大则不稳定。为了解决这个问题，有多种改进的算法被提出。 但都无法完全解决l m s 算法的收敛问题。 而由j h o l l a n d 教授提出的遗传算法( g a ) 是一种借鉴生物界自然选择和自然遗传机制 的随机化搜索算法，这是一种全局收敛的算法，可以有效地应用于太规模搜索空间。遗传算 法具有鲁棒性、并行化的特点，其目标函数不要求连续、可微等条件，甚至不要求有具体的 函数形式，只需能够得到目标函数的结果数据，便可以求得全局极值。因此，本文应用遗传 算法来实现自适应噪声抵消系统，以取得传统方法所无法达到的效果。 第9 页 东南大学硕士研究生学位论文 第二章遗传算法 由j h o l l a n d 教授提出的遗传算法( g a ) e 3 5 是一种借鉴生物界自然选择和自然遗传机 制的随机化搜索算法，本质上是一种求解问题的高效并行全局搜索方法可以有效地应用于 大规模搜索空间。遗传算法具有鲁棒性、并行化的特点其目标函数不要求连续、可微等条 件，甚至不要求有具体的函数形式，只需能够得到目标函数的结果数据，便可以求得全局极 值。所以遗传算法的适用范围非常广泛，已成功地地应用于控制、规划、设计、组合优化、 图像处理、信号处理、机器人及人工生命等诸多领域。本章将简单介绍遗传算法中的一些基 本问题，然后针对遗传算法中全局收敛和局部搜索效率的提高这两个主要问题作进一步的阐 述。 2 1 编码与群体设定 遗传算法的操作，首先要将所要解决的问题的解空间的解转化为遗传空间的个体，这就 是编码( c o d e i n g ) 。编码的策略直接影响到遗传操作和遗传算子的选择，如何针对所要解决 的问题选择适当的编码方式，对于遗传算法的搜索效率是十分重要的。 对此，d e j o n g 提出了可操作性较强的编码规则 3 5 ： 1 有意义积木块编码规则：所定编码应当易于生成与所求问题相关的短距和低阶的积 木块。 2 最小字符集编码规则：所定编码应采用晟小字符集咀使问题得到自然的表示或描 述。 一种很自然的选择就是实数编码方法。将所求问题的解点的每个参数用一个实数表示， 该组的实数所组成的矢量即为遗传空间的一个个体。 相比之下，二值编码似乎更适合于二进制的计算机运算。其方法为将所求问题的解点 的参数表示为若干位长度的二进制无符号整数串，如果有多个参数，则将这些整数串合并成 为一个整数串，即组成遗传空间的一个个体。设二进制无符号整数串的长度为，则该子串 所对应的无符号整数为【o ，27 1 】，设参数的取值范围为 u 。u 。】t 则参数与二进制无符 号整数串之间存在一个线性映射关系。 当然对于某些具体问题，相应地采取特殊的编码方式会更有利于遗传算法的实现。例 如。对于旅行商问题( t s p ) ，采用以遍历城市的次序排列进行编码更为自然 3 5 3 。在这里就 不一一叙述。对于滤波器问题，一般是采取实数编码方法和二值编码方法。 第l o 页 东南大学硕士研究生学位论文 遗传算法的初始群体是随机产生的。一般来说，首先根据问题的背景知识，确定最优 解所占空间的分布范围，然后在此范围内设定初始种群。为了使算法能全局收敛，并可以尽 快找到问题的最优解，群体的多样性即群体分布的广泛性，是必须考虑的一个重要问题。 群体的规模越大，当然群体的分布就越广泛。算法陷入局部解的可能性就越小。但是群体规 模太大会过于耗尽有限的计算资源，影响算法的效率。因此群体的选择要适当以使有限的群 体具有尽量广泛的代表性。 2 2 遗传算子 遗传算法的遗传操作包含以下三个遗传算子：1 ) 选择；2 ) 交叉；3 ) 变异。这三个 算子的操作都是随机化操作，其具体形式需要根据具体的问题而定，配合遗传参数的适当选 择，才可以使算法得到最优的效果。以下简要介绍一些常用的遗传算子。其中交叉算子和变 异算子随编码方式的不同而有不同的形式。这里只介绍适应于常用的二值编码遗传算法的交 叉算子和变异算子，在下一章里再介绍适应于实数编码遗传算法的交叉算子和变异算子。 2 2 1 选择算法 从群体中选择优胜的个体以组成下一代的过程叫做选择。选择的目的是把优化的个体直 接遗传倒下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个 体的适应度评估基础上的，常用的选择算子有以下几种： 1 适应度比例方法 3 5 3 适应度比例方法是遗传算法中最基本也最常用的选择方法，也叫轮盘赌或蒙特卡罗选 择。在该方法中。各个个体的选择概率和其适应度成正比。 2 最佳个体保存方法 3 5 该方法的思想是把群体中适应度最高的个体不进行交叉变异操作而直接复制到下一代 这样进化过程中所得到的当前最优解不被交叉和变异操作所破坏。文献 3 4 指出标准的遗传 算法( 比例选择法) 在任意初始化，任意交叉算子以及任意适应度函数下，都不能收敛到全 局最优解。而通过保留当前最优解，理论上则能保证收敛到全局最优解。 3 期望值方法 3 5 在轮盘赌选择方法中，当个体数不多时，由于按适应度大小的概率选择方法所存在的统 计误差，适应度高的个体可能会被淘汰，适应度低的个体反而会被选择，会克服这种误差， 首先计算群体中每个个体在下一代生存的期望数目： m = z 7 = z ，刀 ( 2 2 1 ) 然后复制该个体肘的整数部分个数到下一代，这样就保证了适应度高的个体不被淘汰，最 第1 1 页 东南大学硕士研究生学位论文 后将该个体j 】l 彳的小数部分个数重新按适应度比例方法复制到下一代 4 排序选择方法 3 5 所谓排序选择方法是指在计算每个个体的适应度后，根据适应度大小顺序对群体中个体 排序然后分配事先设计好的概率给每个个体为其选择概率。 5 联赛选择方法 3 5 不管是适应值比例方法还是排序选择方法都要对整个群体进行求和或排序操作，计算量 较大不太适合一些需要实时处理的场合，此时就需要一些计算较为简单的选择算子。联赛 选择方法则十分简单，其操作思想是，从群体中随机选择一组个体，将其中适应值最高的个 体保存到下一代。反复执行这一过程，直到选择到所需要的数目。联赛规模一般选取为2 。 6 排挤方法 6 如果某一个个体过度繁殖就会占据过多的位置，派挤掉其他的个体，导致群体中所有 的个体都陷入同一值而使算法未成熟收敛。为了防止算法的未成熟收敛必须要保持群体的 多样性。d ej o n g 提出了排挤选择方法，新生成的子代将替代或排挤相似的父代个体。 2 2 2 交叉算子 交叉算子是遗传算法中起核心作用的算子，它将两个父代个体的部分结构加以替换重组 而生成新的个体。交叉算子的设计要遵守以下的交叉原则 1 4 ： 1 保证前一代中优秀个体的性状能为后一代的新个体得到遗传和继承。这是其基本原 则。 2 拓展新的搜索空间( e x p l o r i n g ) 与局部寻优( e x p l o i t i n g ) 的平衡 拓展新的搜索空间是为了维持群体的多样性，避免算法的早熟收敛。要求交叉操作保持 种群的统计特性( 如均值与方差) 不变。局部寻优是为了加快算法的收敛速度。 1 一点交叉( o n e p o i n tc r o s s o v e r ) 3 5 在个体串中随机设定一个交叉点，互换父本两个个体在该点的前后部分，生成两个新个 体如下所示： 父本爿00110 0 父本曰 1 1 1 1 010 子本001010 子本b111100 2 多点交叉( m u i t i p o i n tc r o s s o v e r ) 3 5 多点交叉为一点交叉的推广，设置的交叉点为多个，以二点交叉为例 父本爿00 11 1 00 父本b 11 f 01 i 10 子本爿。00 0l00 第1 2 页 东南大学硕士研究生学位论文 子本b 1 11 110 3 一致交叉( u n i f o r mc r o s s o v e r ) 3 5 3 指通过设置屏蔽字( m a s k ) 来决定新个体的基因继承两个父本个体中那个个体的对应基 因。操作过程为：设父本为a ，b ，生成的新个体4 。，b 。当屏蔽字为0 时，新个体a 继承 父本a 中对应的基因，当屏蔽字为1 时，新个体a 继承父本b 中对应的基因反之可生成 新个体b 。举例如下： 父本a 001111 父本b 1 1 1 10 0 屏蔽字010101 子本a 011110 子本b101101 2 2 3 变异算子 遗传算法中，交叉算子因其全局搜索能力而作为主要算予，变异算子作为辅助算子有两 个作用 3 5 ： 1 使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域 时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。这时的变异概率应该取 较小值，以避免破坏优良的模式。 2 使遗传算法维持群体的多样性，以防止出现未成熟收敛现象。此时变异概率应取较 大值，以跳出局部极值点。 相比第一个作用，变异算子的第二个作用更为重要。遗传算法的局部搜索能力通常可以 通过采用其他的局部搜索算法得到加强，这样可以取得比只利用变异算子的局部搜索能力更 为有效的结果。文献 3 5 3 提到排除变异仅有交叉的遗传算法可等效为有限吸收的m a r k o v 过 程。交叉算子没有开辟新的搜索空间的能力，如果初始搜索空间不包含全局最优解，仅有交 叉的遗传算法只能收敛到局部最优解，此时必须依靠变异算子来开辟新的搜索空间。 1 单点变异 3 5 在个体串中随机设定变异点，以一定的变异概率对该点的值施以变异， 0 。1 ) 二值码串 中的变异如下所示： 变异 件夕1 0 1 1 件 变异点 2 逆转算子 3 5 3 第1 3 页 东南大学硕士研究生学位论文 逆转算子是变异算子的一种特殊形式。它的基本操作是，在个体码串中随机挑选二个逆 转点，然后将两个逆转点之间的基因值以一定的逆转概率逆向排序。 逆转 悱夕1 1 1 0 1 01 1 舯 逆转点 3 自适应变异算子 3 5 操作内容同单点变异，不同之处在于变异概率不是固定不变的常数而是随着群体中个体 的多样性而自适应调整。一般是根据交叉所得两个新个体的海明距离进行变化。海明距离越 小，变异概率越大。文献 4 0 通过对二进制编码串中每一比特位赋予不同的变异概率，使得 如果变异后的适应度变化比较太，相应编码位的变异概率就减小得快，从而使群体能够迅速 集中；反之，变异概率就减小得慢，以保证局部搜索性能这样可以加快搜索过程。文献 5 0 将每个个体按适应值大小进行排序，根据个体排序值来自适应地确定变异算子的概率。 2 3 全局收敛性 虽然遗传算法具有全局收敛的能力，但其全局收敛性的理论分析仍是个有待解决的问 题。目前普遍认为标准遗传算法( 采用二值编码，赌轮选择，一点交叉，单点变异的遗传算 法) 并不保证全局最优收敛。如果我们对标准遗传算法作一定改进，即不按比例进行选择， 而是保留当前的最佳值，则算法理论上最终可以收敛到全局最佳值 3 5 3 。不过此时收敛到晟 优解所需的时间可能是很长的。 遗传算法不能全局收敛，而陷入未成熟收敛，其原因在于群体多样性的缺失。为此，必 须在编码、适应度函数和遗传操作等设计中加以考虑以抑制未成熟收敛的发生。一般常用的 方法有： 1 ) 提高变异概率 在进化初始阶段，提高变异概率可以加强遗传个体的随机搜索能力；当群体中的个体有 同一化的趋势时，提高变异概率可以脱离局部极值点。 2 ) 适应度函数定标 3 5 3 一般问题的求解的目标是求取目标函数( 代价函数) 的最小值。遗传操作时需要将其转 化为非负的的适应度函数，且目标函数( 代价函数) 的晟小值对应于适应度函数的最大值。 如果在群体中某一个体的适应度远超出其他个体，若按照比例选择策略，该个体有可能在群 体中占据极大的比例，从而导致算法的未成熟收敛。因此，需要对适应度函数作_ 定的缩放 调整，即适应度函数定标，以抑制该个体的竞争力。定标的常用方法有线性定标、盯截断、 乘幂标等等。 第1 4 页 东南大学硕士研究生学位论文 3 ) 选择操作时采取可以保持群体多样性的措施 单纯的按比例选择操作没有考虑到种群的多样性问题，要保持群体的多样性，可以考虑 以下几种策略：a ) 小生境( n i c h e ) 技术 4 】 1 1 ：将具有共同特征的个体组织为子群体，以维 持群体的多样性，典型的方法有基于预选择( p r e s e l e c t i o n ) 的小生境技术、基于排挤 ( c r o w d i n g ) 机制的小生境技术和基于共享( s h a r i n g ) 机制的小生境技术：b ) 局部化 3 5 ：把 群体分割为若干子群体，每个子群体独立地进行选择操作，这样可使未成熟收敛现象局部化； c ) 单一化5 ：相同的个体单一化，不允许群体中有相同的个体出现。 4 ) 交叉操作时增大配对个体距离 配对个体不是随机进行，而是以海明距离测度或其他测度来判断配对个体的相似度，并 由此来决定配对与否。 2 4 局部搜索能力 基本遗传算法存在着局部搜索能力较差的缺点，从而影响算法的搜索效率。因此，需 要对算法作一定的改进，以增强算法的局部搜索能力。 为了解决这一问题，可以采取多种方法： 1 ) 对基本遗传算法作适当的改进，采取有利于提高局部搜索能力的遗传算子，如将 交叉操作限制在遗传空间较为相邻的个体之间，这样可以在一定程度上改善遗传算法的局部 搜索能力。 2 ) 以当前最优个体为中心，构造一个缩小的遗传空间，在此遗传空间内再进行遗传 操作得到新的最优个体，以此来提高算法的局部搜索能力。 3 ) 将遗传算法与其他局部搜索能力较强的算法如梯度下降法、爬山法( h c ) 、摸拟退 火法( s a ) 、列表寻优法( t a b u ) 等相结合构成混合遗传算法，借助于其他算法的局部搜索能力 以增强算法的局部搜索能力，进一步提高优化质量与搜索效率，达到任何单一方法均无法达 到的效果。具体实现方法主要有 5 3 ：( a ) 首先通过遗传算法搜索近似全局最优解，以群体 中的最优个体作为其他算法的初始点，然后用其他算法进一步搜索全局最优解。( b ) 执行其 他算法，当陷入局部极值点时开始遗传算法，并以群体中最优个体作为下一循环算法的初始 点。( c ) 由其他算法构成遗传算法操作的算子。 2 5 小结 遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法，这是一种全 局收敛的算法，可以有效地应用于大规模搜索空间。其基本流程为首先随机生成一组初始解。 第1 5 页 东南大学硕士研究生学位论文 对其按一定规则编码，对已编码的个体计算其适应度：然后根据适应度迭代进行选择、交叉、 变异操作直至所得最优解满足要求或已达到停止条件。遗传算法具有鲁棒性、并行化的特点， 适用范围非常广泛 遗传算法的操作，首先进行编码操作，编码的策略直接影响到遗传操作和遗传算子的选 择。编码的方式要根据具体问题而定，最为常见的为二值编码和实数编码。遗传算法的初始 群体是随机产生的，为了使算法能全局收敛，并可以尽快找到问题的最优解必须要考虑到 群体的多样性。 根据编码方式的不同。相应地选择不同的选择、交叉、变异算子。选择的目的是把优化 的个体直接遗传倒下一代或通过配对交叉产生新的个体再遗传到下一代。遗传算法中，交叉 算子因其全局搜索能力而作为主要算子。变异算子作为辅助算子，以实现保证前一代中优秀 个体的性状能为后一代的新个体得到遗传和继承，并达到拓展新的搜索空间( e x p l o r i n g ) 与 局部寻优( e x p l o i t i n g ) 的平衡。 标准遗传算法并不保证全局最优收敛。为了使遗传算法全局收敛，而不陷入未成熟收敛， 为此，必须在编码、适应度函数和遗传操作等设计中加以考虑以保持群体的多样性，从而抑 制未成熟收敛的发生。为了改善遗传算法的局部搜索能力，需要对算法作一定的改进，以增 强算法的局部搜索能力。 第1 6 页 东南大学硕士研究生学位论文 第三章基于二值编码遗传算法的自适应噪声抵消 二值编码是遗传算法中最为常用的编码方法。它可以适应于任何变量，且二进制串易于 计算机的处理，对其的理论分析也比较充分。基于二值编码的遗传算法适用范围广，且易于 硬件实现。 本章首先对基于二值编码的遗传算法做一个简单的介绍，然后给出基于遗传算法的自适 应噪声抵消系统的结构框图，并给出基本算法的仿真结果，最后分别介绍其他几种基于二值 编码的遗传算法及其仿真结果。 3 1 引言 二值编码的遗传算法首先要将所求问题的解空间的参数映射为遗传空间的二进制无符 号整数串个体。设二进制无符号整数串的长度为z ，则该子串所对应的无符号整数为 o ，2 - i ，设参数的取值范围为【( ，。u 一】。则参数与二进制无符号整数串之间存在一个 线性映射关系。映射的编码精度s 为： 弘导笋 ( 3 1 1 ) 对于多参数问题，每一个参数对应于一个子串，根据解的精度的需要，每个子串可咀取不同 的长度。子串的长度越长，解的精度自然就越高，但同时搜索空问也随之扩大。 当然为了提高算法的效率，也可以不用标准的二进制码，而采用相邻两数之间汉明距离 ( 。h a m i n gd i s t a n c e ) 为1 的格雷编码( g r a yc o d e ) 5 8 。 关于二值编码的遗传算法的常用遗传算子已经在第二章做了简要的介绍。这里就不再复 述。一般为了解决基本遗传算法存在未成熟收敛的问题，在算法的进化过程中需要动态地改 变遗传算法的遗传参数。在进化初始阶段，需要提高变异概率以加强遗传个体的随机搜索能 力，然后减小变异概率以加快算法的收敛，而当群体中的个体有同一化的趋势时，又要提高 变异概率以脱离局部极值点。 第1 7 页 东南大学硕士研究生学位论文 3 2 系统结构 根据图1 。l 所示，设参考输入噪声为r t l ，滤波器的输出为y ，系统输出为s ，当e 口2 】 取得最小值时，滤波器的输出y 即为原始噪声”o 的最佳估计。根据遗传算法的要求，我们 可以取适应度函数为i e c 2 】，这样得到基于遗传算法的自适应噪声抵消算法，其基本流程 为：首先随机生成一组滤波器组成当前群体，每一个滤波器即对应于群体中的一个个体。对 每一个滤波器，得到采样长度为f 的参考噪声啊、i t l 经该滤波器而产生的输出y l 和系统输 出信号占，然后求得对应于该滤波器的个体适应度。根据个体的适应度进行遗传操作得到新 的群体，这样完成一代遗传操作， 以上的算法流程存在一个问题，即对群体中的每一个个体进行适应度评估时都需要一个 样本，这样群体的个体数正比于学习样本数。而在实际应用中每一代则只有一组采样数据， 即只有一个学习样本。为了解决这个问题，为此，将图1 i 所示的系统结构改为图3 i 所示 的结构 i s 。 信 噪 图3 i 基于遗传算法的系统结构框图 系统有两个传感器，第一个传感器接收到信号s 和一个与信号不相关的加性噪声，即 输入为j + 订o ，组成抵消器的原始输入。第二个传感器接收到与信号s 不相关的而以某种未 知方式与噪声相关的噪声刀l 。该传感器给抵消器提供参考输入。设从噪声源到参考支路的 通道传输函数为h ( z ) 。c ( z ) 为当前自适应滤波器的解集，c ( z ) 为上一代自适应滤波器 解集中的最优解。y l 为珂l 经最优滤波器c ( z ) 而产生的与噪声相匹配的输出，将该输出从 第1 8 页 东南大学硕士研究生学位论文 原始输入中减去产生系统输出占y 2 为啊经c 。( z ) 的输出，将其与y l 和占之和相减得到 误差信号p ，从而来调节自适应滤波器。 假设j ，珂o ，一l 是统计平稳的，并且均值为0 如前所言，s 和胛o ，一i ，y i ，_ y 2 不相关和 n 。相关系统输出为 占= s + n o m ( 3 2 1 ) 误差信号e 为 p = m ，+ 占一y ：= y l + 0 + 丹。一m ) + y 2 ( 3 2 2 ) = s + ( h o y 2 ) 将上式两边平方后，得到 e 2 = s 2 + ( 一。一y 2 ) 2 + 2 s ( n o y 2 ) ( 3 2 3 ) 两边取数学期望值，因为j 和1 1 0y 2 不相关，所以有 e e 2 】= e s 2 】+ e 【( 胛。一_ y 2 ) 2 】+ 2 e s ( n o 一) ，2 ) 】 = e s 2 】+ e 【( 摊。一y 2 ) 2 】 当调节滤波器参数使e p 2 】最小化时，因为e s 2 】与滤波器无关。所以e e 2 】取得最小 值时即有 e m m p 2 = e s 2 】+ e m m ( 一_ y 2 ) 2 】 ( 3 2 5 ) 因而当e e 2 】取得最小值时，e 【( - y 2 ) 2 也取得最小值。所阻滤波器的输出y 2 即为 原始噪声n o 的最佳估计，此时即有j y l 为原始噪声n o 的最佳估计t 系统输出占即为源信号s 的最佳估计。相应地我们可以取遗传算法的适应度函数为1 e e 2 】。 由此可见，对于自适应滤波器解集中的每一个滤波器，只要得到参考噪声t l 经最优滤波 器而产生的输出y 和系统输出信号占，即可得到误差信号e ，从而完成该滤波器所对应个体 的适应度评估。这样，对于每一代遗传操作，只需一个公共样本即可完成整个群体的适应度 评估，从而完成群体的进化。 于是我们得到改进的算法的流程为：首先随机生成一组滤波器，组成当前的自适应滤波 器解集。为了减小算法的初始误差。不妨以传递函数为l 的滤波器作为初始最优滤波器。然 后得到采样长度为z 的参考噪声啊、n i 经最优滤波器而产生的输出y i 和系统输出信号占。 利用y ，和占进行遗传操作得到新的自适应滤波器解集和最优滤波器。在进行遗传操作的同 时最优滤波器保持不变。遗传操作结束的时候，我们得到新的采样信号。然后我们以新的 最优滤波器代替老的最优滤波器，以新的自适应滤波器解集和新的采样信号进行下一代遗传 操作。如此反复进行直到达到算法的终止条件。 第1 9 页 东南大学硕士研究生学位论文 对应的，当滤波器结构为f i r 形式时，自适应噪声抵消系统的结构框图修改为如图3 2 所示。 信 噪 原始输入 图3 2f i r 滤波结构时基于遗传算法的系统结构框图 3 3 基本算法 对应于采用不同的滤波器结构，我们得到使用f i r 滤波器结构和使用i i r 滤波器结构的 两种不同的自适应噪声抵消系统。当自适应滤波器结构为f i r 滤波器结构时，在输入信号和 参考信号都是平稳随机信号的情况下，所期望的响应信号与当自适应滤波器输出信号之间的 均方误差是滤波器系数权矢量的各分量的二次函数，均方误差曲面是一个中间下凹的超抛物 面，有唯一的最低点。此时应用遗传算法来搜索这个唯一的最低点的搜索效果，较之那些常 规的搜索方法，并无太多的优势因而其应用价值不是很大。而遗传算法的长处在于它的全 局收敛能力，特别适用于搜索具有多个局部极值点的复杂的性能平面，比如使用f i r 滤波器 结构的自适应噪声抵消系统的性能平面。因此本章只使用i i r 滤波器结构的自适应噪声抵消 系统作算法仿真试验。 系统结构如图3 1 所示。为了保证i i r 滤波器的稳定，采用如图1 4 所示格型形式的 i i r 滤波器，这样只要简单地将滤波器的反射系数( k ，k u _ i ，k 1 ) 限制在1 以内就可以 了。 设个体集为t ，个体乙= ( k n ，七i ，k i ，“，c m ，q ，c o ) ，n 为滤波器的阶数- 初 始个体系数( “，七- l ，h ) 取为 一l ，1 1 2 f 司的随机值，0 ，c _ _ 1 ，c l ，c o ) 取为 一2 0 ，2 0 之间的随机值。因为( k ，“+ ，七1 ) 决定了滤波器的极点，对滤波结果的影响较之 ( c ：c _ l ，c l ，c o ) 要大，所以对( “，七- 1 ，k 1 ) 的精度要求较高，对其编码时要用相对较 长的二进制串。设表示七，的二进制无符号整数串的长度为，表示c ，的二进制无符号整数 第2 0 页 东南大学硕士研究生学位论文 串的长度为1 2 ，则对每个个体瓦，需要用，位二进制无符号整数串来表示，其中有： ，= m l + ( n + 1 ) 1 2 ( 3 3 1 ) 对于个体瓦，滤波器的输出为y 2 = 瓦。刀l ，残差信号为e ，适应度函数f i t n e s s 选取如下 所示： j f i t n e s s i = 1 e ( f ) 2 ( 3 3 2 ) f 其中，为采样长度。 3 3 1 遗传算法结构 设个体集为丁对每个个体瓦，用z 位二进制无符号整数串来表示，则得 五= ( 瓦j ，五，2 ，正) ，其中有瓦 o ，1 ) ，f = l ， 选择笋子采用适应度比例方法，同时保留最佳个体最佳个体不进行交叉、变异操作， 直接复制到下一代群体。 交叉操作采取单点交叉。设交叉概率为p 。，具体的交叉操作为： 1 随机选择两个个体，设为五= ( 五j ，五。，巧，) ，正= ( t l l ，正。，正，) 2 随机得到【0 ，l 】之间的数，若有， p 。，则保持原个体不变，否则选择 1 ，妇之间的 随机数f ，得到新个体如下所示： 个体五五p 巧p ，瓦卜- z f i ，五l ：- ，互刀，互一，乃p ，正，新个体五 个体正瓦p 瓦，正，。扛，一，正，瓦p 正，五卜。，互，五，新个体乏 交叉点 变异操作采用单点变异。设变异概率为p 。，从群体中随机选择一个个体 瓦= ( 瓦1 ，瓦。，瓦) ，对其每一位按变异概率变异，设第f 位变异，则得到新个体瓦如 下所示： 个体五 ，新个体瓦 疋p 珏，瓦，l 正p 正，瓦，互， j 变异点 以上算法称之为算法一。 东南大学硕士研究生学位论文 3 3 2 仿真结果 源信号为一段音乐信号如图3 3 所示。噪声为幅度为0 3 1 的高斯噪声被噪声污染的 信号如图3 4 所示，其信噪比为- 4 8 d b 。 0 0 2 46 v l n 圈3 3 源信号 设噪声通道传输函数为h ( z 1 为： 图3 4 被噪声污染的信号 日( z ) = 雨丽万1 - 而0 9 z 而- i + 西0 8 可z - 2 蕊- 0 西7 2 z 可- 3 瓜歹 ( 3 3 3 )、4 l + o 4 8 z 叫+ 0 6 0 7 5 z 叫+ 0 3 6 3 z q + o 1 4 z _ 4 遗传参数取为：样本采样长度取为2 0 0 ，群体个数取为2 0 ，算法运行3 0 0 代，交叉概率 为0 8 ，变异概率为0 1 。乙= k nk _ l ，k l ，c ，c ，c l ，) 的每个参数都用i 0 位二 进制子串表示， 取滤波器的阶数为4 阶，得仿真结果如图3 5 所示。取最后4 0 代的系统输出信号，得 其信噪比为2 1 d b 。仿真结果表明基本算法的搜索效果比较差，因此需要对基本算法加以改 造以得到所需要的搜索效果。 溃传代数 图3 5 算法运行结果 第2 2 页 东南大学硕士研究生学位论文 3 4 自适应遗传算法 遗传算法的搜索性能与其遗传参数的设置有着很大的关系。交叉概率以控制着交叉操 作被使用的频度。较大的交叉概率可以增强遗传算法开辟新的搜索区域的能力但高性能的模 式遭到破坏的可能性也随之增大；若交叉概率太低，遗传算法搜索可能陷入停滞状态。一般 取以为0 2 5 到1 之间。变异操作是遗传算法的主要操作之一，它对维持群体的多样性起着 重要的作用。选择较大的变异概率就会成为随机搜索，选择较小变异概率又不容易逃脱局部 极值点 3 5 。因此设计自适应的变异操作非常重要。 文献 3 8 提出了一种基于种群熵估计的参数自适应遗传算法。该算法每一进化代的新种 群由保留、繁殖和随机3 部分子种群组成，其数量则由相应的参数进行控制。通过引入种群 熵的概念对种群内个体的多样性进行度量并使用一种简单的方法对其进行估计以确定各控 制参数，该算法实现了参数的自适应调节，从而获得运行过程中对接索空间勘探和开采的平 衡。 文献 5 0 提出了一种基于排序操作的进化算子自适应的遗传算法，该算法中，每个个体 按适应值大小进行排序，个体的选择、交叉、变异算子的概率根据个体排序值来自适应地确 定，其中选择概率还随进化过程而调节。这样通过自适应调节选择率以及保留当前最优解和 加快较差解的进化速度来获得较快的全局收敛性。 一般在变异操作中是以一定概率随机改变编码串中的每一位，文献 4 0 1 考虑到不同编 码位的改变造成个体适应度的改变程度不同，也即各个编码位的重要性不是等同的。例如： 对于个体x ： 1 1 0 0 1 1 0 0 1 ，其经过变异可能生成这样的两个个体 1 1 0 0 1 1 0 0 0 ) 和 0 1 0 0 1 1 0 0 1 ) 。假设适应度函数是连续的，且把编码对应的十进制值作为自变量取值。由于 变异