基于贪婪算法的配网多阶段快速重构新方法

赵胜举，么莉，林济铿，张旭

(1. 天津大学 电气自动化与信息工程学院，天津 300072；2. 同济大学 电子与信息工程学院，上海 201804)

0 引言

配网重构是配电自动化实现优化调度及运行的重要职能之一，快速有效的网络重构求解方法在保证配网运行安全的前提下，可明显提升运行的经济性[1]。

对于静态重构的求解策略，求解策略大致可分为3类：（1）确定性方法重构。文献[2-3]采用分支定界算法确定配电网开关状态实现重构。文献[4]将非线性整数规划的配网重构模型转换为可用商用优化工具求解的混合整数二次锥优化模型实现重构。文献[5]构建了有功网损最小的运行方式调整和最优负荷恢复的负荷调整两阶段配网重构模型，采用分支定界算法进行求解。对于中小规模的系统，该类方法可求得其局部最优解，但对于大规模系统而言，求解速度较慢并且收敛性没有理论上的保证。（2）进化优化算法重构。文献[6]建立了基于遗传算法的配网重构优化模型。文献[7]提出了考虑合环约束的网络重构优化算法并采用贪婪自适应搜索算法进行求解。文献[8]提出一种综合优化网络损耗、开关动作次数、电压平稳性的多目标模型，然后利用改进后的粒子群算法对其进行求解。文献[9]将Mayeda生成树算法应用到网络重构优化问题中，然后采用粒子群算法进行求解。文献[10]构建了基于改进布谷鸟算法的配网重构模型及求解算法。文献[11]提出了基于动态小生境差分算法的配网重构模型及求解算法。文献[12]提出基于十进制编码策略的遗传算法的配网重构模型及求解策略，因求解过程中避免了无效解过多而加快了计算速度。文献[13]提出了基于改进克隆算法的配网重构模型及求解算法。文献[14]提出了简化网络技术与遗传算法相结合的配网重构模型及求解算法。该类模型的构建求解过程相对简单，但需要进一步克服计算效率问题。（3）启发式算法。文献[15]建立了考虑网络损耗和节点负荷稳定性的优化数学模型并采用改进支路交换法进行求解。文献[16]提出基于改进最优流的配网重构求解算法。文献[17]提出把回路中网络损耗增量最小确定为最优开断支路的启发式规则。文献[18]提出基于最优环路电流快速确定开断支路的规则。这些方法的突出优点是计算速度快，但往往只能求得局部最优解。

对于上述3类静态重构算法，如何在大幅提升其计算速度的同时，获得最优解或近似最优解是仍需深入探索的共同课题。

对于动态重构，其求解策略大都通过一定方式转化为若干个相互关联的静态重构来求解[19-22]。文献[19]建立以网络损耗成本与支路开断动作成本之和为目标函数的配网重构优化模型，然后利用信息熵把整个重构时段划分为若干阶段并采用杂草混合算法进行求解。文献[20]构建网损和电压偏移量的归一化综合评估指标把整个重构时段划分为若干个阶段，对于每一阶段分别利用遗传算法对配电网进行分段重构。文献[21]基于文献[20]所提出的综合评估指标，将模拟退火算法的Mertropolis准则引入粒子群算法实现对各阶段的快速重构。文献[22]把多阶段负荷需求通过聚类而得到若干聚类中心，进而利用进化优化算法对各中心依次进行网络重构。上述算法基本上均利用进化优化算法进行动态重构，虽有个别算法试图进行重构时段的最优划分以期减少计算量，但合理性及在大系统中实际应用的可行性还有待验证。上述算法理论上能够找到全局最优解，但共同的缺点是当系统的规模较大时计算时间相对于静态重构而言还要长得多，实际工程应用因时间过长而往往不可行。

基于如上所述，当可操作的开关数量较多时，遇到的组合爆炸将导致其计算失败，使得目前动态重构算法在大规模系统上应用有限，面对如上问题，本文提出一种基于贪婪算法的动态重构实用新算法，该方法有望应用于实际大系统，实现有效的快速动态重构。本文首先提出最优流算法与基于Mayeda算法的进化算法相结合的确定性的快速静态重构新算法；然后把该快速静态重构新算法应用于多阶段动态重构，提出一种基于贪婪算法的多阶段快速动态重构新算法，它基于开关动作次数最多的两个相继阶段及给定的寻优尺度参数M，对相应范围内的阶段进行合并，并利用所提出的静态重构新算法进行重构优化，得到当前所有阶段的最优目标函数值；如此反复迭代，直到目标函数值不再减少且当前解为可行解时，即得到近似最优解。算例证明了所提方法的有效性。

1 配网重构的数学模型

若T为日负荷曲线的时段数（如T=24），在此连续的T个时间段内总的有功功率损耗成本和开关动作成本和最小的目标函数为

