（电力系统及其自动化专业论文）基于遗传算法的电力市场有功优化调度.pdf

太原理i 大学硕士学位论文2 a b s t r a c t i nt h i sp a p e r , t h e 两n c i p l e sa n dm e t h o do fg e n e t i ca l g o r i t h mw e r e s u c c e s s f u l l ya p p l i e di np o w e rm a r k e tg e n e r a t i o nd i s p a t c h i n g s o m e p a r a m e t e r so fg e n e t i ca i g o r i t h mw e r ed i s c u s s e di nd e t a i l ，s u c ha s c o d i n g d e c o d i n g ，p o p u l a t i o ni n i t i a l i z a t i o n ，e s t a b l i s h i n go ff i t n e s s f u n c t i o n ，a n dd e t e r m i n a t i o no fg e n e t i co p e r a t i o na n dk e yp a r a m e t e r s o m ew a y so fc o m b i n a t o r i a l o p t i m i z a t i o nb a s i n g o n g e n e t i c a l g o r i t h ma n dh e u r i s t i ct e c h n i q u ew e r ec o m p a r e d e s t a b l i s h e dt h e o p 恤n i z i i 唱m a t h e m a t i c a lm o d e lb a s i n go ng e n e t i ca l g o r i t h m b y m e a n so fc o m b i n a t i o ng e n e t i ca l g o r i t h ma n dh e u r i s t i ct e c h n i q u e ，t h e s o l u t i o ns e a r c hs p a c ew a sr e d u c e de f f e c t i v e l y t h ec o r r e s p o n d i n g s o f t w a r ew i t sp r o g r a m m e do u ta n do b t a i n e ds a t i s f a c t o r yr e s u l t sw i t h c o m p u t i n gi na ni e e e1 0 一g e n e r a t o rt e s t i n gs y 吕t e r n a n ds h e n t o u g e n e r a t o r g r o u po fs h a n x i k e ) 诩c o r d s ：p o w e rm a r k e t ，h e u r i s t i ct e c h n i q u e ，g e n e t i ca l g o r i t h m 2 太原理i 大学硕士学位论文 4 第一章电力市场有功调度遗传算法的应用背景厦要求 1 1 有功调度优化的意义 1 1 1 电力市场的逐步建立 电力市场是近年来电力工业改革的方向，电力工业将从传统的 运行管理机制向着电力市场运行管理机制转变，使全社会从改革 中获得更大的经济效益和社会效益。电力工业要面向市场，引进 竞争，引进市场经济体系，增强活力，已成为世界各国电力工业 发展的趋势，同时建立电力市场也是我国电力发展的需要，这是 大势所趋。 在我国技术条件不发达的情况下，管理及协调手段欠缺，电力 市场无法有效地实施。电力工业做为国有行业，处于独家投资、 独家生产经营的垄断地位，再加上我国电力供应一直比较紧张， 长期处于需大于供的卖方市场，电力市场建立的条件尚不具备。 世界各国也将电力工业作为国有企业来统一控制。随着电力系统 的迅速发展，电网向着大容量、超高压的联合电网发展，电力系统 运行的经济性越来越为人们所重视。科技进步特别是信息技术的 进步也使生产及管理手段大大提高，电力市场硬件成熟。同时世 界各国在电力市场方面也在积极探索，积累了大量宝贵经验，给 电力市场的建立发展创造了有利的条件。 4 太原理工大学硕士学住论文 1 1 2 电力市场的运行机制及其特点 我国原有计划经济下的电力体制已不适应国民经济发展的需 要，为了在电力工业引进竞争机制，促进电力企业提高劳生产力， 降低运行成本，给企业带来活力，国家经贸委、国家电力公司提 出网厂分开，建立发电侧电力市场，电力市场的运行目标是：在 满足系统安全稳定运行的前提下，促进发电厂间的竞争，以发电 成本、网损、辅助服务成本之和最低为优化目标，根据机组报价， 确定发电计划，实时调度各个发电公司的机组发电，以满足用电 负荷需求。 电力市场采用法律、经济等手段，本着公平竞争，自愿互利的 原则，对电力系统运行进行组织、管理和协调。电价是电力市场 的核心内容，电力市场的全过程都是围绕电价展开的。参与者之 间本着公平、公正、公开的原则进行电力、电量交易。同时保证 电力系统的安全稳定，促进电力系统经济运行，保证电能质量， 满足电压、频率、可靠性等指标。 电力市场交易的类型：市场运行部门可将发电侧电力市场的交 易类型分为四种，即现货交易、实时交易、期货交易和辅助服务， 对于不同类型的交易采取不同的处理方法。 1 2 山西电网有功调度的现状 1 2 1 山西电网概述 太原理工大学硕士学位论文 6 山西做为全国能源重化工基地，电网近年来有很大的发展。过 去山西电网电源不足，大量拉闸限电，一定程度上制约了山西的 经济发展和人民生活水 平的提高。近年来特别是 9 0 年代以来，随着大量 新机组的投产，高压电网 的不断巩固，供电紧张局 面大为改善。 截至2 0 0 1 年底，山西 电网统调发电装机容量 为1 4 1 3 9 0 6 1 万千瓦( 其 中水电有7 7 6 0 6 万千 瓦) ，省调装机9 8 1 7 万 千瓦( 其中水电有6 6 8 万千瓦) 。全网1 0 万千瓦 以上机组5 3 台，容量为 图表1 山西电网图 1 1 2 8 万千瓦，占统调发电装机的7 9 7 8 。山西电网2 2 0 k v 及以 上电厂1 5 座，5 0 0 k v 直接接入电源容量为4 0 0 力- 千瓦， 2 2 0 k v 直接接入电源容量为6 6 8 万千瓦。山西电网省调调度的2 2 0 k v 线 路1 2 2 条，长度约5 2 7 1 4 9 4 8 k n ； 地调调度的2 2 0 k v 线路7 条， 长度约1 7 0 4 6 2 k m ；全网共计2 2 0 k v 线路1 2 7 条，长度约 5 4 0 9 3 3 4 8 k i 。山西省境内5 0 0 l v 线路5 条，长度约5 5 7 6 k m 。其 中山西省公司管辖的5 0 0 k v 线路3 条，3 2 7 6 k m 。山西电网省调调 度的5 0 0 k v 变电站1 座，主变1 台，容量为7 5 0 m v a ，2 2 0 k v 变电 站5 0 座，共9 1 台主变压器，容量为1 1 5 6 6 m v a ；地调调度的2 2 0 k v 太原理i 大学硕士学位论文 7 变电站4 座，共8 台主变压器，容量为9 3 0 m v a ；全网2 2 0 k v 及以 上变电站总计5 5 座，9 9 台主变，容量共计1 3 7 5 6 m v a 。山西电网 电厂5 2 联变2 台，容量8 6 0 m v a ；2 一l 联变2 台，容量2 4 0 m v a 。 1 。2 2 山西电力市场的建设及规划 为了适应市场步伐，我省在电力市场初级阶段已进行一些积极 有益的基础工作，并取得了较好的效果。 1 2 2 1 发电厂2 4 小时考核制度 发电厂能否按调度计划指令按时开停机炉并平稳运行是电网 安全与经济的重要支柱。为使发电出力能更好地跟踪计算机按等 微增率原则制定的发电计划曲线，保证电网安全稳定运行，提高 全网综合经济效益。适应多家办电统一调度的的需要，自9 8 年1 月1 日起各发电厂开始执行修订后的山西电网统配发电厂日发 电负荷曲线考核办法( 晋电调字1 9 9 7 另3 4 号) 。该办法将我省 统配发电厂按调整性质分为基荷发电厂和网间潮流调整厂。对于 基荷发电厂按调度下达的2 4 小时负荷曲线带负荷，其误差不超过 计划值的- i - 3 ：对于网间潮流调整厂按其完成的网间潮流合格率 进行考核。该办法给出了全天各时段发电机组出力超出波动范围 后的处罚措施，并对掉机，灭火及未能按时停并等情况作出了处罚 规定。从中可看出在高峰和低谷时段对发电厂的出力要求较平峰 为严格。该办法对省调统配电厂实行计算机分钟实时考核，日统 计、月小计、月公布、年兑现，其结果在发电厂分时厂供电量中 进行调节。自该考核办法实行以来，统配机组运行状况明显提高， 起停调峰后并网的准时率明显提高，周计划的保证率明显提高， 7 太原理工大学硕士学位论文 网间潮流的合格率较往年明显提高。 1 2 2 2 短期与超短期负荷预计 负荷预测的准确程度直接影响发电出力的合理安排，调峰容量 的确定，旋转备用容量的确定。因此，负荷预测对于电网的经济 运行是至关重要的。过去省调采取的基本上是用相似日的方法进 行人工负荷预测。这种方法主观性强，对负荷预测人员的实际经 验要求高，劳动强度大。自9 7 年以来，省调与北京电科院的著名 专家学者一起，先后开发了短期与超短期负荷预测软件，并已投 入使用。短期负荷预测软件是根据s c a d a 系统中所采集的用电历 史数据，结合预测日的负荷类型，温度等因素，由计算机计算后 得出的负荷预测结果。它可进行一天至七天的负荷预测，主要作 为制定次日发电计划曲线的根据。当计划人员认为预测结果有误 时，可进行人工修正。超短期负荷预测也是根据s c a d a 系统中的 用电历史数据，结合负荷预测当日的类型、温度并参考在线实时用 电数据不断修正的一种方法。它主要为调度运行人员提供一个近 期负荷走势，可具体到未来一小时及未来四小时的负荷预测，是 调整网问潮流，安排爬坡等的主要依据。短期和超短期负荷预测 软件的应用对于我们客观准确地安排出力有十分重要的意义。目 前，省调已将此两种软件向全省1 1 个地调进行了推广，并已在各 地调陆续得到了应用。 太原理i 大学硕士学位论文 1 3 电力市场有功调度的算法要求 1 3 1 电力市场对电网调度及日有功计划的要求 我国电力体制改革提出“大家办电厂，国家管电网”的原则， 确立了电网调度的重要地位和作用，一方面强调了电网要统一调 度，另一方面又带来了产权多元化，这两方面是在通过对作为电 力市场载体的电网管理中得到统一实现的。电网不仅是电力沟通 和交换的空间和场所，更重要的是它客观上发挥着维系电力市场 或商品交换关系的重要纽带作用，而这种纽带作用因电力生产的 客观规律所决定，不会随着时间的推移和管理形势的变化而丧失， 这样使得多家办电主体在电网中得到统一管理，也使多元的利益 主体能在电网的统一体中获得各自最大的利益。这样，电网调度 不仅要保证电网的安全、优质、经济运行，还要统筹考虑国家和 各投资者、经营者及使用者的利益。3 有功调度的日计划安排是电力市场中非常重要的一环，它实质 是发电公司与市场运行部门进行的现货交易。日计划的编制原则 是：目计划应以最小的电网运行成本，满足负荷要求为优化目标， 即在满足负荷需求的前提下，总发电成本加上输电成本再加上辅 助服务的成本之和为最小。“3 1 3 2 电力市场有功调度算法的选择 为保证日计划编制的简便和科学，各调度部门普遍用计算机来 辅助或完全依靠计算机完成日计划的编制。所以有功日计划的编 制的经济性和合理性很大程度上取决于其计算机算法的相对优劣 性，而电力系统规模的不断扩大，调度时刻的不断细化，系统中 9 太原理i 大学顼士学位论文1 0 各种类型约束条件的增加，又对求解日有功优化调度的计算机算 法提出了更高的要求。 目有功计划的优化实质上就是对各个发电机组进行优化组合， 机组优化组合是电力系统优化运行的一个重要组成部分，它要求 在一个调度周期内( 2 4 小时) ，根据负荷预报，在满足电力生产 平衡及肩停限制等约束条件下，优化选定各时段参加运行的机组， 决定机组开停时间，使此丹期内的总耗量( 包括运行耗量和启动 耗量) 为最小。机组优化组合有可能获得与负荷优化分配相同或 更大的经济效益。 多种机组优化组合的算法，如优先顺序法、动态规划法、拉各 朗日松弛法等，但由于机组优化的变量和约束条件太多，这些算 法的计算精度均受到不同程度的限制，所以机组优化组合的算法 仍在研究之中，如何减少时间量、提高精度是应进一步探讨的问 题。1 在本文中，采用了遗传算法结合启发式技术的方法，遗传算法 作为一种较新型的搜索方法，在处理这种多峰空间性质的组合优 化搜索时，有其独到之处。关于遗传算法的特点，我们将在下 章中阐述。 1 0 太原理工走学硕士学位论文 第二章遗传算法的特点及基本方法 2 1 遗传算法的特点 2 1 1 遗传算法的原理简介 遗传算法( g e n e t i c a l g o r i t h m - - 一g a ) 是一类借鉴生物界自然 选择和自然遗传的随机化搜索算法，由美国m i c h i g a n 大学的 l h o l l a n d 教授于1 9 7 5 年提出，其主要特点是群体搜索策略和群 体中个体之间的信息交换，搜索不依赖梯度信息。它尤其适用于 处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组 合优化、机器学习、自适应控制、规划设计和人工生命等领域， 是2 1 世纪有关智能计算中的关键之一。“1 不少问题如规划问题和机组优化组合问题，需要在复杂而庞大 的搜索空间中寻找最优解或准最优解。求解此类问题时，若不能 利用问题的固有知识来缩小搜索空间，就会产生搜索的组合爆炸。 因此。研究能在搜索过程中自动获取和积累有关搜索空间的知识， 并自适应地控制搜索过程，从而得到最优解或准最优解的通用搜 索算法一直是令人瞩目的课题。遗传算法就是这种特别有效的算 法。它简单、通用、鲁棒性( r o b u s m e s s ) 较强，适用于并行分步处 理，应用范围广。尽管遗传算法本身在理论和应用方法上仍有许 多待进一步研究的问题，但它在组合优化问题求解、自适应控制、 规划设计、机器学习和人工生命等领域应用中展现了其特色和魅 力。3 太原理工大学硕士学位论文1 2 生物的各项生命活动都有它的物资基础，生物的遗传与变异也 是这样。由现代细胞学和遗传学的研究可知，生物的遗传和变异 有其物质基础，遗传物质的主要载体是染色体( c h r o m o s o m e ) ，染 色体主要是由d n a ( 脱氧核糖核酸) 和蛋白质组成，其中d n a 是最主要的遗传物质。d n a 中基因( g e n e ) 又是有遗传效应的片 段，它储存着遗传信息，可以准确地复制，也能够发生突变，基 因通过控制蛋白质的合成而控制生物的性状。生物体自身通过对 基因的复制和交叉的操作使其性状的遗传得到选择和控制。同时， 通过基因重组、基因变异和染色体在结构和数目上的变异产生丰 富多彩的变异现象。根据达尔文进化论，多种多样的生物之所以 能够适应环境而得以生存进化，是和上述的遗传和变异生命现象 分不开的。生物的遗传特性，使生物界的物种保持相对的稳定： 生物的变异特性，是生物个体产生新的性状，以至于形成新的物 种，推动了生物的进化和发展。 遗传算法就是模拟上述生物进化过程的计算模型。遗传算法 中，复数个基因组成染色体，染色体中基因的位置称为基因座， 而基因所取的值称为等位基因，基因和基因座决定了染色体的特 征，也决定了生物个体的性状，染色体有两种相应的表示模式， 即基因型和表现型，表现型是指个体所表现出来的性状，基因型 是指与表现型密切相关的基因组成。实际计算中，染色体对应于 数据或数组，通常由一维的串结构数据来表现。串上的各个位置 所取的值即为“基因”。遗传算法处理的是这些染色体，或者口q 基 因型个体( i n d i v i d u a l s ) 。一定数量的个体组成了群体( p o p u l a t i o n ) ， 也叫集团。群体中个体的数目称为群体的大小( p 叩u l a t i o ns i z e ) ， 也叫群体规模。而各个个体对环境的适应程度叫做适应度 l2 太原理i 大学硕士学位论文 ( f i t n e s s ) 。此外，执行遗传算法时，包含两个必需的数据转换操 作，一个是表现型到基因型的转换，令一个是基因型到表现型生 物转换。前者为编码( c o d i n g ) 操作，后者为译码( d e c o d i n g ) 操 作。1 遗传算法具有“生成+ 检测”( g e n e r a t e a n d - t e s t ) 的迭代过程， 它的基本处理流程如图所示： 图表2 遗传算法的基本流程 由图可见，遗传算法是一种群体型操作，该操作以群体中的所 有个体为对象。选择( 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 个主要操作算子，它们构成了遗传算法，使其具 太原理i 大学硕士学位论文 1 4 有了其他传统方法所没有的特性。 遗传算法包含了如下5 个基本要素：1 参数编码；2 初始群体 的设定；3 适应函数的设定；4 遗传操作设计：5 控制参数设定( 主 要指群体大小和使用遗传操作的概率等) 。这5 个要素构成了遗传 算法的核心内容。“” 首先，由于遗传算法只能处理基因型的串结构数据，不能对解 空间的解数据进行直接处理，因此必须通过编码将解数据转换为 遗传空间的基因型串结构数据。 其次，由于遗传算法的群体型操作需要，必须为遗传操作准备 一个由若干初始解组成的初始群体，在此需要确定初始群体的大 小，即此群体中初始解的个数。初始群体也称为进化的初始代。 然后对群体中的个体进行评估。遗传算法在搜索进化过程中一 般不需要其它外部信息，仅用评估函数值来评估个体或解的优劣， 并作为遗传操作的依据。评估函数值又称为适应度( f i m e s s ) 。 个体评估后，对个体进行选择。选择的目的是为了从当前群体 中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。 判断个体优良与否的标准就是个体各自的适应度值，即个体适应 度越高，其被选择的机会就越多。选择操作实现的方式很多，可 以采用轮盘赌等随机方式来选择。由此选出的个体送到配对库 ( m a t i n gp 0 0 1 ) 进行配对繁殖。 个体的配对繁殖，就是个体之间的交叉操作。对配对库中的个 体进行随机配对，在配对个体中随机设定交叉处。这样得到了新 一代个体。 1 4 太原理工大学硕士学位论文 1 5 变异操作也是进行过程中的一项操作，在所有个体范围内，以 一个固定变异概率r ，来对某位( b i t ) 进行变异。r 一般都取 值很小。“ 这样，产生新的一代个体后，再进行评估、选择、交叉、变异 等操作。这就是遗传算法的一般过程。 2 1 2 遗传算法与传统搜索算法 遗传算法的特点，传统搜索方法的对比以及分析它和若于搜索 方法与自律分布系统的亲近关系充分体现出来。 我们先来将其与几个主要的传统搜索方法作一简要的对比。 遗传算法和其它传统搜索方法的对比 解析方法是常用的搜索方法之一。它通常是通过求解使目标函 数梯度为零的一组非线性方程来进行搜索的。一般而言，若目标 函数连续可微，解的空间比较简单，解析法还是可以用的。但是， 若方程的变量有几十或几百个时，它就无能为力了。爬山法也是 常用的搜索方法，它和解析法一样都是属于寻找局部优解的方法。 对于爬山法而言，只有在更好的解位于当前解附近的前提下，才 能继续向优解搜索。显然这种方法对于具有单峰分布性质的解空 间才能进行行之有效的搜索，并得到最优解，而对于多峰分布性 质的解空间，爬山法和解析法连局部最优解都很难得到。“” 另一种典型的搜索方法是穷举法。该方法简单易行，即在一个 连续有限搜索空间或离散无限搜索空间中，计算空间中每个点的 目标函数值，且每次计算一个。显然，这种方法效率太低而鲁棒 太原理i 大学硕士学住论文 1 6 性不强，许多实际问题所对应的搜索空间都很大，不允许一点一 点地慢慢求解。 随机搜索方法比起上述搜索方法有所改进，是一种常用的方 法，但它的搜索效率依然不高。一般而言，只有解在搜索空间中 形成紧致分布时，它的搜索有限才有效。但这一条件在实际应用 中难以满足。需要指出的是，随机搜索( r a n d o ms e a r c h ) 方法并 不等同于随机化技术( r a n d o m i z e d t e c h n i q u e ) 。遗传算法就是利用 随机化技术来指导对一个编码的参数空间进行高效搜索的。而另 一个搜索方法一模拟退火( s i m u l a t e da n n e a l i n g ) 方法也是利用随 机化处理技术来指导对于最小能量状态的搜索。因此随机化技术 并非意味着无方向搜索，这一点是与随机搜索有所不同的。 当然，前述的几种传统搜索方法虽然鲁棒性不强，但这些方法 在一定条件下，尤其是将它们混合使用也是有效的。不过，当面 临更为复杂的问题时，必须采用如遗传算法这样更好的方法。 遗传算法具有十分顽强的鲁棒性，这是因为比起普通的优化搜 索方法，它采用了许多独特的方法和技术，主要有以下几方面： 一遗传算法的处理对象不是参数本身，而是对参数集进行了 编码的个体。此编码操作使得遗传算法可直接对结构对象进行 操作。所谓结构对象泛指集合、序列、矩阵、树、图、链和表 等各种一维或二维甚至三维结构形式的对象。这一特点，使得 遗传算法具有广泛的应用领域。比如： ( 1 ) 通过对连接矩阵的操作，遗传算法可用来对神经网络或 自动机的结构或参数加以优化；用遗传算法可得到 1 6 太原理工大学硕士学位论文 1 7 ( 2 ) 通过对集合的操作，遗传算法可实现对规则集合或知识 库的精练而达到高质量的机器学习目的； ( 3 ) 通过对树结构的操作，用遗传算法可得到用于分类的最 佳决策树： ( 4 ) 通过对任务序列的操作，遗传算法可用于任务规划，而 通过对操作序列的处理，遗传算法可自动构造顺序控制 系统。“” 二如前所述，许多传统搜索方法都是单点搜索算法，即通过 一些变动规则，问题的解从搜索空间中的当前解移到另解。 这种点对点的搜索方法，对于多峰分布的搜索空问常常会陷于 局部的某个单峰的优解。相反，遗传算法是采用同时处理群体 中多个个体的方法，即同时对搜索空间中的多个解进行评估。 更形象地说，遗传算法时并行地爬多个峰。这一特点使遗传算 法具有较好的全局搜索性能，减少了陷于局部优解的风险。同 时，这使遗传算法本身也十分易于并行化。， 三在标准的遗传算法中，基本上不用搜索空间的知识或其他 辅助信息，而仅用适应度函数值来评估个体，并在此基础上进 行遗传操作。需要着重提出的是，遗传算法的适应度函数不仅 不受连续可微的约束，而且其定义域可以任意设定。对适应度 函数的唯一要求是，对于输入可计算出加以比较的正的输出。 遗传算法的这一特点使它是应用范围大大扩展。 四遗传算法不是采用确定性规则，而是采用概率的变迁规则 来指导它的搜索方向。在以后的章节中我们将看到，遗传算法 1 7 太原理工大学顽士学位论文】8 采用概率仅仅是作为种工具来引导其搜索过程朝着搜索空 间的更优化的解区域移动。因此虽然看起来它是一种盲目搜索 方法，但实际上有明确的搜索方向。 上述这些具有特色的技术和方法使得遗传算法使用简单，鲁棒 性强，易于并行化，从而应用范围广泛。尤其在存在多峰问题 的大规模组合优化问题中，遗传算法有其独特的优势。这正是 本文中采用遗传算法解决优化机组有功组合问题的原因。 遗传算法和某些搜索方法的关系 遗传算法作为一种新兴的优化方法，它也与某些搜索方法有着 明显的关联关系。 遗传算法与射束搜索( b e a ms e a r c h ) 方法 射束搜索方法是为了抑制搜索空间计算量的组合爆炸而提出 的一种最优搜索方法。该方法预先把射柬幅度定义为一个长度 为n 的开放表，在搜索的进程中仅维持n 个最优节点，其它 节点一律舍去。通过搜索，若发现有新的更好的节点，则用它 把开放表中最差的节点替换掉。该搜索过程和遗传算法有一定 的相似性。遗传算法中的“群体大小”相当于射束搜索中的“射 柬幅度”。“” 遗传算法与单纯方法( s i m p l e xm e t h o d ) 单纯方法是一种直接搜索方法。它把目标函数值排序加以利 用。这样，由多个端点形成的单路就可对应山的形状，然后进 行爬山搜索。单纯方法的基本操作是“反射操作”( r e f l e c t i o n ) ， 太原理工大学硕士学位论文1 9 且反复进行。这十分类似于遗传算法中的“交叉”操作。同时 单纯方法中形成的单路的端点数相当于遗传算法中的群体大 小。显然，单纯方法和遗传算法在利用多点信息的全局处理上 是有共同点的。 遗传算法和模拟退火法 模拟退火法的最大特点是搜索中可以摆脱局部解，这是传统的 爬山法所不具备的。遗传算法中的“选择”操作是以和个体的 适应度有关的概率来进行的。因此，即使是适应度低的个体也 会有被选择的机会。在这一点上它同模拟退火法十分相似。显 然，通过在搜索过程中动态地控制选择概率，遗传算法可以实 现模拟退火法中的温度控制功能。叫 2 2 遗传算法的基本理论 模式定理和积木块假设 遗传操作中，新的个体的结构模式与其父代个体的结构模式之 间有某种相似性，而这些相似模板( s i m i l a r i t yt e m p l a t e s ) 都对应 高适应值( 高于群体的平均适应度) 。所以说，遗传算法在搜索过 程中一直在搜索群体中个体的某个重要的结构相似性。此相似模 板称为模式( s c h e m a ) 。o ” - 基于三值字符集( o ，1 ，) 所产生的能描述具有某些结构相似性 的o ，1 字符串集的字符串称为模式。符号“阜为通配符。 遗传算法中，串的运算实质上是模式的运算。模式h 中确定位 置的个数称为该模式的模式阶，记为o ( h 】。 太原理工大学硕士学住论文 2 0 显然，一个模式的阶数越高，其样本数就越少，因而确定性越 高，但在遗传算法的变异操作中，阶数高的模式更容易遭到破坏， 也就是说，阶数短的模式生命力强。 模式h 中第一个确定位置和最后一个确定位置之间的距离称 作该模式的定义距，记为6 ( h ) 。 模式的定义距越短，则该模式在交叉运算中被破坏的概率越 小，也就是说，定义距短的模式生命力强。 模式阶和定义距描述了模式的基本性质。 模式定理( s c h e m a t at h e o r e m ) ：在遗传算法选择、交叉和变 异的作用下，具有低阶、短定义距以及平均适应度高于群体平均 适应度的模式在子代中将得以指数级增长。“” 统计确定理论中的双角子机问题表明：要获得最优的可行解， 则必须保证较优解的样本数呈指数级增长。因此模式定理作为遗 传算法的理论基础，它决定了遗传算法能较好地找到全局最优解。 具有低阶、短定义距以及高适应度的模式称为积木块( b u i l d i n g b l o c k ) 。正如搭积木一样，这些“好”的模式在遗传操作下相互 拼搭、结合，产生适应度更高的串，从而找到更优的解，这就是 积木块假设的内容。 积木块假设( b u i l d i n gb l o c kh y p o t h e s i s ) ：低阶、短距、高平均 适应度的模式( 积木块) 在遗传算子作用下，相互结合，能产生 高阶、长距、高平均适应度的模式，可最终生成全局最优解。“” 模式定理保证了较优的模式的样本数呈指数级增长，从而满足 2 0 太原理i 大学硕士学位论文 2 1 了寻找最优解的必要条件，即遗传算法存在寻找到最优解的可能 性。而积木块假设则指出。遗传算法具备寻找到全局最优解的能 力，即积木块在遗传算子的作用下，能生成高阶、长距、高平均 适应度的模式，最终生成全局最优解。 遗传算法的隐并行性 遗传算法中一个串实际隐含着多个模式，遗传算法实质上是模 式的运算。一个长度为，的串，其中隐含有2 ，个模式。那么，若 群体规模为n ，则其中隐含的模式个数介于和h 之间。但由 于交叉操作的作用，并非所有的模式都能高效率地处理，定义距 较长的模式将遭到破坏。遗传算法中能以指数级增长的模式个数 的下限为0 m 0 。 隐并行性( i m p l i c i tp a r a l l e l i s m ) ：尽管遗传算法只对弹个串个 体进行运算，但却隐含地处理了卿1 个模式。遗传算法有效处 理的模式总数正比于群体数h 的立方。” 由遗传算法的隐并行性可知，在遗传操作中，尽管具有高阶、 长定义距的模式在交叉算子和变异算子的作用下遭到破坏，但遗 传算法在处理相对小数目的串时，仍然隐含地处理了大量的模式。 2 3 遗传算法性能评估 遗传算法的实现涉及到前述的五个要素，而每个要素又对应不 同的的环境存在各种相应的设计策略和方法。不同的策略和方法 决定了各自的遗传算法具有不同的性能或特性。因此，评估遗传 算法的性能对于研究和应用搜索遗传算法是十分重要的。 太原理i 太学硕士学拄论文 遗传算法的评估指标大多采用适应度值。在没有具体要求的情 况下，一般采用各代中最优个体的适应度值和群体的平均适应度 值。 定量分析遗传算法的测度包括离线性能( o f f - l i n ep e r f o r m a n c e ) 测度和在线性g ( o n l i n ep e r f o r m a n c e ) 测度。前者测量收敛性，后 者测量动态性能。之所以使用离线和在线测度是为了强调两者在 应用上的差别。一般来说，在离线应用时，优化问题的求解可以 得到模拟，在一定的优化进程停止准则下，当前最好的解可以被 保存和利用：在在线应用中，优化问题的求解必须通过真正的实 验在线实现，其好处在于可以迅速地得到较好的优化结果。 在线性能评估准则 设x e ( s ) 为环境e 下策略s 的在线性能，( t ) 为时刻t 或第t 代中 相应于环境e 的目标函数或平均适应度函数，则x e ( s ) 可以表示 为： x o ( s ) = 去正( f ) 1t 1 忙l 上式表明，在线性能可以用从第一代到当前代的优化进程的平 均渔来表示。如果在线性能用平均适应度来描述，则通过简单计 拿舞一代到当前代的各代平均适应度值对世代数的平均值即可获 得在线性能。“ 离线性能评估准则 设j 乞例为环境e 下策略s 的离线性能，则有： 太原理工大学硕士学位论文 z = 专( d t = l 其中f e ( t ) ：b e s t f e ( 1 ) , f e ( 2 ) 鑫1 ) 。 上式表明，离线性能是特定时刻最佳性能的积累平均。具体来 说，在进化过程中每进化一代就统计目前为止的各代中的最佳适 应度或最佳平均适应度，并计算对进化代数的平均值。“” 2 4 遗传算法的基本方法 2 4 1 编码技术 一维染色体编码 一维染色体编码即搜索空间的参数转换到遗传空间后，其相应 的基因呈一维排列构成染色体。具体来说，在遗传空间中，用以 表示个体的字符集中的要素构成了字符串。 一维染色体编码中最常用的符号集是二值符号集 0 ，1 ) 。基于 此符号集的个体呈二值码串。 二值编码是遗传算法中常用的编码方法。它具有以下特点： 1 ) 简单易行： 2 ) 符合最小字符集编码原则； 3 ) 便于用模式定理进行分析，因为模式定理就是以二值编 码为基础的。 二值编码形式按照精度要求将变量的取值范围分为若干段，变 量的取值便可用整数来代表，例如分为3 2 段，用于0 3 1 代表， 2 3 太原理i 大学硕士学位论文2 4 再将十进制整数换算成二进制数的f o 1 ) 编码形式，经过上述步骤 每个变量形成一个基因链，将各个变量的基因链组合在一起，形 成码链，对应于遗传学中的染色体。 将二进制基因链恢复为对应的实数，称为译码。 但二值编码具有一定的映射误差，特别是它不能直接反映出所 求问题的本身结构特征，因此很难满足前述的生成有意义积木块 编码原则。 多参数映射编码 在优化问题中，常常有多参数优化问题，即需要同时优化多个 参数。对此类问题，遗传算法常用多参数编码，基本思想为把每 个参数先进行二值编丹得到子串，在把这些子串连成一个完整的 染色体。 参数的离散化编码 在许多优化问题中，尤其是优化控制问题中，优化的不仅是一 个控制参数，而是一个连续控制函数。在用遗传算法求解此类问 题时，需要把问题缩小成有限参数的形式后，再对参数编码。此 种变换称为离散化。 可变染色体长度编码 在自然界生物进化过程中，越是高等生物其染色体越长。也就 是说，生物进化过程中，染色体的长度不是固定不变的。由此提 出的可变染色体长度编码又称为g a ( m e s s y g a ) 。 二维染色体编玛 太原理工大学硕士学位论文2 5 当在优化问题中，问题的解成二维或多维的表示。此时，用一 维染色体编码变得不方便，且交叉操作不直观。这种问题，要用 多维编码来解决。 如在处理二维图像的问题中，运用二维染色体编码的方法，染 色体表示为一个二维的二值数组。由于常用了二维编码，其交叉 操作也不同于一般的交叉操作。可采用纵横交叉或窗口交叉的方 法。 在本文中，机组的有功调度问题其实是一个二维数组的组合优 化问题，所以在本文的算例中，参数编码采用二维染色体编码方 式，其交叉操作也就采用窗口式交叉操作。“” 总之，参数的编码应该根据优化问题的具体结构来选择适合的 方法。参数编码以及其染色体交叉操作的方式的适当与否，对于 充分发挥遗传算法的功能，正确产生最优解，起着重要的作用。 2 4 2 群体的设定 在遗传算法中，问题的解采用数字串的形式表示个体。每个个 体包含若干个变量，他们的取值即为优化问题的一组解。遗传操 作是对众多个体同时操作的，众多的个体组成了群体。编码设定 后以随机产生的若干个体组成一个群体，构成第一代解群。般 说来。这些初始解的素质都很差，遗传算法的任务是从第一代群 体出发，模拟进化过程，择优汰劣，最后得出最佳的群体和个体， 以满足优化要求。 初始群体的设定策略 太原理工太学硕士学位论文 2 6 遗传操作是对众多个体同时进行的。这众多的个体组成了群 体。遗传算法的处理流程中，编码设计后的任务就是设定初始群 体，并以此为起点一代代进化，直到按某种进化停止准则来终止 进化过程，由此得到最后一代。 遗传算法的初始群体中的个体是随机产生的。一般地，初始群 体的设定采取以下策略： ( 1 ) 根据问题固有知识，设法把握最优解所占空间在整 个问题空间中的分布范围，然后在此分布范围内设 定初始群体。 ( 2 ) 先随机生成一定数目的个体，然后从中挑出最好的 、个体加到初始群体中。这种过程不断迭代。直到初 始群体中个体数达到了预先确定的规模。1 群体规模的确定与群体多样性 群体规模( 即群体中的个体数目) 的确定受遗传操作中选择操 作的影响很大。由模式定理可知，若群体规模为m ，则遗传操作 可从这m 个个体中生成和检测m 3 个模式，并在此基础上不断形成 和优化积木块，直到找到最优解。显然m 越大，遗传操作所处理 的模式就越多，生成有意义的积木块并逐渐进化为最优解的机会 就越高。也就是说，群体规模越大，群体中个体的多样性越高， 算法陷入局部解的危险就越小。因此。从考虑群体多样性出发， 群体规模应较大。 但是，群体规模太大显然会带来一些弊病：首先从计算效率出 发，群体越大，其适应度评估次数越多，从而计算量也增加，影 太原理工大学硕士学位论文 2 7 响算法的效能；其次，群体中个体生存下来的概率( 即选择概率) 大多采用和适应度成比例的方法，当群体中的个体非常多时，少 量适应度很高的个体会被选择而生存下来，但大多数个体却被淘 汰，这会影响配对库的形成，从而影响交叉操作。 从另一方面考虑，群体规模太小，会使遗传算法的搜索空问中 的分布范围有限。因而搜索有可能停止在未成熟阶段，引起未成 熟收敛( p r e m a t u r ec o n v e r g e n c e ) 现象。显然，要避免未成熟收敛 现象，必须保持群体的多样性，即群体规模不能太小。 如果某字符集中个体长度为l ，则一般地，在二进制编码的前 提下，为满足隐并行性，群体个体数只要设定为2 “2 即可。这个 比较大，因此实际应用中群体个体数的取值范围一般为几十几 百。 2 4 3 适应度函数 遗传算法在进化搜索中基本上不用外部信息，仅用目标函数即 适应度函数为依据。遗传算法的目标函数不受连续可微的约束且 定义域可以为任意集合。对适应度函数的唯一要求是，针对输入 可计算出能加以比较的非负结果。 遗传算法中将个体的变量取值代入适应度函数，算出其适应 度。适应度越大，即表示该个体具有较高的适应性。所以适应度 用以评价个体的优劣，为群体的进化提供依据。 在具体应用中，适应度函数的设计要结合求解问题本身的要求 而定。适应度函数做为选择操作的依据，其设计直接影响到遗传 算法的性能。 查堡兰三垄堂! 主兰竺塑查塑 适应度函数的设计对遗传算法的影响 对适应度函数的定标可以克服未成熟收敛和随机漫游现象，从 而提高遗传算法的优化搜索性能。适应度函数的设计和遗传算法 中的选择操作直接有关，所以它对遗传算法的影响还表现在其它 方面、 适应度函数影响遗传算法的迭代停止条件 严格地讲，遗传算法的迭代停止条件目前尚无定论。当适应度 函数的最大值已知或者最优解适应度的下限可以确定时，一般以 发现满足最大值或准最优解作为遗传算法迭代停止条件。但是， 在许多组合优化问题中，适应度最大值并不清楚，其本身就是搜 索的对象，因此适应度下限很难确定。所以，在许多应用事例中， 若发现群体个体的进化已趋于稳定状态，也就是说，若发现占群 体一定比例的个体己完全是同一个体，则算法终止迭代。 适应度函数与问题约束条件 遗传算法由于仅依靠适应度来评估和引导搜索，所以求解所固 有的约束条件不能明确地表示出来。在实际应用中，许多问题都 是带约束条件，像货郎担问题就是一个典型的约束组合优化问题。 用遗传算法求解此类问题时，需要考虑一些对策。 如在进化过程中，迭代一次就检测一下新的个体是否违背了约 束条件。如果没有违背，则作为有效个体，反之，则作为无效个 体被除去。这种方法对于弱约束问题求解尚为有效，但对于强约 束问题来说则效果不佳。因为在这种情况下，寻找一个有效个体 的难度不亚于寻找最优个体。 太原理工大学硕士学位论文 作为对策，可采用一种惩罚方法( p e n a l t ym e t h o d ) 。该方法的 基本思想是设法对个体违背约束条件的情况给予惩罚，并将此惩 罚体现在适应度函数设计中。这样，一个约束优化问题就转换为 一个附带考虑代价( c o s t ) 或惩罚( p e n a l t y ) 的非约束问题。 通过选择适当的惩罚函数与惩罚系数，对约束条件进行处理， 可以使约束问题转化为非约束问题。但是，需要注意的是，惩罚 函数的值在约束条件边界处会发生急剧变化。 2 4 4 遗传操作 遗传操作包括三个基本遗传算子( g e n e t i co p c r m o r ) ：1 选择； 2 交叉；3 变异。 遗传算子有如下特点： 1 遗传算子的操作都是在随机扰动的情况下进行的，即遗传 操作是随机化操作。因此，群体中个体向最优解迁移的规则是 随机的。但遗传操作进行的这种随机操作是一种高效有向的搜 索，区别于一般随机搜索方法所进行的无向搜索。 2 遗传操作的效果和上述三个遗传算子所取的操作概率，编 码方法，群体大小，初始群体以及适应度函数的设定密切相关。 3 三个基本遗传算子的操作方法或操作策略随具体求解问 题的不同而异，更具体地讲，是和个体的编码方式直接相关。 下面就常见的二值编码方法论述三个基本遗传算子。 太原理i 大学硕士学位论文 2 9 1 选择算子 从群体中选择优胜的个体，淘汰劣质个体的操作叫做选择。选 择的目的是把优化的个体直接遗传到下代或通过配对交叉产生 新的个体再遗传到下一代个体。选择操作是建立在群体中个体的 适应度评估基础上的，目前常用的选择算子有以下几种。 1 适应度比例方法( f i t n e s sp r o p o r t i o n a lm o d e l ) 适应度比例方法是目前最基本也是最常用的选择方法。也叫赌 轮或蒙特卡罗选择。该方法中，各个个体的选择概率与其适应 度的值成比例。 设群体大小为n ，其中个体i 的适应度为丘，则i 被选择的概率 p 。为： 显然，概率p 。反映了个体i 的适应度在整个群体的个体适应度 总和中所占的比例，个体适应度越大，其被选择的概率就越高。 反之则低。” 2 最佳个体保存方法( e l i t i s tm o d e l ) 该方法的思想是把群体中适应度最高的个体不进行配对交叉而 直接复制到下一代中。所以这种选择操作又叫做复制。“” 3 期望值方法( e x p e c t e dv a l u em o d e l ) 在第一种选择方法中，当个体数不太多时，依据产生的随机数 f “ 一 正 = 巳 太原理i 大学硕士学位论文 有可能不正确地反映个体适应度的选择，即存在统计误差。为 克服这种误差，期望值方法用如下方法选择。 一，计算群体中每个个体在下一代生存的期望数目( 期望数 目等于个体适应度除以平均适应度) ； m = z ，= z ( z n ) 二， 若某个体被选中参与配对和交叉，则其在下一代中的期 望数目减去0 5 ；若不参与交叉和配对，则其期望数目 减l ； 三， 之后若一个个体的生存期望小于0 ，则该个体不参与选 择。 4 排序选择方法( r a n k b a s e dm o d e l ) 该方法先计算每个个体的适应度，根据适应度大小对群体个体 进行排序，然后把事先设计好的概率表按序分配给个体，作为 各自的选择概率。该方法需要事先确定选择概率与序号的关系， 大体思