基于改进遗传算法的配电网络重构

　　 基于改进遗传算法的配电网络重构
余健明，蔡利敏
（西安理工大学电气工程系，陕西省 西安市 710048）

DISTRIBUTION NETWORK RECONSTRUCTION BASED ON
IMPROVED GENETIC ALGORITHM
YU Jian-ming，CAI Li-min
（Dept. of Electrical Engineering，Xi’an University of Technology，
Xi’an 710048，Shaanxi Province，China）
ABSTRACT: Taking the maximized reliability of distribution network for objective function and the continuous power supply of distribution system for constraint condition, an improved adaptive genetic algorithm, which is on the basis of ordering selection and direct comparison of the individual that violates the constraint, is put forward. It is a method in which the reliability of distribution network is calculated by preferred search of minimal path according to the depth. Verifying by RBTS Bus 4 system which is a typical calculation example of IEEE, the result shows that the presented algorithm is effective. Comparing with Tabu search, the result shows that with the presented algorithm the optimal project can be obtained and yet with Tabu search only suboptimal project can be obtained.

KEYWORDS: Distribution network；Reliability；Genetic algorithm；Network reconstruction

摘　要：以配电网可靠性最高为目标函数和配电网的运行满足电力连续供应为约束条件，提出了基于排序选择、对违反约束个体进行直接比较的改进自适应遗传算法。这是一种对配电网的可靠性按照深度优先搜索最小路径进行计算的方法。通过IEEE典型算例RBTS Bus 4系统的验证，表明该算法是有效的。与禁忌搜索算法（TS）比较，该算法可获得最优方案，而禁忌搜索算法只能获得次优方案。
关键词：配电网；可靠性；遗传算法；网络重构
1 引言
以最经济的方式向用户连续提供高质量的电能是对电力系统运行的基本要求。“连续”就意味着供电可靠性很高。配电系统是整个电力系统的一部分，它连接着主系统与各用户。因而改善供电可靠性应将重点放在配电系统上。
网络重构是优化配电系统运行的重要手段。它是通过确定开关的断开、闭合状态来优化配电系统运行的。配电网络重构是混合整数非线性规划问题，也是一NP难的组合优化问题，穷举因面临组合爆炸问题而不可行。为此，人们在配电网络重构中采用了各种近似技术和启发式算法，以及随机优化方法，从而避免了进行穷举搜索[1~4]。
本文采用改进的遗传算法，以提高以配电系统可靠性为目标的配电网络重构，无需新增太多投资，只对系统开关设备的运行状态进行最优确定，就可使系统可靠性在现有设备条件下达到最优，从而带来较大的经济效益和社会效益。
本文对遗传算法（GA）的运算以及惩罚函数等进行了改进。运用排序选择（ranking selection）操作、自适应交叉与变异等[3]；在处理约束条件时，采用不同于普通罚函数法的直接比较（Direct Comparison，DC）方法。
2 网络重构的数学模型
以平均用电无效度（ASUI）最低为目标函数的网络重构数学模型为
（1）目标函数
　


基于改进遗传算法的配电网络重构 : 　
式中 Np为系统负荷点数；Ui为负荷点i的年停运时间；Ni为负荷点i的用户数；NT为系统总用户数；R为控制网络中所有开关状态的变量，只能取0或者1，Rj=1表示开关j闭合，Rj=0表示开关j断开。
由于控制变量Rj是只能取0或者1的开关变量，这就决定了网络重构问题是一整数组合优化问题。
（2）约束条件：①必须满足各节点的负荷需求，不能在网络中出现孤立节点而使该节点上的负荷失去电源；②重构后的配电网络必须是连通的；③重构后的网络拓扑必须是辐射形结构。
3 所采用的改进遗传算法
3.1 编码方案
在配电网络重构问题中，要处理的对象是联络开关和分段开关，由于他们只有断开、闭合两种状态，故对所有开关采用二进制编码。编码中的“1”表示某支路开关（即某染色体表示的）闭合，“0”表示某支路开关断开。这种编码方案简单，对于中、低压配电网络可充分发挥其原理清晰、操作简单、适于计算机应用的优点[5]。当联络开关为“1”时，会在网络中形成一环网。当需要打开环网中的一开关时，所需打开的开关由染色体中“0”的位置来决定，即根据染色体中与“0”位相对应的开关编号，寻找相应的分段开关，并断开此开关。
论文基于改进遗传算法的配电网络重构

