（系统工程专业论文）应用改进遗传算法进行PID控制器参数整定.pdf

江苏大学硕士学位论文 摘要 遗传算法是一种基于生物进化理论的全新优化搜索方法，是一种 具有极高鲁棒性的全局优化方法，在自控领域得到广泛的应用。本文 对遗传算法理论进行了深入而细致的研究，针对标准遗传算法易发生 早熟收敛现象和收敛速度过慢的缺陷，提出了遗传算法的改进策略： 最优保存策略以及采用自适应交叉和变异算子，并综合分析了它们对 算法收敛性的影响。 本论文用m a t l a b 作为数据处理工具，分析和仿真了p i d 控制系 统，用遗传算法搜索最佳的p i d 参数。应用改进的遗传算法对p i d 控制 器参数进行优化设计，基于m a t l a b 的仿真结果表明控制系统的性能指 标有很大改善，证明了该改进算法的可行性和有效性。 遗传算法在自控领域的应用目前多数处于理论性仿真研究阶段。 本人应用m a t l a b 软件仿真了实际工业过程控制系统，并验证了遗传算 法在工业过程控制中的巨大应用价值，证实了该方法具有简单、直观 的特点和很强的工程应用价值。 关键词：遗传算法；p i d 优化整定；m a t l a b 仿真；自适应技术；适应 度函数 江苏大学硕士学位论文 a b s t r a c t g e n e t i ca l g o r i t h mi san e w o p t i m i z i n gs e a r c h i n gm e t h o db a s e do nb i o l o g ye v o - l u t i o n a r yt h e o r y i ti sag l o b a lo p t i m i z a t i o na l g o r i t h m s 耐t hh i 曲r o b u s tp e r f o r m a n c e i th a sb e e n 、 ，i d e l ya p p l i e di na u t o m a t i cc o n t r o lf i e l d s o m ei m p r o v e m e n t sl i k eg r e a - t e s tu n i tc o n s e r v e ds t r a t e g y ，a d a p t i v et e c h n i q u et oc r o s s o v e ro p e r a t o ra n dm u t a t i o n o p e r a t o ra r ep r e s e n t e dt oo v e r c o m et h es l o wa n dp r e m a t u r ec o n v e r g e n c es h o r t a g e so f c a n o n i c a lg e n e r i ca l g o r i t h m s a n a l y s i si sm a d eo nt h e i re f f e c t s0 na l g o r i t h mc o n v e r g e n c e i nt h ed i s s e r t a t i o np i d c o n t r o ls y s t e mi sa n a l y z e da n ds i m u l a t e du s i n gm a t l a b a sat 0 0 1 g e n e r i ca l g o r i t h mi su s e dt os e a r c hf o rt h eb e s tp i df a c t o r s b ya p p l y i n gt h e m o d i f i e dg e n e t i ca l g o r i t h mt ot h eo p t i m i z i n go f p a r a m e t e r so f p i dc o n t r o l l e r , b e t t e r p e r f o r m a n c e so f c o n t r o ls y s t e ma r ea c h i e v e da n ds i m u l a t i o nr e s u l tb a s e d o nm a t l a b s h o w si t sf e a s i b i l i t ya n du t i l i t y t h em o s ta p p l i c a t i o n so f t h eg ai nt h ea u t o m a t i cf i e l da r es t i l li nt h e o r e t i c a ls i m u l a t i o n t h i sd i s s e r t a t i o np r e s e n t sad a t ac o m m u n i c a t i o nm o d eb e t w e e nt h es i m u l a - t i v ea n da c t u a ls y s t e m s w h i c hu s e st h em a n a bs i m u l a r i v ep l a n t , t h i sm o d ep r e s e n t s an e wm e t h o dt oa p p l yg ai nt h ee n g i n e e r i n gt od e v e l o pi n d u s t r i a lc o n t r o ls y s t e m s t h i sm e t h o di se a s ya n di n t u i t i o n a l ，a n dv a l u a b l ef o re n g i n e e r i n ga p p l i c a t i o n k e yw o r d s ：g e n e t i ca l g o r i t h m ；p i do p t i m a l t u n i n g ；m a t l a bs i m u l i n k ；a d a p t i v e t e c h n i q u e ；a d a p t a b i l i t yf u n c t i o n 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密口。 学位论文作者签名： 年月日 指导教师签名： 弓毛删 年月 日 江苏大学硕士学位论文 1 1 遗传算法的概念 第一章绪论 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种全局优 化概率搜索算法。遗传算法中，将n 维决策向量x 表示成由n 个记号所组成的编 码符号串，这样就可以将决策向量看做是由刀个遗传基因所组成的一个染色体。 这种编码所组成的排列形式就称为个体的基因型，与它对应的决策向量z 值就 称为个体的表现型。通常个体的基因型和表现型是一一对应的，但有时也允许基 因型和表现型是多对一的关系。对于每一个个体要按照一定的规则确定出其适应 度。个体的适应度与其对应的个体表现型的目标函数值相关联，个体表现型越接 近目标函数的最优值，其适应度越大；反之，其适应度越小。 遗传算法中，决策变量组成了问题的解空间。而对问题最优解的搜索是通过 对染色体的搜索过程来进行的，从而由所有的染色体就组成了问题的搜索空间。 生物的进化是以集团为主体的。与此对应，遗传算法的运算对象是由多个个 体所组成的集合，称为群体。与生物一代一代的自然进化过程类似，遗传算法的 运算过程也是一个反复迭代的过程。群体不断的经过遗传和进化操作，并且每次 都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群 体中会得到一个优良个体，其所对应的表现型将达到或接近问题的最优解。 生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。与 此相对应，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓 的遗传算子作用于群体中，从而得到新一代群体。 1 2 遗传算法的研究历史及国内外研究现状 遗传算法g a ( g e n e t i ea l g o r i t h m s ，简称g a ) 产生于一些生物学家用计算机模 拟生物进化过程的仿真实验。从2 0 世纪4 0 年代，生物模拟就成为计算机的一个 重要组成部分。自从达尔文的进化理论得到人们的普遍接受之后，进化机制便引 起了人们的极大兴趣。大多数生物体通过自然选择和有性生殖这两种基本过程进 化演化。自然选择决定了那些个体能够存活并繁殖；而有性生殖保证了后代基因 中的混合和重组。这种由基因重组产生的后代进化要快得多。自然选择的原则是 1 江苏大学硕士学位论文 优胜劣汰，适者生存。 2 0 世纪5 0 年代中期创立了仿生学，许多科学家从生物中寻求用于人工系统的 灵感。一些科学家如h o l l a n d ，o w e n s 和w a l s h 分别独立地从生物进化机理中发展 出适合于现实世界复杂问题优化的模拟进化算法( s i m u l a t e de v o l u t i o n a r y o p t i m i z a t i o n ) 。进化算法包括三方面内容：遗传算法g a ，进化策略e s ( e v o l u t i o n a r y s t r a t e g y ) 和进化规划e p ( e v o l u t i o n a r yp r o g r a m m i n g ) 。其中遗传算法的研究最为深 入持久应用面也最广。遗传算法早期的研究工作始于2 0 世纪6 0 年代。在此期间， 美国密执安大学的j o h nh o l l a n d 教授正在从事自适应系统的研究，受生物学家们 的启发，h o l l a n d 教授创造性地将模拟遗传算子用于人工系统并成功地利用它解 决了一些实际问题，如“旅行商问题”，它的价值逐渐被人们所认识。 1 9 7 5 年j h h o l l a n d 教授出版了他的经典著作自然和人工系统的适配 ( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m ) ，该书是系统论述遗传算法和人工适 应系统的专著，比较全面地介绍了遗传算法的基本理论和方法并提出了对遗传算 法的理论研究和发展极为重要的模式定理，从而树立了遗传算法发展史上的第一 块里程碑。h o l l a n d 教授也因此被视为遗传算法的创始人。 他所创建的遗传算法是一种概率搜索方法，利用简单的编码技术和复制、交 叉、变异等生物机制来表现复杂的现象，因其搜索空间不受限制性假设的约束， 不必要求诸如连续性、可导、单峰和倒数存在，从而能够解决许多传统方法难以 解决的问题，被广泛用于各种优化问题。并以其固有的并行性，在函数优化、机 器学习、并行处理等领域中得到了广泛的应用。 遗传算法发展史上的第二块里程碑是k e n n e t h 完成了具有指导意义的博士学 位论文遗传自适应系统的行为分析( a na n a l y s i so f t h eb e h a v i o ro f ac l a s so f g e n e t i ca d a p t i v es y s t e m ) ，这篇论文主要研究了遗传算法在函数优化中的应用， 并进行了大量的数值实验。遗传算法作为一种函数优化方法在工程方面的应用受 到了人们越来越多的重视。 从7 0 年代中期起，关于遗传算法的研究逐渐呈现出蓬勃发展的势头。遗传算 法成为人工智能研究的一大热点。1 9 8 7 年，美国出版了遗传算法与模拟退火 ( g e n e t i ca l g o r i t h ma n ds i m u l a t e da n n e a l i n g ) - - 书，以论文形式用大量的实例介绍 了遗传算法的使用。美国亚拉巴马大学的d a v i dg o l d b e r g 在遗传算法的研究中起 着继往开来的作用。1 9 8 9 年出版的搜索优化和机器学习中的遗传算法( g e n e t i c 2 江苏大学硕士学位论文 a l g o r i t h m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g ) - - 书系统总结了遗传算 法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用，可以说 这本书奠定了现代遗传算法坚实的科学基础，为众多研究和发展遗传算法的学者 所瞩目。1 9 9 1 年，l a w r e n c e d a v i s 出版了遗传算法手册( h a n d b o o ko f g e n e t i c a l g o r i t h m ) ，包括了遗传算法在科学计算、工程技术和社会经济中的大量应用实 例，对有效应用遗传算法起了重要的指导作用。从1 9 8 5 年起，大约每两年举办一 届g a 国际会议，美国m i t 出版社从1 9 8 3 年开始出版进化计算( e v o l u t i o n a r y c 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 jt r e n d s ) 已于1 9 9 4 年改名为( c r i t i c a lt e c h n o l o g y t r e n d s ) ，并在更名启事中讲到“遗传算法、自适应系统、细胞自动机和混沌理 论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术。”( i e e e t r a n so nn e u r a ln e t w o r k s ) 于1 9 9 4 年5 月出了关于遗传算法、进化计算的专刊， 并在编者按中指出：“进化思想不仅是生命科学的范畴，进化是一种优化过程， 可以在计算机上模拟，并应用到工程领域”。目前一些商用遗传算法软件已在市 场上出现，遗传算法在生物技术、工程技术、图像识别、人工神经网络等更广阔 的领域内得到了应用。 各国研究人员一直致力于推动遗传算法的发展，对编码方式、控制参数的确 定、选择方式和交叉变异机理进行了深入的探究，引入了动态策略和自适应策略 以改善遗传算法的性能，提出了各种改进的遗传算法。文献 1 提出一种实数编 码的遗传算法并将其应用于优化问题中。文献 2 综合模拟退火算法( s a ) 和遗传 算法( g a ) ，提出一类g a s a 混合优化策略，并借助于非平稳马氏链理论证明混合算 法的全局渐进收敛性，同时定性分析了算法的优化效率。文献 3 提出一种求解 优化问题的混沌遗传算法，其基本思想是把混沌变量加载于遗传算法的变量群体 中，利用混沌变量对子代群体进行微小扰动并随着搜索过程的进行逐渐调整扰动 幅度。 随着计算机技术的高速，近年来我国也掀起了遗传算法的研究热潮。在应用 领域，关于遗传算法操作程序的研究、种群结构的研究、操作算子自适应策略的 研究以及基因编码的研究等方面已经取得了令人瞩目的研究成果。文献 4 对目 前已有的编码机制进行了分析并提出高效编码的原则。文献 5 提出一种自适应 遗传算法，其基本思想是动态调整优化过程的交叉和变异概率，从而快速精确的 江苏大学硕士学位论文 实现全局最优。文献 6 分析了造成遗传算法早熟和局部收敛的原因并提出一种 多种群遗传算法。在解决调度问题、组合优化问题、最优控制、自适应控制、模 糊控制、神经网络控制、机器学习、模式识别等实际应用问题上取得了一系列成 果。 目前，遗传算法的主要应用领域有以下几个方面 7 ： 1 函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行 性能评价的常用算例。对一些非线性、多模型、多目标的函数优化问题，用其它 优化方法较难求解，而遗传算法却可以方便地得到较好的结果。 2 组合优化。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大， 有时在目前的计算机上用枚举法很难甚至不可能求出其精确最优解。对这类复杂 问题，人们已经意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这 种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的n p 完全 ( n o n d e t e r m i n i s t i cp o l y n o m i a lc o m p l e t e n e s s ) 问题非常有效。例如，遗传算法 已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的 应用。 3 生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以 精确求解，目前在现实生产中也主要是靠人工经验来调度。现在遗传算法已经成 为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、 生产规划等方面遗传算法都得到了有效的应用。 4 自动控制。在自动控制领域中，有很多与优化有关的问题学要求解，遗 传算法已经在其中得到了初步的应用，并显示出了良好的效果 1 t 。 遗传算法在自动控制领域中的应用可以粗略地概括为两类。离线设计分析和 在线自适应调节。离线应用又可以分为直接设计法和间接设计法。在直接设计法 中，g a 可被用来作为搜索和优化引擎。例如，对一个已知的被控对象，选择一个 合适的控制结构或优化一个特定控制器的参数设置以满足性能指标的要求。在间 接设计法中，用传统的综合设计方法进行控制系统的设计，而g a 为其提供优化参 数加权函数矩阵。g a 的在线设计也分为两种情况。一种是g a 被用来作为一种学习 机制，辨识未知或时变系统的特征参数，用于自适应控制器的调整。另一种是g a 直接优化控制器参数。此时也可以用传统的辨识方法估计系统状态构成，由g a 作为自适应优化机制的自适应控制器。 4 江苏大学硕士学位论文 5 机器人学。机器人是一类复杂的难以精确建模的人工系统，而遗传算法 的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算 法的一个重要应用领域。 6 图像处理。图像处理是计算机视觉中的一个重要研究领域。在图像处理 过程中，不可避免地会存在一些误差，这些误差会影响图像处理的效果。如何是 这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法已经在这些图像 处理中的优化计算方面得到了应用。 7 人工生命。人工生命使用计算机、机械等人工媒体模拟或构造出来的具 有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两 大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是 研究人工生命现象的重要理论基础。 8 遗传编程。遗传编程指的是，使用一种特殊编码方法，基于对一种树型 结构所进行的遗传操作来自动生成计算机程序。 9 机器学习。学习能力是高级自适应系统所应具备的能力之一。基于遗传 算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。 现在遗传算法的应用研究已从初期的组合优化求解拓展到了许多更新、更工 程化的应用方面。 1 3 本论文的选题意义 直到目前为止，在工业过程控制中，采用最多的控制方式依然是p i d 方式， 有8 0 9 0 的系统还使用p i d 控制。这一方面是由于p i d 控制器具有简单而固定 的形式性；另一方面，是因为p i d 控制方式在很宽泛的操作条件范围内都能保持 较好的鲁棒性。但p i d 控制复杂繁琐的整定过程一直困扰着工程技术人员，所以， 参数自整定技术具有十分重大的工程实践意义。 本文试图利用m a t l a b 对给定的对象模型进行仿真。通过m a t l a b 仿真工具进行 仿真研究，在给定的目标函数下，利用遗传算法g a 来优化p i d 控制器的参数，其 允许工程技术人员以一种简单而直接搜索最优参数的方法来调节p i d 控制器的参 数。 江苏大学硕士学位论文 1 4 本论文的主要工作 本论文进行的主要工作有： 1 分析遗传算法的原理和实现方法； 2 用m a t l a b 和s i 删l i n k 工具对p i d 控制系统进行仿真； 3 设计并实现改进遗传算法，利用遗传算法来优化p i d 控制器的参数。本文 在遗传算法中引入了控制论中一种应用广泛的思想，即自适应思想。在标准遗传 算法的基础上，随着进化代数不同，对个体采用了不同的交叉算子和变异算子， 让交叉和变异概率随着个体适应度值和种群平均适应度值的变化而变化。以这种 自适应的方法来确保种群多样性，避免遗传算法陷入局部最优解中产生早熟现 象。 6 江苏大学硕士学位论文 第二章遗传算法的基本理论 2 1遗传算法的生物遗传学基础 从3 0 多亿年前地球上出现原始的低等生命，逐步从简单的低级生物一直发展 到高级的生命，乃至万物之灵的人类，这是一个漫长的生物进化的过程，这个过 程已经被古生物、胚胎学、比较解剖学上的大量证据所证实。1 8 5 9 年，达尔文发 表了物种起源巨著，提出了以自然选择为基础的生物进化论学说。根据达尔 文的理论，每一物种在不断发展的过程中都是来越适应环境。物种的每个个体的 基本特征被后代所继承，但后代又不完全同于父代，这些新的变化，若适应环境， 则被保留下来。在某一环境中也是那些更能适应环境的个体特征能被保留下来， 这就是适者生存的原理。生物发展进化主要有三个原因：遗传、变异和选择。1 8 6 6 年，孟德尔( m e n d e l ) 在进行豌豆杂交试验时，发现了遗传的两个基本规律：基因 的分离规律和基因的自由组合规律。m e n d e l 认为遗传是作为一种指令遗传码封 装在每个细胞中，并以基因的形式包含在染色体中。每个基因有特殊的位置并控 制某种特殊的性质。由所有基因决定的个体对环境有一定的适应性。基因通过重 组和突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高 的基因结构就保存了下来。遗传算法就是建立在达尔文的自然选择和孟德尔的遗 传学说基础之上的一种迭代自适应全局优化概率性搜索算法。 在遗传算法中，借鉴了生物学的一些基本概念和术语但又与生物学意义有所 不同说明如下 7 ： 染色体( c h r o m o s o m e ) ：遗传物质的主要载体，指多个遗传因子的集合。在使 用g a 时，需要把问题的每一个解编码成为一个染色体。 基因( g e n e ) ：控制生物性状遗传物质的功能和结构的基本单位。 个体( i n d i v i d u l e ) ：染色体带有特征的实体称个体。由于每个个体代表了问题 的一个解，所以一个群体就是问题的解的集合。 种群( p o p u l a t i o n ) ：染色体带有特征的个体的集合称为之种群，又称群体或集 团，该集团的个体数称群体的大小。 适应度( f i t n e s s ) ：个体对其环境的适应程度称适应度。在g a 中个体对应于优 7 江苏大学硕士学位论文 化问题的一个解每个解一对应于一个函数值，：越大，则表明x i 对环境的 适应度越好，所以可以用个体的适应值函数，来衡量它对环境的适应度。 选择( s e l e c t i o n ) ：以一定的概率从群体中选取若干对个体的操作称为选择， 也叫复制或再生( r e d u c t i o n ) 。 交叉( c r o s s o v e r ) 把两个染色体换组的操作称交叉，又称为重组或交换。生 物体的繁衍就是通过染色体的交叉完成的。 突然变异( m u t a t i o n ) ：让遗传因子按一定的概率变化的操作称为突然变异， 又简称变异。 编码( e n c o d i n g ) ：从表现型到遗传子型的映射称为编码。 解码( e n c o d i n g ) ：从遗传子型到表现型的映射成为解码，又称译码。 在上述概念中，选择、交叉及变异对于实现遗传算法是十分重要的。 2 2 标准遗传算法的结构和实现 g a 将问题的求解表示成“染色体”，一般用二进制码串表示，解的特定集 合称为“种群”，解中的变量称为“基因”。将种群置于问题的“环境”中，根 据适者生存的原则，从中选择出适应环境的“染色体”进行复制，通过交叉和变 异两种基因操作产生出新一代更适应环境的“染色体”群。这样一代一代不断进 化，最后收敛到一个最适应环境的个体上，从而求得问题的最优解。 在应用遗传算法求解问题时，首先要完成以下初始化工作： ( 1 ) 确定编码方案 ( 2 ) 确定初始种群 ( 3 ) 确定适应值函数 ( 4 ) 确定控制遗传算法的参数和变量 ( 5 ) 确定指定结果的方法和停止准则 在标准遗传算法中，编码方案是把问题搜索空间的每个可能的点表示为确定 长度为三的字符串，一般以二进制表示；适应值度量为群体中可能的确定长度的 字符串指定一个适应值，它通常是问题本身所包含的，适应值函数必须有能力计 算搜索空间中每个确定长度的特征串的适应值；控制遗传算法的参数主要有复制 概率只( 即选择概率) 、交叉概率只、变异概率己以及种群大小和最大迭代次 8 江苏大学硕士学位论文 数肘。停止准则有两种：输出解达到满意程度或进化已达到指定最大代数。这 些准备工作完成后就可以执行遗传计算。遗传算法的一般过程可以分为初始化、 选择、交叉和变异四个组成部分，其结构如图2 一l 所示。 图2 1 标准遗传算法流程图 ( 1 ) 使用个具有任意染色体的个体组成初始世代种群； ( 2 ) 计算群体中每个个体的适应值z ； ( 3 ) 选择：依据个体的适应值，选择个个体，形成父代染色体。选择操作 在g a 中有多种实现方法，其中最简单的方法就是采用和适应值成比例的概率方 法来进行选择：即轮盘赌法。首先计算群体中所有个体适应值的总和，然 ， 后计算每个个体的适应值所占的比例专每，并以此作为相应的选择概率。 l j t ( 4 ) 交叉：g a 中交叉的实现如下：选择群体中的两个个体x 1 ，x ：，按照所 设定的交叉概率、交叉次数、交叉方法，随机地选取一个截断点，将而，的 染色体在截断点切开，并交换其后半部分，生成两个新的个体而。，x ：。根据适 应值的不同，留下个个体，淘汰其它。 ( 5 ) 变异：根据所确定的变异概率和方法，随机选择个体及遗传子座，用与 之相对立的遗传因子来替代：0 斗l ，1 j0 。 9 江苏大学硕士学位论文 ( 6 ) 满足算法终止条件，输出结果；否则，返回第( 2 ) 步。 从第( 2 ) 步到第( 5 ) 步为遗传过程的一个运行周期，称为世代。 2 3 模式定理 指导遗传算法的基本理论是j o h nh h o l l a n d 教授创立的模式定理 8 。该理 论揭示了遗传算法的基本原理。 在搜索过程中，遗传算法唯一需要的信息是适应值。适应值指导搜索向不断 改进的方向前进。如下面串与适应值的例子： 串0 1 1 0 0 11 1 00 1 01 1 11 0 1 l 适应值3 162 ，7 5 用串的十进制数作为适应值，从表中可以看出，群体中串之间的相似点与适 应值之间存在着一定的关系。例如，首位是1 的串适应值高，首位是0 的适应值 低，前两位都是1 的串适应值更高。通过把适应值和各个串结合起来，发掘串群 体中的相似点，可以得到大量的信息来帮助指导搜索。为了准确统计这些新信息 的量，引入模式的有关概念。 定义2 - 1 ：模式。一个模式就是一个相同的构形，它描述的是一个串的子集。 这个集合中的串之间在某些位上相同，对于二进制代码串，利用 0 ，1 ，】三元 字母表可以表示一个模式，表示不确定字符。一个模式与一个特定的串相匹配 是指它们之间对应的位置上，1 与1 相匹配，0 与0 相匹配，与0 或1 相匹配。 例如模式1 ”描述的是一个集合 1 0 01 0 11 1 01 1 1 。 为了产生搜索空间的几何表示，考虑长度l = 3 的串和模式。在这种情形下， 由于串很短，可以容易地画出搜索空间的图形。如图2 - 2 。在这个空间中，8 个 点表示8 个明确的串，1 2 条边表示只有1 个字符的模式，6 个平面表示含有2 个+ 字符的模式，而含有3 个字符的模式即立方体本身。可见，三位二进制串模 式具有鲜明的几何意义。 l o 江苏大学硕士学位论文 o l z 0 l 梭线 图2 - - 2 模式的几何意义示意图 定义2 - 2 ：模式的阶。模式的阶是指模式中有明确含义的字符的个数，记作 o ( 日) ，日表示模式。在二进制串中，一个模式的阶就是所有l 和0 的数目。例如 模式日( 0 1 1 1 * ) 的阶为4 ，模式h ( 料0 料) 的阶为l 。很明显阶次越低概括性就 越强，所代表的字符串个体数就越多。特殊地，模式阶次为0 时概括性最强，阶 次等于字符串长度时为一指定字符串，对于长度为三的某一确定的二进制字符串 而言，它所含有的模式总数为2 。 定义2 3 ：模式的定义长度。模式的定义长度指模式中第一个确定位置与最 后一个确定位置之间的距离，记做万( ) 。例如模式0 1 1 卑l 料的定义长度6 ) = 4 ， 这是因为第一个确定位置为l ，最后一个确定位置为5 ，它们之间的距离为4 。模 式料丰1 木木仅有一个固定位置，因此其定义长度为1 。 模式的定义长度代表该模式在遗传操作中被破坏的可能性。模式长度越短， 被破坏的可能性越小。例如长度为0 的模式最难被破坏。模式的阶和长度这两个 概念为分析字串的相似性及分析遗传操作对重要模式的影响提供了基本的手段。 1 复制对模式的影响 在世代f 种群中包含日的个体数用m ( h ，f ) 表示，包含日的个体平均适应度 用厂( 日) 表示，种群内所用个体的平均适应度用于表示，在一般g a 的结构条件下， 若遗传操作依概率只选择转移到下一世代的话，则下式成立： 朋，+ 1 ) ：肌，) 掣( 2 - 1 ) ， 可见经过复制操作后，种群中适应值高于平均值的任一模式日的数量在下 一代中会增加，而低于平均适应值的模式在下一代的数量会减少。这种增减是同 江苏大学硕士学位论文 时进行的，遗传算法中隐含的并行机制就在于此。 2 交叉对模式的影响 由单点交叉引起模式日被破坏的概率可以用 p 型( 2 2 ) 。三一l 表示。其中三表示染色体的长度，只为交叉概率。显然，模式长度越短，被破坏 的概率就越小。 3 变异对模式的影响 同样，在变异操作时，特定日的存活率为( 1 一巴) 。哪a 1 一o ( k 蛾 所) 掣卜磐邶) ( 2 - 4 ) 由以上分析和式( 2 4 ) 可以得出结论： 。 定理2 一l ：模式定：理( s c h e m at h e o r y ) 8 那些定义长度短的、位数少的、 平均适应值高的模式数量将随着代数的增加而呈指数增长。 根据模式定理随着遗传算法一代一代地进行那些适应环境的模式( 长度短、 位数少、适应值高) 将越来越多，因而可以期望最后得到的字串的性能也越来越 得到改善，并最终趋向全局的最优解。 2 4 遗传算法的特点和操作关键 c a 衣i 用了生物进化和遗传的思想，所以它与许多传统优化算法如解析法、 枚举法等具有不同的特点： ( 1 ) g a 是对问题参数的编码群进行进化，而不是对参数本身。 c a 要求将优化问题的参数编码成长度有限的代码集( 一般为 o ，l ) 组成的有 限串。c a 是在求解问题的决定因素和控制参数的编码串上进行操作，从中找出 高适应值的串，而不是对函数和控制参数直接操作，因此不受被优化函数约束的 限制，也不受搜索空间的限制。所以很多用传统方法难以解决的问题g a 都能解 决。 ( 2 ) c a 是在字串群体中进行搜索而不是在单个点上进行寻优。 江苏大学硕士学位论文 在最优化问题中，传统的方法是从一个点开始搜索，如登山( c l i m b i n g ) 法， 若一个细微变动能改善质量，则沿该方向前进，否则取相反方向。然而复杂问题 会使“地形”中出现若干“山峰”，传统的方法很容易走入“假山峰”。而g a 同时从串群的每个串开始搜索，像一张网罩在“地形”上，数量极大的串同时在 很多区域中进行采样，大大减少了陷入局部解的可能性。因此g a 具有全局快速 收敛的特点。 ( 3 ) g a 使用问题本身的目标函数或适应值进行搜索，而不需要导数等其它信 息。 传统搜索需要一些辅助信息，如梯度算法需要导数，当这些信息不存在时， 算法即宣告失败。而g a 只需目标函数和编码串，因此g a 几乎可以处理任何优化 问题而无须任何先决条件和信息。 ( 4 ) g a 使用随机规则进行搜索。 g a 使用的复制、交叉、变异这三个算子都是随机操作，而不是确定规则。 但这并不意味着g a 是简单的随机搜索，g a 是使用随机工具来指导搜索向着最优 解前进。 ( 5 ) g a 具有隐含的并行性( i m p l i c i tp a r a l l e l i s m ) 1 1 0 1 1 0 0 1 这个串既是1 1 ”+ 区域的成员，同时也属于1 ”1 和”o ”0 0 等区域。对于那些较大的区域，串的群体中表示它们的串就较多。g a 在搜索空 间里使用相对少的串就可以表示数量极大的区域，这种特性叫做隐含的并行性。 事实上，g a 虽然每代只对个串进行操作，但实际上处理了大约o ( n ) 个模式。 从而每代只执行与群体规模成比例的计算量就可以同时达到并行地对大约d ( ) 个模式进行有效处理的目的，并且无额外存储。这种隐含的并行性正是遗传算法 优于其它算法的关键所在。 ( 6 ) g a 最善于搜索复杂地区，从中找出期望值高的区域。 在解决简单问题时，g a 的效率并不高。正女 1 g a 的创始人j h h o l l a n d 所指 出的：“如果只对几个变量做微小的改动就能进一步改进解，则最好能另外使用 一些更普遍的方法，来为遗传算法助一臂之力”。 在应用g a 时以下几个问题是关键： ( 1 ) 如何将问题描述成串的形式，即问题的编码表示。在参数优化等问题中， 一般将各参数用二进制编码构成子串，再将子串拼接起来构成染色体。但不同的 江苏大学硕士学位论文 串长和码制，对求解的精度和g a 收敛时间会有很大影响。对于复杂问题，如变 结构的控制器，神经网络等，如何将问题描述成串的形式就不那么简单，而且同 一问题可以有不同的编码方式。 ( 2 ) 如何确定适应值函数。适应值函数用于评价各串的性能。函数优化问题 一般可直接将函数本身作为适应值函数；但对于复杂系统，往往需要针对问题设 计出能对解的性能进行评价的适应值函数。 ( 3 ) 确定控带i j g a 的参数 种群数目：种群数目直接影响g a 的有效性。太小，不能提供足够的采 样点，所以群体大小应该较大。这样，遗传操作处理的模式较多，生成有意 义的基因块并逐渐进化为最优解的机会就高，算法陷入局部最优解的危险就小。 但是，太大，会增加计算量，使收敛时间加长。根据大量的文献报道，一般 取在2 0 1 6 0 之间 交换概率只：只控制着交换操作的频率。太大会使高适应值的结构很快 被破坏掉；只太小会使搜索停止不前。一般取0 6 一o 8 。 变异概率匕：只是增加种群多样性的一个重要参数，它直接影响算法的收 敛性和最终解的性能。p 卅太小不会产生新的基因，增大变异概率，会使算法不 断地探索新的解空间，增加模式的多样性。但只太大又会使g a 变成随机搜索。 在实际应用中己取值通常较小，一般取0 0 0 1 0 1 。 2 5 标准遗传算法的局限 标准遗传算法具有特殊重要的经典地位。但无论从生物学角度还是从数学角 度衡量，标准遗传算法都存在着局限性。 从生物学的角度看，标准遗传算法所立足的d a r w i n 理论，虽成功揭示了生物 长期自然选择的进化发展规律，然而仍留下许多难解之谜。因此出现t e l d r i d g e 和g o u l d 的间断平衡理论、m o r g a n 发现的基因连锁现象以及m a y e r 的边缘物种形 成理论等。其中间断平衡理论是以如下古生物的重大发现为依据的： ( 1 ) 几乎所有的进化演变都集中发生在物种形成初期。换言之，小的初始种 群通常具有更快的进化速率。 ( 2 ) 物种形成结束后就进入一段比较漫长的相对停滞期。 1 4 江苏大学硕士学位论文 间断平衡理论突破了达尔文进化论中单一渐变模式的束缚，认为渐变模式和 骤变模式的交替才真正反映了进化过程的本质。m o r g a n 和m a y e r 的理论表达了同 样的观点，即变异在空间和时间上不可能是均匀的。 自然选择在进化过程中发挥了极其重要的作用：它规定和制约了进化的可能 方式和倾向。因此，有理由认为，自然选择是作为一种反馈机制作用于生物系统 的，适应或不适应决定了是采用正反馈还是负反馈，其渐进结果便是生存或灭亡。 从数学的角度看，遗传算法的理论基础是模式定理。但在模式定理的推导中， 只侧重讨论交叉、变异算子对染色体的破坏作用，忽视了染色体被重新生成的可 能性。所以模式定理的成立是有条件的。 正如生物是不断发展进化的一样，遗传算法本身也在不断地改进发展。针对 标准遗传算法的种种缺陷，人们对遗传算法进行了更深入细致的研究，提出了很 多改进的方法，形成了庞大的遗传算法的理论体系。 目前，对遗传算法的研究主要集中在以下几方面： 1 遗传算法收敛性的分析。 2 对编码机制遗传算子的分析和研究。 3 对并行遗传算法的研究。 4 遗传算法融合于其它算法如人工神经网络的研究。 江苏大学硕士学位论文 第三章遗传算法的理论研究及改进 3 1 编码策略 遗传算法主要是对群体中的个体施加操作，从而完成优化的。遗传算法不能 直接处理问题空间的参数，而只能处理以基因链码即染色体形式表现的个体，因 此需要对问题的解的参数形式进行编码。编码问题实际是从问题空间到表达空间 的影射问题。一般来讲，由于遗传算法的鲁棒性，它对编码的要求并不苛刻，但 编码的策略和方法对于遗传操作，尤其对于交叉操作有很大的影响。因此恰当地 设计编码方法，对于充分发挥遗传算法的功能是十分重要的。 编码的指导思想是d ej o n g 提出的编码规则 9 ： ( 1 ) 有意义基因块编码规则：所设计的编码方案应当易于生成与求解问题相 关的短定义距和低阶的基因块； ( 2 ) 最小字符集编码规则：所设计的编码方案应采用最小字符集以使问题得 到自然的表示或描述。 上述的两个编码原理为编码设计提供了一定的准则，但在实际应用时仍要具 体问题具体设计。例如一个5 城市的“旅行商”问题：各城市之间的距离己知， 从某个城市出发，经过每个城市一次且只经过一次，要求在所有这样的旅行路线 中找出总路径“距离”之和最小的路径。 我们将5 个城市编号为a 、b 、c 、d 和e ，对于问题的一个解，可以有如下两种 表示方法： ( 1 ) a b c d e 1 2 0p m b p m c p m d p m e p b c p 8 d p 8 e p c d p c e p d e = 1 0 0 0 1 0 0 1 0 1 上 7队 、o 乏巴7 ，) 图3 1 一个5 城市的旅行商问题 1 6 江苏大学硕士学位论文 编码( 1 ) 基于由5 个城市编号按访蚓顿序组成的字符集：编码( 2 ) 是二进制编 码，其中= 1 表示a 、b 之间的路径被走过，= o 表示a 、c 之间的路径未 被走过。显然编码( 2 ) 容易满足最小字符集编码规则，但容易生成无意义的个体 ( 1 的个数超过5 个) ，而编码( 1 ) 则容易满足编码规则( 1 ) 。 遗传算法的几种常用编码技术如下： 1 二进制编码 二进制编码是最常使用的编码方案，它具有其它编码方案无法比拟的优点： ( 1 ) 简单易行； ( 2 ) 符合最小字符集编码规则( 只有0 和1 两个字符) ； ( 3 ) 能表达的模式数最多，便于用模式定理进行分析。 应用二进制编码时，要先根据所要求的解的精度确定染色体的串长。对于多 参数优化问题，可将各个参数分别用长度符合要求的串来表示，然后再将各子串 顺序连接起来作为解的染色体串。该字串即可作为遗传算法的操作对象。 需要说明的是，对于离散变量采用二进制编码需要格外小心。例如假设变量 z 有1 0 个离散值，则至少需要4 位二进制码，但4 位二进制串共有1 6 个离散值， 那么多余的6 个必须进行相应处理( 如某些变量被重复表示) ，否则就会出错。 尽管二进制编码是求解优化问题的首选，但它也存在缺点。如高维优化问题 的字串太长、效率太低、算法缺乏微调功能以及h a m m i n g , 悬崖( 考虑7 和8 的二进 制表示0 1 1 1 和1 0 0 0 算法从7 进化到8 就必须改变所有的位) 。 2 格雷( g r a y ) 编码 格雷编码即是将二进制编码通过一个变换而得到的编码，其目的是克服二进 制编码中的h a m m i n g 悬崖。设有二进制串b i b 2 吒，对应的c , r a y $ 为a l a 2 ， 则从二进制码至l j g r a y 的变换为： 铲k 乞4 臻嘉( 3 - 1 ， 其中0 表示模2 加。 而从一个g r a y 串到二进制串的变换为 6 = q ( m o d 2 ) ( 3 2 ) 3 动态编码 1 7 江苏大学硕士学位论文 动态编码是当算法收敛到某局部值时增加搜索的精度，即在保持串长不变的 前提下，减小搜索区域。 4 实数编码 对于问题的变量是实向量的情形，可以采用十进制进行编码，这是一种“没 有编码”的编码，这样便可以直接对解进行操作。试验证明，对于大部分的数值 优化问题，通过一些专门设计的遗传算子的引入，采用实数编码比采用二进制编 码的效率要高。这是因为，个体编码串的长度较短时，二进制编码可能达不到解 的精度要求；而个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传 算法的搜索空间急剧扩大。其次，二进制编码也不便于反应所求问题的特定知识。 目前，基于实