（电力系统及其自动化专业论文）城市配电网优化规划模型和算法的研究及其实现.pdf

! 业堡兰 型卫型! 垒型垡丝塑型蕉型塑塞鎏塑型塞壁! 壅塑 a b s t r a c t d i s t r i b u t i o ns y s t e mp l a n n i n gi sai l o n - l i n e a ra n dc o m p l i c a t e dp r o b l e mt h a tw a s s i m p l i f i e d t o o g r e a t i y i n m a n yp r e s e n tm o d e l s s oam o r ec o m p l e t em o d e lw a s p r o p o s e di nt h i sp a p e r r e l i a b i l i t y , p a t h so fl i n e s ，m i d d l en o d e s ，c i r c u i tn u m b e ra n d t y p eo fl i n e s ，r e b u i l d i n ga n dm u l t i p l el o a da n dr u n n i n gs t a t e sw e r ec o n s i d e r e di nt h e n o v e lm o d e l o n eo ft h er e a s o n sf o rt h ef o r m e rs i m p l em o d e l sw a st h el a c ko f p o w e r f u le n o u g h a l g o r i t h m s oam o r er o b u s ta n de f f i c i e n tm e t h o dw a si n t r o d u c e d t h i sm e t h o dw a s b a s e do nt h ee v o l u t i o n a r ya l g o r i t h mt h a tw a sk n o w na sak i n do fg e n e r a l p u r p o s e m e t h o df o rn o n l i n e a ra n dc o m p l i c a t e do p t i m i z a t i o np r o b l e m w h e np e o p l eu s e de a f o rd i s t r i b u t i o ns y s t e mp l a n n i n g ，t h es p e c i a lk n o w l e d g ea b o u tt h ed i s t r i b u t i o ns y s t e m w a so f t e n i g n o r e d t h i sp a p e r f o u n daw a yt ou s et h e k n o w l e d g eb yk e e p i n g c o n s t r u c t i n gt h en e to f d i s t r i b u t i o ns y s t e mi n s t e a do f o p e r a t i n go n t h ec h r o m o s o m eo r o t h e rn u m e r i c a ld a t a t h u s ，t h e a l g o r i t h m sp e r f o r m a n c ew a sh i g h e r a n dm o r e c o m p l i c a t e dm o d e lw a ss o l v a b l e w i t h i na c c e p t a b l et i m e a tt h es a m et i m e ，s o m e i m p r o v e m e n tw a s m a d ef o re a a tl a s t ，s o m ee x a m p l e sw e r ep r o v i d e da n dt h er e s u l ts h o w e dt h a tt h em o d e lw a s f e a s i b l ea n dt h ea l g o r i t h mw a se f f e c t i v e k e y w o r d s ：d i s t r i b u t i o ns y s t e mp l a n n i n g ，m o d e l ，a l g o r i t h m ，e v o l u t i o n a r y a l g o r i t h m ，r e l i a b i l i t y f 哦l 论史 城市配i 乜嘲优化规划模型和算法的硼f 究及其实现 1 绪论 1 1 配电网规划的意义 随着国民经济的发展和人民物质文化生活水平的不断提高，社会对电力需求 越来越大，对供电质量和供电可靠性要求越来越高，促使电力事业迅速发展，电 网不断扩大，技术不断提高。 通常把电力系统中二次降压变电所低压侧直接或降压后向用户供电的网络， 称为配电网( d i s t r i b u t i o n n e t w o r k ) 。配电网是电力系统电能发、变、送、配中最 后一个向用户供电的环节。它由架空线或电缆配电线路、配电所或柱上降压变压 器直接接入用户所构成。 从8 0 年代起，我国城市配电网的发展进入了一个新的时期。各城市在总结 城网改造经验的基础上，认真研究在城市经济建设快速发展的新形势下，城市电 网如何发展的新问题，认识到迫切需要编制一个整体改造的远景发展的城市电网 舰划，包括用统一技术规范和质量标准来促进建设一个经济合理和安全可靠的现 代城市电网。 配电网的特点是设备繁杂，用户众多，覆盖面广，地理情况变化多样，且受 用户增容等外界条件以及城市建设等因素的影响。为了满足需要，配电管理系统 得到大力发展。通常把从变电、配电到用电过程的监视、控制和管理的综合自动 化系统，称为配电管理系统( d i s t r i b u t i o nm a n a g e m e n ts y s t e m ，简称d m s ) 。其内 容包括配电网数据采集和监控( s c a d a ，包括配网进线监视、配电变电站自动 化、馈线自动化和配电巡检及低压无功补偿) 、地理信息系统、网络分析和优化 ( n e t w o r ka n a l y z e ，简称n a ) 、工作管理系统、需方管理( 包括负荷监控及管 理和远方抄表及计费自动化) 和调度员培训模拟系统几个部分。其中，配电网的 网络分析和优化包括潮流分析和网络拓扑优化，目的在于通过以上手段达到减少 线损，降低运行成本，改善电压质量等目的。 传统上，配电网优化仅指根据预测的负荷分布进行离线的优化计算。随着配 电网的发展，配电自动化水平不断提高，配电网的在线调节和控制能力不断增强， 配电网的灵活性和可靠性也得到一定的提升。在这些条件下，在线优化成为新的 研究方向，通常称之为网络重构。因此，现在的优化。包括了离线和在线两个方 面。本文中的优化规划仅指离线优化。 1 2 配电网优化规划的内容 目前，各个城市先后建立了2 2 0 k v 超高压外环网或双环网，进一步简化输 丛尘论文城市配j u 网优化捌划模型和算法的研究及其实现 配电电压等级，以2 2 0 k v 或1 1 0 k v 高压变电所深入市区，城订电网结构模式和 变、配电所的主接线进一步得到改进。地下电缆增加很快，架空配电线绝缘化， 配电装置小型化，采用g i s 、综合自动化等新设备、新技术有很大进展，使城市 电网趋向合理，可靠性提高，逐步向着现代化方向发展。 为了进一步建设改造城市配电网，采取了以。f 一些技术措施【1 i ： a ) 加强规划工作 搞好规划将带来长远效益。城网规划应以负荷预测为依据，以提高可靠 性为主要目标，而负荷预测要针对城市电网布局的特点，强调做好城市分区 小块负荷预测。对规划中的电网结构原则和供电设施的标准化等。些主要问 题，如电网接线模式、变配电所的主接线、合理容量的配置、用户供电方式 等，应能够通过优化计算和技术经济论证，考虑到实施的可行性，用优化方 法做出综合评价，确定规划的技术原则。 b ) 简化电压等级 简化电压等级，减少电压层次，逐步提高配电电压等级有利于配电网的 管理和经济运行。目前基本确立以3 8 0 2 2 0 v 、1 0 k v 、3 5 ( 6 3 ) k v 、1 1 0 k v 和 2 2 0 k v 为标准电压，很多城市逐步简化成2 2 0 1 1 0 1 0 0 3 8 k v 、 2 2 0 6 3 1 0 0 3 8 k v 和2 2 0 3 5 1 0 0 3 8 k v 四级降压层次，目标是以2 2 0 k v 为基 础，高、中、低压各只采用一级，避免重复降压。 c ) 建设外围环网，高压深入市区供电 城市外围的环网是供应城市配电网的主要电源，是重要的骨干网架，对 其可靠性要求很高，通过环网上的枢纽变电所向城市中心直接放射供电和经 降压配电。 高压深入城市负荷中心是城市用电大幅增长后的必然趋势。 d 1 改进电网结构和设施 城市配电网进一步向简化、完善和高可靠性发展，如变电所接线开始推 广采用线路变压器组、单母线接线等。配电网络结构推广采用多回路、各式 上 ：网、多分段多连接等方式，以提高利用率和供电可靠性，馈线加装自动化 装置以减少故障恢复时间。各种先进的现代化配电设施得到逐步应用，配网 自动化水平不断提高。 在作城市配电网规划时，通常把变电所布局和网络连接分开进行。一般是根 据预测的负荷分布进行优化计算，确定供电区内最佳的变电所数及其规模，然后 在此基础上进行网络规划计算，确定在给定目标条件下的最佳网络结构。 a 1 变电所最佳供电面积优化计算 为了使城市居民和各企业获得充足的电量，需要建设一定数量的变电所， 坝i ：论义 城市配电删优化规划模型和算法的研究及其实现 变电所数量多，则每座变电所供电面积小，线路短，电压损失、线路功率损 耗也就小。反之，则情况相反。 通过变电所最佳供电面积计算可得供电区内应建几座变电所，在帽周的 条件下通过变电所最佳容量及变压器台数计算也可得供电区内应建几座变 电所。两者是一致的。 b ) 网络优化规划 在电网规划模型中，通常以电网建设的总投资和电能损失、维修费用为 同标函数。在满足用户用电、保证电能的前提下，对众多的方案用不同的目 标函数优选的结果是不同的。而在电网规划时还会受到种利t 限制，如自然条 件、状态参数( 电压损失、过负荷等) 的制约，这称为约束条件f 2 l 。目标甬 数与约束条件、状态参数( 变量) 有关，三者之间进行协调处理即为“优化”。 规划有单阶段和多阶段【3j 之分，单阶段规划是针对某一个负荷水平，进 行网架规划，只需考虑已有网架，不管今后发展。而一个实际的城市电网， 始终伴随社会和经济的发展而不断发展，不同的时期会有不同的发展速度， 决不会停留在某一个水平上。所以，作各阶段规划时要前后协调，以免发生 前期架设的线路后期可能被拆掉的情况；同时，不是以各个阶段的性能指标 最优来选取方案，而是以整个过程总的性能指标最优来评价方案，这种规划 方法称多阶段规划。 1 3 国内外研究现状 电网优化规划是一个十分复杂的问题，主要有以下几个难点： a ) 多目标性； 在实际中，对一个电力网络不仅要求投资费用少，还要求可靠性高、占 地面积少、环境污染小等，这样就存在一个如何综合衡量多个目标的问题。 b ) 复杂性； 配电网的建设和运行都是一个复杂的过程，其中包含很多与实际相关的 细节，例如，建设线路时要考虑线路的走径、分支节点和中间节点如何规划 等。这些复杂的问题如何在模型中得到反映。值得深入的研究。 c ) 非线性； 电力系统是一个非线性的系统。可对非线性问题线性化，以降低复杂度， 然后通过逼近、迭代的方法来求解，或者采用某些智能算法进行计算。 d ) 整数性： 电力线路的建设与投运是整数性的，是或者不是，不存在一个过渡状态。 正是这种不连续性，给分析和处理带来了很大难度，因为此时无法利用导数 堡! ：堡塞塑量虫配电网优化规划模型和算法的研究及j e 实现 概念来推测某状态点周围的性态。目前处理整数性的仍是“枚举”，各种改 进也都是在如何提高枚举中的效率上做文章。 e ) 不确定性： 未来的负荷，发电量以及线路的投资费用等采用的均是当前的预测值， 其准确性尚有待将来的验证。在社会和经济的发展过程中还存在其他各种不 确定的因素。 n多阶段性。 在规划中为了避免短视行为和盲目性，应从长远的角度从整数综合考虑 电网的布局。即要求在当前阶段的规划中计及各待选线路对以后各阶段的影 响。 目日口，国内外学者已研究出各种配电网优化规划的模型和算法。其中，模型 主要有最小运输费用模型、网络模型和基于线路选择的各种非线性模型。最小运 输费用模型认为电能在电网中的传送和货物在交通网络中的运输情况类似，可采 用最小运输费用模型进行计算；网络模型将配电网络用有向图表示，然后根据图 的结构建立方程；网络模型与最小运输费用模型都是完全的线性化模型，未能有 效的描述问题，而应用较广的是基于线路选择的非线性模型，该模型在给出的可 选线路集合中，选出某些线路，构成相应的网络，在约束条件下。使非线性的目 标函数值最小。这些模型解决了配电网优化规划中的某些问题，但是，还有些 尚末得到有效的解决，例如线路走径、中问节点、可靠性、原有网络的改建等。 由于配电网优化是一个高度复杂的非线性、不确定问题，因此常规的数学规 划方法很难有效的解决问题，为此，发展了多种解决配电网优化问题的算法。主 要包括支路交换算法、遗传算法 4 j 【5 】【6 】【7 1 、进化规划和进化策略队禁忌算法 【4 】【7j 【9 】、模拟退火算法】等。支路交换算法对辐射结构配电网重复进行支路交 换，直到目标函数值最好为止，用这种方法只能达到局部优选，未能较好的满足 问题的要求：遗传算法是求解全局优化问题的随机搜索算法，遗传算法应用与配 电网优化规划中，己取得很多研究成果，其效果也得到一定的认同；进化规划和 进化策略与遗传算法一样属于模拟进化算法，但更重视变异的作用，通常认为其 效果不亚于遗传算法。禁忌算法是一种单线随机搜索算法，往往和其他算法联合 使用；模拟退火算法利用概率突跳性在解空间中随机寻找目标函数的全局最优 解，和禁忌算法一样，往往也是和其他算法相结合。这些算法往往没有利用配电 网优化规划问题的专有知识，而仅依赖那些通用算法的计算能力。虽然在解决简 单模型所描述的问题时，性能基本可以接受，但“弱方法”的计算能力妨碍了更 全面、更复杂问题的解决，这也是现有的配电网优化规划模型相对简化的一个原 因。 碳小论文城市配电刚优化规划模型和算法的研究及j 实现 1 3 本文工作 本课题的研究工作主要包括以下几点： a )了解配电网优化规划方面的概况，包括配电网优化规划的意义、要求、 模型和算法。 b ) 深入分析各种模型和算法， 出新的方案。 c ) 编写软件，通过模拟计算， 找出目前的不足之处，针对存在的问题，提 验证新方案的有效性。 型垄型l 一 塑虫墼! 鱼旦垡垡塑型型塑整鲨笪丛! ；丛2 塞型 2 配电网优化规划模型简析 配电网一般运行在辐射状( 树状) 结构下，其优点是结构简单、节省电网投 资、简化继电保护设计、限制供电系统的短路容量。因此，现有的模型大多是以 辐射网优化规划为主。 2 1 最小运输费用模型 在做网络规划时，供电范围内各负荷点的负荷分配给各变电所，要求变电所 对每块负荷实现最经济而又不使变压器发生过负荷。可采用最小运输费用模型 进行计算，因为电能在电网中的传送和货物在交通网络中的运输情况类似。最小 运输费用模型以电源变电所供给负荷点的电能为货物，以从电源变电所到负荷的 可能最小距离为运输距离，考察运输费用。 a ) 目标函数 n gn d f = m i n s l 。乃 f = i = l 式中，n g ：电源变电所数； n d ：负荷数； 观“从电源变电所i 到负荷j 的可能最小距离； p ，：从电源变电所i 供给负荷j 的负荷量。 b ) 约束条件 n g 只= 弓，= 1 , 2 d i = l n o 0 = s ，i = 1 , 2 n d i m 式中，只：负荷j 的负荷量； s ：电源变电所i 的输出负荷。 用最小运输费用模型确定的是一个是电网投资和运行费用均可行的初始网 架，但还不是最合理的最终网架。需要进一步对其接线方式作相应修改，以便在 初始网架基础上形成一个安全与经济统一的电网接线方案。 最小运输费用模型是过于简化的线性化模型，至多只能形成主干网络的参考 解，远远不能满足优化的要求。文献1 2 虽然采用一种逐次线性化方法，可以在 一定程度上消除线性化带来的误差，但是，这种线性化只能应用于辐射网中的线 路选择，而配电网优化的很多方面是很难全部线性化的。 6 坝1 。论义 城市配l u 嘲优化规划模型和算法的碰究及j t 实现 22 网络模型 对应于图论中的概念，将配电网络用有向图表示，图的弧就是连接两节点之 间的线路图的节点就是接受或发送功率的负荷、发电厂或变电站。然后根据图 的结构建立方程。该模型以各弧段上输送单位功率( 或电流) 需要的费用为弧的 权以实际输送功率为变量，考察综合费用。 a ) 目标函数 f = m i n e c 女x 式中，c ：常数，k 弧段上输送单位功率( 或电流) 需要的费用，包括建造线 路的投资费和运行费； a ：待建线路数； x 。：k 弧段上的输送功率。 b ) 约束条件 以一x ，l ，j e p e 川 e o n g 0 x s u ，k a 式中，p ：网络节点的集合； l ：j 节点负荷值； i n ：指向j 节点方向的弧段； o n ，：离开j 节点方向的弧段； u 。：k 弧段的允许传输功率上限。 网络模型与最小运输费用模型很接近，同样不能满足优化的要求。 2 3 基于线路选择的非线性模型 基于线路选择的非线性模型是在给出的可选线路集合中，选出某些线路，构 成相应的网络1 3 】【1 3 】【1 4 】1 1 5 l ，使得非线性的目标函数最小。 a ) 目标函数 f = r a i n z ( c + p 咒。衅) r = l 式中， f ： 目标函数，年综合费用； z 。：二值变量，当支路i 被选中时取l ，否则取o ； c ：支路i 的年综合费用，包括投资和维护费用等，由于配电网的建 设和使用周期较长，因此一般需要进行一些折算； 魁论义城市配j 乜网优化规划模型和算法的研究及e 实现 p ： 电价： l ： 最大运行小时数： 尸：支路i 的有功损耗； 棚；可选支路数 b ) 约束条件 节点的功率平衡约束； 支路的电压平衡约束； 支路的最大电流约束； 支路的最大电压降约束； 运行网络的辐射状约束。 线路选择模型是应用最广泛的模型。事先确定可选的线路，大大a & j 、了解空 间的规模。如果可选线路选择的比较适当，往往可以取得较优的结果。 但是，过分限制解空间的规模，在没有系统、可靠、有效的方法确定可选线 路的情况下，只是依靠专家的经验和技巧，将会使得该模型缺乏取得更优解的条 件。 浚模型的目标函数，没有包含配电网可靠性的相关信息。仅用于形成辐射网。 由于该模型保留了原始问题中存在的非线性，从而对优化的算法提出很高的要 求。它要求优化算法能够解决大规模、非线性、高复杂度的问题。 有些文献【u 1 该模型的目标函数进行了简化，较多的是采用线性化的方法。但 是，这些模型在消去配网优化问题本身固有的非线性时，没有采取指应j ： 匀补偿措 施，因此，这些过于简化模型不能完全表达原有问题的需要，扶而不能得到更 优的解。 塑：! ：丝直城市配乜网优化规划模型和算法的研究及j 实现 3 配电网优化规划算法分析 配电网优化是一个高度复杂的非线性问题，因此常规的数学规划方法很难有 效的解决问题，为此，研究人员发展出多种解决配电网优化问题的方法，这些方 法使用了各种通用优化算法，包括遗传算法、禁忌算法、人工神经网络法等。本 章将列这些算法做一些讨论，并选出一种作为本文配电网优化规划算法的基础。 3 1 通用优化算法简介 本节将对通用优化算法做一些简介，通过层层的细化分类和讨论，确定本文 关于通用优化算法的研究范围。 31 1 通用优化算法的分类 目前，经典算法已被认为不能满足配电网优化规划问题的求解。而适用于大 规模、非线性、高复杂度优化问题的有效方法主要有两种： a ) 邻域搜索法 从初始解或解群出发，对其邻域进行搜索并用更优解替换原有的解来实 现优化。 b ) 基于系统动态演化的方法 将优化过程转化为系统动态的演化过程，基于系统的动态演化束实现优 化，如神经网络等。这类方法要求大量数据柬促进系统的演化，而且演化的 结果与所给的数掘是密切相关的。 由于配网优化问题是复杂多样的，很难保证第二类方法在一定的初始数掘i ： 能够演化出适应范围较广的配网优化系统，目前研究也没有发现此类方法有较好 的结果。因此，本文将主要研究邻域搜索方法， 31 2 邻域搜索法的分类 计算机求解优化问题的主要手段就是对优化问题的可行解空问进行搜索，而 按照搜索策略的不同，我们可以将主要的搜索方法分为三类： a ) 枚举法 枚举法对整个可行解空间的所有点的性能都进行比较并找出最优点。枚 举法的策略最简单，计算量也最大。而且枚举法只能应用于可行解空间是有 限集合的情形。 b ) 解析法( 梯度法) 型1 ：堡：里地立刚l b 网优化规划模型和算法的研究及) e 实现 解析法在搜索过程中主要使用目标函数的解析性质，如一阶导数、二阶 导数等。解析法根据目标函数的梯度方向来确定下一步的搜索方向。所以又 可称为“梯度法”。解析法采用的是“最速下降( 上升) ”策略，即沿着最陡 的方向爬向一个局部最优点。但是当目标函数有多个极值点时，爬山法难以 找到全局最优点。主要的解析搜索方法有：n e w t o n 法、共轭梯度法、爬l i i 法等。 c ) 随机法 随机法在搜索过程中对搜索方向引入随机的变化，使得算法在搜索过程 中以较大的概率跳出局部极值点。随机法可分为盲目随机法和导向随机法。 盲目随机法在解空间中随机地选择不同的点进行检测。导向随机法以一定的 概率( 于当前搜索到的最优解的好坏程度和搜索时间有关) 改变当前的搜索 方向，在其他方向上进行搜索。导向随机法主要有进化搜索方法( 包括遗传 算法、进化策略、进化规划等) 、模拟退火法、禁忌算法( t a b u 搜索法) 等。 研究表明，由于配电网优化问题的非线性及复杂性，应用枚举法和解析法难 以取得较好的结果。因此，下面将仅讨论各种随机搜索方法。 3 1 3 随机法的搜索策略 一个优化问题的搜索空问，根据不同的搜索方法，可以分成一些子空间。当 我们对于目标函数的性质不清楚时，我们可以将每个子空问视为一个分布未知的 随机变量，算法对某个子空间的一步搜索可以视为对这个随机变量的一次实验 ( 采样) ，而搜索算法在搜索策略上的差异就表现在它们对各个随机变量分配实 验次数的策略上，也就是算法对于改变当前搜索方向，转移到未知搜索的子空间 所采取的策略上的差异上。 对于具有多个极值点的复杂目标函数，在某一个随机变量进行实验的过程 巾，搜索算法将会积累有关这个随机变量分布状况的一些信息( 子空间的一些解 析信息，例如近似的梯度方向等) ，利用这些信息，可以更加有效的搜索这个子 空间，以获得性能上的提高。显然，仅仅对某个随机变量进行若干次实验，并不 能保证得到全局最优值，而不利用所积累的信息将实验次数合理分配到各个随机 变量，又会造成算法效率低下，这就使得算法在分配实验次数时面临着两难问题。 这就是利用积累信息与探索未知空问的矛盾。 各种搜索方法在解决这个矛盾时采用了不同的策略。我们应当认识到，一个 好的算法在处理利用积累信息与探索未知空间的矛盾时必须采用折衷的策略，既 利用积累信息探索当前子空间，又要兼顾到对未知子空间的探索。一味的盲目搜 索而完全不利用积累信息，将使算法效率低下到不可接受的程度。 堡生堡兰塑立墼虫网优业规划模型和算法的研究及j e 实现 3 2 支路交换算法 支路交换算法 1 用于辐射式结构配电网优化的计算方法。其基本思想是：从 一个初始辐射型网络开始，加一条闭合联络支路，使辐射型网络形成一个闭合回 路，然后将网络中某一条支路断丌，恢复网络的辐射型结构，并按给定目标函数 对新辐射型网络进行计算。重复上述过程，直到目标函数值最好为止，对应的网 络即为所选接线。用这种方法虽然只能达到局部优选，但简单实用。 支路交换法的搜索策略是几乎完全依赖积累信息，在某个子空问中，对当前 点的某个有限临域进行随机搜索，寻找更好的点，从而没有跳出局部极值点的机 制。 支路交换的过程是指向局部最优解的【 】，每次交换可得到一些改进，降低目 标函数值。步骤简单。易于实现，速度也很快，可满足在线优化在计算时问上的 要求。但是，在做对对阎要求很低的离线优化时。往往陷入局部优值后不能跳出， 因此，效果不是很好。 3 3 进化计算( e c ) 3 3 1 进化计算的起源 尽管人们已经可以让计算机完成些过去无法想象的任务，但仍然有f ：多复 杂的实际问题得不到很好的解决【l g l 【坞1 ，例如人工智能模拟【2 0 i i “1 、非线性优化、 图像识别等等。这些问题所具有的一个共同特点就是它们都是高度非线性的。许 多学者都认识到常规方法是无法解决这些问题的，要解决好这些问题需要一些具 有自组织、自适应能力的大规模并行算法。另一方面，自然界的各种生物( 包括 人类) 都具有各种复杂的结构，并能够产生非常复杂的行为，因此，模拟生物或 备种自然现象就成为了一种研究方向。这些研究导致了一些新方法的出现，其中 就包括进化算法。 自然界中存在着各种各样的生物，这些生物的多样性和复杂性是人们至今难 以了解的。达尔文的生物进化学说认为，自然界中丰富多彩的生物是自然选择和 进化的结果，现代分子生物学的发展也为这一学说提供了直接的证据，所有生物 都具有遗传物质d n a 和r n a 。进化使得生物能够更好的适应自然环境。虽 然进化的结果非常复杂，但进化的过程却很简单：繁殖、变异、竞争、选择。 在自然界的启示下，一些学者希望通过模拟自然界的生物进化过程来解决实 际问题，这就导致了进化计算这一学科的诞生。自然选择消除了软件设计中的最 大障碍：需要实现描述问题的全部特点，并说明针对问题的特点，程序应采取的 措施。 塑二坚堡坚塑立墼电网优化规划模型和算法的研究及e 实现 进化计算的研究起源于2 0 世纪5 0 年代末，成熟于8 0 年代。在6 0 年代中叶， h o l l a n d 提出了遗传算法( g a ；g e n e t i c a l g o r i t h m ) ，r e c h e n b e r g 和s c h w e f e t 提出 进化策略( e s ：e v o l u t i o n a r ys t r a t e g i e s ) ，f o g e l 提出了进化规划( e p ：e v o l u t i o n a r y p r o g r a m m i n g ) ，形成三大主要流派。这三种方法具有共同的本质，分别强调了自 然进化中的不同方面：遗传算法强调染色体的操作，进化策略强调个体级的行为 变化，而进化规划则强调种群级上的行为变化。现在学术界把遗传算法、进化策 略和进化规划通称为进化计算。 近年来的研究表明，进化理论不仅是生物学的统一理论，而且进化可以作为 所有智能过程的统一描述。不管学习是由个体、物种，还是由社会群体实现的， 每个智能体都采用了功能上等价的繁殖、变异、竞争和选择。每个系统具有产生 新行为的变异性单元和存储知识的储蓄库。学习是通过某些形式的随即搜索和用 于了解环境的学习系统实现的。学习系统不断进化调节它的行为，以在很宽范围 内达到所需的要求。智能不是进化的最终结果，而是被编织成过程本身。智能和 进化是不能分开的。 进化策略与进化规划在很多方面具有明显的相似性，排除思想本质的讨论， 在工程上，一种的结果往往可以直接应用到另一种上，因此后面将只讨论遗传算 法和进化规划。 3 3 2 遗传算法 遗传算法是求解全局优化问题的随机搜索算法【2 ”，可以解决组合优化问题以 及目标函数或某些约束条件不可微的非线性优化问题。 遗传算法采用某种编码技术来表示各种复杂的结构，并将每个编码称为一个 个体。算法维持一个一定数目的编码集合。称为种群，并通过对种群中的每个个 体进行某些遗传操作来模拟进化过程1 2 3 1 ，最终获得一些具有较高性能指标的编 码。常用的遗传操作有变异、交叉、选择等等。其中变异是模拟自然界中生物遗 传物质的变异，交叉则是模拟有性生殖过程中的染色体交换过程，选择则是模拟 自然界的优胜劣汰过程， 遗传算法中把要进化的对象用二值串表示，很像生物体中的基因。所以遗传 算法被认为是采用还原主义的观念和自下而上的途径。其主要的理论基础是建筑 块理论。g a 每对种群的进行一次操作就会同时作用于大量的模式。，利用建筑块 的概念可以证明，繁殖和选择对于建筑块的优化具有隐含并行性。这一性质被称 为“隐含并行性”。遗传算法的隐含并行性使得它能利用较少的串来搜索、发掘 和校验空闻中的大量区域。 遗传算法强调交叉的作用，而把变异看作是第二位的。h o l l a n d 认为：进化 ! 坐! ：堡苎 塑巫型皇塑垡丝塑型夔型塑簦鎏盐婴塑丝! ! 塞塑 是一个运行在染色体上的过程，而不是运行在它们所编码的生命体上的过程，交 叉繁殖过程是进化发生的地点。 图3 3 1g a 的定义( m 为子代规模) 通常我们把h o l l a n d 所提出的算法称为标准遗传算法( c a n o n i c a lg e n e r i c a i g o r i t h m ) ，简称g a 、c g a 或s g a ( 如图3 _ 3 1 ) ，而将其他的“g a 类”算法 称为g a s ( g e n e r i ca l g o r i t h m s ) 。经过多年的发展，g a s 在理论上和实际应用中 都取得了很大的发展。但是，在本质上，这些方法同g a 是相似的。 型卫羔l 些! 堕墼! 皇塑垡丝型型壁型垫簦鲨塑型签丝! ! 壅型 a ) 模式定理及建筑块假说 模式定理及建筑块假说是遗传算法的理论基础。 1 ) 模式定理及建筑块假说简介 定义3 3 1 设g a 的个体p b 7 ，记集合，s = 0 ，l ，+ ，则称v s s 为一个 模式( s c h e m a t a ) 。其中，“ 代表通配符。 定义3 3 2 一个模式s 的阶就是出现在模式中的“0 ”和“l ”的数日。记为 o ( s ) 。 定义3 3 3 一个模式的长度就是模式中第一个确定位置和最后一个确定位 霄问的距离，记为8 ( s 1 。 可证明，模式s 的代表串( 即包含模式s 的串) 的数目随代数增长的幅度正 比于模式s 的适应值与群体平均适应值的比值。这就是说，适应值高于群体平均 通应值的模式在f 一代中的代表串数目将会增加，而适应值低于群体平均适应值 的模式在下一代中的代表串数目将会减少。而且，模式的数目是按照指数方式增 加或减少g a 按照指数增加或减少的方式在模式中分配实验次数。考虑到交叉 和变异将可能会破坏模式。且破坏的概率按照模式的长度和阶数成指数增加，因 此，得到了如下的模式定理： 定理3 3 1( 模式定理) 适应值在群体平均适应值之上的，长度较短的， 低阶模式在g a 的迭代过程中将按指数增长率被采样。 h o l l a n d 和g o l d b e r g 在模式定理的基础上提出了“建筑块假说”。 h o l l a n d 指出，交叉算自可以将不同的低阶模式组合成高阶模式，从而大大 缩小后代的搜索范围。认为，交叉是g a 探索未知空间的主要操作，而变异只是 一种保持种群多样性的“背景”操作。所以，应将交叉概率取较大的值，而将变 异概率取很小的值。 g o l d b e r g 将短的、低阶的、具有较高适应值的模式称为“建筑块”。g a 在搜 索过程中将各种不同的“建筑块“通过遗传算子( 如交叉) 的作用结合在一起， 形成新的模式，这样将大大缩小g a 的搜索范围。建筑块通过遗传算子的作用集 合在一起的过程称为“建筑块混合”，当那些构成最优点( 或近似最优点) 的“建 筑块”结合在一起时，就得到了最优点。 2 1 局限性 按照模式定理，遗传算法具有内在并行性，且个体中包含的模式越多，g a 一次处理的模式数目就越多，g a 的并行性就越高。h o l l a n d 证明，当使用二进 制编码时，个体中包含的模式数目最多，所以，他建议使用二进制串来表示个体。 但是，最大的内在并行性并不能保证有最优的性能。二值串的使用并没有得到普 遍赞同。二值串的精度较差，一致性也没有实数值好。研究表明，实数值编码在 坝l 论文城市配 b 网优化规划模型和算法的研究及其实现 很多问题下优于二值串编码。 在对实际问题应用遗传算法时，实际问题的非线性，使得在编码中存在广泛 的多基因性和基因多效性。多基因性是指，个体的单个表现型特征可能决定于许 多基因的相互作用；基因多效性是指，单个基因可以同时影响若干个表现型特征。 多基因性和基因多效性统称为上位效应。在g a 的基本理论中，经常假设在基因 型和表现型之间的关系时一个或少数几个基因对应于一个或少数几个特征。虽然 这种还原主义的简化使得数学上容易处理，并且已经广泛地用于分析，但是对于 预报和评估个体地适应性，不是十分有用。这种效应被称为“豆袋基因”。 上位效应使得判断某个基因是不是“好”基因变得更加困难，因为此时一个 基因在个体中所起的作用与个体中的其他基因有关，也这就是说，这里的多个基 因合成的高阶模式才能使得个体的适应值较高。模式定理并不能保证“好”的高 阶模式的增长，也就不能保证得到最优解。由于很多实际问题的复杂性和非线性， 使得建筑块的存在性受到广泛的质疑。 若构成问题最优解的所有低阶模式的适应值都较低，这时g a 就很难收敛到 最优解。这类问题被称为“欺骗问题”。并且，由于编码方案的差异将导致基因 排列顺序的变化，所以即使存在这样的建筑块，也可能由于不恰当的编码方案而 遭到破坏。而对于一般的问题而言，我们又不可能知道问题中存在哪些建筑块而 主动采取有利的编码方案。这个问题被称为“链接问题”。进一步观察可以发现， 在不同编码下，各种交叉和变异算子对于建筑块也具有不同的作用，从而影响到 g a 的性能。 b ) 搜索策略 1 ) 搜索策略 根据模式定理，遗传算法不是按照各个极值点的作用范围来划分整个解空 f i l j ，而是根据“模式”来将整个解空间划分为各个子空间。每一时刻，遗传算法 都维持一定规模的种群，同时在多个子空间进行搜索。g a 采用了折衷的搜索策 略，在搜索过程中，g a 通过选择来使得具有较高适应值的个体数目不断增加， 从而使得对某些子空间的搜索次数不断增加。同时，g a 也通过交叉、变异来引 入新的个体及新的模式，对未知子空间进行搜索。理论上可以证明【2 4 1 ，对于搜索 过程中积累收益( 所有个体适应值的总和) 最大化这个目标，g a 对不同子空间 实验次数的分配方法是个近似最优的方案。 2 ) 局限性 在证明g a 分配实验次数的合理性时，有如下假设： ( 1 ) 模式是随机变量： ( 2 ) 对模式的采样是独立的； 坝i j 论义 城市配电嘲优化规划模型和算法的研究及儿实现 ( 3 ) 群体规模足够大，可以应用中心极限定理； ( 4 ) 将合理性定义为积累收益最大。 显然，假设1 并非完全适用于所有的问题；假设2 往往在各种编码方式下不 在成立；群体规模受各种实际条件的限制，在问题规模和模式数很大时，难以满 足。 特别是将合理性定义为积累收益最大也是不确切的，可能使得算法无法找到 全局最优解。例如，考察两个具有给定形式适应值分布的随机变量x 1 、x 2 ，其 中一个分布具有均值和方差盯? ，而第二个分布具有均值l ： 盯? ，如图3 3 2 所示。 x 2 厂、 纨 图3 3 2 随机变量x 1 、x 2 的分布 那么，为了获得最大的期望收获，将期望损失最小化，所有样本就应该投入 第一个分布，因为第一个分布具有较大的均值，但是这就使得不能寻找最优的 串，因为它可能是第二个分布中的成员。搜索到一个具有高于平均性能的模式， 在一般情况下并不能保证它包含全局最优解的信息，而全局最优解可能被描述在 具有低于平均性能的模式中。所以，将积累收益最大化的准则是非常保守的，它 可能妨碍了算法搜索到全局最优解。 c ) 收敛性分析 1 ) 收敛性 在分析遗传算法的收敛性之前，应该先给出其收敛性定义。我们知道，遗传 算法是一种随机搜索算法，所以，可以从不同的角度来给出遗传算法的收敛性定 义。遗传算法维持了一个具有一定规模的种群，所以，在定义算法收敛性是就存 在两种思路：一种是针对整个种群进行定义，另一种是针对个体进行定义。 现将所有可能的种群所组成集合视为一个状念空间x ，算法在t 时刻的种群 为x ，。那么，针对整个群体的算法的收敛性可以定义如下： 定义3 3 4 若算法在t 时刻的种群x 满足： 脚2 x 0 ，x 0 x 型生上论翌城市配电网优化规划模型和算法的研究及其实现 则称算法渐进收敛到。 s g a 由于具有随机性，而不具有渐进收敛性，m i c h a l e w i c z 设计了一种新的 g a s ，称为压缩映射g a ( c o n t r a c t m a p p i n g g e n e r i c a l g o r i t h m ，c m g a ) ，并利用压 缩映射原理证明了这种算法具有渐进收敛的性质。 c m g a 与s g a 的最大差别在于，如果某一代种群的平均适应值相对于上一 代没有得到增长，则不直接进入下一代，而是反复应用选择、交叉、变异，知道 种群的平均适应值得到增长，才进入下一代。最终将会收敛于一个不动点种群， 且陔种群中的每个个体都是全局最优解。 存实际求解问题时，往往不可能事先知道问题最优解的具体值。由丁s g a 具有的随机性，即使群体中的每个个体都为全局最优解，求解过程仍会继续进行。 所以，在定义遗传算法收敛性时，应当考察随机因素作用下算法收敛到最优解的 能力。f 而是种针对个体的收敛性定义： 定义3 _ 3 5 设z ，为t 时刻种群中所包含的个体的适应值的最大值，+ 为全局 塌优解的适应值，若z ，满足： 】i m p 五= f ) = 】 ，叶 则称算法收敛到最优解。 通常情况下g a 采用二进制编码，并且种群中只包含有限个个体，所以，其 可能的种群所组成的集合是一个有限集合。若将某一时刻的种群看作个状态变 量，则整个状态空间只包含有限个不同的状态。那么，若个体的长度为，种群 规模为n ，则整个状态空间中共包含了n 。= 27 ”个不同的状态。g a 就是通过各 种遗传算子的作用使得状态变量( 种群) _ 以一定的概率在这有限个状态中演化。 在这个意义上可以将g a 过程看作是一个有限状态m a r k o v 链。可以证明s g a 所生成的m a r k o v 链是各态历经，而非收敛的。 一个种群中的一个或多个最优个体称为超级个体( 或精英个体) ，已证明无 论是在选择前或选择后保存最优个体的g a ( m g a ) 都可以收敛到全局最优解。 上面给出了两种收敛性定义，但是应当看到，收敛性描述的是时间无限延长 时算法的特性，在实际使用时，不可能无限延长计算时间，这就要求我们考察算 法的收敛速度和停止准则。收敛速度与很多因素有关，也是一个被广泛研究的课 题。这罩暂不讨论。 下面给出一些经常使用的停止准则： ( ”适值边界法 当g a s 搜索到适值大于某一边界值的个体后，终止g a s ： ( 2 ) 时间边界法 当g a s 运行时间超过某边界值后终止g a s ； 枷j j 论义 城市配i u 嘲优化规划模型和算法的研究及j e 实现 ( 3 ) 个体数目边界法 当g a s 计算的个体数目超过某一边界值后终j i 二g a s 。 ( 4 ) 适应值数目边界法 这是对个体数目边界法的改进：当g a s 计算到的不同适应值的数目超过 某一边界值后终止g a s 。 ( 5 ) 基于b a y e s 方法的最小损失法 2 ) 局限性 在应用g a 解决实际问题时，人们发现它有时在很长的时间内都不能收敛到 全局最优值，而且种群中大部分个体都在一个局部极值附近，这种现象被称为“早 熟收敛”。早熟收敛是遗传算法和其他一些全局搜索算法的一个其同问题。 当通过染色体的交叉和变异，种群已经“很难”产生优于亲木的子代个体， 就会发生早熟收敛。在遗传算法中经常观察到早熟收敛，因为伴随着交叉和选择 的作用，观察到的最优个体会以指数速度繁殖，该个体很快占据种群的大部分。 发生早熟收敛时，通常的做法时增大变异率，以期跳出局部最优解或者直接 “重启”。显然这两种方法都不会有很好的效果。所以，更多的研究和试验集巾 在如何防止早熟上。 研究表明，早熟收敛与算法所采用的选择算子密切相关，不同的选择算予会 对个体产生不同的“选择压力”。当选择压力偏低时，选择算子的择优作用被削 弱，其行为更加接近于随机游动，算法的收敛速度变慢。而当选择压力偏高时， 选择算子的择优作用被放大，从而使得算法的收敛速度加快，但此时就有可能导 致早熟收敛。所以，为了防止出现早熟收敛的现象，需要选择一神适当的选择算 子。这里如何确定选择压力的问题，本质上是一个如何平衡的探索未知空间和利 用积累信息的问题。过大的选择压力，使得种群中适应值较低的个体迅速“死亡”， 种群的多样性遭到破坏，从而使得算法搜索空间减小，不容易搜索到全局最优值。 相反，过小的选择压力，使得种群中具有较高适应值的个体不容易在种群中产生 更多的后代，从而使得搜索过程的随机性增强，降低搜索效率，算法的收敛速度 变慢。 有限的个体数目使得采样误差增大，从而使得算法的搜索路径大大偏离了应 有的方向，也会导致早熟收敛到局部极值点。解决方法就是增加种群