基于最短路算法和遗传算法的配电网络重构

由机电之家行业门户网运行

	\| 首页 \| 业内资讯 \| 设备管理 \| 设备维修 \| 监测诊断 \| 润滑密封 \| 安全生产 \| 专业术语 \| 变频技术 \|
	\| 论坛 \| 学术论文 \| 管理天地 \| 专业培训 \| 会展信息 \| 现代理论 \| 采购中心 \| 资料下载 \| PLC技术 \|

文章下载

最新公告：

没有公告

您现在的位置：设备维修与管理 >> 设备管理 >> 基础管理 >> 维修管理 >> 资讯正文

赞助商

客户服务

如果您有设备方面好的文章或见解,您可以送到我们的投稿信箱
客服电话：0571-87774297
信　箱：88ctv@163.com
我们保证在48小时内回复

设

备

管

理

网

基于最短路算法和遗传算法的配电网络重构

作者：佚名文章来源：不详点击数：更新时间：2008-9-24 9:46:59

                                                          余贻鑫，段刚
                                          天津大学电力系，天津市300072
1　引言
　　网络重构的主要目的就是通过改变线路开关的状态来变换网络结构，在实现电力供需平衡的前提下，减少网络的运行损耗，并满足容量和电压等约束。配电网络通常呈放射状运行，因此其重构问题实际上是在弧的权值随流量非线性变化的网络上寻找最小费用树的问题。这一大规模、混和整型、非线性组合优化问题，属于NP难问题。见诸于文献的求解方法有以下几种：①启发式方法：如支路交换法［1］和破环法［2］，它们缺乏数学意义上的全局最优性；②传统的数学优化方法：如分支定界法，其存在严重的“维数灾”问题；③文［3］采用了神经网络法，其只能求解小规模网络，而且由于训练过程中采用支路交换法的优化结果，其最优性没有保证；④文［4］采用的模拟退火法，其温度控制难以掌握，寻优速度很慢；⑤文［5］采用遗传算法及文［6］采用的进化规划。这些进化方法均基于开关开合或线路被选择与否进行编码，在遗传操作中会产生大量不可行解，并且由于仅依靠遗传操作进行寻优，没有利用问题的特有性质，所以收敛速度慢，局部精确寻优能力差。
　　本文方法的最大特点是由以往算法的通过组合支路（或开关）寻优转为通过组合负荷寻优。该算法把约束尽力体现在寻找解的过程中，而不仅仅是对已找到的解进行事后评价。本文方法的优势在于它适宜于求解结构非常复杂的多网孔网络，而对于这种网络，现有基于支路（或开关）组合寻优的方法候选操作太多，计算量很大。
2　数学模型
    网损最小配电网络重构的目标函数可表示成

    式中　Nf为线路和变电站总数；rj、Pj、Qj、Vj分别为元件电阻、有功、无功以及功率注入节点的复电压。
　　配电网络重构应满足以下约束条件：
    （1）流量守恒约束

    式中　Dk为节点k的功率需求；Nn为节点总数；ETk（EFk）为潮流流向（出）节点k的弧的起点（终点）集合。
    （2）容量约束
　　Il≤IUl　　l＝1，…，Nf（3）
    式中　IUl为元件l的最大允许电流；Il为通过元件l的电流。
    （3）电压约束　
　　VLk≤Vk≤VUk　　k＝1，…，Nn（4）
    式中　VUk、VLk分别为节点k的电压上、下界。
    （4）放射状运行约束
    潮流流向节点k的弧数，即入弧数Nin－k满足　
　　Nin－k∈｛0，1｝k＝1，2，…，Nn（5）

3　基于最短路法的局部优化算法
3．1　全体负荷供电路径的优化
　　首先构造一便于利用遗传算法构成全局优化算法时调用的局部寻优重构算法。在算法中按某一负荷顺序SQ逐步形成局优树状网络，每一步利用最短路径法只寻找1个负荷点的供电路径。每找到1个负荷点的供电路径，就立即修改“被寻路网络”，使得将要找到的下1个负荷点的供电路径不会与已存在的供电线路形成环。
    假设以如下顺序SQ满足所有Nload个负荷点，
　　SQ＝｛L1，L2，…，Lm－1，Lm，…，LNload｝（6）
    式中　Lm表示第m个负荷点，其功率数值为Sm＝Pm＋jQm。
