（计算机软件与理论专业论文）混合遗传算法在供水管网优化调度中的应用.pdf

中山大学硕士论文摘要 混合遗传算法在供水管网优化调度中的应用 专业：计算机软件与理论 硕士生：周海军 指导教师：李磊教授 摘要 管网调度的目的是可靠地将水压、水量、水质均符合要求的水送往每一用户， 以期最大限度地降低生产成木，取得较好的社会效益和经济效益，在保证服务质 量的前提下使供水费用最低。 本文主要利用与支持向量机( s v m ) 相结合的遗传算法来求解供水管网的 一级调度问题，即在各个水厂的历史供水量和出水压力数据的基础上，确定在今 后一个调度周期中各时间段内各个水厂的最佳供水量和出水压力，使自来水厂效 益最佳。在生成初始种群时，不是简单的随机生成，而是用支持向量机( s v m ) 对历史数据进行分类，用较优的一类历史数据作为初始种群；在约束条件的处理 上，本文借鉴常规方法中的罚函数法，采用将约束条件作为罚函数包含到适应度 评价中去的方法；在选择算子上，本文引入了支持向量机( s v m ) 的方法，增 加了选择的多样性，增加算法搜索到全局最优解的概率：同时针对交叉概率和变 异概率在算法的前后期不同的情况，本文引入了s f i n v i v a s 等提出的动态自适应 的方法，使得交叉概率和变异概率能够随着算法中个体的质量动态改变，提高算 法的效率。本文的最后给出了多种不同算法针对管网调度问题的实验结果的比 较，从而论证了本文提出的改进遗传算法在性能上的提高。 关键字：支持向量机遗传算法管网优化调度 中山大学硕士论文 t h e a p p l i c a t i o no fm i x e dg e n e t i ca l g o r i t h m sf o r o p t i m a ld i s p a t c hi nw a t e rs u p p l ys y s t e m s m a j o r ：c o m p u t e rs o f t w a r e & t h e o r y n a m e ：z h o uh a i - j u n s u p e r v i s o r ：l il e ip r o f a b s t r a c t t h eg o a lo fo p t i m a ld i s p a t c hi nw a t e rs u p p l ys y s t e m si st o g e tt h el o w e s t - c o s t s u p p l ya n do b t a i nt h eb e t t e r s o c i a lb e n e f i t sa n dt h ee c o n o m i cb e n e f i t s i nt h i sp a p e r iu s et h em i x e dg e n e t i ca l g o r i t h m st os o l v et h ef i r s tl e v e ld i s p a t c h i nw a t e rs u p p l ys y s t e m s ic s t yo nt h ec l a s s i f i c a t i o nw i t ht h es u p p o r tv e c t o rm a c h i n e ( s v m ) t ot h eh i s t o r i c a ld a t aa n dt a k et h ei m t i a lp o p u l a t i o nw i t hb e t t e rh i s t o r i c a ld a t a w h e np r o c e s s i n gt h er e s t r a i n e dc o n d i t i o n s ，w ec o n v e f lt h er e s t r a i n e dc o n d i t i o n si n t o p u n i s hf u n c t i o na n da d di tt of i t n e s sf u n c t i o nw h i c hp r o f i t sf r o mt h ec o n v e n t i o n a l m e t h o d w ei n t r o d u c et h es u p p o r tv e c t o rm a c h i n er s v m ) t ot h es e l e c t i o no p e r a t o r , w h i c hi n c r e a s e s t h em u l t i p l i c i t yo fs e l e c t i o na n di n c r e a s e st h ep r o b a b i l i t yo ft h e a l g o r i t h mg e t t i n gt h eo v e r a l lo p t i m a ls o l u t i o n a l s o ，w eu s et h ea d a p t i v ep r o b a b i l i t i e s o fc r o s s o v e ra n dm u t a t i o ni nm i x e dg a sw h i c he n h a n c e st h ee f f i c i e n c yo ft h e a l g o r i t h m t h er e s u l to ft e s t sa b o u tt h es y s t e mi n d i c a t e st h a tt h ei m p r o v e dg e n e t i c a l g o r i t h mh a sm o r eh i 曲c o n v e r g e n c es p e e da n db e t t e rs o l u t i o nq u a l i t y k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e ，g e n e t i ca l g o r i t h m s ，w a t e rs u p p l ys y s t e m ， o p t i m a ld i s p a t c h i i 中山大学硕士论文第一章引言 第一章引言 1 1选题的背景及意义 1 1 1 供水管网经济调度的内容 供水管网优化调度的目的是安全可靠地将水压、水量、水质均符合要求的水 送往每一用户，以期最大限度地降低生产成木，取得较好的社会效益和经济效益。 调度是在系统获得的历史和实时运行信息的基础上，确定系统今后一个调度周期 中各时间段内各种调节装置的运行状况，在保证系统服务质量的前提下使供水费 用最低。为进行调度须有遥控、遥测、遥讯的中心调度机构，以便统一调度各水 厂的水泵，保持整个系统水量和水压的动态平衡。对管网中有代表性的测压点进 行水压遥控，对所有水库和水位遥狈9 ，对各水厂的出水管进行流量遥测，对所有 泵站和主要阀门进行遥控。目前我国不少城市的水厂己经建立城市供水的数据采 集和监控系统，即s c a d a 系统，在此基础上，通过在线或离线的数据分析和处 理系统、水量顶测预报系统等，逐渐朝优化调度的方向迈进。 给水管网优化调度与管网平差、优化设计同属于管网水力计算的范畴，但 其研究对象各有不同【l 】。优化调度可分为直接优化调度和两级优化调度：直接优 化调度是以各泵站投入运行的水泵单机流量和开机台数为变量，将水源、水泵及 管网作为一个有机整体来建立模型，两级优化调度分为管网级优化调度和泵站级 优化调度，管网级优化调度是在管网布置己定，通过对用水量的顶测，确定各水 源的供水量和供水压力，泵站级优化调度是根据各水源的供水量和供水压力，来 确定各个水泵的工作状态，选择费用最小的泵组合；管网平差是在管径、管长及 水源压力和供水量己知，假定节点流量、管道摩阻的条件下，求解各节点的供水 压力；优化设计计算是在管网布置确定，假定节点流量和管道摩阻的条件下，求 解各管段的管径和水源供水压力，同时对初分的管段流量进行调整。 中山大学硕= f j 论文 第章引言 1 1 2给水管网经济调度国内外研究现状 早在2 0 世纪6 0 年代，一些发达国家就开始了以计算机作为供水系统辅助调 度管理的探索，如美国的费城、加拿大的多伦多等城市，就是采用遥控设备将管 网中控制点的压力、水厂出水压力、出厂流量、水位、功率及温度等实际运行参 数自动地传送到中心调度室，并对超常现象做出自动报警，以此作为控制人员实 际操作的依据。另外，国外学者如美国的r y s z a r dkl e m p o u s 、j e r z yk o t o w s k i 引， 英国的r sp o w e l l l 3 】【4 】、b c o u l b e e k 、( ；h e n y l 5 1 6 1 ，日本的k a z u m a s a m u g u r u m a ! 训， 以色列的u s h a m i r l 8 】等，这些人在调度管理的建模理论上进行了许多有益的探讨。 目前，在美国、英国、日本、法国等国家的一些城市基本上实现了供水系统的计 算机优化管理调度。从2 0 世纪7 0 年代起，国内一些专家学者，开始尝试将计算 机技术应用于供水系统的模拟，优化设计水厂水质控制方面。在供水系统优化调 度管理方面也进行了一些有益的探讨和尝试，也编制了些相应的软件，如 w n w ( 给水管网信息管理和分析系统) 等，并在大庆、郑州等地开始应用。近 年来，吕谋、赵洪宾1 9 1 t 1 0 1 1 1 】【1 2 1 1 1 3 等人在供水管网优化调度方法探讨方面作了许 多较有价值的研究，对管网调度方法和建模研究方面也较有贡献。综合国内外， 管网调度主要方法有模拟退火算法1 1 4 】、广义简约梯度法【1 5 1 、动态规划法、遗传 算法【1 6 j 、非线性规划法及混合离散变量法【1 7 1 等。 1 2本文的研究重点 本文的研究工作是广州市自来水公司供水调度系统项目工作的一部分。系统 主要包括数据采集、水量预测、管网和泵站调度、统计分析、系统优化等几个部 分f 1 8 j 。 本文的研究重点是利用与支持向量机( s v m ) 相结合的遗传算法来求解自 来水管网一级调度问题，即在水厂的历史供水量和出水压力数据的基础上，利用 与支持向量机相结合的遗传算法确定各水厂的最佳供水量和出水压力。针对遗传 算法中经常出现的“早熟”( p r e m a t u r i t y ) 等现象，对遗传算法作出了一些改进， 通过这些改进，不仅能提高算法的收敛性，而且能改进求解质量，提高算法获取 2 中山大学硕士论文第一章引言 全局最优解的能力。在编码上，根据供水压力和供水量是连续变量的特点，采取 了实数编码，提高了算法全局最优解的逼近能力，便于对连续的函数进行局部空 间的搜索；在生成初始种群时，不是简单的随机生成，而是用支持向量机( s v m ) 对历史数据进行分类，从较优的一类历史数据中选取一部分作为初始种群；在约 束条件的处理上，本文借鉴常规方法中的罚函数法，采用将约束条件作为罚函数 包含到适应度评价中去的方法；在选择算子上，本文引入了支持向量机( s v m ) 的方法，增强了算法中选择的多样性，增大算法搜索到全局最优解的概率；同时 针对交叉概率和变异概率在算法的前后期不同的情况，本文引入了s r i n v i v a s 等【1 9 1 提出的动态自适应的观点，使得交叉概率和变异概率能够随着算法中个体的质量 动态改变，提高算法的效率。本文的最后给出了多种不同算法针对管网调度问题 的实验结果的比较，从而论证了本文提出的改进遗传算法在性能上的提高。 1 3本文的结构框架 本文主要围绕利用改进的遗传算法求解广州市自来水公司供水管网的一级 调度问题这个核心来展开阐述的，具体结构如下： 第一部分：主要阐述了本文的研究意义、背景以及对研究重点的简要介绍。 第二部分：主要阐述了遗传算法的理论基础，研究状况以及应用；简单介绍 了支持向量机( s v m ) 模型。 第三部分：主要介绍了自来水给水管网控制决策模型及研究状况。 第四部分：这章是本文的重点，主要围绕改进的遗传算法来阐述，具体涉及 到改进算法提出的思想基础、求解问题的数学模型、系统设计的纲要以及对遗传 算法的具体改进方案。 第五部分：主要是对研究工作的总结以及对研究趋势的展望。 文章的最后是参考文献和致谢。 中山大学硕士论文第二章遗传算法及支持向量机概述 第二章遗传算法及支持向量机概述 2 1遗传算法的基本原理 自从1 9 7 5 年j o h n ，h h o l l a n d 教授口0 1 在他的开创性著作a d a p l a t i o ni nn a t u r a l a n da r t i f i c i a ls y s t e m s 中正式提出了遗传算法的基本概念以来，经过短短二十多 年的发展，作为一种适合大规模操作的智能算法，遗传算法不仅在理论上日趋成 熟，而且在工程应用上也得到丰硕的成果。 2 1 1 遗传算法( g a ) 的思想 g a 的思想是基于达尔文的进化论和蒙德尔的遗传学原理。达尔文的进化论 认为：每物种在不断的发展中越来越适应环境，只有最适个体将进一步生存、 再生，将遗传物质传递给子代，而不适者将被迫淘汰，那些更能适应环境的个体 特征被保留下来，这就是适者生存的原理。蒙德尔的遗传学原理认为：遗传是通 过细胞中的遗传密码进行的，遗传密码封装于细胞之中，并以基因的形式包含在 染色体中。每个基因有特定的位置并控制某个特殊的性质，每个基因产生的个体 对环境有一定的适应性。基因的杂交和变异产生更适应环境的子代，通过优胜劣 汰的自然选择，对环境适应度值高的基因结构被保留下来。 g a 在求解一个优化问题时，将操作变量( 自变量) 表示成“染色体”，选择一 群( p o p u l m i o n ) “染色体”个体( i n d i v i d u a l s ) ，将它们置于问题的“环境”( 约 束) 中，对它们进行交叉、变异、再生等“基因操作”，淘汰对环境适应性差的“染 色体”，保留对环境适应度高的“染色体”，反复操作，筛选出最适个体，从而求 出问题的解。 2 1 2 标准遗传算法 h o l l a n d 教授所提出的遗传算法通常称为标准遗传算法( s t a n d a r dg e n e t i c 中山大学硕士论文 第二章遗传算法及支持向量机概述 a l g o r i t h m ，s g a ) ，它的主要步骤如下： 1 对待解决问题进行编码。 2 确定群体规模h ，使用随机方法产生n 个可能解z ，( 七) ( 1 蔓i s n ) 组 成初始解群。 3 对于每一个个体z ，( i ) ( 1 i i ) ( 变量k 作“代”数，初始时k = 1 ) ，计 算其适应度f ( x ，( 七) ) 。 4 对于每一个体x ( t ) ( 1 i n ) ，计算其生存概率只( 女) ： p a k ) = 厂( 五) ，( 置) ( 2 1 ) i = i 5 然后设计一个随机选择器，依据e ( j | ) 以一定的随机方法产生配种个体 x i ) 。 6 产生下一代解群。选取两个配种个体x i i ) ，x ，( j ) ，并依据一定的组合 规则( 交叉，变异) 将x j | ) 、j 】 ) k ) 结合成两个新一代的个体肚+ 1 ) 、 z 船+ 1 ) ，直至新一代n 个个体形成完毕。 7 重复( 3 ) 一( 6 ) 步，直至满足程序终结条件。 它的基本流程图如图2 1 所示。 2 1 3遗传算法的特点 遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法，与其 他算法有着不可替代的优异性，与传统的搜索方法相比，遗传算法具有以下特点： 1 遗传算法并不是对问题的待优化参数本身进行操作，而是通过由这些参数 所编码形成的染色体进行交叉，变异和选择等操作。 2 遗传算法是采用同时处理群体中多个个体的方法，即同时对搜索空间中的 多个解来进行评估。这使遗传算法具有较好的全局搜索性能，减少了陷于局部最 优解的风险。同时，也使遗传算法本身也十分易于并行化。 中山大学硕士论文 第二章遗传算法及支持向量机概述 图2 - 1 遗传算法的基本流程 3 遗传算法不同于常规算法，要依赖领域信息来指导搜索，它对问题的依赖 性小，仅用适应度函数值来评估个体，并在此基础上进行遗传操作。 4 遗传算法对于待优化的函数限制少，既不要求可导可微，也不要求函数具 有连续性，通用性好，鲁棒性强。 5 遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索 方向，虽然它看起来是一种盲目搜索方法，但实际上有明确的搜索方向。 6 遗传算法实现简单，效果良好。 7 遗传算法具有可扩展性，易于同其他方法混合。 当然，遗传算法也有其自身的缺陷有待改进： 1 遗传算法是对种群进行概率性操作，所以，在全局最优的搜索上效果良好， 而在局部晟优的搜索上存在不足。在算法进行的前期，搜索效果良好，而在算法 进行的后期，搜索速度缓慢。 2 遗传算法虽然实现简单，但实现的效果很大程度上取决问题的表示，种群 6 中山大学硕士论文 第二章遗传算法及支持向量机概述 的规模，最大遗传代数，遗传算子的选择，交叉变异概率等多种参数都是一些经 验参数，往往无规律可循，要通过大量的实验结果来获取，而且参数的选取不具 有通用性，当问题本身发生改变时，往往要重新指定新的参数，这些都要花费很 大代价。 3 是否能保证收敛到最优解以及容易出现“早熟”现象等。 2 2遗传算法的描述 遗传算法是一种群体型操作，该操作以群体中所有个体为对象。一般的遗传 算法由五个部分组成：问题表示、适应度函数、选择算子、交叉算子、变异算子 1 2 1 1 1 2 2 1 2 3 】阱】。 2 2 1 问题表示( r e p r e s e n t a t i o n ) 也称作编码机制，g a 不是对研究对象直接进行讨论，而是通过某种编码机 制把对象统一赋予由特定符号( 字母) 按一定顺序排成的串。算法的编码机制直接 影响着算法的整体性能，并且也决定了种群初始化和各种遗传算子的设计等各种 过程，因此，编码机制是遗传算法的关键步骤。 对于具体问题的编码，目前还没有统一的方法。针对一个具体问题，如何设 计一个完美高效的编码方案是遗传算法的难点之一，也是当前遗传算法研究的重 要课题。 迄今为止人们经常用到编码方案有如下几种： 2 2 1 1二进制编码 二进制编码机制是遗传算法中最为常见的编码机制。它所用到的字符集是 0 ，1 ) ，由二进制编码所构成的染色体是由一串0 、l 符号所组成的符号串。 二进制编码机制有着操作简单，符合最小字符集编码原则，便于用模式定 理进行分析等优点，但是也有不可弥补的缺陷：海明悬崖( h a m m i n gc l i f f s ) 问题。 海明悬崖问题不利于遗传算法获得全局最优解，因为在算法后期过程中逼近最优 中山大学硕士论文 第二章遗传算法及支持向量机概述 解时，近似最优解和全局最优解间存在着海明悬崖问题，从而会导致从近似最优 解到最优解之间的逼近过程缓慢，甚至找不到最优解。 2 2 1 2 g r a y 编码 g r a y 编码是针对二进制编码中存在着海明悬崖问题缺陷而提出的，是x j - 进制编码进行转换得到的。 设有二迸制串。，反展) ，对应的g r a y 串( 如以) ，则从二进制编码到 g r a y 编码的变换为： 锻。反是( 2 2 ) 由于g r a y 编码的邻近两个数之间的海明距离短，使得算法从近似最优解逼 近全局最优解的代价减少，有利于提高遗传算法朝全局最优解的逼近能力，便于 对连续的函数进行局部空间的搜索。 g r a y 编码仍然是二进制编码的一种变形，所以，g r a y 编码仍然可以沿用传 统遗传算法的选择、交叉、变异等遗传算子。 2 2 1 3实数编码 对于一些问题的表现形式是实向量的情形，如果使用二进制编码机制，会 存在效率低下，无法控制算法精度的缺陷，所以一般采用实数编码机制。这样， 可以在解的表现形式上直观简单，便于遗传算法的操作，有利于引入问题相关领 域的启发式信息以增强算法的搜索能力。 实数编码从理论上讲仍然可以沿用二进制编码下的各种遗传操作，因为实 数在机器中的最终表现形式仍是二进制表示。针对实数编码的特性，引入其他一 些遗传算子，而且实验数据也表明，这些精心设计的针对实数编码提出的遗传算 子比采用二进制编码下的遗传算子平均效率更高。 m i c h a l e w i c z l 2 a l 比较了二进制编码和实数编码这两种编码机制的优缺点，并 且指出了各自的应用范围，林丹，李敏强等【2 叼分析了在绝大多数实际应用中使 中山大学硕士论文第二章遗传算法及支持向量机概述 用的f g a 的收敛性问题，在采用最优个体保留策略的前提下得到了保证收敛性 的一般条件，并以之检验了采用常用的变异与交叉算子时f g a 的收敛性。 2 2 2种群的初始化 种群的初始化操作是指如何生产第一代初始种群。种群的初始化操作都是 随机的，一般来讲，初始群体的设定可以采取如下的策略： 1 根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布 范围，然后在此分布范围内设定初始群体。 2 先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。 这种过程不断迭代，直到初始群体中个体数达到了预定的规模。 群体规模越大，群体中个体的多样性越高，算法陷入局部解的危险性越小， 但是群体规模太大会影响计算效率和遗传操作。 2 2 3 适应度( f i t n e s s ) 遗传算法在进化搜索中基本上不用外部信息，仅用目标函数即适应度函数 为依据。遗传算法对于领域知识的利用就是通过适应度标准反映出来。遗传算法 的目标函数不受连续可微的约束且定义域可以为任意集合。对目标函数的唯一要 求是，针对输入可计算出能加以比较的非负结果。 目标函数映射成适应度函数后需要进行一些调整，称作适应度定标。自从 d ej o n g 开始引入适应度函数的定标问题以来，定标已成为保持进化过程中竞争 水平的重要技术。目前，定标方式大致有以下几种： 1 线性定标( 1 i n e a rs e a l i n g ) 设原适应度函数为，定标后的适应度函数为，则线性定标可采用下式 表示： f 。= a t + b( 2 3 ) 口，b 可以有多种途径设定。 2 占截断( s i g m a t r u n c a t i o n ) 9 中山大学硕士论文 第二章遗传算法及支持向量机概述 由f o r r e s t 提出，主要利用了群体标准方差信息来对适应度进行预处理。表 示式如下： f 。= 一( f c 占) ( 2 4 ) 式中c 要适当选择。 3 乘幂标 该定标方式由g i l l i e s 提出，可定义如下： f 。= 厂( 2 5 ) 式中，k 与求解问题有关。 2 2 4 选择算子侣e l e c t i o no p e r a t o r ) 选择算子的设计对于算法性能起到举足轻重的影响，不同的选择操作将会导 致不同的选择效果。较大的选择压力将会导致当前种群中的最优个体具有较高的 复制数目，从而使得算法会以较快的速度收敛，这时容易出现“早熟”( p r e m a t u r i t y ) 的现象，即在算法早期，在种群中出现了超级个体，该个体的适应度值将会大大 超过了当前种群的平均个体适应度值f , _ l v ，则该个体将会很快在种群中占据 绝对的比例，从而使得算法较早收敛于局部最优点。相反，如果较小的选择压力 将会使得种群的繁衍保持多样性，有利于种群跳出局部最优，收敛于全局摄优点， 不过缺点是收敛速度慢，效率低下。 常用的选择算子有以下几种： 2 2 4 1 轮盘赌选择( r o u l e t t ew h e e ls e l e c t i o n ) 轮盘赌选择算子在遗传算法中应用最多，具体过程如下： 1 计算种群中每个个体的适应度值石 2 计算种群的总的适应度值z ； 3 坩算种舯每爪爪体在该种群中的相对适应度值轰： 0 中山大学硕士论文第二章遗传算法及支持向量机概述 4 对于每个个体，按照其在种群中的相对适应度值轰作为其繁衔虾一 代的生存概率，即随即生成一个 o ，1 之间的数r ，p ，表示第i 个个体的相对适 应值，如果+ p l + p 2 + + p j l l r p o + p l + p 2 + + p f _ i + p ，那么选择个体 i 进入到下一代种群中。重复选择n 次，从而生成下一代种群的n 个个体。 轮盘赌选择能够简单地实现选择操作，但是这种选择操作剥夺了较小适应 度值个体的生存机会，而放大了超级个体的生存机会，不利于保持种群的多样性， 所以容易出现上面所说的“早熟”现象。 2 2 4 2 基于排序的选择( r a n k - b a s e ds e l e c t i o n ) 所谓排序选择方法是指在计算每个个体适应度后，根据适应度大小顺序对群 体中个体排序，然后把事先设计好的概率表按序分配给个体，作为各自的选择概 率。它和轮盘赌选择一样都是一种基于概率的选择，所以仍有统计误差。 2 2 4 3 锦标赛选择法( t o u r n a m e n ts d e c t i o n ) 该方法十分简单，其操作思想是，从群体中任意选择一定数目的个体( 称为 联赛规模) ，其中适应度最高的个体保存到下一代。这个过程反复执行，直到保 存的下一代个体数达到预先设定的数目为止。联赛规模一般取2 。 2 2 4 4 最佳个体保存方法( e l i t i s tm o d e l ) 在大规模种群中，交叉，变异等操作会破坏当前种群中的最佳个体，因此它 会降低种群的平均适应度，不利于算法的收敛，所以，研究者提出了最佳个体保 存法，即当前种群中的最佳个体不参与种群的选择操作，直接进入到下一代种群 中。 2 2 4 5 b o l t z m a n n 选择 b o l t z m 锄 2 刀选择实际上是一种适应度调节策略，它使用函数 中山大学硕士论文 第二章遗传算法及支持向量机概述 占( z ) = e x p ( f , t ) 将适应度进行变换，以改变原始的选择压力。这里t 是一个控 制常数，t 取较大( 小) 值时选择具有较大( 小) 的选择压力，即适应度的相对 比例变小( 大) 。b o l t z r n a n n 选择实际上是把模拟退火算法的思想融入到了选择 操作中，这样做的目的在于使得一些适应度小的优良个体也能以一定的概率被下 一代种群所接受，从而保持了种群的多样性。 2 2 5 交叉算子( e r o s s o v e ro p e r a t o r ) 遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把父代个体 的部分结构加以替换重组而生成新个体的操作。交叉算子的设计是遗传算法中的 难点之一。它一方面要考虑尽量生成更多不同的个体，保持种群进化的多样性， 另一方面，它又要避免破坏种群中的优良个体，加快种群的收敛速度。很明显， 一个良好的交叉算子的设计要兼顾到这两个方面，使种群的多样性和收敛性达到 和谐的统一。 常见的交叉算子有如下几种： 2 2 5 1 单点交叉( o n e - p o i n te r o $ s o v e r ) 单点交叉中，两个相互配对的染色体石( ，x 2 ，工，) ，j ，( y 。，y ，y ：，虬一。) 长度为n ，则交叉点k 的取值范围为【1 ，n 1 】，k 为整数，经过交叉后所生成的新 染色体为：j 。( ，x l ，如， _ l ，儿，n + 1 ，儿一- ) ，y i ( ，儿，y 2 ，以- l ，以，以+ l ，矗一1 ) 。 子十体 台口麴 圜蠹二 图2 - 2 单点交叉 2 2 5 2 两点交i 叉( t w o - p o i n tc r o s s o v e r ) 两点交叉的操作和单点交叉类似，只是设置两个交叉点。 章 中山大学硕士论文第二章遗传算法及支持向量机概述 具体过程图2 3 所示 父个体 子个体 邑匮卫 囤口圈 图2 3 两点交叉 2 2 5 3 多点交叉( m u l t i - p o i n tc r o s s o v e r ) 多点交叉中交叉点可能有多个，是对单点和两点交叉的一种放大，也叫广义 交叉。 2 3 5 4 算术交叉( a r i t h m e t i ec r o s s o v e r ) 前面的单点交叉，多点交叉和均匀交叉一般是针对二进制编码的，而对于实 数编码，一般不采用二进制编码下的交叉算子，而是采用针对实数型编码引入的 其他交叉算子。实验表明，采用这些算子说产生的效率比采用二进制编码下的算 子全局效率更高。算术交叉就是基于这种思想提出来的【2 8 1 。 在算术编码中，两个个体x ( x o ，x l ，x 2 ，x + 1 ) ，r ( y o ，m ，y 2 ，儿一1 ) ，通过对个 体中的每个基因一，_ y 进行线性组合，从而生成两个新的个体 z 。( x o ，x l ，x 2 ，x 。一1 ) ，r ( y o ，y 1 ，y 2 ，y 。一1 ) 。中： 敞竺- t ：( 1 一娈- 0 l ，州( 2 - 6 ) 【y = 叼一l + ( 1 一口) 工p l 口是一个参数，它可以是固定常数。 2 2 6 变异算子( m u t a t i o no p e r a t o r ) 变异是指父代染色体中的某些基因片，以相对较小的概率发生随机改变的过 程。变异是以一定的概率进行的，这种概率称之为变异率。变异率定义为：种群 中发生变异个体的数目在该种群总个体数目的百分比。变异率决定了种群中个体 中山大学硕士论文第二章遗传算法及支持向量机概述 发生变异的机会大小，如果制定过高，则容易破坏种群中已有的优良个体结构， 使得算法丧失了对以往操作结果的学习能力，算法近似于随机搜索；如果制定过 低，则产生新个体的速度慢，算法收敛速度慢，甚至算法可能陷入局部最优。 常见的变异算子有如下几种： 2 2 6 1 基本变异算子 对于二进制编码的个体，变异操作是指以一定的概率对数串中的某些基因进 行取反操作，进行取反操作的基因是随机指定的。 假设有一二进制编码的个x ( x o ，x 。，屯，稚，) ，变异率为p ，随机生成的 概率为p ，经过变异操作后，生成的新个体为z o 。，x 。，x 。，x 。) ，则满足： = 偿筹圳 z 疗一， 2 2 6 2 逆转算子( i n v e r s i o no p e r a t o r ) 逆转算子是变异算子的一种特殊形式。他的基本操作内容是在个体串中随机 挑选两个逆转点，然后将两个逆转点间的基因值以逆转率p 逆向排序 2 2 6 3 自适应变异算子( a d a p t i v em u t a t i o no p e r a t o r ) 与基本变异算子的操作内容类似，唯一不同的是变异概率只不是固定不变 而是随群体中个体的多样性程度而自适应调整。 2 3遗传算法的基础理论 2 3 1 模式定理( s c h e m a t at h e o r e m 、 【模式定理】：遗传算法中，在选择、交叉和变异算子的作用下，具有低阶、 短的定义长度、并且平均适应度高于群体平均适应度的模式将按指数级增长。 公式表示： 1 4 中山大学硕士论文 第二章遗传算法及支持向量机概述 唧+ 1 ) 加( 聊等t 1 公式2 - 8 中， 办箬d ( 以川( 2 - 8 ) m ( h ，h 1 ) ：表示在，+ l 代种群中存在模式日的个体数目 m ( h ，t ) ：表示在，代种群中存在模式的个体数目： f ( h ，t ) ：表示在，代种群中包含模式日所有个体的平均适应度； 7 ( 0 ：表示在，代种群中所有个体的平均适应度 8 ( h ) ：表示模式日的定义长度： f ：表示个体的长度； p 。：表示交叉率； o ( h 1 ：模式的阶： p 。：变异率： 模式定理从理论上为遗传算法的运行机理提供了有力的数学工具，为遗传算 法的应用提供了指导意义，是遗传算法的理论基础。有关证明可以参考相关文献。 2 3 2 积木块假设( b u i l d i n gb l o c kh y p o t h e s i s ) 【积木块假设】：短定义距、低阶以及高平均适应度的个体基因( 积木块) 通过选择、交叉和变异等遗传操作的作用，通过相互结合能够最终逼近全局最优 解。 积木块假设比模式定理更加明确地指出了利用遗传算法能够找到全局最优 解，为遗传算法的应用指明了清晰的求解思路。有关积木块的证明可以参考相关 文献。 2 3 3 骗问题( d e c e p “v ep r o b l e m ) 各种实验表明这样存在的数据环境，即最优解被次优解所包围，通过对次优 中山大学硕士论文 第二章遗传算法及支持向量机概述 解的操作是很难找到通向最优解的道路的。存在这样的数据环境的问题一般被称 之为“g a 一难”问题。在遗传算法中将这种现象称为遗传算法欺骗问题。 2 3 4 隐并行性( i m p l i c i tp a r a l l e l i s m l 在遗传算法的代与代之问的遗传操作中，虽然表面上每代处理染色体的数目 都是一定的，但是由于每个染色体都隐含着多种不同的模式，所以每次参与遗传 算子操作的个体却就不仅仅是两个。因此，就总体而言，代与代之间的所处理的 染色体远远大于其表面的数目，这就是遗传算法独特的隐式并行性。隐式并行性 是遗传算法的两大显著特征之一，它从理论上证明了遗传算法的高效性所在。 【隐式并行性定理】1 2 卵遗传算法所处理的有效模式总数约与群体规模m 的 立方成正比，即： 刀= o ( m 3 、 由隐式并行性定理我们知道，虽然遗传算法每一代只处理了m 个个体，而 事实上有与m 成立方数目的个体参与了操作。隐式并行性为遗传算法的高效性 提供了理论依据。 2 3 5 性能评估 目前，遗传算法的评估指标大多采用适应度值。特别在没有具体要求的情况 下，一般采用各代中最优个体的适应度值和群体的平均适应度值。以此为依据， d ej o n g 提出了两个用于定量分析遗传算法的测度。 【在线性能评估准则】设置为环境p 下策略j 的在线性能，z ( ，) 为时刻 f 或第f 代中相应于环境e 的目标函数或平均适应度函数，则x 。( s ) 可以表示为 1r x e ( s ) = 工( f ) ( 2 - 9 ) 1i l l 上式表明，在线性能可以用从第一代到当前代的优化进程的平均值来表示。 【离线性能评估准则】设五( j ) 为环境e 下策略s 的离线性能，则有 中山大学硕士论文第二章遗传算法及支持向量机概述 纵班；喜抛) ( 2 _ 1 0 ) 其中，正( ，) = b e s t l ( 1 ) ，正( 2 ) z o ) 。上式表明，离线性能是特定时刻晟佳 性能的累积平均。 2 3 6 收敛性 模式定理虽然指出了具有优良结构的模式在算法的进化过程中的演变趋势， 但是，它并未回答了遗传算法最终收敛于最优解的概率为多少。积木块假设虽然 指明了遗传算法能够收敛于全局最优解，但是仅仅是通过大量的应用数据来证明 其有效性，还没有完整而严密的数学证明。利用马尔可夫链对遗传算法的分析严 格论证了遗传算法收敛性方面的一些重要性质，有力地支撑了遗传算法的理论基 础。下面是由马尔可夫链推导出来的一些结论，具体证明可以参考相关文献。 【收敛性定理1 】标准遗传算法不能收敛至全局最优值。 【收敛性定理2 】使用保留最佳个体策略的遗传算法最终能收敛到全局最 优值。 2 4遗传算法的研究现状 自从1 9 7 5 年j h h o l l a n d 系统地提出遗传算法的完整结构和理论以来，众多 学者一直致力于推动遗传算法的发展，对编码方式、控制参数的确定、选择方式 和交叉机理等进行了深入的研究，引入了动态策略和自适应策略以改善遗传算法 的性能，提出了各种变形的遗传算法。其基本途径概括起来有下面几个方面： 1 改变遗传算法的组成成分或使用技术，如选用优化控制参数、适合问题特 性的编码技术等。 2 采用混合遗传算法。 3 采用动态自适应技术，在进化过程中调整算法控制参数和编码粒度。 4 采用非标准的遗传操作算子。 5 采用并行遗传算法。 主些查堂堡主笙苎一一 兰三童垫堡簦鲨垄塞堡旦量垫塑鎏 主要包括下面七种改进遗传算法： ( 1 ) 分层遗传算法( h i e r a r c h i cg e n e t i ca l g o r i t h m ) 图2 - 4 分层遗传算法 ( 2 ) c h c 算法 c h c 算法是e s h e l m a n 于1 9 9 1 年提出的一种改进的遗传算法的缩称，c 代 表跨世代精英选择策略( c r o s sg e n e r a t i o n a le l i t i s ts e l e c t i o n ) ，h 代表异物种重组 ( h e t e r o g e n e o u sr e c o m b i n a t i o n ) ，第二个c 代表大变异( c a t a c l y s m i cm u t a t i o n ) 。 ( 3 ) m e s s y g a m e s s y 由g a g o l d b e r g 等在1 9 8 9 年提出，是一种变长度染色体遗传算法， 该算法在不影响模式定义距的情况下，使优良的模式得以增值。 ( 4 ) 自适应遗传算法( a d a p t i v eg a ) s r i n i v a s 等提出了对交叉概率和变异概率进行算法动态自适应的思想，并且 i r 中山大学硕士论文 第二章遗传算法及支持向量机概述 给出了计算公式，通过交叉概率和变异概率动态自适应，能够协调种群的多样性 和算法的收敛性之间的矛盾，从而达到一个很良好的算法求解效果。 ( 5 ) 基于小生境技术的遗传算法( n i c h e dg a ，简称n g a ) 小生境技术是指将每代种群中的个体按照适应度的大小进行划分为多个类， 然后在每个类中选取适应度较大的个体组成一个新的种群，最后通过这些种群之 间的共享机制来完成种群问优秀个体的交流共享，从而达到寻找最优解的搜索过 程。 ( 6 ) 并行遗传算法( p a r a l l e lg a ) 由于遗传算法自身存在的隐式并行性的特性，所以利用并行技术来提高遗传 算法的效率是很自然的发展途径。目前，并行遗传算法主要存在主从式模型，粗 粒度模型和细粒度模型等三种主要框架。 ( 7 ) 混合遗传算法： 法。 图2 5 混合遗传算法构成示意图 遗传算法与最速下降法相结合的混合遗传算法。 遗传算法与模拟退火算法( s i m u l a t e da n n e a l i n gs a ) 相结合的混合遗传算 1 9 中山大学硕士论文 第二章遗传算法及支持向量机概述 2 5遗传算法的应用 遗传算法由于具有鲁棒性强，实现简单，对问题依赖性小等优点，为求解复 杂系统优化问题提供了通用框架，因而在许多方面得到了大量的应用，归纳起来 有如下几个领域： 1 函数优化 2 组合优化 3 生产调度问题 4 自动控制 5 机器学习 6 图像处理和模式识别 7 遗传编程 2 6 支持向量机( s 哪 支持向量机( s u p p o r tv e r t o rm a c h i n e ) 是统计学理论中最年轻的内容，也是 最实用的部分，其核心内容是v a p n i k 等人在1 9 9 2 到1 9 9 5 年之间提出的，目前 仍处在不断发展阶段。 s v m 的主要思想可以概括为两点：( 1 ) 它是针对线性可分情况进行分析，对 于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样 本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样 本的非线性特征进行线性分析成为可能；( 2 ) 它基于结构风险最小化理论之上在 特征空间中建构最优分割超平面，使得学习器得到全局最优化，并且在整个样本 空间的期望风险以某个概率满足一定上界1 3 0 1 1 3 1 1 1 3 2 1 1 3 3 1 。 2 6 1 广义最优分类面 s v m 是从线性可分情况下的最优分类面发展而来的，基本思想可用图2 - 6 的二维情况说明。 中山大学硕士论文第二章遗传算法及支持向量机概述 拄 琏 图2 - 6 线形可分情况下的最优分类线 图中，实心点和空心点代表两类样本，日为分类线，q ，坞分别为过各类中离 分类线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔。所谓 最优分类线就是要求分类线不但能将两类正确分开( 训练错误率为0 ) ，而且使分 类间隔最大。分类线方程为 帕= 0 ，我们可以对它进行归一化，使得对 线性可分的样本集( z