3.2 最优保留的排序选择方法
令所有开关位均置“1”，将随机抽取的联络开关编号的个数位置“0”，生成初始种群。基于排序的选择操作，不同于传统的用序号充当个体适应度值的排序选择操作[6]，它先计算每个个体的目标函数，对所得的适应度进行由大到小排序（此处假定为最大化目标函数，若为最小化目标函数则由小到大排序），然后将前m个个体复制两份，淘汰掉后面m个个体，序号在中间的个体则复制一份。 这种方法能确保种群大小不变，且编程非常容易。大量仿真计算表明，此种改进不仅极其简单方便，而且同样有效。
3.3 适应度函数的确定
在GA中，用适应度函数来评价染色体的优劣，因而适应度函数是能反映实际问题的目标函数。在以供电可靠性最高为目标的配电网络重构问题中，目标函数是平均用电无效度（ASUI）最低，因此，本文所选的适应度函数F(x)为
　 F(x)=1.01fit-ASUI
式中 fit为初始网络目标函数值。
3.4 自适应的交叉和变异
齐次有限马尔柯夫链已严格证明了简单遗传算法（simple GA）不是全局收敛的[7]，而加入最优保留操作的遗传算法（optimum maintaining GA）是全局收敛的，自适应遗传算法（adaptive GA）也是全局收敛的。本文在选择操作中使用了最优保留操作，在交叉和变异中使用了自适应的遗传算法，既肯定了全局收敛性，又减少了迭代次数，因此收敛的速度大为提高。
　
式中 Pop为种群规模数；Pc1和Pm1分别为对应于群体中最小适应度值的个体交叉率和变异率；Pc2和Pm2分别为对应于群体中最大适应度值的个体交叉率和变异率；rank(V)为个体X在种群中所对应的序号值；为要交叉的两个个体中序号较小者。
根据实际程序运算经验及文献[8]，操作中宜取Pc1=0.9，Pc2=0.6，Pm1=0.1，Pm2=0.01。
运用自适应遗传算法的一个实际问题是最优个体易被破坏。而本文采取最优保留法来保留最优个体，从而较好地解决了此问题。
3.5 对违反约束条件个体的处理
用GA求解约束问题时，传统的方法是使用罚函数，即在适应度函数上再加上由罚因子构成的罚函数项。但这种方法生成的新目标函数的最优解依赖于罚因子的选择，而且无论罚因子过小或过大都会给求解最优解带来困难。本文采用了一种新的在GA中广泛使用的竞争选择方法[9]，它不需要罚因子而直接比较个体优劣。即对于两个给定的个体，当两个解个体都可行时，通过比较他们的适应度值来直接判断其优劣。当两个解个体中有一个可行一个不可行时，则无条件地认为可行解个体为优；当这两个解个体都不可行时，则根据他们所对应的作为度量违反约束程度的罚函数值来判断他们的优劣，违反约束越小的个体越好，无需选择罚因子。
4 配电网络可靠性的求取
配电网络具有闭环结构、开环运行的特点。在正常运行下，形成了图论中最重要的树形结构。对此本文采用深度优先搜索（depth first search）算法来搜索配电网中的最小路径。对于最小路径上的元件的处理原则是：如果系统无备用电源，则当最小路径上的任一个元件发生故障时，均会引起负荷点的停运，因此参与计算的是元件停运率和停运时间；如果系统有备用电源，且主馈线上装有分段装置，则由前段元件的故障引起的后段负荷点的停运时间为开关的倒闸操作时间，最小路径上的任一元件停运均会引起负荷点的停运，参与计算的是元件停运率和停运时间。对于非最小路径上的元件的处理原则是：当分支线装有熔断器时，分支线上的元件发生故障时不会影响其它支路；当主馈线上装有隔离开关或分段断路器时，后段元件的检修不会引起前段负荷点的停运；对于其它一些对负荷点可靠性指标有影响的元件，将其影响折算到相应的最小路径的节点上。


基于改进遗传算法的配电网络重构 : 　
辐射形系统是由一组串联元件组成，系统中任一负荷点的用户要求它和电源点之间的所有元件都运行，因此可靠性指标可按如下公式计算：