　　在寻路前先将原无向元件网络G转化成有向网络G0：变电站弧变成由（公共）虚拟源点指向该站的有向弧；负荷弧转化成由负荷点指向（公共）虚拟汇点的有向弧；馈电线弧转化成2条方向相反的有向弧Aij和Aji，其功率流必须与弧的方向一致，分别表示为：Sij和Sji。
　　先为L1寻找供电路径，继而为L2寻找供电路径，依次类推。每找到1个负荷的供电路径，就修正有向图G0，包括弧流量修正和节点入弧数修正。例如，第m－1个负荷Lm－1的供电路径Rm－1被找到，若弧Aij∈Rm－1，则　
Sij－m＝Sij－m－1＋Sm－1（7）

    式中　下标“－m”、“－m－1”分别表示在寻找负荷Lm、Lm－1供电路径之前相应变量的值。同时令　　
Nin－j－m＝1（8）

    表示节点j已经有了入弧。
　　为了形成树状网并加快寻路速度，寻找某一负荷点Lm的供电路径时，并非在整个有向图G0上进行，而是在一被称之为“Lm的寻路网络”Gm上进行。Gm在G0（前m－1个负荷的功率流已反映到G0上）的基础上，经过以下步骤形成：
　　（1）若某节点k当前的入弧数Nin－k－m＝1，则舍弃其余指向该节点的有向弧（其潮流必为0）。
　　（2）若此时正向弧Aij的功率流Sij－m≠0，则对应的反向弧Aji被舍弃，反之亦然。
    （3）弧Aij的剩余电流容量Ir－ij－m定义为　　
Ir－ij－m＝IU－ij－Iij－m（9）

     式中　IU－ij为Aij的电流容量限；Iij－m为Aij当前的电流流量。
     若Ir－ij－m＜Im，则舍弃弧Aij。
    （4）除Lm的负荷弧以外，其余负荷弧均舍弃。
    （5）若某节点i的电压Vi－m－1满足
0≤Vi－m－1－（1－ε）Ve＜e（10）
　
    式中　Ve为额定电压；ε为允许电压降；e为很小的电压值。
    则该节点电压几乎越限，与其相连接的0流量弧均舍弃。
    （6）舍弃距离Lm很远的弧。
    （7）舍弃因其它原因不可能为Lm供电的弧。
　　因为网络重构的目标函数是网损最小，所以有向图Gm中弧的权重本应是流过负荷Lm的功率所引起的损耗增量。但是通过图1所示的简单例子我们将看到在弧权重中考虑容量约束的必要性：若我们不给具有较大容量的弧较大的被选中机会，则无论以何种负荷顺序都不能找到该问题的解，而实际上却存在一个解：L1的供电路径为A2－A3，而L2的供电路径是A2－A4。因此，容量约束不仅意味着弧流量不能超过某一特定值，而且意味着具有较大容量裕量的弧应具有较大的机会被先选中。本文提出的方法将容量裕量加以折算并和损耗共同构成弧权重来利用这一特性。折算系数kc随着弧的容量裕量的变化而动态变化，它对折算的有效性有较大影响。可采用一定的优化方法对这一参数进行优化。容量折算的强度在数值上通常不是很大，本文采用下面的简单方法选取kc。kc分别取0～kc－max间的整数进行优化，选其中最好的优化结果。kc取0时，表示寻路时不考虑容量特性；kc取kc－max时，表示考虑容量特性的强度最大。因此kc是反映容量折算强度的量。kc和kc－max的选取将在第3．2节中论述。

　　综上所述，我们可以得到全体负荷供电路径优化的算法，其伪代码如下：
    （1）将无向网络G转换成有向网络G0
　　（2）调用全体负荷供电路径优化子程序AllLoadRoute（G0，SQ）
    （3）将寻优G0的最优结果反映到G上
　　全体负荷供电路径优化子程序AllLoadRoute（参数：G0，SQ）：
    （1）循环1：For kc＝0 to kc＿max；
    循环2：For m＝1 to Nl
     ①成Lm的寻路网络Gm
    ②单一负荷供电路径优化子程序
    OneLoadRoute（Gm，SQ，kc，m）［见第3．2节］
    ③若寻路成功，则由寻路结果修正G0；
    否则中止循环2。
    循环2：End
    循环1：End
　　（2）选择最优的kc所对应的G0的结果
3．2　单一负荷供电路径的优化
　　在此给出某一负荷寻找损耗最小的供电路径算法，即子程序OneLoadRoute的实现。假设该负荷是负荷序列SQ中第m个负荷Lm，前m－1个负荷的供电路径已经被确定。寻找Lm的供电路径时不能变动这些供电路径，而且不能与这些负荷的供电路径形成环。这2个要求实际上已经在第3．1节中形成Lm的寻路网络Gm时做到了。这里所要考虑的是：如何在考虑容量约束以及电压约束的条件下，在Gm上找出Lm的损耗最小供电路径，其中确定每条弧的权值是问题的关键。
    步骤1：计算不计容量约束和电压约束时弧的权值
