【精彩论文】基于贪婪算法的配网多阶段快速重构新方法

‍

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

赵胜举¹, 么莉¹, 林济铿², 张旭¹

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

摘要：针对多阶段动态重构计算速度慢的问题，提出一种动态重构新方法。该方法基于给定的寻优尺度参数M，对以开关动作次数最多的两个相继阶段为中心的2M+2个阶段进行各种可能合并，分别对各个合并后的新阶段进行静态重构，然后选择目标函数值最小的合并方案为当前最优合并方案；如此反复迭代，直到目标函数值不再减少且当前解为可行解时，即得到近似最优解。方法在获得与全局最优解近似解的前提下，其计算速度都比全局最优解快近2个数量级。算例表明该方法因其求解的高效性而具有较好的工程应用前景。

引文信息

赵胜举, 么莉, 林济铿, 等. 基于贪婪算法的配网多阶段快速重构新方法[J]. 中国电力, 2022, 55(6): 33-41.

ZHAO Shengju, YAO Li, LIN Jikeng, et al. Fast multi-stage reconfiguration method for distribution system based on greedy algorithm[J]. Electric Power, 2022, 55(6): 33-41.

引言

配网重构是配电自动化实现优化调度及运行的重要职能之一，快速有效的网络重构求解方法在保证配网运行安全的前提下，可明显提升运行的经济性^[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个时间段内总的有功功率损耗成本和开关动作成本和最小的目标函数为

式中：F为时段T系统总目标函数值；N_b为系统支路总数；R_i为支路 i 的电阻；I_i,t 为时段 t 支路 i 的电流有效值；ΔZ_t,i 为时段 t 支路 i 的开关相对上一时段开关的动作次数，其表达式为 ΔZ_t,i=|Z_t,i−Z_t−1,i| ，其中 Z_t,i 为时段 t 支路 i 的开关状态；α_c、 β_c 分别为功率损耗成本和开关动作成本。

相关的约束条件如下。

（1）拓扑辐射性约束为

式中：B_t 为时段 t 系统拓扑结构（t=1,2,···,T）；B_T,s 为总时段 T 内满足辐射性且无孤立节点的系统拓扑集合。

（2）容量约束为

式中：S_t,j 、 S_j,max 分别为时段 t 支路 j 的视在功率及视在功率最大值。

（3）节点电压约束为

式中： U_t,i 、 U_i,max 和 U_i,min 分别为时段 t 节点 i 的节点电压及节点 i 电压上、下限；N 为节点总数。

（4）潮流约束为

式中：P_g,t,i 、 Q_g,t,i 分别为时段 t 节点 i 的注入有功和无功功率；P_l,t,i 、 Q_l,t,i 分别为时段 t 节点 i 的负荷有功和无功功率，t=1,2, ···,T； B_ij 、 G_ij 分别为支路ij的电导、电纳；θ_t,ij 为时段 t 支路ij电压相角。

（5）开关约束为

式中：K_T,i,max 为时段T支路 i 的支路允许开断总数；K_T,max 为时段T系统内所有支路允许开断总数。

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

2  单阶段静态重构算法

文献[23]为提升编码效率提出了一种基于矩阵环和操作的Mayeda生成树实用方法。文献[9]将该方法和粒子群算法相结合，即采用粒子群算法随机选择来代替文献[23]中穷举方法来确认候选支路集中的待交换支路，进而获得更快的计算速度，另外该方法因利用了完整树的构建方法，其所生成的新树满足放射性要求而无须进行非常烦琐的放射性约束检测，计算速度相对于其他进化类算法而言具有明显优势，算例也充分证明了其先进性。但因仍属于随机类算法，理论上必须具有足够长的计算时间，才能得到全局最优解，尤其当系统规模较大时，计算时间仍然较长。本文提出把确定性的最优流算法与基于Mayeda生成树的重构算法相结合，获得快速的单阶段配网重构新算法，简称为静态重构算法。该算法的基本思想是：在Mayeda生成树产生过程中，采用最优流方法生成交换支路取代随机方式生成交换支路，具体是把由环和计算获得的候选支路集，逐一开断候选支路集中的支路，其中引起功率损耗增量最小的支路即作为交换支路，与待交换支路（实际是当前树的一个连枝）进行替换，从而完成一次树枝与连枝的交换；每一连枝的交换支路均按上述方式形成，直至生成一棵新树。如此反复循环迭代，直至收敛。上述做法因采用局部的最优支路代替随机方式生成的交换支路，最后所生成的解只能是近似的最优解，或次优解，相应的目标函数与全局最优解有一定的差距，但计算速度得到了明显的提升，实际上是实现了二者方法的优势互补。静态重构算法的基本过程如下。（1）初始化。根据初始网络结构获得初始生成树 t₀ 和网络矩阵M₀； k=1 ；并对 t₀ 中树枝和相应连枝进行编号、排序，分别形成树枝序列 B_to={e₁,⋅⋅⋅,e_N−1} 和连枝序列 B_lo={l₁,⋅⋅⋅,l_h} （ h 为连枝总数目），初始待交换支路为 l₁ 。f_flag =0；记变量 v_i(i=1,2,⋯,N−1) 代表当前树支序列 B_to 中的支路是否被交换：v_i =1表示该支路已经用于支路交换，否则，该支路没有用于支路交换；（2）确定 v_i=0 且矩阵M_k-1与M₀中第 k 列均为1元素所在行对应的树枝支路，由满足上述条件的所有 e_i 加上 l_k 共同构成用于交换连支 l_k 的候选支路集。闭合连枝 l_k 采用最优流法确定交换支路：对该单环网进行潮流计算，并将候选支路集中支路开断后引起网损增量最小的支路确定为用于与 l_k 交换的支路；（3）将步骤（2）中确定的交换支路断开，连枝支路 l_k 闭合，得到新树 t_k ；如果 k=h ，转步骤（4）；否则利用文献[23]中的环和操作获得网络矩阵M_k， k=k+1 ；转步骤（2）；（4）计算与新树 t_k 对应的配电网络的有功功率损耗loss；若 f_flag=0 ，则 f_flag=f_flag+1 ，L_loss*=L_loss；转步骤（6）；（5）判断是否满足收敛判据 |L_loss−L_loss∗|＜ε ，若满足则算法结束，得到新树 t^∗=t_h ；不满足则令L_loss*=L_loss；（6）利用文献[23]中的环和操作获得网络矩阵M_k；并将 t_k 和M_k分别定义为参考树 t₀ 和网络矩阵M₀， k=1 ，转步骤（2）。3  基于贪婪算法的多阶段重构算法

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

基于第2节所提出的快速单阶段重构算法，本文进一步基于贪婪算法提出对于由式（1）~（6）组成的多阶段重构问题的快速求解新算法，其可以通过2个阶段的优化获得：（1）0~T中的任意连续时段的合并，获得相应的时段合并方案，当T比较大时，时段合并方案的数目非常庞大；（2）基于阶段（1）所确定的时段合并方案，采用进化优化策略获得所有合并时段的相应开关动作策略，使得在满足约束的条件下目标函数最小；如此反复迭代计算，直至遍历所有时段合并方案，在所有可行方案中目标函数最小的时段合并及开关动作可行方案，即为最后的最优解。若T比较大时，其阶段（1）的时段合并方案的数目就非常大，而每一时段合并方案均需要计算其最优开关动作策略，从而总体计算时间会非常的长。基于单纯的进化优化算法的动态重构，其计算复杂度与上述全局组合优化算法是等价的。上述算法用于大系统时可能遇到计算时间过长问题，而限制了其应用。为了克服该问题，本文基于贪婪算法提出一种多阶段重构问题的快速求解新算法。其基本思想如下。（1）不划分阶段（1）优化及阶段（2）优化，以最小时段作为初始的阶段划分，对于初始阶段（就是最小的时段）分别按单阶段静态优化方法确定每一阶段的最佳开关动作方案及网损值。（2）对当前状态下的所有相继的两个阶段的开关动作次数进行排序，然后进行如下操作。确定开关动作次数最多的两个相继阶段 w₀ 、 w₁ ，给定寻优尺度参数 M ，记 s₁=w₀−M 、 s₂=w₁+M ，对阶段范围 s₁∼s₂ 内所包含的任意 J （ 2≤J≤ min(5,s₂−s₁+1) ）个连续时段进行合并（若 w₀−M＜1 或 w₁+M＞T ，相应地 s₁=1 、 s₂=T ），采用本文阶段（2）所提出的静态重构优化方法确定相应阶段合并之后的开关最优动作方案；各个方案目标函数的最小值所对应的方案即为 s₁∼s₂ 阶段范围内的最终动作方案。其步骤如下。①若有解，则获得阶段合并之后的新阶段解；②若无可行解，放弃相应阶段合并，选择当前状态下的所有相继2个阶段的开关动作次数与当前的一样或次于当前的2个阶段，按上述方法所确定的相应的阶段范围进行合并，并进行阶段合并之后的静态重构计算，并重复上述过程，直到找到合并之后具有可行解的相继阶段，并进行阶段合并，而获得其阶段合并之后的解，转步骤③；若所有阶段均合并之后，仍无法获得可行解，意味着目前的负荷状态无解，算法结束；③获得当前状态下的所有阶段的总目标函数，若新的目标函数小于上一次阶段合并的目标函数，或不是可行解，回到步骤②；若新的目标函数大于上一次阶段合并的目标函数且当前解是可行解，已得到了最优解，算法结束。

3.2  多阶段重构算法步骤

为便于描述，先设置变量。假定每条支路均配置开关；T^m 表示第 m 次合并后的总阶段数目；i=1,2,⋅⋅⋅,N_b ；M(0≤M≤T⁰−2) 为预先给定寻优尺度参数。（1） m=0 。将日负荷曲线均分为 T⁰ 个阶段，（本文 T⁰=24 ），并令各单阶段内各负荷功率出力保持恒定，初始阶段，各阶段所包含的单时段数为1；然后采用第2节提出的静态配网重构算法分别对各阶段进行重构优化，把各阶段对应目标函数值记为t=1,⋅⋅⋅,T⁰ ；同时建立两列 T^m 行的Tab表，表的第1列为阶段号，即阶段 t(t=1,⋅⋅⋅,T^m) ；第2列为第1列阶段号所包括的单位时段号，初始时，Tab表的第2列与其对应的第1列元素相同。（2）遍历Tab表的第1列，即遍历所有阶段 T^m ，把第 t(t=1,⋅⋅⋅,T^m−1) 阶段与下一阶段的开关动作次数之和记为 D_t ，找出 max{D_t} （如果最大值存在多个，则任选其一即可）所对应的两个相继阶段，记为 t_j 、 t_j+1 ，并进行赋值操作， w₀=t_j 、 w₁=t_j+1 ，记 s₁=w₀−M 、 s₂=w₁+M （如果 w₀−M＜1 或 w₁+M＞T^m ，那么相应地 s₁=1 、 s₂=T^m ）,其中 M 为给定的搜索范围尺度参数。（3）对阶段范围 s₁∼s₂ 内进行合并，不妨设共有 r 个合并后的新阶段，对于其中任一合并后的新阶段 r1 ，则按式（7）~（11）所给数学模型确定合并后开关优化方案。

式中：s_p 、 s_q 为新阶段 r₁ 对应合并前起始、终止阶段；表示第 k （ 1≤k≤ω ）个合并方案中的第 r₁ 阶段的重构总成本目标函数；ω 为合并方案总数， v₀ 、 v₁ 分别表示第 r₁ 段的起始、终止时段；r₁∈{1,2,⋯,r} 。其约束条件如下。

拓扑辐射形约束为

容量约束为

节点电压约束为

潮流约束为

式中：a={t_tab(s_p,2),⋅⋅⋅,t_tab(s_q,2)} 。

对于上述 r 个阶段,分别采用第2节所介绍的静态优化的方法进行求解，获得各自可行最优解；r 个目标函数值的和即为第 k 个方案的目标函数值， r 个阶段的解相应组成了第 k 个方案的解，即 F_k=∑minF_r1 （ 1≤r₁≤r ）；若某个阶段无解，则第 k 个方案的目标函数为无穷大，其解为空解。

对于 ω 个合并方案，每一方案均按上述方法进行求解，获得相应的 F_k 及相应的可行最优解。进而， min{F_k} （ 1≤k≤ω ）对应的阶段合并方案即为 s₁∼s₂ 范围内阶段合并后的最终结果，共有 r^∗ 个合并后的新阶段，其中阶段 r₂ 的起始、终止时段分别为（ r₂∈{1,2,⋅⋅⋅,r^∗} ）。若在阶段合并范围 s₁∼s₂ 内任一方案均无可行解，在 D_t 中找出相邻阶段开关动作次数和仅次于或与当前值一样的 D_t ，并将该值对应的相邻两阶段也记为 t_j 、 t_j+1 ，赋值 w₀=t_j 、 w₁=t_j+1 ，并得到要合并的阶段范围 s₁∼s₂ （ s₁=w₀−M 、 s₂=w₁+M ；若 w₀−M＜1 或 w₁+M＞T^m ，相应地 s₁=1 、 s₂=T^m ），重复步骤3；若所有时段已经合并，仍无法获得可行解，意味着当前负荷状态无法获得可行解，算法结束；否则在中记录相应的成本目标函数值并更新Tab表：①令 r₂=1 ；②若 r₂≤r^∗ ，把Tab表第 (s₁+r₂−1) 行内容更新为 t_tab(s₁+r₂−1,2)=③ r₂++ ；若 r₂>r^∗ ， γ=0 ，转步骤iv)；否则，转步骤②；④把Tab表的第 s₁+r^∗+γ 行内容更新为Tab表的第 s₂+γ+1 行内容；γ++ ，若 γ≤T^m−s₂ ,转步骤（4）)；否则， m++ ， T^m=T^m−1− (s₂−s₁+1)+r^∗ ，转步骤（4）。

（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。其中 α_c 、 β_c 取为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  动态重构结果分析

采用基于贪婪算法与本文所提出的静态重构快速算法相结合的动态重构快速求解方法在不同的尺度参数 M(0≤M≤22) 下分别对系统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
图5  系统4的性能对比Fig.5  Performance comparison of system 4
由图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倍。实现保证重构质量下计算效率显著地提升。因此，该计算结果充分地证明了本文方法的有效性及先进性。
表3  开关动作次数比较Table 3  Comparison of switching action times
5  结论

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

（责任编辑　张重实）

作者介绍

赵胜举(1995—)，男，硕士，从事配网自动化研究，E-mail：[e-mail];

★

林济铿(1967—)，男，通信作者，教授，从事系统稳定性分析及控制、智能电网研究，E-mail：[e-mail].

欢迎点击文后“阅读原文”跳转期刊官网，获取更多信息！

 往期回顾 

◀

编辑：杨彪

校对：蒋东方

审核：方彤

声明

根据国家版权局最新规定，纸媒、网站、微博、微信公众号转载、摘编《中国电力》编辑部的作品，转载时要包含本微信号名称、二维码等关键信息，在文首注明《中国电力》原创。个人请按本微信原文转发、分享。欢迎大家转载分享。