（电力系统及其自动化专业论文）基于食物链生态进化算法的配电网重构.pdf

a b s t r a c t a b s t r a c t an e wd i s t r i b u t i o nn e t w o r k r e c o n f i g u r a t i o n m e t h o d e m p l o y i n ge c o l o g y e v o l u t i o n a r ya l g o r i t h mo ff o o dc h a i na so p t i m a lm e a n sh a sb e e np r e s e n t e d t h e a l g o r i t h m ，w h i c hs i m u l a t e st h ec o m p e t i t i v ee v o l u t i o n a r ya p p r o a c ho fd i v e r s es t o c k s o fe c o l o g i c a lf o o dc h a i na n de n h a n c e st h ed i v e r s i t yo fi n d i v i d u a l sa n dt h el e v e l so f e v o l u t i o n ，h a sag o o do v e r a l la n dl o c a ls e a r c hc a p a b i l i t ya n do v e r c o m e st h ei m m a t u r e c o n v e r g e n c eo fs o m eo t h e rb i o n i ca l g o r i t h m s 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 f d i s t r i b u t i o nn e t w o r k ，ar e a ln u m b e re n c o d i n gm e t h o di sp r o p o s e df o rr e d u c i n gt h e d i m e n s i o no fd e c i s i o nv a r i a b l e o nt h eb a s i so ft h a td e s c r i b e st h eo p e r a t i n gm a n n e ro f s w i t c h e si nf o u rs t a t e so fo p e n ，c l o s e ，i n c i d e n tc l o s ea n dl o n g t e r mc l o s e ，t h ei n c i d e n t c l o s em a n n e ro fs w i t c h e si sf u r t h e rd i v i d e di n t od i r e c ti n c i d e n tc l o s ea n di n d i r e c t i n c i d e n tc l o s e ，a n dt h ed i f f e r e n tm e a s u r ei st a k e nt oe n s u r et h a ta l lt h ef o u n ds o l u t i o n s i ni t e r a t i v ep r o c e s sm e e tt h er e q u i r e m e n t so fr a d i a ln e t w o r ka n dn o n - i s o l a t e di s l a n d c r o s s i n gn o d ee x t r a c t i o ni sm a d et oc h e c kt h ev a r i e t yo fc o m p l i c a t e ds i t u a t i o no f n e e di n d i r e c ti n c i d e n tc l o s e e n c o d i n gm e t h o da n do p e r a t i n gm a n n e ro fs w i t c h e sa l e c o m b i n e do r g a n i c a l l yt oa v o i du n f e a s i b l es o l u t i o na p p e a r i n gi nt h eo p t i m i z a t i o n p r o c e s s ，t oi m p r o v et h ee f f i c i e n c yo ft h es e a r c ha l g o r i t h m t ov e r i f yt h ee f f e c t i v e n e s s o ft h ep r o p o s e dm e t h o d ，c o m p a r a t i v es t u d i e sa r ec o n d u c t e do ni e e e16b u s ，i e e e3 3 b u sa n di e e e6 9b u ss a m p l es y s t e m s ，a n dr a t h e re n c o u r a g i n gr e s u l t sa l ea t t a i n e d i e e e16t e s ts y s t e mi si m p r o v e dt od y n a m i cl o a d o nt h eb a s i so fi n - d e p t ha n a l y s i st o d i s t r i b u t i o nn e t w o r ks t a t i c r e c o n f i g u r a t i o n ，d y n a m i cr e c o n f i g u r a t i o n o ft h e d i s t r i b u t i o nn e t w o r ki sd i s c u s s e dw i t ht h ed y n a m i cs y s t e m k e yw o r d s ：d i s t r i b u t i o nn e t w o r k ；n e t w o r kr e c o n f i g u r a t i o n ；e c o l o g ye v o l u t i o n a r y a l g o r i t h m o f f o o d c h a i n ； r e a ln u m b e r e n c o d i n g ；d y n a m i c r e c o n f i g u r a t i o n i i 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得壹量盘堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名( 手写) ：易小平 签字日期：一矿年2 月胗日 学位论文版权使用授权书 本学位论文作者完全了解南昌大堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权壹墨盘堂可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。同时授 权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名( 手写) ：易啦罕 导师签名( 手写) ：砂17 l 签字日期：1 年l i p 月 第1 章绪论 第1 章绪论 配电网具有环状结构、开环运行的特点。配电网中包含了大量的常合开关 及少量的常开开关。配电网重构就是在保证配网呈辐射状、满足馈线热容、电 压降落要求和变压器容量等的前提下，改变分段开关、联络开关的组合状态， 使配电网某些指标( 如：配电网线损、负荷均衡或供电电压质量等) 为最佳的配网 运行方式。从数学角度来看，配电网重构是一个典型的多目标非线性整数组合 优化的问题，也是一个n p 难的组合优化问题。 1 1 概述 在现代电力系统中，大型的发电厂往往远离负荷中心，发电厂发出的电能、 一般要通过高压或超高压输电网络送到负荷中心，然后在负荷中心由电压等级 较低的网络把电能分配到不同电压等级的用户。这种在电力网中主要起分配电 能作用的网络就称为配电网络。 配电网络在电力系统中所承担的任务就是把从电源或输电网获得的电能直 接分配给不同电压等级的用户。与输电网相比，它拥有极大数量的电力设备， 并占整个供电系统投资的6 0 及运行成本的2 0 。我国与世界其它发达国家相 比，配电网发展起步较晚，发展水平较低，建设相对落后。城市配电网，特别 是老城网，已或多或少滞后于城市的经济发展，成为制约城市发展的瓶颈。配 电网结构不合理，电力设备数量多但性能落后、免维护水平低且不适合自动化 要求等，导致停电事故频繁发生，恢复供电效率低，可靠性不高，严重影响了 人民的生活水平和经济建设的发展。 随着国民经济的高速发展和用电负荷不断的增长，我国的电力系统，特别 是配电网及配电设备得到了长足的发展，配电系统的网络结构同趋复杂，供电 运行方式的变化越来越频繁，控制操作及事故处理的难度也越来越大。与此同 时，由于日益增长的能源成本、环境问题和高昂的资本投入，迫使电力公司尽 可能地利用现有网络并优化现有的系统结构，以达到产生更多运行容量、减缓 投资压力、为用户提供低廉的电价与优质服务的目的。网络重构正是供电公司 充分发挥现在设备潜力，提高电网运行的经济水平和供电可靠性，降低运营成 第1 章绪论 本的一种有效途径。 配电网络重构包括配电系统正常运行时的网络重构与故障情况下的网络重 构。配电网络正常运行时通过改变联络丌关和分段开关的分合状态来改变网络 拓扑，从而改变网络中的功率流，以达到降低网损、平衡负荷和提高供电电压 质量的目的。故障时的配电网络重构主要为了快速恢复非故障区域供电，一般 称为故障恢复。配电网络重构可以有效提高供电可靠性、降低网损、均衡负荷 和改善供电电压质量，是现代配电网自动化的重要功能之一。对非故障区域实 现最佳的恢复供电路径，仅仅实现快速恢复供电对于电力体制改革不断深化的 今天是远远不够的。企业的运作理念应深入到各个可挖掘的环节，以力争安全、 可靠、经济、实效。因此，在快速恢复供电的同时，必须满足线路负载容量的 要求、线损最小、操作次数最少、恢复后各馈线负荷平衡、可靠性最高等条件。 1 2 配电网重构研究现状 现有方法主要有：数学优化技术【l 】，其优点是算法比较成熟，可以得到不 依赖于初始网络结构的全局最优解，但存在严重的“维数灾”问题，数学优化 技术属于“贪婪 搜索算法，计算时间非常长，不能处理复杂的大规模的电力 系统拓扑结构。最优流模式算法【2 。3 1 ，将复杂的开关组合问题简化为优化潮流 问题，使复杂问题得到了简化，并且其重构的结果与初始网络状态无关，比较 容易收敛于最优解。但缺乏数学意义上的全局最优；支路交换算法【4 引，支路 交换算法是由s c i v a n l a r 等人首先提出的，该方法首先计算配电网的初始潮流和 网络损耗；然后闭合网络中的一个联络开关，形成一个环网；再在环网中选择 一个分段开关打开，使配电网恢复为辐射状网络，从而实现负荷转移，达到降 低网损、负荷均衡和消除线路过载等目的。支路交换法通过启发式规则可以减 少需要考虑的开关组合，可以快速的确定降低配电网线损的重构结果。但是该 方法受网络初始状态影响，不能保证得到全局最优解；并且每次只能考虑一对 开关操作，算法并行性差。人工智能算法，如模拟退火算法【6 j 、人工神经网络 【7 1 、遗传算法【8 - 9 】等。基于随机性、正反馈性和协同性的人工智能算法能以较大 概率收敛到全局最优解。但是模拟退火算法计算量大且对参数和退火方案依赖 性大；人工神经网络训练困难；遗传算法依赖于操作算子和初始种群并且其后 期极易陷入局部最优。 2 第1 章绪论 实际上，配电网重构分为两类：一类是基于时间点的静态重构，前文所述 方法都是指静态重构。静态重构给定恒定负荷下的最优网络结构。另一类是基 于时间区域( 通常l d ) 的动态重构。即在负荷不断变化的一个时间区间内找出 最佳的重构时间和对应的网络结构，使整个时间区间内的运行费用最小。为了 更好地保证配电系统的安全、优质、经济运行，常常需要依据负荷的变化对配 电网结构进行动态调整，即需要进行动态重构。文献 1 0 1 将各时间点的负荷进行 等效，将整个时间序列内变化的负荷分成1 个或几个恒定的水平段，再用静态 方法进行重构。由于该方法采用近似法来等效负荷，在每个等效时间段的初始时 刻进行优化，虽在工程上有一定的实用性，但不是真正的动态优化。文献【l1 】 根据优化的需要将开关操作次数按时间点的先后顺序进行分配。显然，如果前 面时段的重构开关操作次数较多，则后面时段的重构只能选次优的组合方式来 避免开关操作次数的越限，采用的是一种简化、折衷的策略。文献 1 2 1 先求出各 时间点的较优结构，然后以时间点作为阶段，将各时间点的较优结构作为状态， 用动态规划法求解，使整个时间区间的网损最小。由于各阶段状态的选取局限 在几个较优的结构中，所求结果对于整个时间区间来说未必是最优解。文献 1 3 】 将开关组状态和三进制时间一起编码，对网络结构和重构时间同时进行优化， 对改进系统进行了动态重构。 1 3 本文的主要工作 本文从理论研究和工程应用出发，对配电网网络结构进行优化研究，提出 了相应的配电网网络重构方法，针对配电网重构中的具体问题提出了解决方法。 由于时间有限，本文的重点放在配电网静态重构，在对配电网静态重构进行深 入分析的基础上，对基于食物链生态进化算法的配电网动态重构进行探讨。将 食物链生态进化算法e e a f c ( e c o l o g ye v o l u t i o n a r ya l g o r i t h mo ff o o dc h a i n ) 应用 于配电网重构。该算法模拟生态食物链多种群并存的竞争进化方式，提高了个 体的多样性和进化的层次性，具有良好的全局和局部搜索能力，并且避免了已 有仿生类算法参数难于确定和未成熟收敛等缺陷。主要工作如下： l 、对配电网潮流计算方法进行比较研究。对前推回代法进行m a t l a b 编程实 现，对其性能进行分析比较。将前推回代法计算结果与牛顿拉夫逊法以及相关 文献进行比较，确保配电网重构中潮流计算的准确性。 3 第1 章绪论 2 、对本文将用于配电网重构的优化算法( 食物链生态进化算法) 进行研究， 并作相应的改进，使其能很好地解决配电网重构的寻优任务。 3 、配电网正常运行时网络结构呈开环辐射状。网络优化过程中会产生大量 不符合配电网运行结构的不可行解。本文在分析配电网网络结构的基础上，提 出不可行解的避免方法。 4 、将食物链生态进化算法应用于配电网静态重构。提出了基于基本环路的 整数编码方法，降低了变量维数，减小了存储空间。采用i e e e l 6 、i e e e 3 3 和 i e e e 6 9 三个不同规模测试系统对所提方法进行了验证，并与改进的遗传算法和 相关文献结果进行比较。 5 、将食物链生态进化算法应用于配电网动态重构。将i e e e l 6 系统进行动 态改良模拟，使其包含重工业、轻工业、市政生活等多种变化负荷。应用食物 链生态进化算法对其进行等时间分割的多时间段落动态重构，并比较优化前后 的运行成本。 4 第2 章配电网潮流计算方法研究 第2 章配电网潮流计算方法研究 2 1 配电网潮流计算方法概述 配电网具有闭环设计、开环运行的特点，即在某些情况下，比如为了平衡 馈线之间转移负荷时，会出现暂时的双电源或闭环情况，但是在正常运行时， 配电网采用单电源点，开环运行。在正常运行时，一条馈线只有一个电源点， 这个电源点在潮流计算中作为平衡节点，而且每个负荷节点只有一个父节点， 馈线整体呈辐射状拓扑结构，所以配电网潮流计算研究以辐射状网络为研究模 型。 配电网潮流计算是配电网分析的基础，配电网的网络重构、故障处理、无 功优化和状态估计等都需要用到配电网的潮流数据。配电网具有闭环结构、开 环运行的特性，稳态运行时网络结构呈树形、多分支的单向辐射状，只有在发 生故障或切换负荷时才有可能出现短时环网运行；线路r x 值较高，多数情况 大于1 。网络的p q 节点多，p v 节点较少。与输电网相比，配电网的网络结构 有明显的差异，使得其潮流计算也有自身的特点。 文献 1 4 】将配电网潮流计算分为三类：牛顿类、母线类和支路类。由于牛顿 法具有二阶收敛特性，在配电网潮流计算中仍然保持着收敛速度和迭代次数方 面的优势。在配电网潮流计算的实际应用中仍然是一种性能优良的潮流计算方 法。牛顿法和快速分解算法由于要求解雅可比矩阵，因此计算时间较长。并且 牛顿法对初值敏感，在不合适的初值情况下，算法可能不收敛。而各种快速分 解法受到阻抗比的限制在配电网潮流计算应用中存在很大的局限性。 母线类算法主要以y b u s 法和z b u s 为代表。母线类方法中z b u s 和y b u s 算 法本质上是一样的，主要是根据迭加原理，母线上的电压可以通过根节点在母 线上产生的电压，以及母线上等值注入电流产生的电压迭加求得。等值注入电 流指除根节点以外的其它网络元件，包括负荷、电抗器、无功补偿设备等在其 所连的母线上产生的等值电流。由于导纳矩阵是极度稀疏，导致y b u s 法收敛速 度慢。z b u s 是一阶收敛的算法，但也是一种性能优良的潮流计算方法，具有接 近牛顿法的收敛速度和收敛特性。在实际应用也是一种可以被采用的配电网潮 流计算方法。 5 第2 章配电网潮流计算方法研究 支路类方法包括回路法、前推回代法和基于支路电流( 功率) 的潮流计算 方法等。回路法是指针对配电网短时出现的环网情况提出的，能够较好地处理 配电网出现环网情况下的潮流。前推回代法则需要分层处理各支路。基于支路 电流的潮流计算和基于支路功率的潮流计算在本质上是一致的，其原理相当于 已知根节点的电压和各支路末端的负荷电流( 功率) 时求解辐射状网络的潮流。 支路类算法编程简单，当配电网的复杂程度不高时，此类算法具有收敛速度快 数值稳定性好的特点，其中前推回代法不需要进行矩阵运算，占用计算机资源 少。另外多数前推回代方法不能求解电压角度，所以这类算法在不需要处理无 功的场合是非常适合的。对于实际的不同规模和复杂程度的配电网系统以及不 同的具体问题，上述配电网潮流计算方法的计算效果肯定是不同的。 2 2 前推回代法配电网潮流计算 前推回代配电网潮流计算方法是依据配电网网络结构特点和运行特点而开 发的相应计算方法。以网损最小为目标的配电网重构每次寻求到一种网络结构 都要进行一次潮流计算，对相应的潮流计算方法的性能要求较高。配电网重构 也是在满足配电网网络结构特点和运行特点的前提下寻求最优的网络结构。前 推回代法对于辐射状运行的配电网潮流计算有其独特的优势，并且由于算法本 身的计算速度快，稳定性高等优点，应用在配电网重构问题中是非常合适的。 2 2 1 前推回代法计算原理 文献【1 5 针对前推回代法中存在的复杂编号或分层的问题，提出了一个无需 节点和支路编号、只要直接输入节点名称的以功率损耗和节点电压为参数的前 推回代算法。考虑如图( 2 1 ) 所示的一个三相平衡的辐射网络，其基本的支路 潮流方程为： p l o s s ，= 勺( 乎+ 彰) 吁 ( 2 1 ) q l o s s ，= x 口( 巧+ 彰) 吁 ( 2 2 ) 0 = 只+ p l s s 。 ( 2 3 ) 或= q ，+ q l o s s l ， ( 2 4 ) 只= p l ，+ 只肌 ( 2 5 ) 6 第2 章配电网潮流计算方法研究 q = 舛，+ 鲰 m n j 呼= k 2 - ( r , j p , + q ) ( + x ! ，2 ) ( 只2 + q j 2 ) k 2 ( 2 6 ) ( 2 7 ) 式中p l o s s 盯、q l o s s 为支路 ，的有功和无功功率损耗；弓、g 为节点f 的注入有 功和无功功率( 节点f 的负荷+ 节点f 后续所有支路功率损耗) ；p l 。、舛；为节点f 的有功和无功负荷，k 为节点f 的电压幅值，n j 是以f 为始节点的支路的终节点集， 下面以图2 1 为例，分析前推回代法计算过程。 馈线1馈线2馈线3 1 s ” 2 $ 1 3 4 5 1 4 s 2 2 11 13 图2 1i e e e e l 6 配电网系统 对节点随意进行命名，并按任意顺序分别形成网络的支路文件和节点文件。 其中支路文件中的每一个记录都包含有支路两端节点的名称、电阻、电抗。节 点文件中的每一个记录都包含有节点的名称、有功负荷、无功负荷。现以图2 1 所示的网络为例。1 6 节点配电网系统的计算流程如下，按习惯以节点顺序排列 形成的网络支路文件和节点文件见表2 1 和表2 2 所示。表2 1 中，、，为支路两 端的节点名称，r 、x 为支路的电阻和电抗，表2 2 中，为节点的名称，尸、q 为 节点的有功和无功负荷。 7 第2 章配电网潮流计算方法研究 8 第2 章配电网潮流计算方法研究 在开始潮流计算前，先对支路文件和节点文件进行一次排序。辐射型网络 的一个显著特点是节点数等于其支路数加1 ，也就是除电源节点外，每一条支路 对应着一个节点。针对辐射状网络的这个特点，支路数据记录编号从1 开始， 节点数据记录编号从l 开始，这样使得按下述方法排序后的支路文件和节点文 件的同一序号的记录具有一一对应的关系( 即节点和它的注入功率支路具有同 一个序号) 。具体排序方法如下：首先根据电源节点的名称在节点文件中搜索出 电源节点，并将其移到文件中序号为o 的位置，接着进入支路文件，搜索出第一 条与电源节点相联的支路，将该支路移到支路文件中序号为1 的位置，并使得 支路首末端与功率流动方向一致( 即功率流动方向为始端一终端) ；返回节点 文件，搜索出这个支路的另一节点，并将其移到序号为1 的位置，再进入支路 文件，搜索出第二条与电源点相联的支路，将该支路移到支路文件中序号为2 的 位置，并使得支路首末端与功率流动方向一致；重回节点文件，搜索出这个支 路的另一节点，并将其移到序号为2 的位置，如此继续下去，直到与电源点相联 的支路搜索完毕。然后按同样的方法分别在支路文件和节点文件中搜索出与节 点文件中序号为1 的节点相联的所有支路及支路对应的另一端节点，整个过程 直到全部支路搜索完毕。图2 1 对应的文件排序后的结果如表2 3 和表2 4 所示。 表2 3 中，、，分别为支路首端和末端的节点名称。 表2 3i e e e l 6 排序后的支路数据文件 9 第2 章配电网潮流计算方法研究 前推回代过程： 第一步：初始化，给定配电网跟节点电压甜，并为其他节点赋初值u i = l + j 0 ， i = 1 ，2 ，n ，n 为跟节点以外的所有节点。 第二步：从最低层一级负荷节点开始，根据节点功率+ q ，。计算注入该 节点的支路电流厶，：墨丝，表示共轭。 “ 第三步：利用公式( 2 1 ) ( 2 4 ) 算出各支路的功率损耗和首端功率。并 将计算出的支路首端功率按公式( 2 5 ) 和( 2 6 ) 合并进支路首端节点的注入功 率中( 既加上第二步中没有考虑的公式( 2 5 ) 和( 2 6 ) 中的第二项) 。这个过 程直到全部支路计算完毕。 第四步：根据所求得的功率分布，从序号1 开始，顺着排序后文件的顺序，按 公式( 2 7 ) 依次求出各节点电压。 第五步：计算各个负荷节点相邻两次迭代电压幅值差的最大值m a x laul ， 是否小于预先给定的收敛条件e ，若是，则停止计算；否则，n = ”+ 1 ，转步 骤二。 1 0 第2 章配电网潮流计算方法研究 第六步：得到各个节点的电压和支路电流后，计算网损圪。 2 2 2 前推回代法结果分析 算例为图2 1 所示的i e e e l 6 节点系统【4 1 。该系统额定电压为2 3 k v ，有1 6 个节 点和1 6 条支路，总负荷为2 8 6 0 0 k w + j1 7 3 0 0 k v a r ，s 1 5 、$ 2 1 和s 2 6 为联络开关。节点 1 为电源点电压v = i 0 5 ，收敛判剧为s 1 0 - 6 ，联络开关处于断开状态。使用m a t l a b 编程语言，在w i n d o w sx p 操作系统单任务环境下运行前推回代法和牛顿拉夫逊 法潮流程序。 c q 童 毒 刁 图2 2 前推回代法与牛顿拉夫逊法迭代过程比较 图2 2 为前推回代法与牛顿拉夫逊法迭代过程比较。横坐标表示迭代次数， 纵坐标为每次迭代待求量的平均偏差( d e v i a t i o n ) 。从图中可以看出前推回代法 仅用3 次迭代就收敛到精度范围内，过程非常的稳定。牛顿拉夫逊法是二阶收 敛算法，对解具有平方逼近性，在接近于真解时，依然具有较强的活跃性，特 别适合求解精确度高的系统。对比两根曲线可以看出前推回代法收敛速度快、 稳定性高。达到同样的收敛精度，前推回代法的迭代次数要少。 第2 章配电网潮流计算方法研究 表2 5 为前推回代法与牛顿拉夫逊法计算结果比较。在同样的收敛判据下， 前推回代法的迭代次数为3 ，少于牛顿拉夫逊法的5 次。由于牛顿拉夫逊法每次 迭代都要计算雅可比矩阵，因此比前推回代法耗费的时间多很多。前推回代法 可以得到与牛顿拉夫逊法同样精确的计算结果。 表2 。5 前推同代法与牛顿拉夫逊法计算结果比较 比较项目 前推回代法牛顿拉夫逊法 迭代次数 35 计算时司( s )0 2 3 51 1 4 1 节点21 0 4 1 11 0 4 1 1 节点3 1 0 3 5 81 0 3 8 4 节点41 0 4 4 71 0 4 4 7 节点51 0 3 8 41 0 3 8 4 节点61 0 3 6 71 0 3 6 7 待 节点71 0 3 3 71 0 3 3 7 求 节点81 0 3 3 91 0 3 3 9 电 压 节点91 0 4 2 21 0 4 2 2 模 节点1 01 0 4 5 11 0 4 5 1 值 节点1 11 0 3 5 61 0 3 5 6 节点1 21 0 3 9 51 0 3 9 5 节点1 31 0 3 2 21 0 3 2 2 节点1 41 0 4 1 71 0 4 1 7 网络损耗k w5 1 1 4 75 1 1 4 7 1 2 第3 章食物链生态进化算法 第3 章食物链生态进化算法 3 1 生物进化与遗传算法 按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化 历程，生物种群从低级、简单的类型逐步发展成为高级、复杂的类型。各种生 物要生存下来，都要经过“自然选择，适者生存 的过程。根据孟德尔( m e n d e l ) 和摩根( m o r g a n ) 的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞 中，并以基因的形式组合产生的个体对环境的适应性不一样，通过基因杂交和 突变可以产生对环境适应性强的后代。通过优胜劣汰的自然选择，适应值高的 基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了 遗传和变异的基本规律。在一定的环境影响下，生物物种通过自然选择、基因 交换和变异等过程进行繁殖生长，构成了生物的整个进化过程【l 6 1 。 图3 1 生物进化过程 这个框图表明，生物的群体经过大自然的选择，适者生存，劣者淘汰，成 为优胜群体。种群内的生物经过交叉产生子代( 新个体) 。子代生物与父代产生 了一些变异，变异了的新生代群体替代旧群体。这一过程循环往复使生物进化。 由此可见，生物的遗传进化是一个生物与自然界逐步适应的优化过程。 生物进化过程的发生需要4 个基本条件：1 、存在由多个个体组成的种群； 2 、生物个体之间存在着差异，或群体具有多样性；3 、生物能够自我繁殖；4 、 不同个体具有不同的环境适应能力，具有优良基因机构的个体繁殖能力强，反 之则弱。 生物群体的进化机制可以分为三种基本形式： 1 3 第3 章食物链生态进化算法 曲自然选择控制生物体群体行为的发展方向，能够适应环境变化 的生物个体具有更高的生存能力，使得他们在群体中的数量不断的 增加，同时该生物个体所具有的染色体形状特征在自然选择过程中 得以保留。 b ) 杂交通过杂交随机组合来自父代染色体上的遗传物质，产生不 同于他们父代的染色体。生物进化过程不需要记忆，能很好地适应 自然环境的信息都包含在当前生物体所携带的基因库中，并由子代 个体继承下来。 c ) 突变随机改变父代个体的染色体上的基因结构，产生具有新染 色体的子代个体。变异是一种不可逆的过程，具有突发性、间断性 和不可预测性，对于保证群体的多样性具有不可替代的作用。 生物进化是完美的问题求解器。因此应用数学家和计算机科学家都从生物 学进化中获得新的启示。遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 就是从模拟生物 遗传进化过程中得到的，将计算机科学与进化论结合起来应用于优化的计算。上 世纪6 0 年代中期，美国m i c h i g a n 大学的j o h nh o l l a n d 在f r a s e r 和b r e m e r m a n 等人的工作基础上提出了位串编码技术。这种编码既适合变异又适合于交配( 杂 交、交叉) 操作，并且强调将交配作为主要的遗传操作。随后，h o l l a n d 将该算 法用于自然和人工系统的自适应行为的研究中，并于1 9 7 5 年出版其开创性的著 作a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s 1 7 】。后来，h o l l a n d 与他的学生们 将该算法加以推广并应用到优化及机器学习等问题之中，并j 下式定名为遗传算 法。h o l l a n d 的g a 常被称为简单遗传算法( s g a ) ，其操作对象是一群二进制 串( 称为染色体) 即种群( p o p u l a t i o n ) ，每个染色体都对应于问题的一个解。从 初始种群出发，采用基于适应值的选择策略在当前种群中选择个体，使用交叉 和变异操作来产生下一代种群。如此一代代进化下去，直到满足期望的终止条 件。 遗传算法是一种基于自然选择和群体遗传机理的搜索算法，它模拟了自然 选择和自然遗传过程中发生的繁殖、杂交和突变现象。在利用遗传算法求解问 题时，问题的每个可能的解都被编码成一个“染色体”，即个体。几个个体构成 了群体( 所有可能解) 。在遗传算法开始时，总是随机的产生一些个体( 即初始解) ， 根据预定的目标函数对每个个体进行评价，给出一个适应度值，基于此适应度 值，选择个体用来复制下一代。选择操作体现了“适者生存 原理，“好”的个 1 4 第3 章食物链生态进化算法 体被选择用来复制，而“坏”的个体则被淘汰。然后选择出来的个体经过交叉 和变异算子进行再组合生成新一代。这一群新个体由于继承了上一代的一些优 良性状，因而在性能上要优于上一代，这样逐步朝着更优解的方向进化。因此， 遗传算法可以看作是一个由可行解组成的群体逐步进化的过程。其中，选择、 交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度 函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内 容。 一、生物学概念与遗传算法数学概念的对应关系： 进化适者生存目标函数取得最大值 个体可行解 染色体解的码( c o d e ) 基因码中的元素 适应性适应函数值 群体选定一组可行解 种群根据入选概率定出的一组解 选择根据适应值产生一组新解 交配根据交叉原则产生一组新解 变异码的某一元素改变 二、遗传算法步骤 计算前必须确定适应函数定义、停止计算的法则和编码规则，计算框图3 2 。 第一步，给出个个体，经编码成为个染色体( 编码) 作为初始群体， 记作p o p ( 1 ) ，= 1 。 第二步，按式3 1 计算群体p o p ( 1 ) 中每一个染色体的适应函数值， z = f i t n e s s ( p o p ，( 1 ) ) ( 3 1 ) 第三步，判断是否满足停止法则，若满足停止计算打印结果，否则按式( 3 2 ) 计算每一个染色体的入选概率 2 殛z n i = 1 , 2 n ( 3 2 ) 第四步，把n e w p o p ( t + 1 ) 中个体成对交叉，形成交配后的新染色体组成的种 群，c r o s s ( t + 1 ) 1 5 第3 章食物链生态进化算法 第五步，以一小概率使c r o s s ( t + 1 ) 中的个体基因改变到m u t p o p ( t + 1 ) 新群体 替代旧群体p o p ( t ) = m u t p o p ( t ) ；转向第二步。 图3 2 遗传算法框图 遗传算法利用生物进化和遗传思想实现优化过程，区别于传统优化算法， 它具有以下特点： ( 1 )g a 对问题参数编码成“染色体”后进行进化操作，而不是针对参数 本身，这使得g a 不受函数约束条件的限制，如连续性、可导性等。 ( 2 )g a 的搜索过程是从问题解的一个集合开始的，而不是从单个个体开 始的，具有隐含并行搜索特性，从而大大减小了陷入局部小的可能。 ( 3 )g a 使用的操作均是随机操作，同时g a 只根据个体的适应值信息无 需其他信息进行搜索。 ( 4 )g a 具有全局搜索能力，能解决复杂非线性优化问题。 但实际应用g a 时，往往出现早熟、收敛性能差和陷入局部极优等缺点【1 8 】。 首先，理论上g a 的全局收敛性保证了算法对初值的鲁棒性，但在实际应用 时由于收敛条件难以保证，从而导致算法的优化性能和效率对初始种群的依赖 性。如果随机初始种群分布较局部，那么遗传算法极易陷入局部最优。 1 6 第3 章食物链生态进化算法 其次，对函数适应值梯度依赖性大。由于操作算子固定不变，适应值梯度 较小时，遗传算法失去了在几个相近解中搜索最优解的能力。 本文提出采用食物链生态进化算法解决配电网重构问题。食物链生态进化 算法( e e a f c ) 是模拟生态环境中生物界的能量传递方式( 食物链) 的一种多 模式协同进化的生态进化算法m e e a ( m u l t i p a t t e me c o l o g ye v o l u t i o n a r y a l g o r i t h m s ) 。各模式采用遗传算法操作算子( 选择、交叉、变异) 纵向进化，同 时模式间横向沿食物链以捕食方式竞争进化。食物链生态进化算法是以自然基 因选择机制和物种竞争机制为基础的优化算法。它继承了遗传算法综合自然基 因适应自然和目标优化的优点，同时引进多种群模式协同进化，克服单种群遗 传算法局部极优和收敛慢等缺陷。 3 2 食物链简介 生态环境中生物界的能量传递是以食物链的方式进行的。所谓食物链是指 生态系统内不同物种之间在营养关系中形成的一环套一环的链条式关系，物质 和能量沿着食物链，一级一级地从低级物种转移到高级物种，沿着食物链种群 个体的数量逐级减少，种群密度逐级降低，繁殖速率逐级减慢。这样以生物种 群的个体数量比较形成了图1 所示的一个底部宽、上部窄的生态金字塔【1 9 1 。 l 顶级l i 食肉生物l l食肉生物i l 食草生物 l l 白养生物 l 图3 3生态系统中的生态金字塔 由不同级别物种组成的食物链有以下特点：各物种接受环境的考验独立 进化；食物链中相邻物种按式( 3 3 ) 所示的林德曼生态效率进行能量传递； 各物种独立进化时可能产生更高级的物种。 口= i n i 位 1 ) ( 3 3 ) 式中：口为林德曼生态效率；，。、i n 一。分别为相邻高、低两物种层的能量摄取量。 3 3 食物链生态进化算法 食物链生态进化算法e e a f c ( e c o l o g ye v o l u t i o n a r ya l g o r i t h mo ff o o dc h a i n ) 1 7 第3 章食物链生态进化算法 是以自然基因选择机制和物种竞争机制为基础的优化算法。它继承了遗传算法 综合自然基因适应自然和目标优化的优点，同时引进多种群模式协同进化，克 服单种群遗传算法局部极优和收敛慢等缺陷。一般取高级、普通、低级三个种 群模式用于优化计算。 此算法将生态环境压力对应待求解问题，每个个体对应问题搜索空间的一 个候选解，个体对环境的适应度对应目标适应度函数的值。算法模拟食物链的 能量传递方式构造进化链，沿着进化链个体的数量逐级递减，而个体的适应度、 稳定性逐级提高。由低到高采用多种不同的模式来进化个体。不同个体在环境 中的成长可能不同，个体进化的方式可沿进化链从低级模式向高级模式迁移， 利用模式调整实现算法从一个局部极优状态向下一个更好的局部极优状态定向 移动【1 6 j 。 计算过程如下： a ) 初始化：产生初始种群。 b ) 生成进化链：计算适应度，生成多模式食物链。生成依据为林德曼生态 效率口 1 6 】( 如式3 4 ) 。构造结构如表3 1 ，例如n i = 2 0 0 ，口= 0 1 。 表3 1 食物链种群个体数构造 n t = a n i + 1 ( 3 4 ) 式中：i 、分别为高低种群个体数。 c )多种群模式进化：各模式种群独立按各自模式进化，更新模式，操作算 子为选择、交叉、变异。对于变异，由于低级种群对环境的适应度较小， 一般变异率取值较大，而高级、中级种群变异率取值较小。 d ) 模式调整：将优良个体移动到高一级模式中；高级种群模式中的个 体对下级种群i j 。个体进行调整替换。 e ) 收敛校验，满足条件，停止计算；否则，重复( c ) 、 ( d ) 。 1 8 第3 章食物链生态进化算法 图3 4 基于食物链生物进化算法的配电网重构流程 这种多模式协同进化算法有如下特征： ( 1 ) 进化链上多种不同生存方式固有的产生和保持多样性的能力，可以维 持算法的全局搜索能力而不陷入局部极优解。 ( 2 ) 进化链中各类同时按各自模式进化所体现的并行处理能力，使算法既 可体现进化链顶端个体的稳定性，也可体现进化链低端个体的活跃性，从而同 时具有良好的全局和局部搜索能力。 ( 3 ) 进化链中各类按各自模式独立进化所体现的进化隔离机制，可以使算 法中进化链顶端个体的优良特性得以稳定，不受低端个体的影响。 ( 4 ) 进化链中的定向传递机制，可使算法中的多模式间建立和保持稳定的 联系。 1 9 一多模式协同进化 一 -ij!il 第4 章配电网网络结构分析与配电网重构编码方法 第4 章配电网网络结构分析与配电网重构编码方法 4 1 图论的基本概念 4 1 1 图论术语 图论是组合数学的一个分支，由于它和数学中的运筹学、控制论和信息科 学有着密切的联系，因此发展迅猛。下面是图论的一些基本概念。 图由一个点集矿以及连接其中某些点对的线段( 称为边) 集e 构成的图 形。其中，点集v 中的点称为顶点，e 中的线段称为边( 它们可以是曲线段) 。 简单图若一条边连结的是同一顶点，则称该边为环；若两个顶点间有 腹扮= 2 ) 条边相连，则称这些边为平行边。若一图没有环，也没有平行边，这样 的图称为简单图。 完全图每两个顶点之间都有边相连的简单图称为完全图。刀各顶点的完全 图记为七。 顶点的度图中与顶点相连的边数。 连通图如果图中的任何两个顶点，都有从一个到另一个的完整路径，那 么此图称为连通图。一个连通且没有圈的图称为树。 4 1 2 树 树在图论中很重要。连通图g 具备下述条件者称为树【2 0 】： 曲包含全部节点； b 】不包含回路； c )连通。 树的补图称为补树。树的支路称为树支，补树的支路称为连支。 对于有n ，个点的连通图任一树的树支数为 n = n ，一l ( 4 1 ) 若连通图g 支路数为b ，则连支数为 ，= b - ( n ，- 1 ) ( 4 2 ) 在图论中称 7 为图g 的秩，称，为图g 的环秩。 2 0 第4 章配电网网络结构分析与配电网重构编码方法 b 图4 1 树 树r 的任二点间必有且仅有一条通路。因为树是连通的，所以必有通路； 因为不存在回路，所以不可能有第二条通路。这是树的一个重要定理。任二点 间若加上连支，必存在一个唯一的单连支回路。如图中a 、b 点，加上虚线所示 的连支，则必有且仅有一个只包含这条连支和a 、b 间唯一树径构成的回路。，条 连支，可以有，各单连支回路。这些单连支回路也称为基本回路。 4 2 配电网网络结构分析 4 2 1 配电网网络接线方式 配电网按电压等级来分类，可分为高压配电网( 3 5 - - - 1 l o k v ) 、中压配电网( 6 l o k v ) 、低压配电网( 2 2 0 - - - - 3 8 0 v ) 。文献 2 1 】将中压配电网接线分为几种典型的方 式。图4 2 所示为一般的树状放射形接线。图4 3 所示为环形接线。图4 4 所示 为链形接线，正常运行时打开一部分分段开关。图4 4 所示为网孔形接线，正常 运行时，根据运行要求按开环方式运行。 2 l 第4 章配电网网络结构分析与配电网重构编码方法 图4 2 配电网放射形接线 图4 3 配电网环形接线 图4 4 配电网链形接线 第4 章配电网网络结构分析与配电网重构编码方法 图4 5 配电网网孔形接线 4 2 2 配电