　　计算Gm中每条弧的权值时，设每条弧的功率流量均增加Sm，Sm＝Pm＋jQm，此时弧Aij功率损耗的增量为
ΔPloss－ij－m＝I2t－ij－mrij－I2ij－mrij＝
rij（2 Pij－mPm＋2 Qij－mQm＋P2m＋Q2m）／V2e（11）

式中Iij－m和It－ij－m分别为增加Sm前、后弧Aij的电流；采用Ve是一种近似处理。
　　在不计容量约束和电压约束的情况下，弧Aij的权值为
　　
wP－ij－m＝ΔPloss－ij－m（12）

    此时利用最短路算法找到的从虚拟源点到虚拟汇点的最短路就是为负荷Lm供电的损耗最小的路径。
    步骤2：计算考虑容量约束时弧的权值
　　第3．1节给出了弧Aij的剩余电流容量Ir－ij－m的定义和使其在Gm中至少能满足对Lm供电的限定。这里将进一步根据Gm中各弧剩余电流容量能继续满足的后续负荷数，对这些弧确定剩余容量等级cscale－ij－m。

    式中em反映剩余容量对弧权重的影响强度，应满足：①当仅剩1个负荷待满足时，即m＝Nload时，应有eNload＝0，也就是说，在不需要为后续负荷预留容量空间的情况下，不应进行弧权重的容量折算；②在m＝1时，有最多的后续负荷待满足，因此容量　　折算要最强烈，即，e1取em的最大值E；③随着剩余负荷的减少，em也应减小，直到为0。
    根据以上要求，采用式（18）或（19）求em

    式中　E＝h×kc，kc顺次取为［0，kc－max］间的整数；h为步长。
　　因为E是指数，系统负荷数通常也较大，由式（17）知E不宜太大，否则各条弧的费用都会极小。通常E取2是足够大的。为了保证寻优的精度，通常h可取得较小，如0．05，相应地kc－max可取为40。
    步骤3：调用最短路算法程序
　　调用最短路算法程序在有向图Gm上寻找从虚拟源点到虚拟汇点（相当于负荷点Lm）的权值最小的路径。例如，可以使用Dijkstra算法。若找不到Lm的供电路径Rm，则中止这次OneLoadRoute子程序的调用。若找到负荷Lm的供电路径Rm，则对Gm的
弧流量进行修正，得出临时弧流量

　　步骤4：电压近似计算及电压约束校验
　　由Gm上流量不为0的弧以及相应的m个负荷，可构成一假想树状运行网络。只要检验最短路径Rm所在树上各负荷点电压，即可确定整个网络是否有电压越限的节点，因为其它负荷点电压没有变化。为了降低计算量，可采用下面的近似潮流算法。
    源点的电压定为V0，则各负荷点电压近似为

    式中　Rl是第l个负荷的供电路径；rij和xij分别为弧Aij的电阻和电抗；Pt－ij－m＋1和Qt－ij－m＋1为当前通过弧Aij的临时有功和无功；用额定电压Ve近似求得弧Aij的复电流。用ε表示允许电压波动百分率，若对所有被检验的负荷点电压均有

    Sij－m＋1，然后中止这次OneLoadRoute子程序的调用。反之，若存在不符合要求的节点电压，则首先将临时弧流量St－ij－m＋1恢复为原实际弧流量Sij－m，然后按式（23）对当前找到的最短供电路径Rm上弧的权值进行一定程度的惩罚，使得重新为该负荷寻路时，尽可能避开这条路径上的线路，并返回步骤3。由于只是改变了Gm中弧的权重，而弧容量与网络结构均未变，因此必定还能找到供电路径。若连续NV－fail －max次失败，则中止这次OneLoadRoute子程序的调用。

    式中k为不满足电压约束的次数；β为大于1的罚因子。最大失败次数NV－fail－max可取为10。

4　全局优化的最短路径遗传算法
　　将基于最短路径法的网络重构局部优化算法与遗传算法结合就可得到重构问题的全局优化算法。
    步骤1：种群初始化
　　首先，将负荷由大至小排序并编号。然后，随机排列这些编号构成染色体，以编号作为基因，染色体长度为负荷数目。随机产生Nchrom个这样的染色体构成初始种群。每个染色体作为1个负荷序列，将被应用于局部优化算法AllLoadRoute程序中。负荷由大至小这一排列被保证包含于第1代种群中，因为这一排列最可能包含较多的优良基因组合。
    步骤2：适应度评价
　　调用基于最短路法的网络重构局部优化算法程序，求得各染色体对应的网络结构及相应网损。然后将原始适应度（此处为网损，应极小化）转换成遗传算法适应度（需极大化）。对于重构问题，在相同网损情况下，使kc大者具有稍大的适应度，因为其较大可能具有大的容量裕量。评价结果不仅作为下面选择、复制等遗传操作的依据，而且用于判断遗传算法是否应该中止。
    步骤3：选择和复制
    采用赌轮法和最优保留机制［7］。
    步骤4：交叉
