（控制理论与控制工程专业论文）混合式遗传算法的研究与应用.pdf

哈尔滨工程大学硕： 学位论文 摘要 遗传算法由美国密执安大学的j o h n h o l l a n d 教授首先提出，以达 尔文的生物进化论为启发而创建的，是一种有效的全局优化技术。本 文首先介绍了遗传算法的基本原理，并针对标准遗传算法在实际应用 中存在的问题进行了细致的分析。同时参考了大量的文献。根据前人 的研究成果结合在p i d 参数寻优中实际应用，得出标准遗传算法不是 全局收敛的，容易出现“早熟现象”。为了改进这种情况，本文提出了 几种改进的方案，并将其应用蓟p i o 参数寻优中，效果比较明显。但 在实际应用中遗传算法还存在另一个问题即在迭代末期收敛速度比较 慢，导致计算效率下降。单纯形法是一种局部优化技术，它可以在不 了解函数特性的情况下，使寻优结果向局部最优值靠近，但其存在着 一个弊端即对初始值比较敏感。基于此思想本文将遗传算法和单纯形 算法有机的结合起来，提出了两种改进的措施，并将其与基本遗传算 法进行比较，最后得出一个满意的结果。 关键字：标准遗传算法( s g a ) ，扩散式遗传算法( s c g a ) ，单纯形 哈尔滨工程大学硕十学位论文 1 a b s t r a c t g e n e t i ca l g o r i t h mi sd e v e l o p e db yj o h n h o l l a n dw h oi sap r o f e s s o r i nm i c h i g a nu n i v e r s i t yi nu n i t e ds t a t e ，b a s e do nd a r w i n st h e o r yo f e v o l u t i o n i ti sa ne f f i c i e n to p t i m a lt e c h n o l o g y t h i sp a p e ri n t r o d u c e st h e e l e m e n t a lt h e o r yo ft h eg e n e t i ca l g o r i t h ma tf i r s t ，a n dg i v e sad e d i c a t e a n a l y s i s t ot h ep r o b l e mw h i c hi sf o u n dw h e nw eu s et h e g e n e t i c a l g o r i t h mt oo p t i m i z et h ep a r a m e t e ro ft h e ：p i dc o n t r o l l e r a c c o r d i n gt o t h ea c h i e v e m e n to f p r e d e c e s s o r a n dt h e a p p l i c a t i o no ft h e g e n e t i c a l g o r i t h mo p t i m i z i n gt h ep a r a m e t e ro ft h ep i dc o n t r o l l e r ，w en o t i c et h a t t h es t a n d a r dg e n e t i ca l g o r i t h mi sn o tag l o b a l l yo p t i m a tt e c h n o l o g y ，a n d e a s i l yf a l i e ni nt h e “t h e ：e a r l y m a t u r i n gp h e n o m e n o n ”i nt h i sp a p e r ，w e g i v e st h es t r i c tt e s t i f yb a s e do nt h em a r k e rc h a i n f o rs o l v i n gt h i s p r o b l e m ，w ed e v e l o ps o m en e wa l g o r i t h m so ft h eg e n e t i ca l g o r i t h ma n d u s et h e mt ot h eo p t i m a lo fp i dp a r a m e t e r t h er e s u l ts h o w st h a tt h e ya r e b e t t e rt h a nt h es t a n d a r dg e n e t i ca l g o r i t h m b u tt h e r ei sa n o t h e rp r o b l e m o nt h ea p p l i c a t i o no ft h eg e n e t i ca l g o r i t h mw h i c hi st h er a t eo f c o n v e r g e n c e i s t o ol o w t h e s i m p l e x o p t i m a l m e t h o di sa n o t h e r o p t i m i z i n gt e c h n o l o g yw h i c hc a nf i n dal o c a lb e s ts o l u t i o nw i t h o u tt h e c h a r a c t e ro ff u n c t i o n b u tt h e r ee x i t sa l s oap r o b l e mi nt h es i m p l e x o p t i m a lm e t h o dw h i c hi st h er e s u l ti se a s i e ri n f l u e n c e db yt h ei n i t i a l v a l u e s b a s e do nt h ec h a r a c t e r so ft h es i m p l e xo p t i m a lm e t h o da n dt h e g e n e t i ca l g o r i t h m , w ed e v e l o ps o m en e wg e n e t i ca l g o r i t h m sf o rt h e o p t i m i z i n gt e c h n o l o g y t h e s en e w g e n e t i ca l g o r i t h m sc o m b i n et h ec l a s s i c g e n e t i ca l g o r i t h ma n dt h es i m p l e xo p t i m a lm e t h o d a tl a s t ，w eu s en e w g e n e t i ca l g o r i t h ma n dt h ec l a s s i cg e n e t i ca l g o r i t h mt oo p t i m i z et h e p a r a m e t e ro fp i dc o n t r o l l e r ，r e s p e c t i v e l y 。c o m p a r i n gt h e i rr e s u l t s ，w e f i n dt h a tt h en e wg e n e t i ca l g o r i t h mi sd i s t i n c t l yb e t t e rt h a nt h ec l a s s i c g e n e t i ca l g o r i t h m k e y w o r d ：s t a n d a r dg e n e t i ca l g o r i t h m ，s c a t t e rg e n e t i ca l g o r i t h m s i m p l e x 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献等的 引用已在文中指出，并与参考文献相对应。除文中已经注明 引用的内容外，本论文不包含任何其他个人或集体己经公开 发表的作品成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律 结果由本人承担。 作者( 签字) ： 级叁 日期：2 0 0 5 年0 5 月2 0 日 堕笙堡上堡叁= i 三堡兰笪笙墨 第1 章概述 随着科学的发展和社会的进步，人类面临的问题越来越多，这些 问题的难度也越来越大。其中，在工程技术领域中的参数优化就是一 类典型的问题。迄今为止，我们已有许多的优化方法。如：间接寻优 法，梯度法，爬山法等，这些方法针对不同的对象都表现出不同的特 点。然而，这些方法在应用中都或多或少的表现出一些弊端如：变 量梯度法需要函数可微，单纯形法对初始值比较敏感等。为了找到一 个更好的寻优技术，人们在不断的探索着。 1 1 遗传算法的诞生与发展 2 0 世4 0 年代以来，科学家不断努力从生物学中寻找用于计算科 学和人工系统的薪思维、新方法，比如早期的自动机理论就试图采用 类似神经元的元素建造一种新型的思维机器。很多学者提出了关于从 生物进化和遗传的机理中发展出适合与现实世界复杂适应系统研究的 计算方法自然进化算法和模拟进化算法等，进行了开拓性的长期探 索和研究。美国人j o h n h o l l a n d 及其学生首次提出韵遗传算法就是一 个重要的发展方向。 遗传算法是从大自然的杰作生物进化论中得到的灵感和启迪 1 ， 地球上的生物在漫长的进化过程中，逐渐从最简单的低级生物一直发 展到万物之灵的人类，这是一个绝妙的优化过程，并且是已经由古生 物学、胚胎学和比较解刹学等方面的研究工作所证实的。生拐进化的 原因从古到今有着各种不同的解释，其中被人们广泛接受的是达尔文 的自然选择学说 2 卜 5 。达尔文的生物进化论说明，生物进化经历突 变、自然选择、和隔离等过程的逐渐分化，而得以发展成为新物种。 这一奇迹并非来自神创，而是一个“物竟天演，适者生存”的自然选 择过程的必然结果，生物要生存下来就必须将进行生存斗争。生存斗 争包括种内斗争、种问斗争、以及生物跟无机环境之间的斗争三个方 面。生存斗争中，具有适应性强的个体容易存活下来，并且有更多的 哈尔滨r 程大学硕士学位论文 机会将有利变异传给后代；具有不利变异的个体就比较容易被淘汰， 产生后代的机会也少得多。因此凡是在生存斗争中获胜的个体都对环 境是适应性比较强的 6 。达尔文把这种，在生存斗争中适者生存，不 适者淘汰的过程叫做自然选择。 达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在 因素。遗传是指父代与子代之间，在性状上存在的相似现象。变异是 指父代与子代之间以及子代个体之间在形状上或多或少的存在的差异 现象。生物的各项生命活动都由他的生物基础，生物的遗传与变异也 是这样。根据现代细胞学和遗传学的研究得知，遗传物质的主要部分 保存在染色体中，染色体主要是由d n a ( 拖延核糖核酸) 和蛋白质组 成，其中d n a 又是最主要的遗传物质。现代分子水平的遗传学研究又 进一步证明，基因是由遗传效应的片断，它存储的遗传信息，可以精 确的复制，也可以发生突变，并可以通过控制蛋白质的合成而控制生 物的性状。生物体自身通过对基因的复制和交叉即基因分离、基因自 由组合和基因连锁呼唤的操作使其性状的遗传得到选择和控制。同时， 通过基因重组、基因变异和染色体在结构和数目上的变异产生丰富多 彩的变异现象 7 一 1 5 。 需要指出的是，根据达尔文进化论，多种多样的生物之间所以能 够适应环境而得以生存进化，是和上述的遗传和变异生命现象分不开 的，生物的遗传特性，使生物界韵物种保持相对稳定，生物的变异特 性，使生物个体产生新的性状，以至形成了新的杨种，推动了生物的 进化和发展。那么，能否将“自然选择”这一法则，用于科学研究和 工程实际中的种种搜索和优化阎题中? 遗传算法正是从这一疑问开始 的 1 6 。 h o l l a n d 的早期工作主要集中于生物学、社会学、控制工程、人 工智能等领域中的一类动态系统的适应性问题，其中适应性概念描述 了在环境中表现出较好行为和性能的系统结构的逐渐改变过程，简称 系统的适应过程。h o l l a n d 认为，通过简单的模拟机制可以描述复杂 的适应性现象。因此h o l l a n d 试图建立适应过程的一般描述模型，并 在计算机上开展模拟实验研究，分析自然系统或者人工系统对环境变 2 晗自i 滨j 棒人学硕十学位论文 化的适应性现象，其中遗传算法仅仅是一种具体的算法形式 1 7 卜 2 0 。 b r e m e r m a n n ，d ej o n g 等人则注重将遗传算法应用于参数优化问 题，极大地促进了遗传算法的应用。所以，遗传算法既是一种自然进 化系统的计算模型，也是一种通用的求解优化问题的适应性搜索方法。 目前，人们最关注和普遍使用的遗传算法是其后一种性质 2 1 卜 2 r 。 从整体上来讲，遗传算法是进化算法中产生最早、影响最大、应 用也比较广泛的一个研究方向和领域，它不仅包括了进化算法的基本 形式和全部优点，同时还具备若干独特的性能： 1 、在求解问题时，遗传算法首先要选择编码方式，它直接处理的 对象是参数的编码集而不是问题参数本身，搜索过程既不受优化函数 连续性的约束，也没有优化函数导数必须存在的要求，通过优良染色 体基因的重组，遗传算法可以有效的处理系统上非常复杂的优化函数 求解问题。 2 、若遗传算法在每一代对群体规模r l 豹个体进行操作，实际上处 理了大约o ( n 3 ) 个模式，具有很离的并行性，因而具有显著的搜索效率。 3 、在所求解问题为非连续、多峰以及有噪声的情况下能够以很大 的概率收敛副最优解或满意解，因而具有较好的全局最优解求解能力。 4 、对函数的形态无要求，针对某一问题的遗传算法经简单修改即 可适应与其它问题，或者加入特定问题的领域知识，或者与以有算法 相结合，能够较好地解决一类复杂问题，因而具有较好的适应性和易 扩充性。 5 、遗传算法豹基本思想简单，运行方式和实现步骤规范，便于具 体使用。 鉴于遗传算法具有上述特性，一经提出即在理论上引起了高度重 视，并在实际工程技术和经济管理领域得到了广泛的应用，产生了大 量的成功案例 2 8 卜 3 0 。 1 9 6 2 年，j o h nh o l l a n d 在o u t l i l i ef o ral o g i ct h e o r yo fa d a p t i v e s y s t e m s 一文中提出了所谓监控程序的概念，即利用群体进化模拟适 3 哈尔滨r 群人学颂十产位论文 应性系统的思想。他注意到在建立智能机器的研究中，不仅可以完成 单个生物体的适应性改进，而且通过个种群的许多代的进化也可以 取得非常好的适应性效果。为了获得一个好的学习方法，仅靠单个策 略的改进是不够的，采用多策略的群体繁殖往往能产生显著的学习效 果。尽管他当时每给出实现这些思想的具体技术，但却引进了群体、 适应值、选择、变异、交叉等基本概念。1 9 6 6 年，f o g e l 等人也提出 了类似的思想，但其重点是放在变异算子。1 9 6 7 年，j d b a g l e y 通过 对跳棋游戏参数的研究，在其博士论文中首次提出了“遗传算法”一 词。 3 1 一 4 0 3 同时，f r a s e r 采用计算机模拟自然遗传系统，1 9 6 2 年提出了和现 在的遗传算法十分相似的概念与思想。 在2 0 世纪6 0 年代中期至7 0 年代末期，基于自然进化的思想遭到 怀疑和反对。h o l l a n d 及其数位博士坚持了这一方向的研究。在 h o l l a n d 发表论文后的十余年中，从事遗传算法豹论文慢慢出现。大 多数研究都集中在美国m i c h ig a n 大学的h 0 1 1 a n d 及其学生当中。因此， 遗传算法的大多数著名学者多数是m i c h i g a n 大学豹学生。1 9 7 5 年 h o l l a n d 出版了专著自然与人工系统的适应行为，该书系统的阐述 了遗传算法的基本理论和方法，提出了对遗传算法的理论发展极为重 要的模式理论，其中首次确认了交叉、选择、变异等算子，以及遗传 算法的引并行性，并将遗传算法应用于适应性系统模拟、函数优化、 机器学习、自动控制等领域。 另外，d a n i e lj 。c a v i c c h i 0 的博士论文中探讨了一组实验，将基 于整数编码韵遗传算法应用与模式识别问题。研究了保持群体差异性 的选择策略，d ej o n g 在其博士论文研究中首次将遗传算法应用到函 数优化中，并对遗传算法韵机理与参数设计问题进行了较为系统的研 究。1 9 7 5 年以后，遗传算法作为函数优化器不但在各个领域得到广泛 应用，而且还丰富和发展了若干遗传算法的基本理论。1 9 8 0 年，b e t h k e 对函数优化遗传算法进行了系统的研究，包括应用研究和数学分析， 在数学分析方面主要应用了随机过程理论。s m i t h 在1 9 8 0 年首次提出 使用变长位串的概念，这在某种程度上以为咀后的遗传规划奠定了基 4 哈尔滨i 程人学硕十1 位论文 础 4 1 卜 4 5 。 1 9 8 9 年，i ) a v i d6 0 ld b e r g 出版了g e n e t i ca l g o r it h mi n s e a r c h o p t i m iz a t i o na n dm a c h i n el e a r n in g 。书，这是第一本 遗传算法的教科本，它是对当时关于遗传算法领域研究工作的全面而 系统的总结，因而成为引用最多的参考书之。1 9 9 1 年，d a y is 编辑 出版了h a n d b o o ko fg e n e t i ca l g o r i t h m s ，其中包括了遗传算法在 工程技术和社会生活的大量的实际例子 4 6 。j o h nr k o z a 将遗传算 法用于处理不定长树形字符串或一组程序，提出了遗传规划的概念。树 状表示方法是k o z a 教授于1 9 8 9 年首次提出的，这种表示方法的主要特 点之一就是染色体结构是动态变化的层次结构，它受环境的影响而改 变，因而对问题的表示更加自然，该方法是一种与领域无关的自适应搜 索解空间的有效方法 4 7 。通过增加染色体结构的复杂性，它拓广了传 统遗传算法韵应用范围 4 8 。 1 9 9 2 年，k o z a 博士出舨了第一本遗传规划专著g e n e t i c p r o g r a m m i n g1 。髓着遗传算法研究和应用的不断深入与扩展。1 9 8 5 年，在美国召开了第一届遗传算法国际会议，即i c g a 这次会议是遗传 算法发展的重要里程碑，此会以后每隔一年举行一次。从1 9 9 9 年起 i c g a 和g p 的系列会议合并为每一年一次的遗传和进化国际会仪 ( g e c c o ) 。1 9 9 4 年1 月，i e e e 神经网络委员会出版了第一本迸化计算 专集。1 9 9 4 年6 月i e e e 神经网络委员会召开第一届“进化计算”国 际会议，以后每年举行一次 4 9 卜 5 2 。 这些众多的研究单位和频繁的国际学术会议集中的反应了遗传算 法的学术意义和应用价值。目前，遗传算法以成为了一个多学科、多 领域的重要研究方向。 1 2 单纯形优化技术 非线性单纯形法是一种多维直接搜索法，是求解非线性函数的无 约束极值的一种经验方法。1 9 6 2 年由s p e n d l e y 、h e x t 、h i m s w o r t h 等 人提出。单纯形法是一种可以在不知到函数特性的情况下，使结果向 最优解靠近的优化方法，是一种直接搜索方法。它不需要探询搜索的 哈尔滨i1 样人学硕七学位论文 有利方向，而是求解单纯形的各个顶点的函数值，并加以比较，丢掉 最坏点，代之以新点，如此迭代直至达到局部最优解。单纯形法的基 本操作是反射操作，且反复进行。这十分类似于遗传算法的“交叉操 作”。同时单纯形法和遗传算法在点数上相当于遗传算法中群体大小。 显然，单纯形法和遗传算法在利用多点信息的全局处理是共同点的。 该方法有较强的鲁棒性，对函数没有太多的要求。但它存在一个在致 命的缺点，就是结果对初始点的位置特别敏感，即对初始值的适应性 比较差。对于初始值的微妙差别，可能会引起搜索结果的巨大变化。 对于同一个问题，根据所绘的初始点的不同，其最终结果有较大的不 同，如此导致单纯形法很容易陷入局部最优解。这一缺点也是阻碍 它发展的主要障碍。 1 ，3p i _ d 控栽器的应用 p i d 控制是工业过程控制中应用最广泛韵策略之一，在本世纪4 0 年代以前，除在最简单的情况下可采用开关控制外，它是唯一的一种 控制方式。以后。随着科学技术的发展特别是电子计算机的诞生和发 展，涌现出了许多新的控制方法。然而直到现在，p i d 控制由于本身 的优点仍是最广泛应用的控制方式，传统舱p i d 调节器参数是采用实 验加试凑的方式由人工整定豹 5 4 。这种整定工作不仅需要熟练的技 巧，而且往往还相当费时，更重要钓是当被控对象特性发生变化需要 调节器参数相应的变化时，p i d 控制器没有这种“自适应”能力，只 能依靠人工重新繁定参数。由于生产过程的连续性和参数整定所需要 的时间，这种重整定的方法实际是难以实现的，甚至是不可能的”1 。因 此近年来p i d 参数整定问题是一个比较热门蚤勺话题 5 5 。 p i d 控制器具有结构简单、实现方便、鲁棒性强、易于操作调整、 效果满意的特点，并且人们对其原理和物理意义等都比较熟悉，已经 建立了比较完善的理论体系，尤其在工业现场控制过程中应用尤为普 遍，特别是用于对象特性未完全掌握、得不到精确数学模型、难以用 控制理论来进行分析和综合的场合。而且由于工业现场计算机控制的 普遍应用，要求对离散控制器的设计也越来越多。基于此种状况，就 6 喻尔滨l ：样人学硕t 学位论文 有必要设计一种通用的控制器来满足不同的现场要求。 离散的p i d 控制器正是满足这一要求的最佳候选。离散的d i d 控制 器广泛地应用于冶金、机械、化工、热工、轻工、电化等工业过程控 制之中。p i d 控制也是迄今为止最通用的控制方法。近年来，人们为它 的发展和推广做出了巨大的努力，使之成功为工业过程控制中主要的 和可靠的技术方案和工具。在p i d 控制中，一个至关重要的问题是p i d 参数( 比例系数、积分时间、微分时间) 的整定，典型的p i d 参数整 定方法是在获取对象数学模型的基础上，根据某一整定原则来确定p i d 参数。参数整定的优劣不但会影响到控制质量，而且还会影响到控制 系统的稳定性和鲁棒性。由于现代工业过程的复杂性、多样性、多变 性与不确定性，都将可能造成模型参数变化和模型结构韵改变，致使 系统不能在原所整定的工况下工作，偏离控制性能指标。据文献 1 介绍：在一篇关于加拿大造纸厂的统计报告中表明，一座典型的造纸 厂一般有2 0 0 0 多个控制回路，其中9 7 以上的回路采用p i d 控制，但仅 有2 0 的控制回路工作比较满意，控制回路性能普遍偏差的原因中，参 数整定不合适占3 0 ；阀门问题占3 0 ；传感器问题、采样频率选取问 题、滤波问题等占2 0 。由此可见在工业过程控制中对p i d 控制技术的 研究仍然是一个重要的课题和任务。 水转鉴于以上所述，过程控制中韵干扰与不确定性影响了p i d 的参 数。人们将自适应控制原理结合常规p i d 控制技术，形成了自适应 p i d 控制。自适应p i d 控制系统除具有常规p i i ) 的优点外，其可利用其中 的可调系统的各种输入、状态和输出来度量某个性能指标，将所测得 的性能指标与规定的性能指标相比较，由自适应机构来修正可调系统 的参数( kp 、k i 、kd ) 或者产生一个辅助韵输入信号，以保持系统 的性能指标接近规定的指标，使系统达到最优或次优的控制效果。在 这个控制器中，它能够自动辨识被控过程参数、自动整定控制器参数、 自动适应被控过程参数的变化，并兼有两者的优点，成为过程控制中 一种较理想的自动化装置。参数自适应p i d 控制和非参数p i d 控制是 近年来人们硪究的主要课题。非参数自适应p i d 控制器不需要在线辨 识被控系统的模型参数，从而回避了许多难以解决韵难题。在造纸业 7 哈尔滨l ? 群人学硕十_ 学位论文 中的定量水分控制、热泵供汽控制、纸浆浓度控制、上网流送过程控 制、浆处理过程控制、纸机传动控制、d c s f e 4 浆造纸过程集散控制等等 过程控制中，已开始引入自适应p i d 和智能p i d 控制技术，并且已取得 好的效果。 p i d 控制算法是迄今为止最通用的控制策略，自适应控制技术和智 能控制技术的引入应用，使p i d 控制进入了一个更为深入和广阔的应用 天地；仿生学控制理论结合到p i d 控制中使由此构成的控制器的控制性 能更趋完善，有着相当好的动态控制特性和强的鲁棒性。勿容置疑， 智能p i d 控制技术将随着传感器集成化程度的提高，随着价廉物美的微 处理器( 例如p i c 、d s p 等) 的运算速度的大幅度增加( 其信号采集、 信号处理、信息融合、数据通讯等功能将更为强大) ，必将是过程控 制中极有发展前途的研究和应用方向。 1 4p i d 参数的优化方法 p i d 参数的优化问题是一个比较常见的且非常重要的问题。用参 数寻优方法设计离散p i d 控制器有很多方法，例如：最速下降法、共 轭梯度法和单纯形法。但是以梯度为基础的多边量寻优方法，都要求 计算目标函数q ( a ) 梯度，而实际问题中往往得不到其梯度的形式。因 此采用这种方法寻优时，只能用近似的方法计算梯度的值。这样会产 生很大的误差，计算量也很大。 为了避免计算梯度，产生了许多计算目标函数的寻优方法，即模 式寻优法。所谓模式寻优法，就是直接根据目标函数的信息来确定寻 优方向钓方法。而其中单纯形法韵理论比较成熟，所以本文采用此方 法。单纯性法利用单纯形的定点计算目标函数值，按一定规则进行探 索性搜索，并对搜索区间钓单纯形定点的函数值进行比较，判断目标 函数的变化趋势，确定有利钓搜索方向和步长。但由于单纯形法存在 着对初始值敏感的缺点，所以不适合单一利用单纯形算法进行优化。 本文结合最新的遗传进化技术和单纯形方法，经过大量的实验提出了 几种混合式的寻优方法。该方法将遗传算法和单纯形方法有机的结合 起来，并在它们的基础上对其进行了改进，经过改进的方法克服原有 哈尔滨程大学硕七学位论文 的缺点和不足，使混合算法可以在较短的时删内给出更加精确的参数 值，将所得参数应用到实际的系统中，结果非常理想。 1 5 本章小结 本章首先简要叙述了遗传算法发展史。遗传算法是从大自然的杰 作生物进化论中得到的灵感和启迪，它根据生物进化的原理，按照“优 胜劣态适者生存”的原则对目标函数进行优化。经过多次迭代计算， 得到最有结果。遗传算法不需要知道函数的特性，可以对任意函数进 行优化，这一特点是一般优化方法所不能比拟的。单纯性算法是一种 经典的优化方法，该方法不需要知道函数的特性，对函数没什么要求。 可以迅速求出函数的局部最优解。但该方法存在着一个再大的缺点， 就是对初始值非常敏感，这也是阻碍其广泛应用的主要原因。p i d 控 制是一种古老的控制技术，它结构简单，易于实现而且效果明显，所 以在工业中得以广泛应用。本章简要豹叙述了p i d 控制技术的发展史 和现状，以及在工业中韵应用。 9 堕尘堕! ：型叁堂堡主兰垡堡墨 第2 章遗传算法的基本原理 遗传算法在整个进化过程中的遗传操作是随机性的，但它所呈现 出的特性并不是完全随机搜索，它能有效的利用历史信息来推测f 一 代期望能有所提高的寻优点集。这样逐代的不断进化，最后收敛到最 适应环境的个体上，即所求问题的最优解。整个搜索过程是一个平稳 的随机过程。遗传算法涉及到五大要素：参数编码、初始种群的设定、 适应度函数的设计、遗传操作的设计和控制参数的设计。这些要素构 成了遗传算法的主体框架。五大要素中最重耍的是参数编码和遗传操 作的设计。参数编码决定了算法的计算效率，遗传操作决定了算法的 优化成功与否。遗传操作主要由三部分组成：选择操作、交叉操作和 变异操作。它们分别描绘了生物进化的不同过程。遗传算法所操作的 对象不是参数本身，而是其编码值。对应每一个编码串称其为一个染 色体，每一位叫做一个基因。 2 。1基本甩语 由于遗传算法是自然遗传学和计算机科学相互渗透而成的新的计 算方法，所以遗传算法经常是有关自然进化中的一些基础用语。如前 所述，生物的遗传物质的主要载体是染色体，9 n a 是其中最主要的遗 传物质，而基因又是控制生物性状的遗传物质的功能单位和结构单位。 复数个基因组成染色体，染毡体中基因的位置称为基因座，而基因所 取得值叫做等位基因。基因和基因座决定了染色体的特征，也就决定 了生物个体的性状。此外，染色体有两种相应豹表示模式，即基因型 ( g e n e t y p e ) 和表示型( p h e n o t y p e ) 所谓表现型是指生物个体所表示出 来的性状，而基因型指与表现型密切相关的基因组成。同一种基因型 的生物个体在不同韵环境条件下可以有不同构表现型，因此表现型和 基因型与环境条件相互作用的结果。在遗传算法中，染色体对应的是 数据或数组。在标准的遗传算法中，这通常是由一维的串结构数据表 示的。串上各个位置对应上述的基因座，而各个位置上所取得值对应 哈尔滨i ，样人学硕| 掌位论文 上述的等位基因。遗传算法处理的是染色体，或者叫基因型个体。一 定数量的个体组成了群体，也叫集团。群体中个体的数目称为群体的 大小，也叫群体规模。而个体对环境的适应程度叫做适应度。 此外，执行遗传算法时包括两个必需韵数据转换操作，一个是表 示型到基因型的转换，另一个是基因型到表示型的转换。前者是把搜 索的空间中的参数或解转换成遗传空间中的染色体或个体，此过程又 叫编码操作；后者是前者的一个相反操作，叫做译码操作。 2 2 遗传算法的流程 我们通常采用的遗传算法的工作流程和结构形式是g o l d b e r g 在 天然气管道控制优化应用中首先提出的，一般称为标准遗传算法 ( s t a n d a r dg a 简称s g a ) 。具有“生成+ 检测”的迭代过程的搜索算法。 它的基本处理流程如母( 2 1 ) 。 由图我们可以看出遗传算法是一种群体型操作，该操作以群体中 的所有个体为对象。选择( 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 ) 是遗传算法的3 个主要操作算子，它们构成了所有的遗 传操作，使遗抟算法具有个传统算法所不具有的特点。遗传算法的运 行过程为一个典：型的迭代过程，其必须完成的工作和内容豹基本步骤 如下： 1 ) 选择编码策略，香巴参数集合x 和域转换位串结构空间s ； 2 ) 定义适应值函数f ( x ) ： 3 ) 确定遗传策略，包括选择群体大小n ，选择、交叉、变异方法， 以及确定交叉概率p c 、交异概率p m 等遗传参数： 4 ) 随机初始化生成群体p ； 5 ) 计算群体中个体位串解码后的适应值f ( x ) ； 6 ) 按照遗传策略，运用选择、交叉和变异算子作用与群体，形成 下一代； 7 ) 判断群体性能是否满足某一指标，或者已完成预定迭代次数， 不满足则返回步骤6 ) ，或者修改遗传策略再返回步骤6 ) ： 堕丛鎏! 型查堂堡堂笪笙墨 图2 1 标准遗传算法的流程图 2 3 参数编码 由于遗传算法不能直接处理解空间的解数据，因此我们必须通过编 码将它们表示成遗传空间的基因型结构数据。经典遗传算法多采用二 进制表示形式。该编码形式得到了t t o l l a n d 早期理论结果( s c h e m a 定 理、最小字母表原理) 的支持，但它仍然有许多不足之处。灰色编码 可用于克服二进制编码映射的不连续问题( 即欧式空间中临近点的二 进制编码在h a m m i n g 距离下并不临近) 。动态参数编码( d y n a m i c p a r a m e t e re n c o d i n g ) 的提出是为了克服搜索效率与表示精度间的矛 盾，同时对克服过早收敛想象也有所帮助。实数编码对于函数优化问 题最有效。对于实数编码在函数优化和约束优化领域比二进制编码和 啥尔滨l 程大学颂十学位论文 灰色编码更有效的说法，已经得到广泛的验证。由于实数编码基因型 空问中拓扑结构与表现型空嵋j 中的拓扑结构一致，因此很容易从传统 优化方法中借鉴好的技巧来形成有效的遗传算子。整数和字母排列编 码( 1 i t e r a lp e r m u t a t i o ne n c o d i n g ) 对于组合优化问题最为有效。 由于组合优化问题最关键的是要寻找满足约束项目的最佳排列或组 合，因此字母排列编码对于这类问题是最有效的方法。对于更为复杂 的现实问题，用合适的数据结构来表示基因的等位基因，可以有效抓 住问题的本质。在这种情况下，基因可能是1 3 维数组或更为复杂的数 据结构。从以上所述可以看出，编码的方式有很多种，但这些编码方 法的提出是启发式的，均缺乏理论基础来判断各种编码方法的好坏并 指导它们的设计。 根据编码的结构，编码方法还可以分成为如下两类：( 1 ) 一维编码 ( o n e d i m e n s i o n a e n c o d i n g ) ，( 2 ) 多为编码( m u l t i d i m e n s i o n a l e n c o d i n g ) 。大多数实践中采用了一维编码。然而许多实际问题需要多 维结构的解，用多维编码方法来表示这些解就很自然。根据编码的内 容，编码方法还可以看作如下两类：( 1 ) 仅包括解，( 2 ) 包括解和参 数。在遗传算法实践中，第一种方法被广泛用来针对给定的问题开发 合适的编码。第二种方法在r e c h e n b e r g 和s c h w e f e l 提出的进化策略 中被采用。一个个体包含两个部分：首先是给定问题的解，其次是策 略参数，包括变异中正态分布的方差和协方差。将策略参数并进个体 中表示的目的是通过将进化算子应用于这些参数来促进它们的进化自 适应性。因此搜索就在解空间和进化参数上同时进行。通过这样方法， 可以在任意环境下获得变异参数的合理调熬和爹样性。 编码的不可行性和非法性。遗传算法交替啻勺在编码空间和解空间中 进行操作。换句话说，也就是交替的在基因型空间和表示型空间中进 行操作。遗传算子作用于基因型空间中，而评价和选择则作用于表现 型空间中。自然选择连接了染色体和编码产生的解的性能。从基因型 空间到表现型空间中。自然选择连接了染色体和编码产生的解的性能。 从基因型空间到表现型空目的映射对于遗传算子的性能有很大影响。 其中一个与映射相关的重要问题就是某些个体对应着给定那个问题的 1 3 哈尔滨i 样人学硕十学位论文 不可行解。对于约束最优化和组合最优化问题而言，这个问题可能很 严重。不可行性指的是某个染色体编码出来的解在给定问题的可行区 域之外的现象。而非法性指的是某染色体不能代表给定问题的解得现 象。 染色体的不可行性起源于约束优化问题。无论是采用传统方法还是 遗传算法，都必须处理约束。对于许多问题来说，可行区域可以表示 为由等式和不等式组成的系统。在约束优化问题中，最优解常常陷在 可行与不可行区域的交界处。罚方法可以迫使遗传搜索分别从可行和 不可行区域两个逼近最优解。 染色体的非法性起源于编码方式。对于许多组合优化问题来说， 通常采用的是依赖于问题的编码方式。这种编码当采用简单的单点杂 交处理操作时通常会产生非法后代。由于非法染色体不能被解码为一 个解，罚方法无法处理这种情况。修补方法通常用来将非法染色体转 换为合法。o r v o s h 和d a v i s 的研究表明，对于组合优化问题来说，修 补不可行或非法的染色体相对较容易，而且修补策略的效果比其他诸 如抛弃法或罚方法要好。 2 4 初始种群的设定 由于遗传算法的群体型操作需要，所以我们必须为遗传操作准备一 个由若干初始解组成的初始群体。通常初始种群采用随机生成的形式。 初始种群豹数量一般要根据染色体的长度而定。较长的染色体需要更 多的初始种群，但过多的初始种群会增大计算量。另外，如果种群数 目过多，遗传算法的搜索过程将会趋近于髓机搜索的过程，这样算法 也将会失去其意义。 2 5 适应度函数的设计 遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函 数值来评估个体或解的优劣，并作为阻后遗传操作的依据。评估函数 值又称做适应度( f i t n e s s ) 。评估函数即是我们要优化的指标函数， 其可以是任意形式的函数。 堕! ! 蔓! ：型查堂堡堂笪笙苎 2 6 遗传操作的设计 当很难获得问题的求解步骤时，搜索就成为更为广泛的问题求解方 法之一。两种有代表性的搜索行为：随机搜索和局部搜索。随机搜索 ( r a n d o ms e a r c h ) 广泛搜索整个解空间并且能够从局部最优中逃离。 局部搜索( 1 0 c a ls e a r c h ) 深度搜索最优解并且能够依据局部最优解 进行爬山。这两种搜索能力构成了整个搜索彼此互补的组成部分。理 想的搜索应该同时具有这两种性质。采用传统方法来设计这样的理想 搜索方法可以在对搜索空间进行深度搜索和广度搜索之间维持很好的 平衡。在遗传算法中，由选择机制来深度搜索积累的信息，由遗传算 子来广度搜索解空间中新的区域。 在传统遗传算法中，杂交算予被用作主要的算子，遗传系统的性能 在很大程度上依赖于杂交算子的性能。变异算子在各个染色体中自动 产生随机变化，通常被用作次要的算子。从本质上讲，遗传算子执行 的是随机搜索，不能保证产生改进的后代。已经发现对于许多大规模 组合优化问题，遗传算法的搜索速度很慢。对于杂交和变异有许多经 验式的研究。关于变异优势比较杂交更重要的论断已经得到确认。 关于解释遗传算法是如何搜索分布式信息来产生优秀个体存在两 个假设：( 1 ) 积木块( b u i l d i n g - b l o c k ) 假设，( 2 ) 受控收敛偏差假 设。积木块假设有h o l l a n d 提出，并由g o l d b e r g 加以改进。根据该 假设，杂交算子重组两个父代的特性来产生子代。有时杂交会重组两 个父代的最好特性并产生优秀的子代。由于个体的适应值不同通常依 赖于简单性质的复杂模式，因此算子能够把对父代适应值有所贡献的 这些模式传播给子代就显得非常重要。 受控偏差收敛假设由e s h e l m a n ，m a t h i a s 和s c h a f f e r 提出。该假 设认为应利用种群收敛的程度来指导搜索。新的点从某一分布中进行 采样。随着种群逐渐收敛，偏差变得越来越小。积木块假设强调在父 代种群中保留的性质的重组与传播，而受控收敛假设则强调从当前种 群的分布函数中进行随机采样。 如何概念化遗传搜索将对遗传算子的设计产生重大影响。从搜索能 哈尔滨i 。科人学硕+ 学位论文 力的角度出发，期望设计出能够同时具有随机搜索和有向搜索两种能 力的方法。 2 6 1选择算子 遗传算法的原理从本质上来说是基于达尔文的自然选择学说。选 择提供了遗传算法的驱动力。如果驱动力太大，遗传搜索将过早的终 止；而如果驱动力太小，进化过程将慢得难以接受。通常需要在遗传 搜索的早期采用较小的选择压力( 用来对搜索空间进行广度搜索) ，在 晚期则推荐采用较大的选择压力( 用来限制搜索空间) 。选择将遗传算 法引导到搜索空间中有前途的区域与中。在过去的2 0 年中提出、验证 并比较了许多选择方法，主要有适应值比例选择、b o l t m a n n 选择、排 序选择、联赛选择等形式。为了舫止由选择误差，或者交叉和变异的 破坏作用而导致当前群体的最优个体在下一代的丢失，d ej o n g 提出 了精英保留策略。另外，遗传算法在机器学习等领域应用过程中， h 0 1 1 a n d 提出了稳态选择方法。 1 适应值比例选择 适应值比例选择是最基本的选择方法，其中每个个体被选择的期 望数量与其适应值和群体平均遥j 煎值的比例有关，通常采用轮盘堵的 方式实现。这种方式酋先计算每个个体的适应值，然后计算出此适应 值在群体适应值总和中所占的比饼，表示该个体在选择过程中韵概率。 选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想，并 且保证优良基因传给下一代个体。 对于给定的规模为n 的群体p - 扣，口z ， ，个体4 p 的适应值 为f ( a j ) ，其选择概率为 只q ，) 。善生，( ，1 ，2 ，n ) 善m ( 2 _ 1 ) 该式决定后代种群中个体的概率分布。经过选择操作生成用于繁 1 6 哈尔滨l 程大学硕十学位论文 殖的交配池，其中父代群众个体生存的期望数目： p o ，) 2 ”只0j ) ， ，一1 2 ，” r2 - 2 、 当群体中个体适应值的差异非常大时，最优个体与最差个体被选 择的概率之比也将按照指数增长。最优个体再下一代的生存机会将会 显著增加，而且最差个体的生存机会将会剥夺。当前群体中的最佳个 体将快速充满整个群体，导致群体的多样性下降，遗传算法过早的失 去了进化能力。这是适应度比值选择容易存在的问题。 2 b o l t z m a n n 选择 在群体进化过程中，不同阶段需要不同的选择压力，早期阶段选 择压力较小，我们希望交叉的个体也有一定的生存机会，使得群体保 持较高的多样性；后期阶段选择压力较大，我们希望遗传算法缩小搜 索领域，加快当前最优解改变豹速度。为了动态调整群体进化过程中 的选择压力，g o l d b e r