（热能工程专业论文）基于遗传编程的协调控制系统建模和设计.pdf

华北电力大学博士论文摘要 摘要 单元机组协调控制系统，是火电厂自动化系统中最为核心的组成部分，其 控制品质决定着单元机组的安全性和经济性。本文分别从线性和非线性角度， 探讨了单元机组协调控制对象智能建模和智能设计这两方面问题，本文的主要 工作涵盖4 点。 1 分别采用遗传算法和遗传编程方法，建立典型工况下单元机组协调控制 对象的线性模型。第一种方法，由机理分析得出协调控制对象的模型结构，再 根据对象的输入输出数据，采用遗传算法辨识出模型的相关参数。第二种方法， 协调控制对象的模型结构和模型参数都未知，只根据对象的输入输出数据，采 用遗传编程辨识出模型的结构和参数。 2 基于模糊多模型控制的单元机组协调控制系统设计。在典型工况下，采 用遗传算法辨识出协调控制对象的静态解耦网络，再分别设计压力回路和功率 回路的控制器。根据模糊多模型控制器设计原理，用典型工况下的解耦控制器， 构造出可以适应工况大范围变化的协调控制系统模糊多模型控制器。 3 建立单元机组协调控制对象的非线性模型。采用n a r m a x 模型描述协 调控制对象的非线性动态特性，用遗传编程方法辨识n a r m a x 模型的结构和 参数。针对常规遗传编程方法建立n a r m a x 时表现出的不足，提出了一种新 的建立n a r m a x 模型的智能方法一基于遗传编程与粒子群优化的混合智能方 法。采用了3 种方法建立单元机组协调控制系统的n a r m a x 模型： 常规遗传编程； 多目标遗传编程； 遗传编程与粒子群优化。 4 基于动态解耦的单元机组协调控制系统设计。基于遗传编程与粒子群优 化方法建立单元机组协调控制系统的动态解耦网络。实现协调控制对象的动态 解耦后，再分别设计压力回路和功率回路的控制器，最后得到单元机组协调系 统的动态解耦控制系统。 关键词：单元机组协调控制系统，n a r m a x 模型，遗传算法，多目标遗传编 程，粒子群优化 华北电力大学博士论文摘要 a b s t r a c t t h ec o o r d i n a t ec o n t r o ls y s t e mi st h em o s ti m p o r t a n tp a r to fp o w e rg e n e r a t i o nu n i t ， a n di t sc o n t r o lq u a l i t yw i l li m p a c tt h es e c u r i t ya n de c o n o m i e so ft h eu n i t f r o mt h e p e r s p e c t i v e so fl i n e a rc o n t r o la n dn o n l i n e a rc o n t r o l ，t h i sd i s s e r t a t i o ns t u d i e sh o w t o m o d e l i n ga n dh o wt os y n t h e s i z et h e c o o r d i n a t ec o n t r o ls y s t e mu s i n gs o m e i n t e l l i g e n tm e t h o d t h em a i nw o r ko ft h i st h e s i sc o v e r s4p o i n t sa sf e l l o w s ： 1 i nt h et y p i c a lw o r k i n gc o n d i t i o n s ，h o wt om o d e l i n gt h el i n e a rm o d e lo ft h e c o o r d i n a t ec o n t r o ls y s t e mu s i n gt h eg e n e t i ca l g o r i t h ma n dt h eg e n e t i cp r o g r a m m i n g ? t h ea n s w e ro ft h eq u e s t i o nh a st w oa s p e c t s o n ei st og a i nt h em o d e lf r a m e w o r kb y t h e o r e t i c a la n a l y s i sa n dt h e nt or e c o g n i z et h em o d e lp a r a m e t e ru s i n gt h eg e n e t i c a l g o r i t h m t h eo t h e ri st og a i nt h em o d e lf r a m e w o r ka n dm o d e lp a r a m e t e ra t t h e s a m et i m eu s i n gt h eg e n e t i cp r o g r a m m i n g 2 t os y n t h e s i z et h ec o o r d i n a t ec o n t r o ls y s t e mb a s e do nt h ef u z z ym u l t i p l e m o d e lt h e o r y i nt h et y p i c a lw o r k i n gc o n d i t i o n s ，t h es t a t i cd e c o u p l i n gc o n t r o l l e r s o ft h ec o o r d i n a t ec o n t r o ls y s t e mc a nb es c h e m e do u tb yu s i n gt h eg e n e t i ca l g o r i t h m b a s e do nt h ef u z z ym u l t i p l em o d e lt h e o r y ，af u z z ym u l t i p l em o d e lc o n t r o l l e ro ft h e c o o r d i n a t ec o n t r o ls y s t e m ，w h i c hc o n t r o le f f e c t u a l n e s si sr o b u s tw h e nt h ew o r k i n g c o n d i t i o n sv a r yi nal a r g es c a l e ，c a nb ew o r ko u tt h r o u g ht h es t a t i cd e c o u p l i n g c o n t r o l l e r sm e n t i o n e da b o v e 3 t om o d e l i n gt h en o n l i n e a rm o d e lf o rt h ec o o r d i n a t ec o n t r o ls y s t e m t h e n a r m a xm o d e li se l i g i b l ef o rt h ec o o r d i n a t ec o n t r o ls y s t e m ，a n dt h eg e n e t i c p r o g r a m m i n g i s ag o o dc h o i c et o m o d e l i n g i t a st h et r a d i t i o n a l g e n e t i c p r o g r a m m i n gs h o ws o m es h o r t a g ew h e nu s e dt om o d e l i n gt h en a r m a xm o d e l ，a n o v e lm o d e l i n gm e t h o di sp u tf o r w a r db a s e do nt h eg e n e t i cp r o g r a m m i n ga n dt h e p a r t i c l es w a r mo p t i m i z a t i o n t h e r ea r et h r e ed i f f e r e n tm e t h o d su s e dt om o d e l i n gt h e n a r m a xm o d e l ： t h et r a d i t i o n a lg e n e t i cp r o g r a m m i n g ： t h em u l t i o b j e c t i v eg e n e t i cp r o g r a m m i n g ； t h ec o m m i x e di n t e l l i g e n tm e t h o db a s e do ng e n e t i cp r o g r a m m i n ga n d 华北电力大学博士论文摘要 p a r t i c l es w a r mo p t i m i z a t i o n 4 t os y n t h e s i z et h ec o o r d i n a t ec o n t r o ls y s t e mb a s e do nd y n a m i cd e c o u p l e a d y n a m i cd e c o u p l ec o n t r o l l e ri ss c h e m e do u tb a s e do nt h eg e n e t i cp r o g r a m m i n ga n d p a r t i c l es w a r mo p t i m i z a t i o n a f t e rd y n a m i cd e c o u p l i n g ，t h ec o o r d i n a t e c o n t r o l s y s t e mi ss y n t h e s i z e db yd e s i g n i n gt h ep i dc o n t r o l l e ro ft h ep r e s s u r el o o pa n dt h e p o w e rl o o p k e yw o r d s ：t h ec o o r d i n a t ec o n t r o ls y s t e mo fp o w e rg e n e r a t i o nu n i t ，n a r m a x m o d e l ，g e n e t i ca l g o r i t h m ，m u l t i o b je c t i v eg e n e t i cp r o g r a m m i n g ，p a r t i c l es w a r m o p t i m i z a t i o n 声明尸明 本人郑重声明：此处所提交的博士学位论文基于遗传编程的协调控制系 统建模和设计，是本人在华北电力大学攻读博士学位期间，在导师指导下，独 立进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外，本学 位论文的研究成果不包含任何他人享有著作权的内容。对本论文所涉及的研究工 作做出贡献的其他个人和集体，均已在文中以明确方式标明。 期：2 谬! 丝 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有 权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩 印或其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅； 学校可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同 方式在不同媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：必竺 e l期： 2 1 1 壁：垒丛 导师签名：气乏! 丛白 日 期：2 础。出次 华北电力大学博士学位论文 第一章绪论 随着我国现代化建设步伐加快，用电量需求逐年增加，用电负荷峰谷差逐 渐加大，电网中的大容量单元机组也频繁地加入调峰和调频的工作中，这就必 须把单元机组的锅炉和汽轮发电机作为一个整体进行控制。当电网负荷发生变 化时，锅炉和汽轮发电机应密切配合，既要尽快满足电网负荷的需要，又要使 主汽压变化尽可能地小。单元机组协调控制系统( c o o r d i n a t ec o n t r o ls y s t e m ) ， 就是把锅炉和汽轮机发电机作为一个整体进行综合控制的负荷控制系统，它是 单元制机组的控制中枢，是现代火电厂自动化系统中最为核心的组成部分。 1 1 单元机组协调控制系统的组成及特点 单元机组协调控制系统，又称为机炉协调控制系统，结构复杂，由多个子 系统构成，其中包括制粉系统、炉内燃烧传热系统、烟风系统、烟氧量系统、 蒸汽发生系统、过热器及其连接管道、汽轮机的压力流量通道和汽轮发电机系 统i ，历经化学能_ 热能_ 机械能一电能的转换：是单元机组的重要组成部分。 图1 1 给出了单元机组锅炉和汽轮发电机最主要的控制系统部分。还有一系列 相对独立的控制系统，如汽温控制系统、汽包锅炉的给水控制系统以及许多辅 机控制系统【2 j ，这里就不再一一赘述了。 操作员指令中调指令频差指令 单元机组主控系统 汽机指令锅炉指令 i 1 l r 士1 汽轮 燃料风量给水 机控 控制控制控制 制系 系统系统系统 统 进燃 风 给 汽料水 量量 量 量 r、r1r，r 机炉受控对象 图1 1单元机组协调控制系统的主要组成部分 第一章绪论 根据对单元机组的特性分析可知，协调控制系统是多输入多输出的复杂系 统，具有强耦合、非线性、大惯性、参数时变和不确定性等特性【引，具体体现 在6 方面。 1 ) 具有多个控制量和被控制量。 单元机组协调控制系统，具有主汽压p t 和输出功率两个被控制量，其 控制量分别是给煤量b 和主蒸汽阀门开度。即单元机组协调控制系统是两输 入两输出系统。 2 ) 非线性。 当机组负荷大范围变化时，单元机组协调控制系统表现出明显的非线性。 田亮等1 4 娟】通过机理分析建立了国产3 3 0 m w 和5 0 0 m w 发电机组的简化非线性 模型，从定性的角度，将协调控制对象的非线性分为两个方面：第一，给煤量 曰与主汽压p t 之间存在非线性函数关系，可用p t = f ( 口l 5 ) 来描述；第二， 主蒸汽阀门开度变化时，主汽压p t 的值与和它本身的乘积有关，即p t = 厂( g x p t ) 。 3 ) 大惯性和大迟延。 由火电机组生产流程知，给煤量的变化要经过给煤机、磨煤机、锅炉受热 面等环节，才能产生主汽压和输出功率的变化。而煤粉磨制和过热蒸汽制备过 程具有非常大的惯性和迟延，这就造成了单元机组协调控制对象的大惯性和大 迟延特性。经测量，给煤量到主汽压回路的纯滞后时间约为2 4 分钟，惯性时 间约为5 7 分钟。 4 ) 时变性。 单元机组协调控制对象由于煤粉磨制过程和过热蒸汽制备过程而存在大 惯性和大迟延，且惯性和迟延特性会随着煤质变化、磨煤机的磨损情况和锅炉 受热面的结焦情况而出现时变性变化。 5 ) 强耦合。 单元机组协调控制对象具有强耦合特性，表现在两个方面：第一，当给 煤量召增加时，主汽压p t 和输出功率都会增大；第二，当主蒸汽阀门开度 开大时，输出功率先增大再回到初始值，而主汽压p t 将降低。由于协调对 象的耦合特性非常强，必须解耦，使给煤量曰变化时输出功率不变和进汽阀 门变化时主汽压p t 不变。 6 ) 对象的不确定性。 由于煤种、煤质偏离设计值，磨煤机、给煤机的不确定性，以及电网负荷 变化的不确定性，造成了单元机组协调控制对象的不确定性。 单元机组协调控制对象具有的上述特性，增加了建立其动态特性的难度， 再加上它在火电厂的重要性，使得协调控制系统建模成为了一项具有挑战性的 2 华北屯力大学l 尊士学位论文 工作，也成为热工控制领域的研究热点。 1 2 单元机组协调控制对象建模的国内外研究动态 国外单元机组协调控制对象建模这项工作开展较早，具有影响的成果有： 1 9 7 1 年m c d o n a l d 得出具有中间再热的单元机组非线性模型1 7 l ；a s t r 6 m 于1 9 7 2 年发表的非线性微分方程表示的数学模型【8 】；c h e r e s 在1 9 9 0 年发表的汽包锅 炉简化非线性模型 9 , 1 0 j ；c h a w d r y 和h o g g 于1 9 8 9 年发表的由1 4 个微分方程、 8 2 个线性或非线性代数方程，包含1 6 个局部流程动态特性的6 输入6 输出锅 炉一汽轮机系统模型1 1 1 j ：以及d em e l l o 于1 9 9 1 年提出的锅炉汽机对象的非线 性模型【1 2 , 1 3 】 在早期模型中，被引用最多的是b e l l a s t r 6 m 模型和d em e l l o 模型。 b e l l a s t r 6 m 模型是由非线性微分方程表示的数学模型，它是基于瑞典 s y d v e n s k ak r a f ta b 电站的1 6 0 m w 的燃油机组建立起来的，最早的模型有6 个 状态变量，于1 9 6 9 年经实验建模得到的。1 9 8 7 年，b e l l 和a s t r 6 m 对该模型进 行了降阶，简化为3 入3 出状态方程【1 4 l ，具体的表达式见式( 1 1 ) 。2 0 0 0 年， b e l l 和a s t r 6 m 进一步总结了1 6 0 m w 、3 3 0 m w 和6 6 0 m w 机组的动态模型i l 副。 鲁= - 0 0 0 1 渤2 p i + o 1 - 0 1 血3 鲁川0 7 锄2 - o 0 1 6 ) p 吾- o 埸 ( 1 - 1 ) d p ，0 4 1 u 3 一( 1 1 u 2 一o 1 9 ) p ) d t8 5 其中，p 是汽包压力( k g c m 2 ) ，p 0 是输出功率( m w ) ，办是流体密度( k g m 3 ) 。系 统的标准化输入分别是u l 燃料流量阀门开度，“2 蒸汽控制阀门开度，u 3 给水流 量阀门开度。 d em e l l o 根据机理分析的方法得出了锅炉汽机对象的非线性模型，d e m e l l o 模型是由线性和非线性模块构成的方框图，见图1 2 。输入量是给煤量b 和主蒸汽阀门开度弘，输出量是输出功率和主汽压研。d em e l l o 数学模型定 义了两个非线性特征：汽包压力pd 和主汽压p t 的压力差与汽包出口蒸汽量 d d 之间存在平方根关系。主蒸汽流量d t 与主蒸汽阀门开度和主汽压p t 的乘 积成比例。 3 第一章绪论 图1 2单元机组d em e l l o 模型结构图 国内关于热工过程动态特性的研究始于上世纪6 0 年代，典型代表作是高 镗年的热工控制对象动力学1 1 6 l 和章臣樾的锅炉动态特性及其数学模型 【1 7 】，它们总结了单元机组动态数学模型方面的研究成果。后者通过机理分析， 得出了由2 7 个常微分方程和7 0 多个代数方程构成的单元机组非线性集总参数 模型，以及线性化集总参数模型。 最近几年对单元机组动态建模的研究热点集中在建立非线性模型和智能 建模方法。华北电力大学曾德良、陈彦桥、田亮等【4 - 6 , 1 8 - 2 0 】以d em e l l o 模型为 基础，通过机理分析，得到一种由传递函数和非线性代数方程联合表示的数学 模型，并将该模型作为协调控制系统设计的基础。中国电力科学院韩忠旭【2 卜2 3 1 对线性化增量模型，增量式状态空间表达式和非线性动态仿真数学模型作了深 入研究，对线性化增量模型与非线性动态仿真数学模型的内在联系作了分析， 还将非线性动态仿真数学模型应用于姚孟发电厂2 号机3 0 0 m w 单元机组的 d c s 。 智能建模方法为单元机组协调控制系统建模研究注入了新的活力。基于模 糊规则【2 4 】和小波神经网络1 2 5 】的建模方法，可以一定程度地反映单元机组协调控 制系统动态的非线性特性，它们不需要繁复的理论推导，只根据输入输出数据 采用相应的智能化方法得出模型的结构和参数，是试验建模方法。但是，至今 没有看到智能方法建模的实际应用。 1 3 选题意义 被控对象的动态特性可以通过机理分析或系统辨识( 又称为试验建模) 来 获得。机理分析是根据基本的物理、化学定律和工艺参数，在一定的假设条件 下，推导出被控对象的数学模型。系统辨识先根据经验或对试验数据的分析确 定模型的结构，然后由试验数据确定其未知参数【2 6 1 。鉴于单元机组协调控制对 4 华北电力人学博士学位论文 象的复杂性，通常采用机理分析和系统辨识相结合的方式来获得其模型，首先 采用机理分析建立协调系统各个局部对象模型的结构，再用这些局部对象模型 建立整体模型的结构，最后通过系统辨识得出整体模型的参数。 对单元机组协调对象建模是一件非常复杂的工作。其复杂性表现在两方 面：第一，单元机组本身是一个复杂的能量转换系统，要建立各部分的详细模 型以及它们之间的广泛联系是十分困难的。第二，单元机组可能经常在变工况 下运行，在负荷峰谷差较大的电网中，还有不少机组需要经常启停。在启停和 变工况的情形下，单元机组的动态特性和非线性特性变化非常大，用常规方法 建立它的模型更加困难。目前的研究成果多集中表现为，采用实验数据或者机 理分析建立某个单元机组的线性模型或简化的非线性模型，然后将非线性模型 在几个典型的工况下线性化。 进化计算的发展为复杂动态系统建模提供了一个有利工具，本文拟采用进 化计算方法遗传算法和遗传编程来建立单元机组协调控制的动态特性。基 于遗传算法和遗传编程的建模方法是一种试验建模方法，它不需要繁复的机理 分析，只需根据动态系统输入和输出数据，随机生成模型群，再利用“适者生 存 原理从中找出与待辨识系统最接近的模型。显然，模型的生成、对模型遗 传操作以及最终模型的选择都是由计算机自动完成的，这是一种智能的建模方 法。 对多变量非线性系统实现解耦控制，有两种不同的思路。第一种，将多变 量非线性系统在典型工况下线性化，得到一组线性模型，采用多变量线性系统 的解耦方法，分别设计每个线性模型的解耦网络。第二种，采用非线性动态解 耦思想，设计多变量非线性系统的解耦网络。 第一种解耦思路，在对象线性模型已知的前提下，可以根据完全解耦原理， 由对象模型计算推导出解耦网络模型。这种解耦方法存在以下几个不足： 按照完全解耦原理推导出的解耦网络，可能是无法实现的； 对于某些对象( 如某些非最小相位系统) ，得出的解耦网络可能是本质 不稳定的； 解耦网络所产生的误差很容易引起系统不稳定； 由于实际系统是时变的和非线性的，在某个典型工况下得出的解耦网 络，不能完全适应系统的时变性和非线性。 第二种解耦思路，采用s i n g h 算法或l a n e 逆系统构造算法等，对多变量非 线性系统解耦。l a n e 逆系统构造算法成立的充分必要条件是f a l b w o l o v i c h 矩 阵非奇异，显然当f a l b w o l o v i c h 矩阵奇异时，l a n e 算法失效。而s i n g h 算法 不需要f a l b w o l o v i c h 矩阵非奇异，通过该算法能够得到解耦控制律，相比l a n e 气 第一章绪论 算法得到静态解耦，在这种控制律下可以得到动态解耦。s i n g h 算法构成采用 状态反馈与动态补偿的解耦控制律，从而将原系统补偿成为标准的积分型解耦 系统。积分型解耦系统又称为伪线性系统，可按照线性系统理论进行设计。 1 4 主要研究内容 本课题的主要研究内容是：如何采用智能方法建立单元机组协调控制对象 的动态模型，以及如何采用智能方法设计单元机组协调控制系统的控制器。分 别从线性和非线性两个角度，探讨了单元机组协调控制系统智能建模和智能设 计这两个问题。本课题的研究内容可以概括为以下4 点。 1 4 1 建立单元机组协调控制对象的线性模型 在典型工况下，单元机组协调控制对象的动态特性是线性的，其数学表达 式可以用传递函数矩阵来表示。本课题用了两种不同的思路，分别采用遗传算 法和遗传编程方法建立传递函数矩阵形式的协调控制对象线性模型。 将机理分析得出的带参数的协调控制对象的传递函数矩阵，作为模型 的结构。根据协调控制对象的输入输出数据，采用遗传算法辨识出模 型的相关参数。 已知协调控制对象的线性模型为传递函数矩阵，但模型的结构和参数 都是未知的。根据协调控制对象的输入输出数据，采用遗传编程辨识 出模型的结构和参数。 遗传编程方法可以同时得到模型的结构和参数，并且结果是显式的，与神 经网络等方法得出的隐式结果相比，遗传编程辨识方法更具工程价值。通过改 进常规遗传编程方法程序树的结构、实现方法和适应度函数，提出了一种新的 基于多目标遗传编程的建立线性模型的方法。 1 4 2 基于模糊多模型控制的单元机组协调控制系统设计 基于模糊多模型控制的单元机组协调控制系统设计分两步： 在典型工况下，采用遗传算法辨识出单元机组协调控制对象的静态解 耦网络，再分别设计压力回路和功率回路的控制器，得出典型工况下 的单元机组协调控制系统。 根据模糊多模型控制器设计原理，用典型工况下的解耦控制器，构造 出可以适应工况大范围变化的协调控制系统模糊多模型控制器。 1 4 3 建立单元机组协调控制对象的非线性动态模型 非线性自回归滑动平均模型( n o n l i n e a ra u t or e g r e s s i v em o v i n ga v e r a g e 6 华北电力大学博士学位论文 w i t he x o g e n o u si n p u t s ，n a r m a x ) 2 7 l 是b i l l i n g s 等提出的，为有限可实现的非 线性系统提供了最为一般的输入输出表达式1 2 引。本文采用n a r m a x 模型描述 单元机组协调控制对象的非线性动态特性，用遗传编程方法辨识n a r m a x 模 型的结构和参数。针对常规遗传编程方法建立n a r m a x 时表现出的不足，提 出了一种新的建立n a r m a x 模型的智能方法一基于遗传编程与粒子群优化的 混合智能方法。采用了3 种方法建立单元机组协调控制系统的n a r m a x 模型： 常规遗传编程： 多目标遗传编程； 遗传编程与粒子群优化。 1 4 4 基于动态解耦的单元机组协调控制系统设计 根据5 4 3 节中提出的基于遗传编程和粒子群优化方法，分别设计了协调 控制系统的主汽压和功率回路的动态解耦网络。经解耦网络补偿后，协调控制 系统等效为两个单回路系统，分别设计它们的控制器，得到协调控制系统的解 耦控制系统。仿真结果表明，所设计的解耦网络，可以实现协调控制系统的动 态解耦。 实现动态解耦后，再分别设计压力回路和功率回路的控制器，最后得到了 单元机组协调系统的非线性动态解耦控制系统。 7 第二章 遗传算法和遗传编程 第二章遗传算法和遗传编程 达尔文提出的自然进化论不仅是生物界的里程碑，也启发了人们应用计 算机模拟生物界的进化规律来解决复杂问题。19 7 5 年，美国芝加哥大学的 j o h n h h o l l a n d 教授模拟达尔文的自然进化论与孟德尔的遗传变异理论， 提出遗传算法( g e n e t i ca l g o r i t h m ) 。遗传算法适用予无表达式或有表达式的 任何类型函数，具有广泛的应用价值。但遗传算法采用字符串描述问题， 在处理复杂问题时不直观1 29 1 。1 9 8 9 年，美国斯坦福大学的k o z a 教授在遗 传算法的基础上提出了遗传编程( g e n e t i cp r o g r a m m i n g ，也译为遗传规划) ， 遗传编程采用树状结构描述对象，比遗传算法直观，因此成为进化计算一 个新的分支1 3 0 j 。 2 1 遗传算法 遗传算法是一种搜索寻优技术，它以字符串的形式描述所研究的问题， 仿效生物的进化与遗传，根据“生存竞争”和“优胜劣汰”的原则，借助复制、 交叉、突变等操作，使所要解决的问题从初始解一步步地逼近最优解，这 就是遗传算法的原理。 遗传算法的实现过程可概括为4 步： 1 ) 随机产生初始种群，即搜索空间； 2 ) 计算每个个体的适应度； 3 ) 根据遗传概率，利用复制、交叉和突变等遗传操作，产生新的种群； 4 ) 重复2 ) 、3 ) ，直到满足终止条件为止。选择最佳的个体作为遗传算 法的优化结果。 遗传算法的流程如图2 1 所示【29 1 。图中g e n 代表遗传迭代的次数，m 表示种群的规模，i 表示已进化的个体数目，当f = m ，说明这一代个体已 经进化完毕。每次交叉操作涉及两个个体，所以流程图中在交叉操作前执 行f = f + 1 。 遗传算法是一种智能的寻优技术，它不需要对所研究的问题进行理论 分析，只需要根据所研究的问题改变它的实现细节。遗传算法有4 个主要 的实现细节，包括：编码、适应度、遗传操作和终止条件，下面讨论遗传 算法的实现细节。 8 华北电力大学博士学位论文 2 1 1 遗传算法的编码 图2 1 遗传算法流程图 常规遗传算法的工作对象是字符串，编码就是用字符串来反映所研究 问题的性质，编码随所研究问题的不同而变化。+ 编码工作有三项内容：一 是确定字符串的结构，二是确定字符串的长度，三是确定字符串与所研究 问题的对应关系。下面通过例子说明编码的实现过程。 假设我们要用遗传算法，寻找一个与常数万最接近的分数，其分子和 分母的取值范围都是f 0 ，1 0 0 】，如何采用二进制字符编码呢? 首先，明确整 个字符串的结构分为两个长度部分，前面部分表示分子，后面部分表示分 母。其次，由于2 7 = 1 2 8 ，落在0 ，1 0 0 1 区间内的数可以用7 位二进制字符 串来表示，分子和分母部分都用7 位字符串表示，整个字符串的长度为7 x 2 9 第二章 遗传算法和遗传编程 = 1 4 。最后，确定二进制数与十进制数之间的对应关系。当用长度为l 的二进制数e 表示取值范围为【d m i n ，d m a x 】的十进制数d 时，d 和e 之间的对 应关系为 拈d 曲+ 南( d m 缸一d m i n ) 则下列编码对应于分数9 2 6 。 0 0 0 11 0 0 ：0 1 0 0 0 0 1 ( 2 1 ) 除了二进制编码外，遗传算法的编码方式还有：浮点数编码和混合编 码。就二进制编码和浮点数编码而言，一般二进制编码较浮点数编码搜索 能力强，但浮点数编码比二进制编码在突变操作上能够保持更好的种群多 样性。有关浮点数编码和混合编码的详细分析见文献f 3 1 】。 2 1 2 适应度 适应度是衡量个体优劣的尺度，是遗传算法的核心，是种群进化的目 标。个体的适应度是由适应度函数计算得到的。常见的适应度有4 种：原 始适应度、标准适应度、调整适应度和归一化适应度f 29 1 。 2 1 2 1 原始适应度 原始适应度是问题适应性自然描述的一种度量。当原始适应度定义为误 差时，个体返回值于实测值之间的距离的总和，就是原始适应度。种群中， 第t 代第f 个个体的原始适应度，( f ，f ) 为 n r ( i ，t ) 一习s g ，j ) 一c ( j ) l z ( 2 2 ) j - 1 其中s ( i ，j ) 是第f 个个体在第次计算中的值，c u ) r e 实测值，是计算的 次数。 因为原始适应度是问题的自然表达，因此以误差表示的原始适应度的 值越小越好。 2 1 2 2 标准适应度 标准适应度是指适应度数值越小适应性越好的适应度，记为s ( i ，f ) 。 那么，以误差表示的原始适应度就是标准适应度， 1 0 华北电力人学博士学位论文 ( 2 - 3 ) 2 1 2 3 调整适应度 调整适应度是根据标准适应度计算得到的，它们之间的对应关系为 n ；鬲1 而 ( 2 4 ) 其中，a ( i ，f ) 为第t 代第f 个个体的调整适应度，s ( i ，f ) 为其标准适应度。通 常s ( f ，f ) 0 ，则a ( i ，t ) e o ，1 】，且调整适应度值越大，个体越优良。 当标准适应度接近于o 时，调整适应度具有扩大标准适应度值微小差 别的作用。这种情况通常出现在进化的最后几代中。随着种群的不断进化， 个体的标准适应度越来越小，它们之间的差别往往很小，这时，调整适应 度的扩张能力就显得特别有效。 2 1 2 4 归一化适应度 归一化适应度n ( i ，f ) 由调整适应度计算得到， ，z ：掣 口( 七，f ) k - 1 ( 2 5 ) 其中，m 为种群中所有个体的总数，也称为种群规模。归一化适应度有3 个理想的特征： 1 ) n ( i ，f ) 【o ，1 】； 2 _ ) 适应度值越大，个体越优良； m 3 ) ，z ，f ) - - - 1 。 k - 1 如果个体选择方法是基于适应性一比例适应度原则，那么归一化适应 度可直接作为个体选择的概率。 2 1 3 遗传操作 遗传算法具有多种遗传操作，例如：复制、交叉、突变、倒序、生态、 显性、多重字符串结构、加倍与删除、性别区分等。其中，复制、交叉和 突变是最常用到的遗传操作，其它遗传操作只是在解决特殊问题时可能会 用到。 2 、- 、 ， ，i 一一 c 一 、- 、g s 习m = 、- 、 f o s 第二章遗传算法和遗传编程 2 1 3 1 复制 复制( r e p r o d u c t i o n ) 是遗传算法的基本操作，它通过选择优良个体，将 它们一成不变地复制到下一代的种群中。适应度好的个体，被复制的几率 大，这也体现了达尔文的适者生存原则。 在遗传算法中，通常采用j o h n h h o l l a n d 教授提出的轮盘赌方式选 择复制的对象。表2 1 描述了这种选择方式，表中第一行说明有1 0 个个体 参与选择，第二行是每个个体的适应度，第三行标记适应度的累计值，总 数为7 6 ，第四行是在【0 ，7 6 】区间内产生的均匀分布的随机数。选择的方法 为，依次将第三行的累计适应度与随机数比较，适应度大于或者等于随机 数的第一个个体被选中。例如，第一个随机数是2 3 ，除了1 号、2 号个体 外，其余个体的累计适应度都大于2 3 ，但是3 号个体是第一个累计适应度 大于2 3 的个体，所以3 号个体被选中1 2 9 1 。 表2 1 遗传算法的轮盘赌选择方式 个体序号1234567891 0 适应度 821 7721 21 1737 累计适应度值 81 0 2 73 43 64 8 5 96 66 97 6 随机数 2 34 97 61312 75 7 被选中的个体号 371 03137 上述选择过程可描述为： 1 ) 计算每个个体的适应度值，进而得相应的累计适应度值a f ，最后一 个个体的累计适应度值为彳甩； 2 ) 在【0 ，a 厅】区间内产生均匀分步的随机数r ； 3 ) 依次将a f 与尺比较，第一个满足a f - r 的个体i 被选择为复制对象； 4 ) 重复2 ) 、3 ) ，直到满足所需要的复制个体数目。 每代群体中，被复制的个体数目由复制概率p ，控制，通常p ，取值 1 0 - 2 0 。 除了轮盘赌选择方法外，常用的选择方法还有3 种，分别是随机遍历 抽样法、锦标赛选择法和局部选择法【3 。 随机遍历抽样法提供了零偏差和最小个体扩展。设定为需要选择的个 体数目n ，等距离选择个体，选择指针的距离为1 n ，第一个指针的位置由 【0 ，1 n 】区间的均匀随机数决定。 1 2 华北电力大学博士学位论文 锦标赛选择法，随机地从种群中挑选一定数目刀个体，然后将最好的 个体复制。重复这个过程，直到满足复制的个体数目为止。锦标赛选择的 参数为竞赛规模以，其取值范围为【2 ，m 】，其中m 为种群规模。 在局部选择法中，每个个体处于一个约束环境中，称为局部邻集，个 体仅与其邻近个体交叉，该邻集的定义由种群的分步结构给出。选择个体 通常是根据个体选择概率，常用的个体选择概率有两种，分别为基于排序 的适应度分配、按比例的适应度分配。 1 ) 基于排序的适应度分配中，种群按目标值进行排序。适应度仅仅取 决于个体在种群中的序位，而不是它的实际大小。 2 ) 按比例的适应度分配，个体的选择概率等于它的归一化适应度。 2 1 3 2 交叉 交叉操作( c r o s s o v e r ) 是遗传算法中产生新个体的主要手段，它仿照生 物学中有性繁殖的原理，将两个个体( 染色体) 的部分字符( 基因) 相互 交换。交叉操作分为3 步：第一步，选择两个个体，作为交叉操作的父代； 第二步，选择父代的交叉点；第三步，执行交换，得到两个新的子代。 执行交叉操作的个体是随机选择的。首先，要确定交叉的概率p 。，一 般p 。取值5 0 8 0 。然后，选择被交换的个体，依次两两进行交叉操作。 交叉点的选择也是随机的。假设字符串长度为l ，则在【2 ，l 1 】区间内 产生随机整数，该整数便是交叉点。注意，交叉点不能选在字符串的第1 位和最后一位，因为交叉点分别位于这两个位置的交叉结果，仍是交叉前 的两个字符串。因此，长度为二的字符串，可供选择的交叉点有仁2 ) 个。 根据交叉点的数目不同，交叉操作可以分为单点交叉、两点交叉和多 点交叉。单点交叉只选取一个交叉点，该点之后的字符参加交叉。两点交 叉，就是选取两个交叉点，在两个交叉点之间的字符参加交叉。当字符串 长度较大时，常采用两点交叉。长字符串一般采用多点交叉，交叉点是无 重复随机选择，在交叉点之间的字符间续地相互交换。以上三种交叉的例 子见表2 2 ，其中带边框的字符为交叉点，带底纹的字符为交叉部分。 通过交叉操作，子代的字符串不同于父代。正是有了交叉操作，遗传 算法的种群才具有多样性。传统的优化算法，例如动态规划法，不能添加 个体性态，只能在原有的个体种群中择优，从而限制了搜索寻优的范围。 2 1 3 3 突变 突变( m u t a t i o n ) 操作是遗传算法产生新个体的另一种操作，它通过对突 变位的字符进行补运算，得到新个体。突变操作分为3 步：第步，选择 1 3 第二章 遗传算法和遗传编程 一个个体，作为突变操作的父代；第二步，选择父代的突变点；第三步， 执行补运算，得到一个新的子代。 突变个体是通过随机选择确定的。突变点也是随机产生的。参加突变 的个体总数，是由突变概率p 用确定的。通常p 朋较小，约为0 1 1 0 。 虽然突变和交叉操作都能产生新的个体，但是在遗传算法中，交叉的 作用远比突变重要。 表2 2 交叉操作 交叉前交叉后 父代1 ：1 0 0 1 巨 1 1 0 1 子代1 ： 1 0 0 1 囡1 1 0 1 单点交叉 父代2 ：0 1 0 0 i 1 1 0 1子代2 ：0 1 0 0 囫1 1 0 1 父代1 ：1 0 巨 1 0 i 1 0 1 子代1 ： 1 0 团1 囡1 0 1 两点交叉 父代2 ：0 1 酌1 囡1 0 1子代2 ：0 1 回1 0 1 i 1 0 1 父代1 ：1 团1 回l 郾1 子代1 ： 1 团。囫1 囡0 1 多点交叉 父代2 ： o 囡0 0 囡1 囡0 1 子代2 ： o 固0 1 团1 团0 1 2 1 4 终止条件 遗传算法是一种反复迭代的搜索方法，它通过多次进化逐渐逼近最优 解而不是恰好等于晟优解，因此需要确定终止条件。常用的终止条件有3 种。 a ) 遗传迭代次数。当遗传迭代次数等于事先规定的最大的迭代次数， 遗传迭代终止。 b _ ) 适应度值。当某个个体的适应度与理想的适应度之差，小于允许值， 则遗传迭代终止。 c ) 适应度值的变化情况。当适应度值没有变化或者变化很小时，遗传 迭代终止。 实际应用中，遗传算法的终止条件可以是以上3 种条件中的一个或者 多个条件。 1 4 华北电力大学博士学位论文 2 2 遗传编程 从前面的讨论可以看出，遗传算法对字符串进行操作，可以解决一系 列的复杂问题，许多研究人员在此基础上提出的理论和方法，极大地丰富 了遗传算法的内容。但是，正是由于遗传算法直接对字符串进行操作，它 表现出3 个缺点【2 9 】： 1 ) 不能描述层次化的问题； 2 1 不能描述计算机程序； 3 1 缺少动态可变性。 k o z a 教授在遗传算法的基础上提出了遗传编程( g e n e t i cp r o g r a m m i n g ) ， 遗传编程采用树状结构描述对象，比遗传算法直观，因此成为进化计算新 的一个分支。 遗传编程即是编写计算机程序模拟自然选择过程，从而实现让计算机 自动解决问题但不需要告诉它怎样解决问题。遗传编程的基本工作原理是： 随机产生一个适用于给定问题的初始种群，即搜索空间，种群中的每个个 体为树状结构( 又称为s 表达式，或程序树) ；计算每个个体的适应度值； 依据达尔文的进化原则，选择遗传操作( 复制、交叉、变异等) 对种群不 断进行迭代优化，直到在某一代上找到最优解或近似最优解【3 2 1 。 遗传编程出现只有短短的十几年，但它已经成功地应用于系统辨识 f 3 引、故障诊断【34 1 、分类【35 1 、预测1 3 6 1 ，优化1 37 1 ，图像和信号处理【38 1 。 遗传编程的实现流程与遗传算法大致相同。应用遗传编程解决问题分 为六步。第一步是确定以下内容： 函数集，； 终止符集z ； 适应度函数 控制运行的参数及变量，包括种群规模m 、迭代次数g 、复制概率 p ，、交叉概率p 。和突变概率p m 等； 表示结果的方法和终止运行准则。 其中，包括运算符( 算术、布尔运算符等) 、函数( s i n 、t a n 等) 、 以及一些表达式( 循环表达式与条件表达式等) 。而典型的终止符是变量和 常量，