　　在种群个体比较丰富的时候采用部分匹配交叉法（PMX）［7］，而当种群个体单调时采用我们提出的部分匹配逆转交叉（PMRX）法。对参与交叉的个体先依据均匀随机分布产生2个位串交叉点，定义这2点间的区域为匹配区域，使用交换操作交换2个父串的匹配区域。例如，2父串及匹配区域为
A＝984｜567｜1320　B＝871｜230｜9546
    首先交换A和B的2个匹配区域，PMX法中采用相同位置基因对应互换的方法得到
PMX：A′＝984｜230｜1320　B′＝871｜567｜9546
    PMRX法中先将1个父串的匹配区域的基因串逆转排列，然后再采用同位置基因互换的方法得到
PMRX：A′＝984｜230｜1320 B′＝871｜765｜9546
    对于A′、B′2子串中匹配区域以外出现的重复负荷点，依据匹配区域内的基因映射关系，逐一进行交换。对于PMX法有
PMX：A″＝984｜230｜1657　B″＝801｜567｜9243
    对于PMRX法有
PMRX：A″＝984｜230｜1675 B″＝821｜765｜9043
    PMRX法使得完全相同的2个父串进行交叉操作也能产生新的基因组合，在进化后期种群个体单调时，算法仍能跳出局优解，开辟新的搜索空间。
    步骤5：变异
　　变异操作只发生在随机选择的少量个体上。我们在对换变异［7］（即，随机选择染色体中的2个基因，然后交换其位置）的基础上提出多次对换变异，这是因为负荷点通常较多，1次对换产生的变异可能还太小，为了加大在原基因排列基础上产生新的基因组合的力度，采用多次对换变异：首先，随机产生对换次数Nx（小于Nload／2），然后执行对换变异。
　　返回步骤2。

5　算例分析
　　目前文献中的算例普遍存在网络结构过于简单的现象，并且不提及算法的时间特性。而本文方法却能够在可行的时间里得到中、大规模复杂配电系统的重构全局优化结果。下面给出1个具有较大规模的复杂系统的计算实例。

　　图2所示是1个负荷发生了较大变化后的系统，共有3个变电站，353段线路，266个负荷，358个节点，网孔数为46个，总有功负荷为42 592．4k W，总无功负荷为26 331．7 kvar，系统额定电压为10kV，图中标出了各负荷点的标称容量，kVA。原来的运行方式中已经出现了容量和电压越限。为了得到新的合理运行方式，需要进行网络重构。采用支路交换法［1］以原网络结构为初始解进行重构优化，无法得到可行解。而采用最短路径———遗传算法却能在相对较短的时间里得到上述系统的重构优化结果。该结果如图2中实线所示，虚线为应开断线路。有功损耗为363．6k W，系统总出力42954．4k W，26475．1kvar。最低电压为10．3kV（图2中点y）。总计算时间为6 h 38 min，运行环境：MicrosoftJava虚拟机（Jview 5．00．2752；Pentium 90；16 MRAM），若采用更快的Java虚拟机或C＋＋语言程序则计算时间会大大缩短。Dijkstra最短路径算法的时间复杂性为O（n2），相应本文算法的计算复杂性为O（n3），n为节点数。可以采用基于堆数据结构和知识的最短路径算法，来进一步提高算法求解大规模问题的能力。

6　结论
　　本文提出了通过组合负荷实现寻优的重构方法，这一方法具有以下特点：
　　（1）利用最短路径法为每个负荷分别寻找供电路径，这一方面使得形成树状网络变得轻而易举，另一方面由于最短路径法对寻路网络无特殊要求，网络环孔多也不会显著增加其复杂性，因此可很容易地解决复杂结构网络的重构寻优问题。
　　（2）利用遗传算法选择优化的负荷排列顺序，在局优解中进一步寻求全局优化解，从而可实现重构问题的高效全局优化。
　　（3）通过将容量约束和电压约束转换成弧的权值，在网络形成的过程中就考虑这些约束，而不是象一般方法那样在约束被违背时才修正网络，从而进一步保证了本算法能高效地找到全局最优解。

参考文献：
［1］Mesut E．Baran，Felix F．Wu．Network Reconfiguration inDistribution Systems for Loss Reduction&n

[1] [2] 下一页

PLC，机器人编程，变频器，挖机，电气，电子--行业培训比蓝X强...

资讯录入：admin 责任编辑：admin

上一篇资讯：昌房500 kV紧凑型线路大负荷试验计算分析

下一篇资讯：面向电力客户的新型配电系统的构想(Ⅰ)——基本概念与电力需求侧网络结构

【字体：小大】【发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口】

　网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！）