式中 S为系统中所有元件的集合；λS为系统的平均停运率；μS为系统的平均年停运时间；rs为系统的平均停运持续时间；λ＇i为元件i的故障停运率；λ〃i为元件i的检修停运率；r＇i为元件i的平均故障修复时间；r〃i为元件i的平均检修持续时间。
5 应用算例
为了验证本文方法的可行性，用本文提出的方法对IEEE典型算例RBTS Bus 4系统[10]进行以可靠性最高为目标函数的网络重构计算。RBTS Bus 4系统有38个负荷点，26个开关，其网络结构和开关编码如图1所示。
对该系统进行计算时，GA的有关参数取值为：Maxgen=100，Popsize=100，计算结果列于表1。表2列出了初始网络结构（方案1）、寻优过程中的一种网络结构（方案2）以及最终寻优所得的网络结构（方案3）的系统可靠性指标。由表2可见，最终结果的ASUI比初始状态时的降低了24%，其余可靠性指标也得到不同程度的改善。



6 禁忌算法与遗传算法的比较
现代优化算法中的禁忌搜索[11]（Tabu Search，TS）的技术性很强，在算法的构造和计算过程中会出现一些困难：①要求尽量少占用机器内存，这就要求禁忌长度、候选集合尽量小，但禁忌长度过短会造成搜索的循环，候选集合过小会造成过早地陷入局部最优。②为减少计算时间而希望解分量变化和目标值变化的禁忌范围要大，但禁忌范围太大又可能导致陷入局部最优点。③Tabu算法是一种从单点出发寻优的方法，它容易陷入局部最优解。而遗传算法是从点的群体开始搜索的，且具有隐含的并行性，因此在搜索过程中不易陷入局部最优，即使在所定义的适应度函数不连续、非规则或有噪声的情况下，找到整体最优解的概率也很大。因此本文采用遗传算法作为网络重构的搜索方法。
7 结论
本文以配电网可靠性最高为目标函数，以配电网的运行满足电力连续供应为约束条件，提出 的改进自适应遗传算法经典型算例的验证，表明是有效的。该算法的最终结果的ASUI比初始状态下的降低了24%，其余系统可靠性指标也有所改善。当考虑的因素增多时，该系统进行重构仍能得到上述最佳方案。采用TS方法对同样问题进行计算的结果表明[12]，它只能找到如表2所列的次优方案1，找不到最优方案3。
参考文献
[1] 王守相，王成山（Wang Shouxiang，Wang Chengshan）．配电网络重构的优化可信度度量的区间方法（Distribution network reconfiguration based on interval algorithm to maximize confidence of energy loss reduction）[J]．电力系统自动化（Automation of Electric Power Systems），2001，25(23)：27-31．
[2] Baran M E，Wu F F．Network reconfiguration in distribution systems for loss reduction and load balancing[J]．IEEE Trans on Power Delivery，1989，4(2)：1401-1407．
[3] 邓佑满，张伯明（DengYouman，Zhang Boming）．配电网络重构和电容器投切的综合优化算法（A comprehensive optimization algorithm for distribution network reconfiguration and capacitor switching）[J]．电力系统自动化（Automation of Electric Power Systems），1996，20(5)：5-9．


基于改进遗传算法的配电网络重构 : 　
[4] 王守相，王成山（Wang Shouxiang，Wang Chengshan）．一种隐含并行的大规模三相不平衡配电网络重构新算法（A novel network reconfiguration algorithm implicitly including parallel searching for large-scale unbalanced distribution systems）[J]．电力系统自动化（Automation of Electric Power Systems），2000，19(24)：34-38．
[5] [日]玄光男，陈润伟. 遗传算法与工程设计[M]．北京：科学出版社，2000．
[6] 张彤，张华，王子才（Zhang Tong，Zhang Hua，Wang Zicai）．浮点数编码的遗传算法及其应用（Float encoding genetic algorithm and its application）[J]． 哈尔滨工业大学学报（Journal of Harbin Institute of Technology），2000，4(32)：59-61．
[7] Goldberg D E．Segrest P．Finite Markov chain analysis of genetic algorithm[A]．Proc of the Second Int Conf on Genetic Algorithms[C]，1987：1-8．
[8] 王小平，曹立明．遗传算法——理论、应用与软件实现[M]．西安：西安交通大学出版社，2002．
[9] Eeb K，Agrawal S．A niched-penalty approach for constrain handing in genetic algorithms[A]. Proceedings of the ICANNGA-99[C]，Portoroz，Slovenia，1999：234-239．
[10] Allan R N，Billinton R．A reliability test system for educational purposes-basic distribution system data and results[J]．IEEE Trans on Power Systems，1991，6(2)：813-820．
[11] 邢文训，谢金星．现代优化计算方法[M]．北京：清华大学出版社，1999．
[12] 吴宏晓．配电系统可靠性与配电网重构[D]．西安：西安交通大学，2000．电网技术


基于改进遗传算法的配电网络重构 :