本文首先提出一个单阶段快速静态重构方法，进而基于此方法，提出快速的多阶段动态重构算法。需要指出的是，目前虽然有很多分布式发电并网，但是因容量很小，本文上述模型实际上对其进行近似处理，忽略出力的不确定性，把相应的负荷减去出力的期望值，得到新的负荷。考虑分布式发电出力的不确定性的最优动态重构模型及算法，将在另文发表。

2 单阶段静态重构算法

文献[23]为提升编码效率提出了一种基于矩阵环和操作的Mayeda生成树实用方法。文献[9]将该方法和粒子群算法相结合，即采用粒子群算法随机选择来代替文献[23]中穷举方法来确认候选支路集中的待交换支路，进而获得更快的计算速度，另外该方法因利用了完整树的构建方法，其所生成的新树满足放射性要求而无须进行非常烦琐的放射性约束检测，计算速度相对于其他进化类算法而言具有明显优势，算例也充分证明了其先进性。但因仍属于随机类算法，理论上必须具有足够长的计算时间，才能得到全局最优解，尤其当系统规模较大时，计算时间仍然较长。

本文提出把确定性的最优流算法与基于Mayeda生成树的重构算法相结合，获得快速的单阶段配网重构新算法，简称为静态重构算法。该算法的基本思想是：在Mayeda生成树产生过程中，采用最优流方法生成交换支路取代随机方式生成交换支路，具体是把由环和计算获得的候选支路集，逐一开断候选支路集中的支路，其中引起功率损耗增量最小的支路即作为交换支路，与待交换支路（实际是当前树的一个连枝）进行替换，从而完成一次树枝与连枝的交换；每一连枝的交换支路均按上述方式形成，直至生成一棵新树。如此反复循环迭代，直至收敛。上述做法因采用局部的最优支路代替随机方式生成的交换支路，最后所生成的解只能是近似的最优解，或次优解，相应的目标函数与全局最优解有一定的差距，但计算速度得到了明显的提升，实际上是实现了二者方法的优势互补。

静态重构算法的基本过程如下。

（6）利用文献[23]中的环和操作获得网络矩阵Mk；并将和Mk分别定义为参考树和网络矩阵M0，，转步骤（2）。

3 基于贪婪算法的多阶段重构算法

3.1 多阶段重构算法基本思想

基于第2节所提出的快速单阶段重构算法，本文进一步基于贪婪算法提出对于由式（1） ～（6）组成的多阶段重构问题的快速求解新算法，其可以通过2个阶段的优化获得：（1）0 ～T中的任意连续时段的合并，获得相应的时段合并方案，当T比较大时，时段合并方案的数目非常庞大；（2）基于阶段（1）所确定的时段合并方案，采用进化优化策略获得所有合并时段的相应开关动作策略，使得在满足约束的条件下目标函数最小；如此反复迭代计算，直至遍历所有时段合并方案，在所有可行方案中目标函数最小的时段合并及开关动作可行方案，即为最后的最优解。若T比较大时，其阶段（1）的时段合并方案的数目就非常大，而每一时段合并方案均需要计算其最优开关动作策略，从而总体计算时间会非常的长。基于单纯的进化优化算法的动态重构，其计算复杂度与上述全局组合优化算法是等价的。

上述算法用于大系统时可能遇到计算时间过长问题，而限制了其应用。为了克服该问题，本文基于贪婪算法提出一种多阶段重构问题的快速求解新算法。其基本思想如下。

（1）不划分阶段（1）优化及阶段（2）优化，以最小时段作为初始的阶段划分，对于初始阶段（就是最小的时段）分别按单阶段静态优化方法确定每一阶段的最佳开关动作方案及网损值。

（2）对当前状态下的所有相继的两个阶段的开关动作次数进行排序，然后进行如下操作。

①若有解，则获得阶段合并之后的新阶段解；

②若无可行解，放弃相应阶段合并，选择当前状态下的所有相继2个阶段的开关动作次数与当前的一样或次于当前的2个阶段，按上述方法所确定的相应的阶段范围进行合并，并进行阶段合并之后的静态重构计算，并重复上述过程，直到找到合并之后具有可行解的相继阶段，并进行阶段合并，而获得其阶段合并之后的解，转步骤③；若所有阶段均合并之后，仍无法获得可行解，意味着目前的负荷状态无解，算法结束；

③获得当前状态下的所有阶段的总目标函数，若新的目标函数小于上一次阶段合并的目标函数，或不是可行解，回到步骤②；若新的目标函数大于上一次阶段合并的目标函数且当前解是可行解，已得到了最优解，算法结束。

3.2 多阶段重构算法步骤

（4）获得当前状态下的所有阶段的总目标函数值，判断是否满足该值小于上一次阶段合并的总目标函数值，若满足或不满足但当前解不是可行解，转步骤（2）；否则，已获得最优解，算法结束。

