关键词：多阶段配电网规划；演化算法；编码策略
分类号：TM715 文献标识码：A
文章编号：0258-8013(2000)03-0034-05OPTIMALMULTI-STAGEDISTRIBUTIONPLANNING
USINGEVOLUTIONARYALGORITHMWANGTian-hua
（BeijingCreativeDistributionAutomationCo.,LTD.,Beijing100085,China）
WANGPing-yang FANMing-tian
（ElectricPowerResearchInstituteChina，Beijing100085，China）ABSTRACT：Inordertotakeintoaccounttheloadchangesbetweendifferentyears,thedistributionplanningshouldbedonestagebystage.Inthispaper,evolutionaryalgorithmisappliedtothemulti-stagedistribution-planningproblem.Anovelchromosomecodingstrategyisproposedtoensurethatalltherandomlygeneratedchromosomesarefeasible.Thiskindofcodingstrategymakesthesearchingprocessconfinedtoonlyfeasiblesolutions.Inaddition,becauseofnoneedofradiallitycheckingprocedure,theevolutionprocessisgreatlyimproved.Theexamplesystemdemonstratestheeffectivityandeffeciencyoftheproposedmethod.
KEYWORDS：multi-stagedistributionplanning;evolutionaryalgorithm;chromosomecodingstrategy▲1 引言在电力系统中，配电系统与用户的联系最紧密，对用户的供电可靠性和供电质量的影响也最直接。好的配电网规划不仅能够为电力公司节省大量的投资和运行费用，而且能够提高用户的供电满意度。在竞争机制不断引入电力市场的今天，配电网规划方法的研究格外受到重视。
配电网规划在本质上是一个离散、非线性、多阶段、多目标的组合优化问题，其目的是：在满足对用户供电和保证网络运行约束的前提下，寻求一组最优的决策变量(变电站的位置和容量、馈线路径和型号、常开和常闭开关的位置)，使得投资、网损和用户停电损失之和最小。在长期配电网规划中，为了动态地考虑不同时间段的负荷变动情况，常常将规划分成几个阶段进行，称之为多阶段配电网规划。一个阶段可能为1年，也可能是几年，这需要根据负荷在整个规划年限内的变化来确定。多阶段规划使得配电网络结构随负荷的变化作动态的调整，以寻求一种动态的设备投入方案来保证规划结果在整个规划年内是最优的。
传统的优化算法在求解配电网规划问题时，往往对问题作如下简化［1，2］：(1)将变电站和馈线系统分开规划；(2)将非线性问题线性化；(3)将多阶段问题分解成单阶段问题；(4)不考虑配电网的辐射状运行约束；(5)不考虑可靠性。所有这些简化使得所求出的解只是在某一特定条件下的局部最优解，从而影响了它的实际应用。遗传算法作为一种通用的问题求解模型，正是在这种背景下引入配电网规划问题的。遗传算法不仅能够考虑非线性、不连续的约束和目标函数，而且可以提供一组优化解以辅助规划人员进行决策，因而特别适于配电网规划的求解。但遗传算法没有很好地利用配电领域的专业知识来指导寻优过程，寻优速度相对较慢。演化算法强调利用领域知识来指导寻优过程，弥补了遗传算法的不足，在具体问题的优化求解中更为有效［3，4］。
在配电网规划中，一个可行方案应该在满足对所有负荷点供电的基础上保持网络的辐射状运行。传统的遗传算法在处理该约束时往往是通过检查方案的辐射性，并对产生环的方案进行惩罚来实现的。由于在随机产生的方案中，可行方案的比例相当低，遗传算法的进化速度就会很慢，不容易找到全局最优解。
本文将演化算法应用于多阶段配电网规划问题的求解，提出了一种能够自动保证方案可行的染色体编码策略。这种编码策略使得演化算法只搜索可行解区域，避免了辐射性检查过程，从而提高了寻优速度。算例证明了算法的有效性和优越性。2 遗传算法处理配电网规划问题的不足配电网规划问题可以形式化地表示为
min(投资＋网损＋可靠性损失)(1)
约束：
变电设备不能过载(2)
节点电压不能超标(3)
辐射状运行(4)
对所有的负荷供电(5)我们把满足约束(4)和(5)的方案称为可行的。很显然，可行方案必须满足：(1)不能形成环路；(2)变电站间不能存在通路；(3)所有负荷节点必须有与源点的通路。
配电网规划总是从一张由现有和备选变电站及馈线组成的网络图开始的，如图1［5］。传统的遗传算法采用随机产生的二进制数或整数串来表示方案的网络结构，0表示配电设备在某阶段不投入，1表示投入运行。这种染色体编码方法是以规划网络图为基础的，编码串的长度取决于设备数。另外，该编码策略很难保证所产生的方案是可行的。即使是可行方案，交叉和变异操作也很容易使之变得不可行。作者曾经对这种随机产生的方案进行过统计，结果只有<1‰的方案是可行的。由此可见，采用这种编码策略，要找到一个可行解也是困难的，而且该策略需要额外的辐射性检验子程序来确定是否对不可行的方案进行惩罚［5］，因而传统遗传算法通常难以在比较短的时间内给出最优规划结果。
因此，遗传算法应用于配电网规划问题的关键是要找到一种编码策略。该策略不仅能够以尽可能短的染色体串来表示网络结构，而且要使得产生的方案从编码上保证所有方案都是可行的。图1 配电网规划初始网络图
Fig.1 Initialnetworkfordistributionplanning3 自动产生可行方案的编码策略为了产生一个可行方案，必须通过不建或装设常闭开关的方式来断开馈线支路，使得网络满足可行方案的三个条件。本节以图论为基础推导出断开馈线支路的几个基本原则，以辅助编码策略的设计。
3.1 图论最大支撑树和节点度的概念
在图论中，最大支撑树是指一个包括所有节点但不形成环的连通图。在最大支撑树中增加一条边则必然形成一条回路，删除一条边则使得图不连通。对于一个由m个节点、n条边组成的图，其基本回路数为n－m＋1，形成最大支撑树的必要条件是必须有n－m＋1条边是断开的。图论中另一个重要概念是节点的度。度反映了节点连接边的个数。
3.2 方案可行的必要条件
在规划网络图中，如果将所有k个变电站节点合并成一个虚拟的电源点，则得到一张虚拟图，其节点数降低为m－k＋1。不难看出，由此虚拟图的最大支撑树形成的规划方案必然满足可行方案的三个条件。此时，需要断开的馈线数为n－(m－k＋1)＋1＝n－m＋k。因此，对于一个由k个变电站、n条馈线、m个节点组成的规划网络图，产生可行方案的必要条件是必须断开其中的n－m＋k条馈线。
3.3 形成简化图
在规划网络中，边(线路)可以分为2类：(1)辐射边。(2)与其他边构成回路的边。图1中，边19-20、18-19等本身就是辐射的，而边21-18和18-17等则是非辐射的。很显然，辐射边是不能断开的，否则无法对其连接的负荷点进行供电。因此，辐射状的馈线支路不存在断开问题，它与网络结构的确定无关，可以从初始图中删除。这样，规划网络图就可以初步简化成只由非辐射边构成的网络。初步简化图中的负荷节点也可以分为2类：度为2的节点和度大于2的节点。为了保证每个负荷节点只有一条馈线对其供电，2个度大于2的节点之间的路径中最多只能有一条边是断开的，否则会造成部分负荷节点成为孤立节点。如节点9和43间的路径9-10-31-37-43中的4条边只能断开一个，具体断开哪一条边可以随机确定。为了方便叙述，称2个度大于2的节点之间的路径为简化边，以简化边构成的网络图称为简化图。如果编码策略能够保证在简化图上产生方案是可行的，从每条断开的简化边中随机选取一条边断开所形成的方案一定是可行的。这种只需在简化图上确保方案可行的编码策略，不仅排除了一些不可行方案，减小了演化算法的搜索空间，而且缩短了染色体串长(图1中简化边仅为22个)。
3.4 编码策略
前2节的论述给[1][2][3]下一页
