（航空宇航推进理论与工程专业论文）遗传算法在航空发动机故障诊断中的应用.pdf

中国民航大学硕士学位论文 摘要 故障诊断是指系统在一定工作环境下，查明导致系统某种功能失调的原因或性质， 判断劣化状态发生的部位或部件，以及预测状态劣化的发展趋势等。航空发动机故障诊 断一般可分为机械故障与气路故障。与机械故障相比，气路故障的诊断难度较大且难以 深入研究。本文主要应用遗传算法对基于概率因果网络的气路故障模型进行诊断。主要 工作如下： ( 1 ) 论文综述了航空发动机故障诊断的发展现状，并对几种现有的航空发动机故 障诊断方法进行概述。 ( 2 ) 为了达到对故障模式进行全面并行搜索的目的，本文采用遗传算法作为解决 故障诊断问题的方法。论文介绍了遗传算法的基本理论和特点，以及与其它搜索方法相 比较所体现出来的优势。为了简单便捷地使用遗传算法，论文还对m a t l a b 中的遗传 算法工具箱的特点和使用方法进行了介绍。 ( 3 ) 本文所应用的是基于概率因果网络的故障诊断模型，论文对该模型进行了理 论知识的介绍，并且提出将故障方程诊断方法中的故障系数与该模型相结合，并且给出 了一定的解释。 ( 4 ) 在应用遗传算法对各个故障模式进行搜索的基础上，论文对所有故障模式进 行简化分类，减少了故障模式的数量，提高算法的搜索速度，取得了较好的效果。最后， 论文对这种应用遗传算法的故障诊断方法进行总结，并且提出展望。 基于遗传算法的航空发动机气路故障诊断方法在国内外还不是很完善，此方法对于 遗传算法在航空发动机故障诊断中的应用也是一个有益的补充。 关键词：航空发动机；遗传算法；故障诊断；概率因果模型 中国民航大学硕士学位论文 a bs t r a c t f a u l td i a g n o s i sm e a n st of i n do u tt h er e a s o no rc h a r a c t e rc a u s i n gt h em a l a d j u s t m e n to f t h es y s t e m ，t oj u d g et h ep a r ta n dc o m p o n e n tw i t hl o wq u a l i t y , a n dt oe s t i m a t et h et r e n do ft h e l o wq u a l i t ys t a t ei ns o m ee n v i r o n m e n t a e r o e n g i n ef a u l td i a g n o s i si sd i v i d e di n t om e c h a n i s m f a u l ta n dg a sp a t hf a u l t c o m p a r e dw i t hm e c h a n i s mf a u l td i a g n o s i s ，g a sp a t hf a u l ti sm o r e d i f f i c u l tt os h o o ta n dr e s e a r c hd e e p l y t h eg a sp a t hf a u l tm o d e lb a s e d0 np r o b a b i l i t yc a s u a l n e ti s d i a g n o s t i c a t e di ng e n e t i ca l g o r i t h mi nt h i st h e s i s t h em a i nr e s e a r c ht a s k sa r e s u m m a r i z e da sf o l l o w s ： ( 1 ) 1 1 1 es t a t e - o f - t h e 眦o ft h ea i r c r a f te n g i n ef a u l td i a g n o s i si ss u m m a r i z e d ，a n dt h e e x i s t i n ga i r c r a f te n g i n ef a u l td i a g n o s i sm e t h o d sa r ei l l u s t r a t e di nt h i st h e s i s ( 2 ) i nt h ep u r p o s eo fs e a r c h i n ga l lt h ef a u l tm o d e sc o l l a t e r a l l y , g e n e t i ca l g o r i t h mi s c h o s e nt os o l v et h ef a u l td i a g n o s i sp r o b l e m t h eb a s i ct h e o r y , c h a r a c t e r i s t i ca n dt h e s u p e r i o r i t i e so f t h eg e n e t i ca l g o r i t h mc o m p a r e dw i t ho t h e rs e a r c h i n gm e t h o d sa r es u m m a r i z e d i nt h et h e s i s 1 1 1 eu s a g ea n dc h a r a c t e r i s t i co fg e n e t i ca l g o r i t h mt o o lb o xi nm a t l a bi s i l l u s t r a t e df o ru s i n gt h eg e n e t i ca l g o r i t h me x p e d i e n t l y ( 3 ) t h ef a u l td i a g n o s i sb a s e do np r o b a b i l i 锣c a u s a lm o d e li sa p p l i e di nt h i st h e s i s ，t h e t h e o r yo ft h em o d e li si l l u s t r a t e d ，a n dt h ef a u l tc o e f f i c i e n ti nf a u l te q u a t i o nm e t h o di s i n t e g r a t e d 、加t ht h em o d e l t h es u f f i c i e n te x p l a n a t i o ni sg i v e ni nt h et h e s i s ( 4 ) 舢lt h ef a u l tm o d e sa r ec l a s s i f i e db a s e do nt h eg e n e t i ca l g o r i t h ms e a r c h i n gt or e d u c e t h ef a u l tn u m b e ra n ds p e e d u pt h ec o m p u t e ，a n dt h er e s u l ti ss h o w nt ob es u c c e s s f u l a tl a s t ， t h ea p p l i c a t i o no fg e n e t i ca l g o r i t h mt oa e r o e n g i n ef a u l td i a g n o s i si ss u m m a r i z e da n dt h e e x p e c t a t i o ni sb r o u g h tf o r w a r d t h eg a sd i a g n o s t i ca p p r o a c hb a s e d o ng e n e t i ca l g o r i t h mi sn o tc o n s u m m a t e ds of a r t h i s m e t h o db e c o m e sah e l p f u lc o m p l e m e n t a r i t yo ft h em a i n t a i n i n gt h e o r i e so fa i r c r a f tt u r b i n e e n g i n ei ng e n e t i ca l g o r i t h mm e t h o d k e yw o r d s ：a e r o e n g i n e ；g e n e t i ca l g o r i t h m ；f a u l td i a g n o s i s ；p r o b a b i l i t yc a s u a lm o d e l 中国民航大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特，l u l j n 以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得中国民航大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 中国民航大学学位论文使用授权声明 中国民航大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件 和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内 容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全 部或部分内容。论文的公布( 包括刊登) 授权中国民航大学研究生部办理。 研究生签名：导师签名：t 薹毽日 中国民航大学硕士学位论文 1 1 课题的意义 第一章绪论 从2 0 世纪6 0 年代开始，随着喷气式客机复杂程度和制造成本的提高以及航空运输 业的迅速发展，飞行延误和航班取消方面的经济影响以及投入维修的人力和材料开支的 增加等问题日趋严重，从而对发动机的研制和使用提出了许多新的研究课题，其中一个 重要课题就是发动机状态监控与故障诊断。所谓发动机状态监控与故障诊断，就是指借 助于一定的有效方式对与发动机各部件工作状态紧密相关的各种参数实施监测，根据所 检测的数据对各部件的工作状态及其发展趋势做出有价值的判断，即对所发生的故障做 出诊断结论，或预报即将发生的故障，及时提出维修的具体技术内容，以达到保证飞行 安全，提高维修经济效益的目的。发动机状态监控与故障诊断的意义在于：一方面，它 可以迅速而准确地确定故障的部位及故障严重程度，有利于确保飞行安全以及减少投入 维修的人力物力，缩短飞行器的停飞时间，提高飞行器的利用率；另一方面，它又是实 现先进的维修思想( 从经验型的“以预防为主的维修思想转向“以可靠性为中心 的 维修思想) 和维修方式( 从单纯的定时方式转向定时维修，视情维修和状态监控三种方 式) 的必要手段与前提条件。【l j 1 2 课题来源 现代民用航空发动机的状态监控，主要指的是对发动机整机性能( 包括气动热力性 能和机械性能) 的监控。对发动机性能变化的监控，包括参数( 气路参数和机械参数) 检测和性能监控两个方面，通过对发动机主要参数如：转子转速、发动机排气温度、燃 油流量和主要站位性能参数等的监视，来反映发动机性能衰退情况、发动机有无故障及 部件有无损伤。除了上述性能变化监视外，同时也要监视发动机的机械参数，包括发动 机滑油监控和对发动机转子振动的监控。 基于气路参数趋势变化的参数趋势分析是发动机健康监控的中心内容，气路参数在 故障诊断状态下与正常值的偏差量与发动机的故障具有对应关系，由此可以实现单元体 部件的故障定位，实现对单元体性能衰退和突发故障的监控。 中国民航大学硕士学位论文 表1 1 部分国外发动机诊断系统 系统名称诊断水平 适用机型 e c m i i 发动机 j t 9 dj t 8 d a d e p t 发动机 c f 6 5 0c f 6 8 0c f m 5 6 s a g e 发动机 c f 6 5 0c f 6 8 0c f m 5 6 t e a m i i i 单元体 p w 4 0 0 0 i e c m s 单元体 t f 4 1 t e m s 单元体 t f 3 4 e d s 单元体 f 1 0 0 c o m p a s s 单元体 v 2 5 0 0 等 趋势分析是发动机健康监视体系的核心，发动机生产厂商都研制了与发动机和飞机 型号相应的监控分析系统作为配套系统提供给航空公司，如p & w 的e c m i i 、t e a m i i i 和e h m ：g e 的a d e p t 、s a g e ；r - r 的c o m p a s s 等。这些系统以及相关的数据处 理系统在发动机的使用和维护中起着至关重要的作用。 气路诊断面临的主要困难是：1 ) 在大多数机型上依然是测量参数个数少于未知参 数个数；2 ) 故障之间存在很强的相关性，区分相似故障很困难；3 ) 测量参数中的噪音 与故障造成的测量参数偏差具有相同的级别，且测量信号存在偏置；4 ) 发动机工作时 很强的非线性及复杂性，且工况及工作环境变化大。【2 】 世界三大发动机厂家的代表产品靠他们各自研制出的相应工程应用软件( 即 e c m i i 、c o m p a s s 、和s a g e ) ，对自己公司的飞机发动机进行状态监控，这三者功能 相似。它们主要对反映发动机总体性能的主要参数进行监控，能够给出发动机性能趋势 报告，发动机性能压缩历史报告、发动机性能排队报告、发动机起飞e g t 裕度报告等。 此外也对发动机振动情况及滑油系统机型基本监控。而且还可以对发动机的诸多参数设 定预警值。 这项技术要求从飞机数据记录器的译码信息或e i c a s ( 发动机指示和机组警告系 统) 提供的信息中提取发动机的有关动热力参数，如发动机进气温度、压力、发动机排 气温度、压力、发动机压力比、转速、燃油流量、滑油温度、滑油压力、滑油量、发动 机引起状态和可调静子叶片位置等。另外，对数据进行处理时，还需要一些与飞行有关 的参数，如大气温度、大气压力、飞行高度、飞行速度、飞行状态等。然后把这些参数 转换成标准大气状态下的数值，与发动机厂家所给定的该型号发动机的标准性能参数进 行比较，考察偏差的变化情况。通过对偏差大小及变化趋势的分析，判断发动机性能衰 退情况以及有无故障，或哪些故障引起的偏差，使用户能及时找出故障原因，以便合理 计划发动机换发，更好地利用维护车间的能力，避免不必要的拆装，提高工作效率，缩 短维修时间，降低维修成本。 状态监控与故障诊断是两种密切相关，然而有区别的技术，现代民航飞机机载的发 动机监控系统基本上具备了发动机状态监控的功能，但尚不具备发动机故障诊断功能。 故障诊断要求能更进一步确定故障的部位( 故障隔离) 、故障的严重程度( 故障辨识) 。 2 中国民航大学硕士学位论文 然而在工程实践中，这些工作都是由工程师将监控软件提供的状态趋势图与发动机厂商 提供的故障指印图进行对照，再凭借经验人工地完成的。因此，开发出先进的发动机故 障诊断技术能极大地提高故障诊断的正确性，从而减少维修差错；减少部件的误换率， 从而减少部件的修理费用和所需备件的数量；减少发动机维修、排故停场时间，进而提 高飞机的利用率。 1 3 发动机故障诊断现状 1 3 1 小偏差故障方程法 小偏差故障方程中的影响系数矩阵通常由发动机数学模型来建立，也可由典型故障 模式建立经验故障方程，利用后者还可减少对模型的依赖，增加诊断鲁棒性。目前，多 数诊断系统采用故障方程法。d o l e 于1 9 9 3 年开发出的t e m p e r 程序【3 j 是在发动机大修 试车时使用，它可确定哪个部件性能下降造成发动机e g t 裕度不足。d o l e 采用了加权 最d x - 乘法，这种方法只有在试车台精确标定情况小，才会有较好的效果，但是诊断结 果中存在着故障扩散化的现象( f a u l ts m e a r i n g ) 【4 j ，即故障本身只有一个部件造成，但 诊断结果却将其归为多个部件造成。p & w 的m a p n e t 也存在类似的问题。早期气路诊 断研究中采用的求影响系数矩阵广义逆的方法【3 】，也发现同样的问题，这是由于测量参 数少，故障种类多造成的。 航空发动机是一个成熟的产品，一般不会在同一时间内出现多种故障，基于此文献 1 中提出了故障主因子的概念。该文是针对商用在役发动机，它只有4 个测量参数， 文中的故障影响系数矩阵来自发动机制造商提供的各种典型故障的指印图。由于引入了 故障主因子概念，在解方程时使故障因子数小于4 ，这样可以有很多组解，然后文中提 出故障相关性准则，其中有衡量线性模型线性显著性的子集显著性准则s s c ( s u b s e t s i g n i f i c a n tc r i t e r i a ) 、衡量变量显著性的变量显著性准则v s c ( v a r i a b l es i g n i f i c a n tc r i t e r i a ) 以及物理准则等，将这些准则用来评价线性拟合的优劣，拟合得最好的即为方程的解。 它本质上是选择最优变量子集进行线性回归的问题。该文中提出的最优变量子集准则对 于影响系数矩阵中存在多重共线性问题也具有很好的区分能力。 1 3 2 基于人工智能的方法 人工智能在故障诊断领域有着广泛的应用，它包括：基于人工神经网络、支持向量 机和基于数据融合等方法【5 1 。 人工神经网络简称为a n n ( a r t i f i c i a ln e u r a ln e t w o r k s ) 人工神经网络模型是在现 代神经生理学和心理学的研究基础上，模仿人的大脑神经元结果特性而建立的一种非线 性动力学网络系统。它是理论化的人脑神经网络的数学模型，由大量的人工神经单元广 3 中国民航大学硕士学位论文 泛连接而成，尽管它不是人脑神经系统的逼真复制，但确实反映了人脑功能的若干特性， 它可以完成学习、记忆、识别和推理等功能。 在故障诊断领域中用得最多也最有成效的是前向多层神经网络，由于该网络在学习 过程中采用了b p ( b a c k p r o p a g a t i o n ) 算法。故有时该网络又称为b p 网络。标准的b p 网络由三层神经元组成，其结构如图卜1 所示。 一l 工2 图卜1b p 网络结构 将神经网络用于故障诊断，首先对神经网络进行训练，只有达到训练要求的网络才 能得出正确的诊断结果，通常按照如图1 - 2 所示的流程进行。 图卜2 神经网络诊断流程 此外，还有r b f 网、概率神经网络、自组织特征映射网( s o f m ) 和自联想网络等。 网络学习方式分为有导师监督型和无导师监督型。 对单故障分类通常采用b p 网、r b f 网和概率神经网络，定量诊断可用故障模式的“大 小来衡量。b p 网是靠整个网络“记住”了故障模式，r b f 网络是靠隐层核函数中心“记 住典型故障，概率神经网络则是由已知模式样本估计出类条件概率密度，然后得到 b a y e s 意义下的最优分类且其网络训练无需迭代。仿真研究发现，这三种网络对单故障 分类诊断效果令人满意。这几种网络模型都属监督型学习网络。 自组织特征映射网属无监督学习网络，它对模型依赖程度低。s o f m 网优点是对未知 故障能够自动聚类，其本质是利用样本的距离来聚类。在对s o f m 的研究中，我们发现 它对模式噪音有很强的鲁棒性。美国空军研究实验室于2 0 世纪9 0 年代中研制的实时发 动机诊断样机系统是先采用s o f m 网进行初始诊断，确认为已知故障后再用b p 网诊断， 通过对s o f m 网的研究发现它对测量噪音具有很强的鲁棒性。 4 中国民航大学硕士学位论文 1 3 3 基于支持向量机的诊断方法 在气路诊断中，神经网络方法具有较好的应用前景。但是，不足之处在于其泛化性 差。为使神经网络有好的泛化性，网络结构的选取及训练精度的控制都有一定经验性， 而支持向量机方法则具有理论上可保证的最佳泛化性。支持向量机方法在活塞发动机爆 燃( e n g i n ek n o c k ) 和喷气发动机振动故障检测中已有应用，该方法同样可用于气路故障 检测。支持向量机作为一种新方法，其诊断的有效性及该方法的可行性都值得深入研究。 支持向量机方法是统计学习理论的具体实现，它反映了当前机器学习这一基础理论 的最新发展。统计学习理论是小样本学习理论，最早由v a p n i l k 于2 0 世纪6 0 年代提出， 但自9 0 年代以来受到越来越多的关注。所谓支持向量就是支撑最优分类面的向量，它的 思路是通过非线性变换将输入模式空间变换到一个高维空间，然后在这个新空间内求取 最优分类面，而这种非线性变换是通过在原空间中定义适当的内积( 核函数) 来实现的。 支持向量机的求解最终是一个二次规划问题，但是由于样本数比较大，常规的二次规划 算法不再适用，目前比较好的是p l a t t 于1 9 9 8 年提出的顺序最小优化s m o ( s e q u e n t i a l m i n i m a lo p t i m i z a t i o n ) 算法。该方法在人脸识别、手写体数字识别、文本自动分类等 领域得到了成功应用。 支持向量机用于故障检测通常有两种方法：一种方法是t a x 于1 9 9 9 年提出的超球 模型，即在样本特征空间内寻找一个中心为a ，半径为r 的超球，如图卜3 所示。正常 样本点位于超球内，异常点位于超球之外。优化目标是超球的体积要尽量小，同时位于 超球外的样本点也要尽量少。另一种方法是s c h o l k o p f 于1 9 9 9 年提出的超平面模型， c a m p b e l l 于2 0 0 1 年提出利用线性规划求解超平面模型。然而超平面模型的不足在于： 特征空间的原点被先验地认为是故障样本区域的中心，然后寻找超平面使得正常样本区 域尽量远离该中心。【6 】 图1 - 3 超球模型 5 中国民航大学硕士学位论文 1 3 4 基于小波神经网络的诊断方法 “小波分析是由法国地质学家j m o r l e t 于1 9 8 1 年首次提出并逐渐发展起来的一 种数学分析方法。它是当前数学中一个迅速发展的新领域，同时具有理论深刻和应用广 泛的双重意义。小波神经网络是将小波分析与在非线性学科中具有重要优势的人工神经 网络相结合而成的一种新型神经网络。小波分析与小波神经网络由于其良好的时一频局 部分析及神经网络特有的属性，在时一频分析、图象处理、语音分析与合成、地震信号 处理、滤波消噪、频谱估计、故障诊断、信号分解、信号检测、非参数估计、系统辨识、 数据压缩等众多方面取得成功应用。 小波神经网络是小波函数在神经网络中的应用。把小波分析思想与神经网络的优势 有机结合，是一个大胆的设想。小波函数的伸缩和平移构成r 尺d ) 空间上的标准正交基， 而小波神经网络就是用小波基来代替通常的s i g m o i d 函数作为网络的神经元函数，生成 了与径向基函数在结构上相似的小波神经网络。这种网络的目标就是根据已有的函数特 点，最佳地选择小波函数的伸缩和平移，用最少的神经元数目来表示该函数，或者等价 地说，用固定神经元数最大限度地表示已有函数，使逼近误差在某种度量标准下为最小。 也有人是用小波分析对信号进行预处理，即以小波空间作为模式识别的特征空间，通过 将小波基与信号的内积进行加权和来实现信号的特征提取，然后将提取的特征向量送入 神经网络处理，这样按照顺序结合起来应用的也n q j , 波神经网络。 但是，随着处理问题维数的增加将导致小波神经网络节点和权值的急剧增加，它 的收敛速度大大放慢甚至不能收敛，即“维数灾难 问题成为制约其应用的瓶颈。所以 多输入多输出用于函数逼近的小波神经网络的还没有很明确简单的构造成功的文献，较 为成功的也只是多输入单输出的小波神经网络如图1 - 4 所示。 t h l u 】 墨，。 f ) 线性输螂节点 图1 - 4 多输入单输出的小波神经网络 6 小敞屡 输入层 中国民航大学硕士学位论文 文献 1 1 应用小波分析对含噪信号进行处理，并且应用小波神经网络对航空发动机 进行故障诊断并且在单故障诊断和复合故障的诊断方面都取得较好效果，这里就不再赘 述。 1 - 4 目前发动机气路故障诊断技术面临的一些问题 目前发动机气路故障诊断和技术面临的主要问题有【1 2 j ： ( 1 ) 发展适合故障诊断的数学模型。目前发动机气路诊断，采用的主要是基于模型 的故障诊断方法。这种方法对模型的精度具有特殊要求。近二十年来，虽然人们对发动 机模型作了大量的工作，所得到的模型精度越来越高，但同时模型的复杂度也增加了很 多。而目前，基于模型的故障诊断技术，在处理线性问题时比较有效。因此，虽然发动 机模型得到了发展，但是用于故障诊断的发动机非线性模型结构却变化不大。由此在应 用这些模型解决问题时，面临如何根据实际问题矫正模型精度的问题。 ( 2 ) 故障试验的成本过大，发动机仿真技术有待于进一步发展。一种发动机的故障 诊断方法从产生到实用化要经过不断的检验。对于发动机这样一个系统来说，每进行一 次试验，都必须进行细致的准备，调动大量的人力物力，试验周期长，试验花费大。目 前很多发动机故障诊断方法都尽量先在仿真阶段进行完善。因此对发动机的仿真结构进 行探讨是一项有意义的工作。 ( 3 ) 故障分离定位问题。故障之间存在很强的相关性，区分相似故障很困难。 1 5 本文的主要工作及结构安排 1 5 1 论文的主要工作 本文主要应用遗传算法对航空发动机的气路故障进行诊断。 1 ) 介绍了遗传算法的基本理论知识。包括遗传算法的基本流程和操作，以及运算 中适应度函数的建立和各个控制参数的选择等。 2 ) 对本课题所要应用的主要软件一m a t l a b 7 o 中的遗传算法工具箱进行了概述。 介绍了该工具箱的特点以及编写m 文件的方法。 3 ) 建立了一种应用遗传算法进行故障诊断的数学模型一集约覆盖理论数学模型。 将基于故障方程的诊断方法中的故障系数与该模型相结合，将经验故障方程中的故障系 数作为概率因果数据计算，最终求出所有故障假设中具有最大似然值的故障集。并且绘 制了遗传算法中各遗传代进化的趋势图。 4 ) 根据故障因子的相似度理论，对所有故障因子进行计算，将相似度较大的故障 因子归为一类，减少故障模型数量。 7 中国民航大学硕士学位论文 1 5 2 论文的结构安排 本文共分六章。 第一章绪论 第二章遗传算法的基本理论 第三章遗传算法工具箱的概述 第四章建立基于集约覆盖理论的故障诊断模型 第五章应用实例与分析 第六章总结与展望 8 中国民航大学硕士学位论文 第二章遗传算法的基本理论 2 1 遗传算法的历史和发展 2 0 世纪4 0 年代以来，科学家不断努力从生物学中寻求用于计算科学和人工系统的 新思想、新方法，比如早期的自动机理论就试图采用类似神经元的元素建造一种新型的 思维机器。很多学者对关于生物进化和遗传的机理中发展出适合于现实世界复杂适应系 统( c o m p l e xa d a p t i v es y s t e m s ) 研究的计算技术一一自然进化系统的计算模型 ( c o m p u t a t i o n a lm o d e l so fn a t u r a le v o l u t i o n a r ys y s t e m s ) 和模拟进化算法( s i m u l a t e d e v o l u t i o n a r ya l g o r i t h m ) 等，进行了开拓性的长期探索和研裂1 3 】- 1 1 9 1 ，h o l l a n d 及其学生首 先提出的遗传算法( g e n e t i ca l g o r i t h r n s ，简称g a s 或g a ) 就是一个重要的发展方向【1 5 】- 【1 9 1 。 h o l l a n d 的早期工作主要集中于生物学、社会学、控制工程、人工智能等领域中的一 类动态系统的适应性问题( a d a p t a t i o n ) ，其中适应性概念描述了在环境中表现较好行为 和性能的系统结构的渐进改变过程，简称系统的适应性过程1 3 】【1 4 】，【19 1 。h o l l a n d 认为， 通过简单的模拟机制可以描述复杂的适应性现象。因此，h o l l a n d 试图建立适应过程的 一般描述模型，并在计算机上开展模拟试验研究，分析自然系统或者人工系统对环境变 化的适应性现象，其中遗传算法仅仅是一种具体的算法形式。 19 6 2 年，j o h nh o l l a n d 在o u t l i n ef o ral o g i ct h e o r yo f a d a p t i v es y s t e m s 一文中，提 出了所谓监控程序( s u p e r v i s o r yp r o g r a m s ) 的概念，即利用群体进化模拟适应性系统的思 想。他注意到在建立智能机器的研究中，不仅可以完成单个生物体的适应性改进，而且 通过一个种群的许多代的进化也可以取得非常好的适应性效果。为了获得一个好的学习 方法，仅靠单个策略的改进是不够的，采用多策略的群体繁殖往往能产生显著的学习效 果。尽管他当时没有给出实现这些思想的具体技术，但却引进了群体、适应值、选择、 变异、交叉等基本概念。1 9 6 6 年，f o g e l 等人也提出了类似的思想，但其重点是放在变 异算子而不是采用交叉算子。1 9 6 7 年，h o l l a n d 的学生j d b a g l e y 通过对跳棋游戏参数 的研究，在其博士论文中首次提出“遗传算法 一词【1 6 】。 h o l l a n d 以二进制字符集 0 ，1 ) 构成的代码串表示实际问题的描述结构或参数，称为 “染色体”( c h r o m o s o m e ) 。对这些“染色体 进行变换，利用“染色体”中所包含的信 息决定新一代“染色体，并最终得到问题的解。这种方法对所要解决的问题类型几乎 没有任何限制，所需要的信息只是每个染色体的评价值。这种使用简单编码和选择机制 的算法能够解决相当复杂的问题，并且解决实际问题时不需要该领域的专门知识。通过 对这些简单的染色体进行迭代处理，从这些染色体中发现并保存好的染色体，进而逐步 发现问题的最优解，这些思想就是遗传算法理论的雏形。 1 9 7 5 年，h o l l a n d 出版了专著自然与人工系统中的适应性行为( a d a p t a t i o ni n 9 中国民航大学硕士学位论文 n a t u r a la n da r t i f i c i a ls y s t e m ) ，该书系统地阐述了遗传算法的基本理论和方法，提出了对 遗传算法的理论发展极为重要的模式理论( s c h e m at h e o r y ) ，其中首次确认了选择、交 叉和变异等遗传算子，以及遗传算法的隐并行性，并将遗传算法应用于适应性系统模拟、 函数优化、机器学习、自动控制等领域。 1 9 9 2 年，k o z a 教授出版了一本遗传规划专著g e n e t i cp r o g r a m m i n g1 ，两年之后又出 版了第二本关于遗传规划的专著。k o z a 教授虽然尚未建立遗传规划的完整理论体系， 但他通过大量的实验说明了遗传规划能够成功地解决一类复杂问题，为基于符号表示的 函数学习问题增添了一个强有力的工具。 美国m i t 出版社从1 9 9 3 年开始出版e v o l u t i o n a r yc o m p u t a t i o n 和a d a p t i v eb e h a v i o r 杂志。世界上第一本关于人工智能研究的杂志a it r e n d s 于1 9 9 3 年更名为c r i t i c a l t e c h n o l o g yt r e n d s ，并在更名启事中讲到“遗传算法、自适应系统、细胞自动机、 混沌理论和人工智能一样，都是对今后十年的计算机技术有重大影响的关键技术 。 这些众多的研究单位和频繁的国际学术活动集中反应了遗传算法的学术意义和应 用价值。目前，遗传算法已成为一个多学科、多领域的重要研究方向。 2 2 遗传算法的基本描述 遗传算法抽象与生物体的进化过程，通过全面模拟自然选择和遗传机制，形成一种 具有“生成+ 检验 特征的搜索算法。遗传算法以编码空间代替问题的参数空间，以适 应度函数为评价依据，以编码群体为进化基础，以对群体中个位串的遗传操作实现选择 和遗传机制，建立起一个迭代过程。在这个过程中，通过随机重组编码位串中的重要的 基因，使新一代的位串集合优于老一代的位串集合，群体的个体不断变化，逐渐接近最 优解，最终达到求解问题的目的。 遗传算法的研究工作主要集中在以下几个方面： ( 1 ) 性能分析。遗传算法的性能分析一直都是遗传算法研究领域中最重要的课题之 一。在遗传算法中，群体规模、杂交和变异算子的概率等控制参数的选取是非常困难的， 同时它们又是必不可少的实验参数，这方面已有一些具有指导性的实验结果。遗传算法 还存在一个过早收敛问题，也就是说遗传算法的最后结果并不是总能达到最优解，怎样 阻止过早收敛是人们感兴趣的问题之一。另外，为了拓广遗传算法的应用范围，人们在 不断研究新的遗传染色体表示法和新的遗传算子。 ( 2 ) 并行遗传算法。遗传算法在操作上具有高度的并行性，许多研究人员正在探索 在并行计算机上高效执行遗传算法的策略。最近几界的遗传算法国际会议论文集上也收 录了这方面的文章。对并行遗传算法的研究表明，只要通过保持多个群体和恰当的控制 群体间的相互作用和模拟并行执行过程，即使不使用计算机，也能提高算法的执行效率。 ( 3 ) 分类系统。分类系统属于遗传算法的机器学习的一种类型，它包括一个简单的 基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。分类系统正被人们 l o 中国民航大学硕士学位论文 越来越多地应用在科学、工程和经济等领域。例如，规则集的演化能预估公司的利润和 对字母序列进行预测。目前，分类系统是遗传算法研究中的一个非常活跃的领域。 遗传算法的另一个活跃的研究方向是在神经网络方面的应用，它包括优化神经网络 连接权系数和网络的空间结构。遗传算法与神经网络相结合已成功地被应用于从时间序 列分析来进行财政预算。 遗传算法的思想是将自然界中的进化过程引入工程研究领域以解决工程中的优化 问题。在用进化思想优化问题时，使用了进化过程中的遗传、选择等概念，并且它们作 为算子参与优化。遗传算法和模拟退火等随机算法以及传统的局部下降的最优化方法相 比有本质的区别，但是它们是互相补充的。遗传算法的全局最优能力是以较大的搜索空 间为代价的，它的出现并不能从理论上解决全局最优解，仅仅提供了可能求得全局最优 解的一个方法。最优化问题一直是人们感兴趣的一个问题，许多人工智能的问题都归结 为一个优化问题，所以对优化问题的研究工作不会停止，遗传算法的出现和深入研究将 使智能优化研究向更深入和更广泛的方向发展【2 0 1 。 2 2 1 遗传算法的基本流程 遗传算法在整个进化过程中的遗传操作是随机性的，但它所呈现出的特性并不是完 全随机搜索，它能有效地利用历史信息来推测使下一代期望性能有所提高的寻优点集。 这样一代代地不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。遗 传算法所涉及的五大要素：参数编码、初始群体的设定、适应度函数的设计、遗传操作 的设计和控制参数的设定。 我们通常采用的遗传算法的工作流程和结构形式是g o l d b e l g 在天然气管道控制优 化应用中首先提出的，一般称为规范遗传算法( c a n o n i c a lg a ，c g a ) 或者标准遗传算法 ( s t a n dg a ，s g a ) 。在g a 应用过程中，人们往往结合问题的特征和领域知识对s g a 进 行各种改变，形成了各种各样的具体的g a ，使得g a 具备解不同类型优化问题的能力， 以及具备强大的全局搜索能力。 简单遗传算法的基本流程和结构如图2 1 所示。 中国民航大学硕士学位论文 图2 - 1 简单遗传算法基本流程框图 从图可以看出，遗传算法的运行过程为一个典型的迭代过程，其必须完成的工作内 容和基本步骤如下： 1 选择编码策略，把参数集合x 的域转换为位串结构空间s ； 2 定义适应值函数f ( x 1 ： 3 确定遗传策略，包括选择群体大小珂，选择、交叉、变异方法，以及确定交叉概 率e 、变异概率等遗传参数； 4 随机初始化生成群体p ； 5 计算群体中个体位串解码后的适应值f ( x 1 ； 6 按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体； 7 判断群体性能是否满足某一指标，或者已完成预定迭代次数，不满足则返回步骤 6 ，或者修改遗传策略再返回步骤6 。【2 l 】 2 2 2 遗传编码 按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标问题实际表示与 遗传算法的染色体位串结构之间建立联系，即确定编码和解码运算3 0 1 。由问题空间向 g a 编码空间的映射称作编码，而由编码空间向问题空间的映射称作译码。问题编码一 1 2 中国民航大学硕士学位论文 般应满足以下3 个原则【1 6 】： ( 1 ) 完备性：问题空间中的所有点( 可行解) 都能成为g a 编码空间中的点( 染色 体位串) 的表现型： ( 2 ) 健全性：g a 编码空间中的染色体位串必须对应问题空间中的某一潜在解； ( 3 ) 非冗余性：染色体和潜在解必须一一对应。 按照遗传算法的模式定理，d ej o n g 进一步提出了较为客观明确的编码评估准则， 称为编码原理【1 9 】， 2 2 1 ，【2 3 1 。具体可以概括为两条规则： ( 1 ) 有意义建筑模块编码规则：编码应当易于生成与所求问题相关的短距和低阶的 建筑模块； ( 2 ) 最小字符集编码规则：编码应采用最小字符集以使问题得到自然、简单的表示 和描述 从应用问题的特征来看，对于少数问题可以直观地判断所对应的g a 编码空间是否 满足建筑模块编码规则，但是实际环境中往往缺乏充分的先验信息，多数问题的确认是 十分困难的。第二条规则提供了一种更为实用的编码原则。 按照问题的特性，编码一般有：二进制编码、大字符集编码、实数编码、序列编码 等多种形式。二进制编码是最基础的编码方式，它的应用范围非常广泛。 1 二进制编码将问题空间表示为基于字符集 0 ，1 构成的染色体位串。以下以连续 实函数的二进制编码为例，分析其编码过程。 设一维连续实函数f 【x ) ，x ( u ，v ) 采用长度为l 的二进制字符串进行定长编码，建立 位串空间： s 工= 口l ，a 2 ，a 3 , a 4 ，a k ) ，a i2 ( 口t l ，a t 2 ，a k l ) ，a 材 0 ，1 ) k ：1 ，2 ，k ；1 = 1 ，2 ，l ；k = 2 l( 2 1 ) 其中，个体的向量表示为a i = ( a k la ，a 舡) ，其字符串形式为以= a k l a | | 2 a 址 ( 从左到右依次表示从高位到低位) ，s k 称为个体a l 【对应的位串。表示精度为： a x = p 一“) ( 2 l 一1 ) ( 2 2 ) 将位串个体从位串空间转化成问题参数的译码函数r ： o ，1 ) 工一 i n ，v 】的公式定义 为： 以= r ( 口 口舡) = “+ 若( 窆2 工- j ) ( 2 3 ) 一1j = l 对于n 维连续函数f 【x ) ，x = ( x l ，x 2 ，x n ) ，x i u i ，v i ( i = l ，2 ，n ) ，各维变量的 二进制编码位串的长度为l i ，那么x 的编码从左到右依次构成总长度为l = l i 的二进 百 制编码位串，相应的g a 编码空间为：s 工= a l , a 2 ，a 篁) ，k = 2 该空间上的个体位串结构为： a k = ( 口：，口t 1 2 , , a l k l l , a 小2 口护2 ，口吖2 ：，口：- ，i ：，胡0 ，口磊，口n ，口磊) 中国民航大学硕士学位论文 j 七2 口t i - 口t 1 ：口。i ，。口t 2 t “t 2 ：口。2 z ：口t i - 口t i z 口：厶口刍口t n z 口乙，口材i o ，1 ) ( 2 4 ) 对于给定的二进制编码位串s t ，位段译码函数r ： o ，1 ) i _ u tu 】的形式为： 铲r 碱i ，锄= ”谐( 喜口矿饥渊2 ，刀( 2 5 ) 其中个体位串口小i 口伽i 口：，为个体位串s k 的第i 段。那么整个s k 的译码函数为 r = r 1 r 2 f 4 。 2 非二进制编码往往结合问题的具体形式，一方面简化编码和解码过程，另一方面 可以采用非传统操作算子，或者与其他搜索算法相结合。非二进制编码主要有大字符集 编码、序列编码和实数编码等形式。 1 ) 大字符集编码 除基于字符集 0 ，1 ) 的二进制编码外，可以结合实际问题的特征采用d 进制或字符 集来表示长度为l 的位串，比如位串a = ( a l ，a 2 ，a l ) ，其中a l e o ，1 ，2 ，d 1 ) 。 2 ) 实数编码 实数编码具有精度高，便于大空间搜索的优点。m i c h a l e w i c z 比较了两种编码的优 缺点【2 4 1 ，指出二进制编码的进化层次是基因，实数编码的进化层次是个体，用前者来指 导后者是不合适的。大量的试验结果表明：对同一优化问题二进制编码和实数编码g a 不存在显著的性能差异。 3 ) 序列编码 采用g a 求解旅行商( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 问题时 1 9 】， 2 4 】，用排列法 进行编码似乎更为自然、合理。如