上述算法的流程如图1所示。

图1 动态重构算法流程Fig. 1 Flow chart for dynamic reconfiguration

4 算例分析

试验电脑配置为：Windows10操作系统；Intel（R）Core（TM）i5-3230M CPU2.60 GHz；4 GB内存；编程实现语言为 Visual C++6.0。其中、取为0.5元/（kW·h）、5元/次。

4.1 静态重构结果分析

本文分别采用最优流算法（下称文献[24]方法）、静态重构算法（下称本文方法）、基于Mayeda生成树的粒子群算法（下称文献[9]方法），对表1算例系统进行静态网络重构，以验证本文所提出的静态重构新算法的在计算效率和精度方面的优势。表2给出各系统在不同算法下的性能对比。

表1 算例系统参数Table 1 The system parameters

表2 3种算法在不同节点系统下的性能对比Table 2 Performance comparison of three algorithms under different test systems

由表2可见，文献[24]方法计算速度最快，但平均网损值明显高于其他两种方法，因此竞争性实际上最弱；本文方法的网络损耗非常接近于文献[9]方法，而计算时间比文献[9]方法少将近两个数量级。不难看出，本文所提出的静态重构算法相对于其他两个算法，具有明显的综合性能优势。

4.2 动态重构结果分析

采用基于贪婪算法与本文所提出的静态重构快速算法相结合的动态重构快速求解方法在不同的尺度参数下分别对系统1（IEEE 69节点系统）、系统2（IEEE 84节点系统）、系统3（IEEE 136节点系统）与系统4（实际配网系统（416节点））4个算例进行动态网络重构计算，节点负荷峰值为文献数据的120%，由第3节介绍方法可知，在M=22时求得动态重构的全局优化解（下称全局优化法），将不同寻优尺度参数下的性能指标值（计算时间、目标函数）分别与获得全局优化解时的相应指标值相比，获得4种算例下的性能对比如图2 ～5所示，各图中的曲线是本文算法结果/全局算法结果。

图2 系统1的性能对比Fig. 2 Performance comparison of system 1

图3 系统2的性能对比Fig. 3 Performance comparison of system 2

图4 系统3的性能对比Fig. 4 Performance comparison of system 3

由图2 ～5可看出本文所提方法的目标函数随着寻优尺度参数M的增大越来越接近于全局优化法。系统1、系统2、系统3等3个算例系统在M=3时，目标函数值之比分别为 1.0639、1.0678和1.0761，系统4在M=4时目标函数值之比为1.0908，意味着此时的本文算法的目标函数已经非常接近于全局优化算法的计算结果，而此时4 个系统的相应的计算时间之比仅为 0.0843、0.0887，0.0787与 0.0629，即本文算法的计算速度比全局优化算法快近两个数量级，在之后随着M上升，本文算法的目标函数值继续减小，到M=22时本文算法等效于全局优化算法。上述算例表明，在M较小情况下，比如等于3或4，本文算法最优解的目标函数值已非常接近于最优解，但计算速度明显优于全局优化算法。

表3给出了本文方法和全局优化法分别对系统1、系统2、系统等3个算例系统在寻优尺度参数M=3时与系统4在M=4时重构优化后的开关动作次数。可以看出，各系统的开关动作总次数相较于全局优化法都得到明显下降，其中系统4开关动作次数下降最为明显，在M=4时比全局优化法减少29次，且计算速度在M=3时相对于全局优化法提升将近14倍，而此时动态重构成本仅是全局优化法1.09倍。同时考虑到M取值的灵活性，结合图5当M=5时计算速度、重构成本分别为全局优化法的7.24倍、1.001倍。实现保证重构质量下计算效率显著地提升。因此，该计算结果充分地证明了本文方法的有效性及先进性。

图5 系统4的性能对比Fig. 5 Performance comparison of system 4

表3 开关动作次数比较Table 3 Comparison of switching action times

5 结论

本文首先提出一种基于最优流法与Mayeda生成树法相结合的静态重构算法，既克服了文献[9]所提出的随机进化优化方法速度慢的缺点，又克服了穷举法生成过多劣树的缺点，达到了快速性与解空间完备性地良好结合，实现了二者的优势互补，而明显提升了计算效果。进而提出一种基于贪婪算法的配网动态重构新方法。方法以静态重构为基础，基于开关动作次数最多的两个相继阶段及给定的寻优尺度参数M，对相应范围内的阶段进行各种可能的合并，并利用所提静态重构算法进行重构，得到当前所有阶段下最优目标函数值；如此反复迭代，直到目标函数值不再减少且当前解为可行解时，即求得近似最优解。算例表明，只要选择较小的M，所提出的方法在解非常接近于全局最优解的前提下，实现了计算速度的接近两个数量级的提高，提升了多阶段重构的计算效率。