分类号：tm715 文献标识码：a
文章编号：0258-8013 (2000) 03-0034-05
optimal multi-stage distribution planning
using evolutionary algorithm
wang tian-hua
（beijing creative distribution automation co.,ltd.,beijing 100085,china）
wang ping-yang fan ming-tian
（electric power research institute china，beijing 100085，china）
abstract：in order to take into account the load changes between different years, the distribution planning should be done stage by stage. in this paper, evolutionary algorithm is applied to the multi-stage distribution-planning problem. a novel chromosome coding strategy is proposed to ensure that all the randomly generated chromosomes are feasible. this kind of coding strategy makes the searching process confined to only feasible solutions. in addition, because of no need of radiallity checking procedure, the evolution process is greatly improved. the example system demonstrates the effectivity and effeciency of the proposed method.
key words：multi-stage distribution planning; evolutionary algorithm; chromosome coding strategy▲
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 initial network for distribution planning
3 自动产生可行方案的编码策略
为了产生一个可行方案，必须通过不建或装设常闭开关的方式来断开馈线支路，使得网络满足可行方案的三个条件。本节以图论为基础推导出断开馈线支路的几个基本原则，以辅助编码策略的设计。
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节的论述给出了编码设计的基本原则：为了保证所产生的方案是可行的，需要断开规划网络中的n－m＋k条馈线，而且只能断开简化边，断开简化边中的具体哪条馈线是随机的。据此，可以初步确定多阶段配电网规划问题的编码策略，如表1。表1将阶段t的编码串分为5个子串。其中，“变电站”子串回答是否“新建或扩展变电站”这一类问题。“简化边”子串确定断开哪些简化边。“馈线”子串确定断开简化边中的哪一条馈线。“线型”和“开关”子串分别确定馈线的型号和是否装设开关设备。显见，配电网结构是由“简化边”和“馈线”子串确定的，其他3个子串的作用是确定网络元件参数。
表1 多阶段配电网规划的编码策略(阶段t)
tab.1 chromosome coding strategy for multi-
stage distribution planning (stage t)
| 串名 | 串长 | 内容 | 编码 |
| 变电站 | k | 整数 |
| 简化边 | t | 0、1 |
| 馈线 | t | 整数 |
| 线型 | m | 整数 |
| 开关 | m | 0、1 |
注：k 变电站数；t 简化边数；m 馈线支路数
采用表1的编码策略求解配电网规划问题时，“变电站”、“馈线”“线型”和“开关”子串各阶段间应该满足一定的关系，如馈线不能出现“架线复拆”现象；馈线一旦架设，其线型在规划水平年内应保持不变；馈线段上一旦装设了开关设备，只能改变其开闭状态(常开或常闭)，而不能拆除开关设备。这种各阶段编码在时间轴上应满足的约束称为纵向约束。
“简化边”子串不存在阶段间的关系。但为了保持编码方案可行，某一阶段的“简化边”子串内的串位间应满足可行性约束。这种阶段编码在染色体各串位上应满足的约束称为横向约束。
这种编码策略层次分明，结构灵活，可以根据规划的目的和要求对编码串进行裁剪和组合。如长期配电网规划不需要对开关的配置作出精确的决策，表1中的“开关”子串可以不采用。但在短期规划和配电自动化规划中，需要采用“开关”子串以进行可靠性分析。为了简化网络，降低备用导线的存储费用，很多电力公司采用单一线型，此时，“线型”子串也可以不采用。
3.5 保证方案可行的算法
表1的编码策略在一定程度上提高了可行方案的比例(作者实验结果为6%)，但仍然不能保证所有产生的方案都是可行的，这是因为3.2节得出的结论只是可行方案的必要条件，而不是充分必要条件。因此，在“简化边”子串的编码过程中需要采用一定的算法来保证方案的可行性。算法描述如下：
(1) 构造虚拟电源点，形成简化图。计算简化图中节点的度。置所有简化边的标记为真。置所有串位的编码值为0。
(2) 判断是否所有简化边的标记都为假。若是，结束“简化边”编码过程。否则，在所有标记为真的简化边中随机取一简化边，置编码值为1，置标记为假，将其所连接的2个节点分别执行步骤(3)。转步骤(2)。
(3) 节点度减1，再判断节点的度是否为1。若是，说明该节点只存在一条馈线支路对其供电，该支路不能断开，对这条不能断开的支路执行步骤(4)。
(4) 置支路标记为假。找出该支路连接的另一节点，若该节点的度为0，该节点已被孤立，对该节点执行步骤(5)。否则，对该节点执行步骤(3)。
(5) 检查该节点是否与电源点存在通路，若不存在通路，该节点为无源点，选择周围的一条断开支路合上，使得该节点与电源点存在通路。
采用该算法对网络结构进行编码时，能够确保：1)每个节点所连接的馈线支路不可能同时断开；2)每个节点都与电源点存在通路；3)满足方案可行的必要条件。可以证明，该算法产生的网络结构是辐射的，且能对所有的节点都供电，也就是说，方案是可行的。
4 交叉变异算子的设计和局部搜索能力的改善
交叉和变异算子是演化算法中2个重要的寻优操作。由于传统的单点交叉和变异算子难以保证方案编码在交叉和变异之后仍然能够满足纵向和横向约束，需要采用一定的修复算法对破坏约束的串位进行修正。纵向修复算子的目的是保持网络元件参数在时间上的约束关系，简单的排序算法就可以解决问题。横向修复算法通过断开或合上违反横向约束的馈线支路来局部修正交叉或变异操作所产生的“简化边”子串。上节中的编码算法能够作为横向修复算法。
演化算法全局搜索能力很强，但局部搜索能力较差［1］。演化算法可以很快地搜索到一个较优解，但越往后，搜索越慢。在配电网规划中，全局搜索主要体现在变电站和网络结构的确定上，而局部搜索通常对应馈线支路参数和开关配置的调整。因此，在演化的初期，应该以较大的概率对“变电站”和“简化边”子串进行交叉和变异。而在演化的后期，交叉和变异应该以较大的概率作用于“馈线”、“线型”和“开关”子串上。
5 适应值函数的设计和选择策略的确定
在演化算法中，适应值是判定方案优劣的主要依据。适应值函数的设计既要反映式(1)的目标函数，还要对违反式(2)、(3)的方案进行惩罚，如图2所示。图中包括目标函数f和3个惩罚函数g1、g2及g3，各符号意义如下：pl为网损；ens为停电损失；ic为投资，pns为过载容量；vv为电压超标程度；pwf为现值因子。
在演化算法中，一些适应度很大的超级个体常常会在演化过程的初期占据整个群体，从而导致早敛而不能搜索到最优解。为了避免这种早敛现象发生，通常需要对适应值进行一定的变换以减小超级个体被选择的机会，并适当增大弱小个体生存的机会，从而保持个体的多样性。这就涉及到如何确定选择策略的问题。本文对轮盘赌选择(roulette wheel selection)、锦标赛选择(tournament selection)及线性排名选择(linear ranking selection)进行实验研究，发现线性排名选择的效果最好。
图2 适应值函数评估流程图
fig.2 flow chart of fitness function evaluation
6 算例计算
本文所提出的算法已在国内的一个城市配电网(4个变电站、70个节点、91条线路、3个阶段)中取得应用。为了方便比较，本文对文［5］中的算例进行规划。规划网络图见图1，详细数据可向作者要求获得。规划结果分别列于表2和表3。为了节省篇幅，表3只列出断开的支路及其断开方式(从中可以看出各变电站的供电区域和联络开关的配置)，而常闭开关的配置则未列出。该算例只采用一种线型，故不作为决策变量。
表2 变电站规划结果(mva)
tab.2 planning result for substation (in mva)
| 变电站 | 阶段1 | 阶段2 | 阶段3 |
| s1 | 16.7 | 16.7 | 16.7 |
| s2 | 16.7 | 16.7 | 30.0 |
| s3 | 22.2 | 22.2 | 22.2 |
| s4 | 22.2 | 22.2 | 22.2 |
演化过程结束后，根据群体中各方案的费用(投资＋损失)与停电损失，得到了图3所示的关系图。图3说明了演化算法不仅能够提供最优方案，而且还能够提供多个次优方案以辅助规划人员决策。
表4是本文算法和文［5］的遗传算法在一些运行数据的比较。从演化代数的比较中可以看出，演化算法在计算条件复杂的情况下仍然能够取得较文［5］快的速度。
表3 断开的支路及其断开方式
tab.3 disconnected branches and disconnect mode
| 阶段1 | 阶段2 | 阶段3 |
| 支路 | 方式 | 支路 | 方式 | 支路 | 方式 |
| 4－7 | 3 | 4－7 | 3 | 7－8 | 3 |
| 9－10 | 3 | 1－9 | 3 | 1－9 | 3 |
| 9－17 | 0 | 9－10 | 3 | 9－17 | 0 |
| 9－22 | 0 | 9－17 | 0 | 25－8 | 0 |
| 25－8 | 0 | 25－8 | 0 | 6－28 | 0 |
| 27－26 | 0 | 6－28 | 0 | 37－31 | 3 |
| 6－28 | 0 | 13－43 | 0 | 13－43 | 0 |
| 13－43 | 0 | 44－38 | 0 | 38－39 | 0 |
| 44－38 | 0 | 38－39 | 0 | 33－8 | 0 |
| 38－39 | 0 | 33－8 | 0 | 40－16 | 0 |
| 39－32 | 0 | 40－16 | 0 | 47－46 | 0 |
| 33－8 | 0 | 49－50 | 0 |
| 40－16 | 0 | 47－46 | 0 |
| 48－49 | 0 | 注：“方式”表示支路断开的方式：3表示支路是通过装设常开开关断开的；0表示不装设。 |
| 49－50 | 0 |
| 47－46 | 0 |
| 46－14 | 0 |
图3 停电损失和费用的关系
fig.3 plot of solutions in a cost vs. reliability space
表4 运行时间的比较
tab.4 comparasion on running data
| 采用算法 | 优化目标/亿 | 计算条件 | 时间/s | 演化代数 |
| 文［5］ | 9.65 | a＋b | 300 | 300 |
| 演化算法 | 9.65 | c＋d | 97 | 230 |
| 演化算法 | 9.15 | c＋d | 156 | 380 |
注：a为粗略考虑可靠性，不考虑开关配置，会出现“架线复拆”现象。b为程序运行于nextstation(33mhz)。c为精确考虑可靠性，考虑开关配置，避免架线复拆现象。d为程序运行于pc 133mhz。
7 结论
传统遗传算法在求解配电网规划问题时，没有充分利用网络结构方面的知识，从而产生大量的不可行编码，导致寻优速度较慢。本文运用图论中最大支撑树和节点度的基本知识对方案可行的3个条件进行了分析，得出了保证方案可行的几条准则：(1)为了保证所产生的方案是可行的，需要断开规划网络中的n－m＋k条馈线;(2)辐射边不能断开,因而与网络结构的确定无关；(3)断开支路只能出现在简化边内；(4)网络结构的编码可以在简化图上进行。据此，本文提出了一种结构式编码策略。这种编码方法在结构上非常灵活，它不仅能根据规划的目的和要求进行调整和裁剪，而且还适用于配电网的其他规划问题的求解(如配电网重构等)。
尽管上述编码方法能够将可行方案的比例提高到一定程度，但并不能保证所有产生的方案都是可行的。因此，本文在3.4节中提出了一种能够自动保持方案可行性约束的编码算法。该算法使得演化算法只搜索可行空间，而且能够以概率的方式搜索整个可行空间。
演化算法由于利用了配电网的专业知识，在寻优速度上较传统的遗传算法有较大提高。算例结果说明了演化算法在求解配电网规划问题时的有效性和优越性。
作者简介：王天华(1969-)，男，湖北蕲春人，博士，从事配电网规划、配电自动化和配电管
理系统(dms)等领域的研究和开发工作；
王平洋(1909-)，男，上海人，博导，ieee lifo feuou；
范明天(1954-)，女，湖南衡阳人，教授，从事电力系统优化和分析等领域的研究
和开发工作。
作者单位：王天华（北京科锐配电自动化技术有限公司，北京 100085）
王平洋（中国电力科学研究院，北京 100085)
范明天（中国电力科学研究院，北京 100085)
参考文献：
［1］ramfrez-rosado i j，berna-agustin j l.genetic algorithms applied to the design of large power distribution system［j］.ieee trans on power systems,may 1998,13(2).
［2］suresh k k,lawrence c l.power distribution planning:a review of models and issues［c］.96 sm 487-9 pwrs.
［3］zbigniew michalewicz.genetic algorithms ＋ data structures ＝ evolution programs［m］.springer, 1996.
［4］潘正君 康立山 陈毓屏.演化计算［m］.清华大学出版社，1998.
［5］vladimiro miranda j v,ranito l m proenca.genetic algorithm in optimal multistage distribution network planning［j］.ieee trans on power system,november 1994,9(4).
