（电力系统及其自动化专业论文）基于诊断策略遗传算法的配电网络重构研究.pdf

d i a g n o s t i cs t r a t e g yb a s e d o ng e n e t i ca l g o r i t hmf o rd i s t r i b u t i o n n e t w o r kr e c o n f i g u r a t i o n b y l ic a i y a n at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n d i s c i p l i n eo fe l e c t r i c a la n di n f o r m a t i o ne n g i n e e r i n g l n c h a n g s h au n i v e r s i t yo fs c i e n c e & t e c h n o l o g y s u p e r v i s o r p r o f e s s o rl i uj i a n h u a a p r i l ，2 0 11 0jji24洲8帅8iii1咖y 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：香乳托 日期：乙1 1 年孓月1 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。同时授权中国科学技术信息研究所将本论文收录到中 国学位论文全文数据库，并通过网络向社会公众提供信息服务。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密囤。 ( 请在以上相应方框内打“”) 日期：石“年 日期：伊、年 ，月翻日 f t 月? o 日 摘要 配电网络重构作为配电管理系统重要的组成部分，是配电系统运行以及控制 的重要手段。其目的是在正常运行情况下或发生故障状况下，通过开关的分、合 状态来寻找一个最佳的网络结构。在这个结构下，使重构后的某一方面或许多方 面的性能，如平衡负荷、降低网络损耗、供电电压质量等方面优丁二其他的网架结 构。从而提高电力系统的可靠性、经济性以及安全性。 配电网络重构的方法有多种，如最优流模式法、支路交换法、遗传算法等等。 从许多学者多年来的研究应用来看，遗传算法在配网重构的应用中是一种优良算 法。 根据配电网络自身的特点，以及在计算过程中产生大量不可行解的难点。本 文在基本遗传算法的基础上，结合人类诊治疾病，以使身体的健康状况得到恢复 或加强的原理上，提出了基于诊断策略的遗传算法。 本文分析了标准遗传算法的基本定义、原理以及数学理论基础等，以网损最 小作为配电网络结构的目标。根据配电网重构的理论，拓扑分析以及潮流计算分 析，再结合配网重构中的重点难点，将诊断策略遗传算法应用到配网重构之中。 运用基于基本环路的编码方式，使有效候选解的比例很大地提高，还对基因库进 行了更新，改进遗传操作，并且提出了诊断操作，即优质基因的插入操作及病态 基因的诊断修复操作。通过打开“回路和连通“孤岛”，将不可行解修复为可 行解。从而有效地克服了标准算法的缺点，使遗传算法应用于配网重构中的难点 问题得以解决。最终达了配网重构的目标。 最后，通过标准算例进行仿真验证，其结果表明了基于诊断策略遗传算法在 配网重构中的可行性以及有效性。 关键词：配电网；遗传算法；网络重构；诊断策略；拓扑分析 a bs t r a c t d i s t r i b u t i o nn e t w o r kr e c o n f i g u r a t i o nf o rp o w e rd 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 ， a ni m p o r t a n tp a r to ft h ed i s t r i b u t i o ns y s t e mi sa ni m p o r t a n tm e a n so fo p e r a t i o na n d c o n t r 0 1 i t sp u r p o s ei su n d e rn o r m a lo p e r a t i n gc o n d i t i o n so rf a i l u r ec o n d i t i o n s ，b y s w i t c h i n gt h ep o i n t s ，t h es t a t eo fb e i n gt of i n da no p t i m a ln e t w o r ks t r u c t u r e i nt h i s s t r u c t u r e ，s ot h a tp e r h a p ss o m ea s p e c to fr e c o n s t r u c t i o n a f t e raw i d e r a n g eo f p r o p e r t i e s ，s u c ha sb a l a n c i n gt h el o a da n d r e d u c en e t w o r ko u t a g e s ，p o w e rs u p p l y v o l t a g eq u a l i t yi ss u p e r i o rt ot h eo t h e rn e t w o r ks t r u c t u r e t oi m p r o v ep o w e rs y s t e m r e l i a b i l i t y ，e c o n o m ya n ds e c u r i t y d i s t r i b u t i o nn e t w o r kr e c o n f i g u r a t i o no fm e a n s ，s u c ha st h eo p t i m a lf l o wp a t t e r n m e t h o d ，b r a n c he x c h a n g em e t h o d ，g e n e t i ca l g o r i t h ma n ds oo n s c h o l a r sf r o mm a n y y e a r so fr e s e a r c ha n da p p l i c a t i o np o i n to fv i e w ，t h eg e n e t i ca l g o r i t h mi nd i s t r i b u t i o n n e t w o r kr e c o n f i g u r a t i o na p p l i c a t i o n si sag o o da l g o r i t h m a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fi t so w nd i s t r i b u t i o nn e t w o r k ，a sw e l l a si n t h ec a l c u l a t i o no fal a r g en u m b e ro fi n f e a s i b l es o l u t i o n sg e n e r a t e di nt h ep r o c e s s d i f f i c u l t y i nt h i sp a p e r ，t h eb a s i cg e n e t i ca l g o r i t h mb a s e d o nt h ec o m b i n a t i o n t r e a t m e n to fh u m a nd i s e a s e st ot h eh e a l t ho ft h eb o d yh a v eb e e nr e s t o r e do re n h a n c e d t h ep r i n c i p l e ，t h ep r o p o s e dd i a g n o s i ss t r a t e g yb a s e do ng e n e t i ca l g o r i t h m s t h i sp a p e ra n a l y z e st h eb a s i c d e f i n i t i o no ft h es t a n d a r dg e n e t i ca l g o r i t h m ， p r i n c i p l e s a n d m a t h e m a t i c a l t h e o r y ，i n o r d e rt om i n i m i z ep o w e rl o s sa st h e d i s t r i b u t i o nn e t w o r ks t r u c t u r eo ft h et a r g e t a c c o r d i n gt ot h et h e o r yo fd i s t r i b u t i o n n e t w o r kr e c o n f i g u r a t i o n ，t o p o l o g ya n a l y s i sa n d f l o wa n a l y s i s ，c o m b i n e dw i t ht h e r e c o n s t r u c t i o no fd i s t r i b u t i o nn e t w o r ki nt h ek e ya n dd i f f i c u l t ，t h ed i a g n o s t i cs t r a t e g y g e n e t i ca l g o r i t h mb e i n ga p p l i e dt o t h ed i s t r i b u t i o nn e t w o r kr e c o n f i g u r a t i o n u s e e n c o d i n gb a s e do nt h eb a s i cl o o p ，s ot h a tac o n s i d e r a b l ep r o p o r t i o no fc a n d i d a t e s o l u t i o n se f f e c t i v e l yt oi m p r o v e ，b u ta l s oo nt h eg e n ep o o lh a s b e e nu p d a t e d ， i m p r o v e dg e n e t i co p e r a t i o n sa n dm a d ead i a g n o s i so fo p e r a t i o n ，n a m e l y ，h i g h q u a l i t y g e n ei n s e r t i o na n dg e n ep a t h o l o g i c a ld i a g n o s i so ft h er e p a i ro p e r a t i o n b yo p e n i n g t h e ”l o o p ”a n dc o n n e c t e d ”i s l a n d s ”w i l lb er e p a i r e dt oaf e a s i b l es o l u t i o ni n f e a s i b l e e f f e c t i v e l yo v e r c o m e t h es h o r t c o m i n g so ft h es t a n d a r d a l g o r i t h m ，t h eg e n e t i c a l g o r i t h mi sa p p l i e dt od i s t r i b u t i o nn e t w o r kr e c o n f i g u r a t i o nd i f f i c u l tp r o b l e m sc a n b e r e s o l v e d t h eu l t i m a t eg o a lo fr e c o n s t r u c t i o no ft h ed i s t r i b u t i o nn e t w o r k i i f i n a l l y ，t h es t a n d a r de x a m p l ef o rs i m u l a t i o n ，t h er e s u l t ss h o wt h a tt h ed i a g n o s t i c s t r a t e g yb a s e do ng e n e t i ca l g o r i t h mi nd i s t r i b u t i o nn e t w o r kr e c o n f i g u r a t i o nf e a s i b i l i t y a n de f f e c t i v e n e s s k e y w o r d s ：d i s t r i b u t i o nn e t w o r k ； g e n e t i ca l g o r i t h m ；n e t w o r kr e c o n f i g u r a t i o n ； d i a g n o s t i cs t r a t e g y ；t o p o l o g i c a la n a l y s i s i i l 目录 摘要i a b s t r a c t i i 第一章绪论 1 1 课题背景及意义1 1 2 配电网络重构的研究现状2 1 2 1 数学优化理论算法2 1 2 2 最优流模式算法2 1 2 3 支路交换算法3 1 2 4 人工智能算法4 1 3 本文的主要工作6 第二章遗传算法的理论分析 2 1 遗传算法简介7 2 2 遗传算法的基本原理8 2 3 编石马9 2 4 适应度值1 0 2 5 遗传操作1 l 2 6 遗传算法的终止条件1 3 2 7 遗传算法的数学理论基础1 3 2 8 遗传算法的约束处理1 4 2 9 本章小结15 第三章诊断策略遗传算法 3 1 概述1 6 3 2 诊断策略遗传算法1 6 3 3 基因库的建立及更新一1 8 3 3 1 基因库的建立l8 3 3 2 基因库的更新1 8 3 4 诊断策略遗传算子18 3 4 1 交叉算子一1 9 3 4 2 变异算子一19 3 4 3 选择算子2 0 3 5 诊断操作2 0 3 6 与免疫遗传算法的对比仿真一2 2 3 7 本章小结2 3 第四章诊断策略遗传算法在配电网重构中的应用 4 1 引。言2 5 4 2 配电网络拓扑结构一2 5 4 2 1 概述2 5 4 2 2 配电网络的拓扑分析一2 6 4 3 配电网重构的数学模型2 7 4 4 配电网重构的潮流计算2 8 4 4 1 概j 苤2 8 4 4 2 拓扑结构存储2 9 4 4 3 前推回代法3 0 4 5 遗传算法在配网重构中的难点3 2 4 5 1 难点分析3 2 4 5 2 不可行解的产生及危害3 2 4 6 基于诊断策略遗传算法在配网重构中的应用3 3 4 6 1 概述3 3 4 6 2 初始种群的选取和个体编码3 4 4 6 3 适应度函数、遗传操作及基因库的更新3 4 4 6 4 诊断操作3 5 4 6 算例分析3 9 4 7 本章小结4 0 第五章总结与展望 5 1 结论4 2 5 2 展望4 2 参考文献4 4 致谢4 7 附录a 攻读学位期间所发表的学术论文4 8 附录b 标准算例数据4 9 第一章绪论弟一早三百可匕 1 1 课题背景及意义 新中国成立以来，特别是近几年，我国的工业、农业都得到了飞速发展，因 此也对电能的需求量也日益增多，同时对供电质量及供电可靠性的要求也相对提 高。配电网是面向用户供电的重要环节：通常把电力系统中二次降压变压器低压 侧到用户之间的网络，系统称为配电网。它是由配电所、柱上降压变压器及架空 线或是电缆配电线路及直接接入用户的设备所组成。配电网络有如下特点：网 络结构复杂。它装有大量的联络开关及分段开关。伴随着用电负荷的日益增长， 配电网络有越来越复杂的趋势，它的运行方式也随着不断变换。不仅仅是处理事 故，连控制操作的难度也日趋加大。总线路里程较长，运行电压较低，从而使 线损较大。倘若网架结构不合理时，则负荷不均衡现象很容易出现，使电能质 量较差。再加上配电网系统内不断要进行设备的更新或扩容，使得网架结构的不 合理性进一步加剧。 由于配电网是电力系统最后的一个环节，与用户有着如此紧密的联系，直接 影响着用户的供电质量及可靠性。 另降低网络损耗也是电力企业提高其经济效益的重要指标。我国线损率大致 为9 ，而西方主要工业国则仅为5 - - 8 左右。由此可见其差距。我国在1 9 9 5 年 城网li o k v 以下配网线损就占了总线损的6 0 。因此，降低配网线损成为了降损 工作的霞点。过去几年里，运用无功补偿技术、合理确定运行电压水平及提高用 户功率因素等手段都被广泛采用在降低配电网络损耗的工作上。如今，随着近几 年来配网自动化技术的显著提高，使得配电网络重构成为了降低网络损耗的一种 更为行之有效的手段。 配电网络重构是优化配电系统运行的重要手段，也是配网自动化的一项重要 内容。配电网运行方式具有闭环设计、开环运行的特点。而配电馈线上装有许多 的联络开关及分段开关。在满足用户供电负荷需求的情况之下，许多不同的供电 路径将会存在。而不同的路径所形成的网络结构也就拥有不同的经济性及安全性 等。哪种结构是其各项综合指标最为优越的? 配电网络重构的目的就是要把这种 最好的最安全经济的结构从诸多结构中寻找出来。 配电网络重构又称为配电网络组态。就是指在正常运行情况下，调度员根据 负荷的变化情况来调整网络的运行结构。即打开常开开关，闭合常闭开关。使之 可达到降低网损、消除过载、平衡负荷及提高供电电压质量等目的。而在发生故 障的情况之下，配网重构可以做到快速隔离故障，缩小停电范围，以及在故障后 迅速恢复供电。 配电网络重构这一问题，随着管理系统的逐步建设和日益完善，成为了电力 工作者予以重视的重要课题。大批工作者在这方面做了许多的研究，并且提出了 大量有效的方法及理论成果。即使不同方法的采用，不同理论的借鉴研究，也没 能使现今配电网络重构在收敛性、运算速度与寻优能力等诸多方面成为一个非常 完美和实用的解决方法。他仍然是一个值得深入探索和研究的重要课题，具有非 常重要的现实意义。 1 2 配电网络重构的研究现状 配电网络蓖构技术最早由m e r li n 和b a c k 于1 9 7 5 年提出来的，至今已超过 三十年的历史了。到如今，已成为了引人注目的热点问题。先后有许多学者们加 入到网络重构的研究工作中，运用了不同的理论及方法来解决这类问题。例如： 直到如今都仍然受到重视及广泛应用的最优流模式及支路交换算法。此类方法提 出较早，此后主要是在加快搜索速度方面进行改进。除此之外，还有传统的数学 优化理论算法、人工智能算法等几类。 1 2 1 数学优化理论算法 处理配电网络重构问题，早期的人们采用的是数学优化理论方法，它主要包 括分支界定法心1 及整数规划方法口4 3 、线性规划法晦1 等等。m e r li n 及b a c k 采用的 是分支界定法，用电流源( 恒定不变的纯有功分量) 来表示。而网络的约束条件 以及电压相角均被忽略不计。即使该方法具有重构结果不依赖于初始状态等的优 点，但仍然由于直流潮流计算被大量采用，致使该算法较费时、效率低。 j i - y u a nf a n 等人1 提出用单纯形法求解：单环网优化问题( 一次只开合一 对开关) 。数学模型具有二次目标函数。此类方法也比较费时。 t p w a n g e r 等人哺1 采用的方法是不需要起始方案，但能在网络结构的优化过 程中形成辐射状。具体是将网损最小的配网重构问题无需加以考虑了，已将它转 化成了考虑二次费用的网络传输问题。并且用分段线性函数来表示二次功率损耗， 在其中包含了热容约束及馈线电压降落。但此类方法搜索速度仍然较慢，对大规 模配电网来说并不十分适应。 1 2 2 最优流模式算法 最优流模式算法是1 9 8 9 年由d s h i r m o h a m m a d i 等人哺1 最先提出的一种启发式 方法。它的目标函数定为有功功率损耗最小。这种方法首先将所有开关关闭，以 形成多环网。再计算潮流，求出“最优流 模式。即使系统功率损耗最小的电流 2 分布。具体步骤为：读入网络及开关数据后，第一步为，合上所有开关，这时几 个环的配网便形成了。第二步为进行多环网的潮流计算，将负荷转化成了节点注 入电流。第三步，不考虑其他约束条件，仅仅使用多环网络的支路电阻再次进行 潮流计算。最优流模式便被确定了。第四步，打开最优流模式下电流最小的开关。 打开一个开关也就意味着解开了一个环路。第五步，检查网络结构是否恢复到辐 射状，所有环路是否均被解开。若为辐射状网络则输出结果，否则继续第二、三、 四步。而此方法，其中任一个被解开的环路都将使其它支路的电流受到影响，其 结果也依赖于打开开关的先后次序。该方法虽然使问题相对简单化了，但假若网 络规模增大，该算法中的潮流计算及最优流计算将变得很繁多，从而大大地增加 了计算时间，使之在大范围的配电网络中实际应用变得比较困难。 1 2 3 支路交换算法 最先提出支路交换算法的是s c i v a n l a r 等人n 1 。他首先进行全网潮流及网损 的计算，将用恒定电流来表示负荷。利用启发式规则来减小需要考虑的开关组合 ( 每次只形成一个环网，即只合上一个联络开关) 。为了使配电网实现降低网损、 达到负荷均衡等目的，要使配网呈现为辐射状。 厂丐nf开始1 进行全网潮流及网损计算将负荷变为恒定电流 利用启发式规则减小需要考虑的开关组合 估算需要考虑的开关操作降低的网损 重段趸茬蒿萎三 卜苎 否仍肓开关操伶 “ 可以降低网损 j r 肓 将最大降损效果的开关打开 进行潮流 是否越限 放弃最后一次开关操作 否 得 到 最 优 网 络 结 构 图1 1 开关交换算法的流程图 3 支路交换算法不但可以通过启发式规则减少需要的开关组合，还能迅速确定 能够降低配网线损的网络结构。但此算法不足的地方是，每次只能考虑一对开关 的操作，并不能保证全局最优解。其次是重构的最终结果依赖于配电网络的初始 状态。负荷相同情况之下，初始结构不同也就意味着网络重构结果很可能截然不 同。 因此，许多的工作者对此方法进行了改进，进行了进一步的研究工作。如： w h e i - m inl i n 等人阳1 为了打开环网的最优点，则依据线损变换的估算公式定义了 3 个开关系数。它每次只考虑哪个开关具有最大降损效果，此操作策略使搜索空 间得以降低了。g p e p o n i s 等人阳1 将最优流模式与开关交换算法结合起来，并对 雅典的一个配电网进行了简化，再进行重构后显示的结果表明此算法拥有更高的 处理效率。张栋等人n 们提出了一种用近似网损代替精确网损的快速算法，并且环 网的最大降损开关由最佳转移负荷的符号及大小来确定。因此，使重构结果的准 确性提高了。此算法在重构过程中不必要计算潮流，因此大大地提高了计算速度。 1 2 4 人工智能算法 人工智能算法就是模拟工作人员在实际工作中获得的经验进行操作所采用的 方法。从第一次提出至今已有5 0 多年的历史。许多的工作者将此理论及方法应用 于配电网络重构中，包括的方法有：人工神经网络法、模拟退火法、遗传算法、 专家系统等等。 1 、人工神经网络法 由大量处理单元广泛互联而成的网络，它的提出是建立在现代神经科学的研 究成果上。此法能够实现在线实时控制，是因为它具有非线性较强的抗干扰及并 行计算能力。既不需要对开关操作的降损效果估算，也不必要计算潮流，从而使 得配网重构时间大大地降低。通过样本的训练将输出与输入之间非线性的关系存 储在神经元权值中，这是人工神经网络法的最大特点。图1 2 是应用在配网重构 中的一个神经网络模型。其输入与输出分别为负荷模式及开关状态。 开美的状采 各节点的负荷教据 图1 2 用于配网重构的神经网络模型 4 神经网络法的不足之处也很明显。配网结构及负荷的变化都非常频繁，所以 神经网络权值经常需要更新，而此法最优解及训练组的数据密切相关。从而致使 此法的实用性有所限制。“麻痹”现象在训练过程时有出现，也无明确的理论来 指明该选用多大神经网络的节点规模。 2 、模拟退火法( s h ) s a 即m e t r o p o l i s 抽样算法，是指由m e t r o p o l i s 等人于1 9 5 3 年为了模拟熔 融态固体热平衡的形成而提出的简易算法。将此法应用至组合优化问题的求解中 是k ir k p a t r i c k 等人于1 9 8 3 年最先实行的，其寻找最优解是通过采用随机搜索的 迭代过程。确定起始冷却温度、冷却率、每个温度下交换支路的总数以及每次交 换数目等全局冷却过程过程设计得是否恰当是此算法的重点之一。通过计算网损 变化量，根据m e t r o p o l i s 接受准则来判定是否来保留此种网络结构，若具有较小 的网损，则接受，置为当前结构。否则，放弃此种结构，继续进行支路交换，一 直到所有待选的结构全部交换完毕。s a 得到的解基本上与初始可行解无关且是全 局最优解或次最优解。它对目标函数的设计并没有特别的要求，并能较好地克服 “维灾数”难题。但该方法在应用时需要进行大量的、多层次的开关交换，需进 行的潮流计算及网损估计的次数也随之增多。因此工程量大，计算繁多。 3 、遗传算法( g a ) 遗传算法( g a ) 的基本思想是适者生存。经过4 0 多年来各位学者的努力与探 索，遗传算法已应用在众多领域，成为配电自动化应用中非常重要的方法n 卜1 2 1 引。 它通过模拟基因串适者生存的理念以及随机进行信息交换的搜索方法来进行优化 结构。通过选择每次最合适的信息去进行下一步新的基因合成，利用过去信息去 寻找新的搜索点。大部分学者都将用“0 ”或“l 二进制字符串来表示开关的开 合状态，每一个适应度函数用一个字符串来表示。通过复制、杂交、变异等一系 列操作，将筛选出字符串代表适应度为最佳，那么即为最优解。 4 、专家系统 此类算法与基于启发式算法有相似的局限性，它无法进行评估及数学运算。 文献 1 4 提出，专家系统可以给调度员提供较好的建议。因为调度员在实际情况 之中并不愿意对系统作出较大的变动，而此法在重构时应顾及到电压控制及继电 保护的影响。 5 、其他算法 对大量算法的研究，使配电网络重构这一领域的理论基础及实际应用都得到 了极大的丰富。如文献 15 提出了粒子群算法，这种方法是基于正态分布的局优 5 邻域闭锁方法，通过设计自适应退火策略以及改进扰动机制，有效地促使粒子群 算法局部收敛的不能足得以克服。文献 1 6 采用禁忌搜索方法对配电网络进行重 构研究。文献 1 7 - 1 8 设置的目标函数为：某一段时间配网经济收益最大，在重构 操作收益评价的体系中包含了开关动作的操作费用。这些算法从不同的角度不同 的方法或多重目标来考虑配网重构问题，使网络重构这一领域得到了很好的发展。 1 3 本文的主要工作 配电网络的重构问题发展到今天，通过了许多学者们努力的探索，已取得了 骄人的成绩，拥有了多种解决方案。本文在前辈们探索的基础上进行了研究工作。 本文的内容作了如下的安排： ( 1 ) 通过对各种算法的研究与比较，在各种算法中选择遗传算法作为配电网 络重构的算法。 ( 2 ) 介绍了标准遗传算法的来源、特点和发展，还有其基本的定理、基本的 操作。分析了遗传算法的数学基本理论基础以及其在运用时的约束问题的处理方 法等。 ( 3 ) 在标准遗传算法的基础上，提出诊断策略遗传算法。对基本遗传操作进 行了改进。并且提出了诊断操作：即优质基因的插入操作以及病态基因的诊断修 复操作。 ( 4 ) 分析了配电网拓扑结构及潮流计算方法，以及分析了遗传算法在配网重 构中的难点，即不可行解问题。本文以网损最小为配网重构的目标，将基于诊断 策略的遗传算法应用于配电网络莺构中。通过提出基于基本环路的编码方式，缩 短染色体的长度，从而缩小搜索空间。将最优选择策略、诊断遗传操作以及建立、 更新基因库应用于配网重构中。 ( 5 ) 将诊断操作，即优质基因的插入操作以及病态基因的诊断修复操作运用 到配网重构中。通过打开“回路 和连通“孤岛 将不可行解修复为可行解，以 解决不可行解难题。 ( 6 ) 对算法进行了仿真试验，以验证其可行性与有效性。 ( 7 ) 总结本文研究成果，展望配电网重构的进一步发展以及针对不足要做的 进一步研究。 6 第二章遗传算法的理论分析 遗传算法是借用生物遗传学的机理，通过自然选择、交叉和变异等操作，实 现寻优的过程的优化算法。其基于多点有向搜索，因而有良好的寻优性能。 2 1 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是一种建立在自然选择原理和自然遗传 机制上的迭代式自适应概率性搜索方法。遗传算法简称的概念是j d b a g l e y 于 1 9 6 7 年首次提出的，在自然选择与遗传的机制上建立起来的。它在人工系统中特 定目标的优化是通过模拟自然界中生物进化的发展规律来实现的。达尔文在1 8 5 9 年就提出了进化论，发表了专著物种起源。他系统阐述了生物在三因素( 交 叉、变异、选择) 的共同作用之下，向前发展的过程，从而使生物从低级到高级 不断地进化。 美国j h h o l l a n d 教授1 9 7 5 年发表的论文则是开创了遗传算法理论和方法得 以应用的先河。文中采取二进制编码方式，变量的表示方式即用一定长度的二进 制数字串( 即0 、1 ) 。而将每一个位于字符串中的二进制位码称为基因。一个个 体都是由一个数串表示，也代表着优化问题的一个解。解的集合也即若干个字符 串组成的集合。他提出的此种模式为日后的研究奠定了浓厚的理论基石。此后， 大批的探索者前朴后继地投入到g a 理论算法的研究中。d e g d d b e r g h 引在此领域 里有最为突出的贡献，他建立且完善了此算法的整个系统，将其理论应用到众多 领域，为g a 开创了宽广的应用空间。到如今，g a 已成为了一种适应性极广的优 化算法。 遗传算法并不是简单机械地挪动。它通过选择，有组织而又随机地交换信息， 通过重组适应度高的个体，让优良基因得以更好更多地繁殖后代，优良特性能够 遗传下来。优胜劣汰的自然规律在此算法中得以体现。每个新个体的生成，都源 于上代适应性好的个体或用新的基因代替原有的性价比低的基因。 遗传算法有着如下特点： 该算法处理的不是参数本身而是待求变量的编码，也即它的操作是在给定 的字符串上进行的。 遗传算法并不是从一点就开始搜索而是使用概率规则从一群体中搜索。它 不需要其他很多的辅助信息，有一个适应度函数值即可。因为它使用的不是确定 性规则指定搜索，能够较好地处理离散型、病态型的优化难题。 由于此算法搜索的不仅仅只有一点而是解空间中众多个点，故能快速全局 7 收敛。 它具有内在并行计算这一重要特性，得以与其他方法区别开来。 遗传算法能够充分搜索空间中不同的区域。从而使得群体序列越来越优化。 但计算速度慢等缺点。 2 2 遗传算法的基本原理 g a 中使用的基本概念及术语如下所示他引： 染色体( c h r o m o s o m e ) ：生物细胞中含有的一种微小的丝状化合物。其是遗 传物质的主要载体，由多个遗传因子组成。 基因( g e n e ) ：又称为遗传因子，指控制生物性状遗传物质的结构及功能的 基本单位。 基因型( g e n o t y p e ) ：是指由遗传因子组合的模式，又或者说是性状染色体 的内部表现。 表现型( p h e n o t y p e ) ：是指根据遗传因子组成的个体，它形状的外部表现由 染色体来决定。 个体( i n d i v i d u a l ) ：指染色体带有特征的实体。 群体( p o p u l a t i o n ) ：染色体带有特征的个体的集合，其数目称为群体规模。 适应度函数( f i t n e s sf u n c t i o n ) ：衡量各个个体适应环境程度的函数。 选择( 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 ) ：让遗传因子以一定的概率变化的操作。 编码( e n c o d i n g ) 指的是从表现型到基因型的影射。 解码( d e c o d i n g ) 指的是从基因型到表现型的影射。 遗传算法的基本思想和过程：染色体因为内部为基因的集合，个体的外部表 现也由它决定了。从表现型到基因型的映射工作也即编码工作在一开始求解时要 进行了。问题的任一个可能解都被编码成一个染色体，也就是个体。所有可能解 由若干个个体组成，即为群体。初始解是算法开始时随机生成的。根据特定的目 标函数来确定适应度值，然后对个体进行选择用来复制下一代。 于是适应度函数值高的个体被复制，低的则被淘汰。选择出来的个体再通过 交叉和变异或倒位算子等遗传操作再生成新的一代群体。此时的群体由于遗传了 上代的基因，故可能优于前代，也就使群体朝着日益进化的方向迈进。图2 1 为 基本遗传算法的原理框图。 8 图2 1 遗传算法原理框图 2 3 编码 编码是遗传算法的一个关键步骤，也是首要解决的工作。在确定了目标函数 及变量之后，就要将实际的问题转化为数字串的形式才能进行下一步的工作。这 就是确定编码方式。因为遗传算法直接对数字串进行操作。待求的目标函数只有 通过数字串表示才能操作。因此，采取何种编码方式对遗传操作运算及效率有着 深远影响。通常编码也应满足如下3 个原则：问题空间中所有的可行解都能成 为编码空间中的点的表现型。必需具有健全性必须使潜在的解要与染色体一 一对应，也即非冗余性。 一般来讲，此算法编码的方式有许多种：例如常见的二进制编码，还有大字 符集编码、实数编码及序列编码等等。 二进制编码此种编码方式操作简单，遗传操作容易实现，由0 和l 组成了 编码字符集。其染色体就是一个二进制符号串。o 和1 分别代表开关的断开和闭 合。若当所有的联络开关全为l 时，便形成了一个环网，要使重构后网络为开式 运行时，就要打开由“0 ”位相对应的分段开关。其原理比较清晰，操作起来也并 不复杂。全对于多维的、精度要求高的连续函数优化问题，二进制编码将存在映 射误差。 浮点数编码浮点数编码指的是个体的基因值使用某一范围内的一个浮点 数表示，个体的编码长度等于其决策变量个数的方法。浮点数编码比二进制编码 9 一般更能反映所求问题的特定知识。且编码结构相对简单点，在变异操作上种群 的多样性能更好地得到保持。但般而言，二进制比它具有更强的搜索能力。 本文采用的是新的编码方式一一基于基本环路的方式，这将在第四章里进一 步阐述。 编码并不只是简单的对问题进行描述，而是它应适应对待解决的问题要合适。 b a l a k a r i s h m a n 对选择编码方法提供了指南，重点包括九个特性陋1 1 ：完全性， 即能构造出分布于所有问题域的解；封闭性：每一个可接受的个体对应一个基 因编码；可扩展性；多重性，基因多重性指的是从基因型到相应的表现型空 间是多对一的关系。表现型多重性是指相同基因型被解码成不同的表现型；紧 致性；个体可塑性；模块性：在基因编码中应避免多个重复的结构存在于表 行解问题是配网 进一步阐述。 其能否找到最优 群中每个个体的 在求解问题时， 目标函数值域的 价，适应函数值 遗传。数值越小 待求的并不是函 问题等。因此不 往往把求函数最 一致性及非负性 ( 2 1 ) ，也可根据试验 数据取值。 变换方法( 二) ： ，( x ) 。i j = _ z _ 而1 ，c 耋o c + f ( x ) 耋o( 2 2 ) 其中c 可以取为目标函数界的保守估计值。 本文选取的是方法( 一) 来求解以网损最小为目标的配电网络重构问题。 2 5 遗传操作 遗传操作是通过模拟生物进化理论，对个体适应度值进行的一系列操作。它 能够使问题逐步趋向最优解。它包括：选择、交叉、变异三个基本操作。此算法 的大部分搜索任务基本上由选择及交叉完成了，而变异则为寻求最优解增添力量。 ( 1 ) 选择算子 选择操作体现了达尔文“适者生存”的理念，实行“优胜劣汰的竞争机制。 它的目的也是从当前种群中挑选出适应度值大的个体，即优良个体，为下一步交 叉操作做准备。它提高了算法的计算效率，也提高了其全局收敛性。个体被选中 的机会与目标函数变换而来的适应度函数值的大小成正比。即数值越大，机会越 多。 因为选择本身并不生成新个体，尽管它能使群体的平均适应值得以提高，但 却损失了群体的多样性。 轮盘赌法是g a 中最常用最基本的选择方法。它又称为适应度比例法。其适 应度大小与各个个体的选择率是成正比关系。它指其后代被遗传的可能性取决于 它比例于各个个体适应值的概率。设f i 为个体i 的适应度，n 为群体大小。则i 被选中到下一代的概率是： p ，= f ，f f ( 2 3 ) f = l ( 2 ) 交叉算子 交叉操作能够产生新个体，是指两个父代个体交换部分信息而生成新个体的 操作。因此产生的两个子代个体一般彼此之间不同，与他们父代个体也不相同， 但都遗传了父代的某些结构。它们以一定的概率进行。一般交