基于归一化谱聚类和约束谱聚类的两阶段主动解列方法

摘要

本发明公开了一种基于归一化谱聚类和约束谱聚类的两阶段主动解列方法，在第一阶段中，利用归一化谱聚类来识别同调机群，并利用这些同调机群形成成对约束；第二阶段则使用约束谱聚类来寻找满足成对约束的、具有最小有功潮流冲击的解列断面。当系统需要被解列为多个孤岛时，使用递归二分法实现。本发明算法考虑了发电机同调和最小有功潮流冲击两个因素，可以在不化简系统拓扑的情况下，对主动解列问题实现实时计算。

说明书

技术领域

本发明属于电力系统安全技术和电力系统紧急控制领域。

背景技术

受用电负荷快速增长、大容量新能源发电并网和电力市场改革等因素的影 响，大型互联电网的运行点越来越接近于其运行极限。这种情况下电网的安全 稳定裕度降低，发生严重的扰动或故障时，如果不能及时采取有效措施，可能 造成事故的扩大乃至整个电力系统的崩溃，例如2003年的美加大停电和2006 年的欧洲“11.4”大停电。

基于广域测量系统的主动解列在系统受到严重扰动、无法继续完整运行时， 根据实时运行状态将系统解列为多个独立运行的孤岛，可有效避免和限制大停 电的影响[文献1SUN Kai，ZH ENG Dazhong，LU Qiang.Splitting strategies for  islanding operation of large-scale power systems using OBDD-based methods.IEEE  Trans.on Power Syst.，2003，18(2)：912-922.]、[文献2沈沉，吴佳耘，乔颖，等.电 力系统主动解列控制方法的研究.中国电机工程学报，2006，26(13)：1-6.]、[文献3 WANGX.Slow coherency grouping based islanding using minimal cutsets and  generator coherency index tracing using the continuation method[D].Ames：lowa  State University，2005.]、[文献4TERZIJA V.，VALVERDE G.，CAI D.Y.，et al.Wide area  monitoring，protection and control of future electric power networks.Proceedings of  the IEEE，2011，99(1)：80-93.]。主动解列可以用来应对不同的紧急事件，例如区域 间振荡、电压崩溃、潮流转移等。与主动解列相关的三个主要问题是：1)是否 解列及何时解列(解列判据和时序问题)；2)在哪儿解列(确定解列策略)；3) 解列后孤岛内的紧急控制措施。在一个有q条线路的系统中，解列的组合有2^q种，是一个指数空间。随着系统规模的增大，在这样一个指数空间内确定解列 策略将遭遇组合爆炸问题，求解极其困难[文献1]。

根据主动解列的目标函数不同，现有的主动解列算法主要可以分为两大类： 最小有功不平衡和最小有功潮流冲击。这两种目标函数的区别在于，有功潮流 冲击可以用解列断面上有功潮流的代数和表示，而有功不平衡则可以用解列断 面上有功潮流算术和的绝对值来表示(需要考虑有功潮流的方向性)。

1)以最小有功不平衡为目标函数的方法

以最小有功不平衡为目标函数，可以保证孤岛内的有功平衡、尽可能减少解 列后需要减载的负荷数量。现有的以有功不平衡为目标函数的方法基本都考虑 了有功不平衡和发电机同调这两个约束条件[文献1]、[文献2]、[文献3]。

由于求解最小有功不平衡问题是一个NP-hard问题，这意味着没有多项式时 间内的有效算法[文献1]。为满足在线计算的快速性要求，现有的方法要么对系 统进行大量化简后(化简到几十节点以下)、搜索问题的全局最优解[文献1]；要 么牺牲对全局最优解的要求、通过启发式算法来寻找系统的本地最优解[文献5 汪成根，张保会，郝治国，等.一种电力系统失步解列面的实时搜索方法.中国 电机工程学报，2010，30(7)：48-55.]。将一个成百上千节点的电力网络化简到几十 节点以下，会丢失很多可行解，从而可能错过最优解；而采用启发式算法，则 解的质量无法保证。

2)以最小有功潮流冲击为目标函数的方法

以最小有功潮流冲击为目标函数，可以降低解列操作对系统带来的冲击。 目前的以最小有功潮流冲击为目标函数的方法都具有较高的计算效率，但它们 将主动解列看作不带约束的优化问题，具有很大的局限性[文献6HAO L.， ROSENWALD G.W.，JUNG J.，et al.Strategic power infrastructure defense. Proceedings of the IEEE，2005，93(5)：918-933]和[文献7PEIRAVI A.，ILDARABADI R.， Comparison of computational requirements for spectral and kernel k-means  bisection of power system.Australian Journal of Basic and Applied Sciences，2009， 3(3)：2366-2388]。忽略发电机的同步约束、得到的解可能包含不同步的发电机， 无法形成稳定的孤岛运行。另外，直接在电网中应用谱聚类而不考虑任何约束， 很容易将某一个孤立的负荷节点分割出来。在求解主动解列时，这两种情况都 是不可接受的。

发明内容

本发明的目的就是为解决上述问题，提供一种基于归一化谱聚类和约束谱 聚类的两阶段主动解列方法。在第一阶段中，利用归一化谱聚类来识别同调机 群，并利用这些同调机群形成成对约束；第二阶段则使用约束谱聚类来寻找满 足成对约束的、具有最小有功潮流冲击的解列断面。本发明考虑了发电机同调 和最小有功潮流冲击两个因素，可以在不化简系统拓扑的情况下，在线确定解 列策略。

为实现上述目的，本发明采用如下技术方案：

一种基于归一化谱聚类和约束谱聚类的两阶段主动解列方法，具体步骤为：

第一阶段，首先根据电力系统的线性化动态模型，构建动态图G_D；这个图 只包含发电机节点，其边的权重为同步系数表示节点i和j之间的动 态耦合；利用归一化谱聚类算法对动态图进行分割，寻找满足式

$[V_{G1}^{*},V_{G2}^{*}]=\underset{V_{G1},V_{G2}⋐V_G}{\arg \min }\left(\underset{j\in V_{G2}}{\Sigma }\underset{i\in V_{G1}}{\Sigma }(\frac{{\partial P}_{\mathrm{ij}}}{{\partial \delta }_{\mathrm{ij}}}·(\frac{1}{H_i}+\frac{1}{H_j}))\right)---\left(1\right)$

所示组合优化问题的最优解，得到同调机群；这些同调机群将作为第二阶段的 约束条件。

其中，argmin表示对优化问题求解；

V_G：系统所有发电机节点的集合；

V_G1：孤岛1的所有发电机节点集合；

V_G2：孤岛2的所有发电机节点集合；

H_i：节点i的标幺化惯量常数；

节点i和j之间的同步系数；

优化问题(1)的最优解；

第二阶段，根据潮流数据构建静态图G_S；这个图将包括所有的母线节点， 其权重定义为有功潮流绝对值|P_ij|；利用约束谱聚类对静态图进行分割，寻找式 $\underset{V_1,V_2⋐V}{\min }\left(\underset{i\in V_1,j\in V_2}{\Sigma }\right|P_{\mathrm{ij}}\left|\right)$满足$V_{G1}^{*}⋐V_1,$$V_{G2}^{*}⋐V_2---\left(2\right)$

所示组合优化问题的最优解，即主动解列的孤岛划分策略；

V：系统所有节点(包括负荷节点和发电机节点)的集合；

V₁：孤岛1的所有节点(包括负荷节点和发电机节点)集合；

V₂：孤岛2的所有节点(包括负荷节点和发电机节点)集合；

P_ij：节点i和j之间的标幺化有功潮流；

当系统需要被解列为多个孤岛时，使用递归二分法来实现。

所述第一阶段的具体步骤为：

1)以作为边的权重来构造动态图G_D；

2)求解广义特征方程得到前两个特征向量

3)以为列向量构成矩阵J，选取J的第i行行向量y_i∈R²对应着图 的节点；

4)利用k-medoids算法将节点y_i∈R²进行聚类，分成V_G1和V_G2两组；

5)假定前m1个发电机属于群V_G1，接下来m2个发电机属于群V_G2，则约 束矩阵如式

$U=\left(\begin{array}{ccc}{1}_{m_1}& 1_{m_1}& 0_{m_1\times (n-b)}\\ 1_{m_2}& -1_{m_2}& 0_{m_2\times (n-b)}\\ 1_{n-b}& 0_{n-b}& I_{(n\times b)\times (n-b)}\end{array}\right)---\left(2\right)$

I是单位矩阵，1是全1的列向量，0是全0的矩阵或列向量，b＝m1+m2； M是发电机节点的惯量矩阵，M＝diag(2H₁/ω₀，2H₂/ω₀，…，2H_m/ω₀)；ω₀是同 步转速；λ为方程的特征值，为特征向量。

所述构建动态图G_D的过程为：针对一个包含m个发电机的电力系统，根据 式(3)来计算其拉普拉斯矩阵L_D，从而构建动态图G_D(V_G)：

${\left[L_D\right]}_{\mathrm{ij}}=\left(\begin{array}{cc}\frac{{\partial P}_{\mathrm{ij}}}{{\partial \delta }_{\mathrm{ij}}}=-\left|V_i\right|\left|V_j\right|B_{\mathrm{ij}}^{\prime }\cos ({\delta }_i-{\delta }_j)& \mathrm{ifi}\ne j\\ -\underset{l=1,l\ne i}{\overset{m}{\Sigma }}{\left[L_D\right]}_{\mathrm{il}}& \mathrm{ifi}=j\end{array}\right)---\left(3\right)$

B′_ij是收缩到发电机节点的导纳矩阵的虚部，动态图G_D表示发电机节点间的动 态耦合，其边的权重为同步系数V_i和V_j分别为节点i和j的电压幅值标 幺值；δ_i和δ_j为节点i和j的电压相位值。

所述第二阶段包括以下步骤：

1)以(|P_ij|+|P_ji|)/2作为边的权重来构造静态图G_S；

2)求解广义特征方程得到前两个特征向量

3)以为列向量构成矩阵J，选取J的第i行行向量y_i∈R²对应 着图的节点；

4)利用k-medoids算法将节点y_i∈R²进行聚类，分成V₁和V₂两组。

U^T是U的转置矩阵。

所述构建静态图G_S的过程为：

针对一个包含n条母线的电力系统，利用潮流数据来构建静态图 G_S(V，E_S，W_S)，表示节点间的有功交换的绝对值；由于网损的影响，线路两端 测到的有功|P_ij|和|P_ji|是不同的，采用(|P_ij|+|P_ji|)/2作为边的权重，则静态图G_S的拉普拉斯矩阵L_S如下所示：

${\left[L_S\right]}_{\mathrm{ij}}=\left(\begin{array}{cc}\frac{\left|P_{\mathrm{ij}}\right|+\left|P_{\mathrm{ji}}\right|}{2}=-\left|V_i\right|\left|V_j\right|B_{\mathrm{ij}}\sin ({\delta }_i-{\delta }_j)& \mathrm{ifi}\ne j\\ -\underset{l=1,l\ne i}{\overset{n}{\Sigma }}{\left[L_S\right]}_{\mathrm{il}}& \mathrm{ifi}=j\end{array}\right)---\left(4\right)$

B_ij是网络导纳矩阵的虚部。

所述当系统需要被解列为多个孤岛时，使用递归二分法，即选取V₁或V₂作为节点集，重新运行所述第一阶段和第二阶段的方法直到得到要求数量的孤 岛。

本发明的原理如下：

1主动解列问题及谱聚类算法

在图论中，可以采用一个边赋权的无向图G(V，V_G，E，W)来描述一个包含m 个发电机、n个母线的电力系统。节点集V＝{v₁，...，v_n}表示母线的集合；V_G是V 的一个子集，代表发电机母线集合；E则表示边的集合，其元素e_ij(i，j＝1，...，n)代 表节点i和j之间的输电线路；W为边的权重矩阵。将图G分为两个子图 G₁(V₁，V_G1，E₁，W₁)和G₂(V₂，V_G2，E₂，W₂)，G₁和G₂分别对应着电力系统的两个 孤岛。当需要解列为多个孤岛时，可以使用递归二分法来实现。

1.1主动解列问题

本发明主要考虑发电机同调和最小化有功潮流冲击两个约束条件。

1.1.1发电机同调

为了保证孤岛的稳定运行，孤岛内的发电机必须保持同步运行。基于经典 发电机模型，含m个发电机的电力系统线性化二阶动态模型可以表示为[文献8 CHOW J.H.Time-scale modeling of dynamic networks with applications to power  systems[M].New York：S pringer-Verlag，1982]：

$\stackrel{··}{x}=\mathrm{Ax}---\left(5\right)$

其中x＝[Δδ₁，…，Δδ_m]^T，Δδ是发电机功角相对于稳定运行点δ₀的偏差；为 x的二阶导数；A为系统状态矩阵。根据慢同调理论，将发电机分为两群相当于 将系统状态矩阵A分割为两个子矩阵A₁₁和A₂₂[文献8]。

非对角子矩阵A₁₂和A₂₁的范数之和可以用于定义子系统G₁和G₂之间的 动态耦合S：

S＝||A₁₂||+||A₂₁||δ(6)

在振荡过程中，具有较强动态耦合的发电机将表现出相同的摇摆特征，具 有较弱动态耦合的发电机则将逐渐分离，因此，寻找同步发电机群的问题就转 换成了寻找发电机之间的弱动态耦合[文献9LAMBA S.S.，NATH R.，Coherency  identification by the method of weak coupling.Electrical Power & Energy Systems， 1985，7(4)：233-242.]。由于系统状态矩阵中，与无功和电压相关的项数值很小， 因此忽略与电压和无功有关的项后，同调约束可以表示为式(7)所示的组合优 化问题[文献8]、[文献9]：

$\min S=\underset{V_{G1},V_{G2}⋐V_G}{\min }\left(\underset{j\in V_{G2}}{\Sigma }\underset{i\in V_{G1}}{\Sigma }(\frac{{\partial P}_{\mathrm{ij}}}{\partial {\delta }_{\mathrm{ij}}}·(\frac{1}{H_i}+\frac{1}{H_j}))\right)---\left(7\right)$

换句话说，通过求解式(7)，可以将系统内的发电机分为2个同调机群V_G1和 V_G2。

1.1.2最小有功潮流冲击

式(8)和式(9)所示的最小有功不平衡和最小有功潮流冲击都可以作为 主动解列问题求解的目标函数，但它们的作用和影响是不同的。

最小有功不平衡侧重于形成功率平衡的孤岛、减少解列后的减载数量，对系 统的经济运行有利；而最小有功潮流冲击则侧重于最小化解列操作对系统的冲 击、可以减弱解列后孤岛内发电机的摇摆、降低孤岛内线路过载的可能性以及 便于系统恢复等，对孤岛形成过程中的暂态稳定性有利[文献10V.E.Henner，A  network separation scheme for emergency control.International Journal of Electrical  Power & Energy Systems，1980，2(2)，109-114.]。

$\underset{V_1,V_2⋐V}{\min }\left|\underset{i\in V_1,j\in V_2}{\Sigma }{P}_{\mathrm{ij}}\right|---\left(8\right)$

$\underset{V_1,V_2⋐V}{\min }\left(\underset{i\in V_1,j\in V_2}{\Sigma }\right|P_{\mathrm{ij}}\left|\right)---\left(9\right)$

在电网的解列过程中，暂态稳定性应当是被优先考虑的。这是因为，一个 功率平衡但暂态稳定裕度为负值的孤岛，不可能实现稳定运行；而一个功率不 平衡但暂态稳定裕度很大的孤岛，则可以通过结合减载措施来实现稳定运行。 只有在暂态稳定裕度足够大的前提下，最小化有功不平衡才有利于系统的经济 运行。因此，本发明采用最小化有功潮流冲击作为主动解列的目标函数。

另外，采用最小化有功潮流冲击作为主动解列的目标函数，还可以极大的 降低问题的求解复杂度。

1.1.3主动解列问题

结合式(7)和(9)，可以得到主动解列问题的组合优化表述：

$\underset{V_1,V_2⋐V}{\min }\left(\underset{i\in V_1,j\in V_2}{\Sigma }\right|P_{\mathrm{ij}}\left|\right)$满足$V_{G1}^{*}⋐V_1,$$V_{G2}^{*}⋐V_2$

(10)

$[V_{G1}^{*},V_{G2}^{*}]=\underset{V_{G1},V_{G2}⋐V_G}{\arg \min }\left(\underset{j\in V_{G2}}{\Sigma }\underset{i=V_{G1}}{\Sigma }(\frac{\partial P_{\mathrm{ij}}}{\partial {\delta }_{\mathrm{ij}}}·(\frac{1}{H_i}+\frac{1}{H_j}))\right)$

是式(7)的优化解，它在式(10)中进一步作为整个优化问题的约 束。也就是说，求解式(10)表示在满足发电机同调的约束下，寻找最小有功 潮流冲击的解列断面。

1.2谱聚类算法

将图切割成两个子图，需要将子图之间连接的边都切断。在图论中，需要 切断的边的集合叫做割集，割集中的边的权重之和叫做割[文献11SHI J.，MALIK J.， Normalized cuts and image segmentation.IEEE Trans.on Pattern Analysis and  Machine Intelligence，2000，22(8)：888-905.]。

$\mathrm{cut}(V_1,V_2)=\underset{i\in V_1,j\in V_2}{\Sigma }{w}_{\mathrm{ij}}---\left(11\right)$

这样，主动解列问题就转换为一个寻找具有最小割的图分割问题，非归一 化谱聚类就可以用来求解最小割。

对图G，定义其拉普拉斯矩阵L为：

L＝D-W    (12)

D为节点权重矩阵，其元素D_i表示连接到节点i上的所有边的权重之和。对任意 无向图，矩阵W和L都是对称的。

非归一化谱聚类算法主要包括以下步骤[文献12LUXBURG U.v.，A tutorial on  spectral clustering.Statistics and Computing，2007，17(4)：395-416]：

1)计算拉普拉斯矩阵L的前两个特征向量

2)以为列向量构成矩阵J，选取J的第i行行向量y_i∈R²对应着图的

节点。

3)利用某种聚类算法(例如k-medoids[文献13TH EODORIDIS S.， KOUTROUMBA K.，Pattern recognition[M].New York：American Press，2008])

将节点y_i∈R²进行聚类，分成两组。

然而，直接求解最小割问题经常会得到孤立的节点，这对主动解列是无用 的。为了解决这个问题，提出了一种代替最小割的标准——规范切，如式(13) 所示，利用节点的权重来使得图分割更加平衡[文献11]。

$\mathrm{Ncut}(V_1,V_2)=\frac{\mathrm{cut}(V_1,V_2)}{\mathrm{weig}\left(V_1\right)}+\frac{\mathrm{cut}(V_1,V_2)}{\mathrm{weig}\left(V_2\right)}---\left(13\right)$

其中，是G₁中所有节点的权重之和，weig(V₂)则是G₂中所 有节点的权重之和。

归一化谱聚类算法可以用来寻找图的最小规范切，其算法步骤如下所示[文 献12]：

1)求解广义特征方程得到前两个特征向量

2)以为列向量构成矩阵J，选取J的第i行行向量y_i∈R²对应着图 的节点。

3)利用某种聚类算法将节点y_i∈R²进行聚类，分成两组。

由于谱聚类算法可以在多项式时间内获得组合优化问题的松弛解，所以谱 聚类算法被用于求解本文中的组合优化问题。

2.两阶段的谱聚类算法

根据式(10)构造动态图和静态图，并利用所提算法对这两个图进行图分 割，从而得到合理的孤岛划分策略。算法流程如图2所示。

第一阶段，首先根据电力系统的线性化动态模型，构建动态图G_D。这个图 只包含发电机节点，其边的权重为同步系数表示节点i和j之间的动 态耦合。利用归一化谱聚类算法对动态图进行分割，得到同调机群。这些同调 机群将作为第二阶段的约束条件。

第二阶段，根据潮流数据构建静态图G_S。这个图将包括所有的母线节点， 其权重定义为有功潮流绝对值|P_ij|。利用约束谱聚类对静态图进行分割，在满足 发电机分群约束的条件下，寻找式(10)所示组合优化问题的最优解。

2.1构建动态图并应用归一化谱聚类

针对一个包含m个发电机的电力系统，可以根据式(14)来计算其拉普拉 斯矩阵，从而构建动态图G_D(V_G)：

${\left[L_D\right]}_{\mathrm{ij}}=\left(\begin{array}{cc}\frac{{\partial P}_{\mathrm{ij}}}{{\partial \delta }_{\mathrm{ij}}}=-\left|V_i\right|\left|V_j\right|B_{\mathrm{ij}}^{\prime }\cos ({\delta }_i-{\delta }_j)& \mathrm{ifi}\ne j\\ -\underset{l=1,l\ne i}{\overset{m}{\Sigma }}{\left[L_D\right]}_{\mathrm{il}}& \mathrm{ifi}=j\end{array}\right)---\left(14\right)$

利用拉普拉斯矩阵L_D，系统的线性二阶动态方程可以重写为：

$M\stackrel{··}{x}=L_{D}x---\left(15\right)$

对比式(7)和(13)，可以看到式(7)其实是图G_D的一种规范割，只不 过这里使用节点的惯量而不是权重来进行规范。在图G_D上应用归一化谱聚类， 则可以找到满足式(7)的最优解。

第一阶段的算法具有以下步骤：

1)以作为边的权重来构造动态图G_D。

2)求解广义特征方程得到前两个特征向量

3)以为列向量构成矩阵J，选取J的第i行行向量y_i∈R²对应着图 的节点。

4)利用k-medoids算法将节点y_i∈R²进行聚类，分成V_G1和V_G2两组。

本发明算法的第一阶段实际上是慢同调理论的谱聚类形式。慢同调基于系 统状态矩阵A的特征向量进行分析，而实际上由于式(5)和(15)是等效的， 所以慢同调理论和上述归一化的谱聚类本质上是相同的。唯一不同点在于慢同 调选取参考发电机节点，并通过分析各发电机节点与参考节点之间的向量夹角 来分组；而采用k-medoids的归一化谱聚类利用节点间相似程度来分组。

2.2构建静态图并应用约束谱聚类

针对一个包含n条母线的电力系统，可以利用潮流数据来构建静态图G_S(V)， 表示节点间的有功交换的绝对值。由于网损的影响，线路两端测到的有功|P_ij|和 |P_ji|是不同的。为了确保图的权重矩阵是对称的，这里采用(|P_ij|+|P_ji|)/2作为 边的权重。

静态图G_S的拉普拉斯矩阵L_S如下所示：

${\left[L_S\right]}_{\mathrm{ij}}=\left(\begin{array}{cc}\frac{\left|P_{\mathrm{ij}}\right|+\left|P_{\mathrm{ji}}\right|}{2}=-\left|V_i\right|\left|V_j\right|B_{\mathrm{ij}}\sin ({\delta }_i-{\delta }_j)& \mathrm{ifi}\ne j\\ -\underset{l=1,l\ne i}{\overset{n}{\Sigma }}{\left[L_S\right]}_{\mathrm{il}}& \mathrm{ifi}=j\end{array}\right)---\left(16\right)$

静态图G_S的最小割，即最小有功潮流冲击，可以利用非归一化的谱聚类来 获得，即式(9)的优化解。但这个解并不是主动解列问题的解，因为没有考虑 发电机同调的约束。因此，形成的孤岛内可能包含不同步的发电机，无法保持 稳定运行。从本发明方法的第一阶段，已经得到了发电机同调机群，这些机群 可以转化为节点间的成对约束：Must-Link约束和Cannot-Link约束[文献14BIE T. D.，SUYKENS J.，MOOR B.D.，Learning from general label constraints.Proc.IAPR  International Workshop on Statistical Pattern Recognition，Lisbon，Aug.2004]。

1)Must-Link约束：如果两个发电机属于同一个同调机群，则两个发电机之前 必须连接，构成一个Must-Link约束；

2)Cannot-Link约束：如果两个发电机不属于同一个同调机群，则两个发电 机一定不能连接，构成一个Cannot-Link约束。

约束谱聚类可以有效解决带成对约束的聚类问题。一种常用方法是利用一 个约束矩阵来修改解的子空间[文献14]。假定前m₁个发电机属于群V_G1，接下来 m₂个发电机属于群V_G2，则约束矩阵如式(17)所示[文献14]：

$U=\left(\begin{array}{ccc}{1}_{m_1}& 1_{m_1}& 0_{m_1\times (n-b)}\\ 1_{m_2}& -1_{m_2}& 0_{m_2\times (n-b)}\\ 1_{n-b}& 0_{n-b}& I_{(n\times b)\times (n-b)}\end{array}\right)---\left(17\right)$

用这种方法，解空间被从n维投影到(n-b+2)维，所有在一个群里的节点都 被合并到一起，不在一个群里的节点的距离被拉开。

通过引入约束矩阵U，约束谱聚类可以应用到静态图G_S上来寻找在发电机 同调机群约束下、具有最小绝对有功交换的解列界面。本发明方法的第二阶段 包括以下步骤：

1)以(|P_ij|+|P_ji|)/2作为边的权重来构造静态图G_S；

2)求解广义特征方程得到前两个特征向量

3)以为列向量构成矩阵J，选取J的第i行行向量y_i∈R²对应着 图的节点。

4)利用k-medoids算法将节点y_i∈R²进行聚类，分成V₁和V₂两组。

使用上述的两阶段算法，可以求得式(10)所示组合优化问题的解，即主 动解列的孤岛划分策略。

当系统需要被解列为多个孤岛时，使用递归二分法实现，即选取V₁或V₂作为节点集，重新运行所述第一阶段和第二阶段的方法直到得到要求数量的孤 岛。

应当指出的是，本发明方法的第二阶段可以与任何在线的发电机同调识别 算法相配合，它只需要利用发电机同调机群来形成约束，而不局限于只和第一 阶段的归一化谱聚类相配合。

对本发明所提出的基于归一化谱聚类和约束谱聚类的两阶段主动解列算 法，利用IEEE9节点和39节点进行详细的仿真[文献 15http://www.ee.washington.edu/research/pstca/.]。

算例1：IEEE 9节点系统

如图3a所示，IEEE 9节点系统的动态图可根据式(3)构建，其边权重为同 步系数使用前述归一化谱聚类算法对动态图的节点进行聚类，可以得 到两个同调机群{1}和{2，3}，并以此来构建约束矩阵U。

第二阶段中，则可以根据式(4)构建如图3b所示的静态图，其边权重为有 功交换的绝对值(|P_ij|+|P_ji|)/2。使用前述约束谱聚类算法对静态图的节点进行聚 类，可以找到两个节点聚类{1，4}和{2，3，5，6，7，8，9}。图3b所示的点虚线即为这两 个节点聚类的划分界面，也就是主动解列的孤岛划分策略，它的割为 0.65p.u＝0.37p.u+0.28p.u。

如果没有考虑发电机分群的约束，直接在静态图上应用非归一化谱聚类， 则可以得到图3b中点划线所示的解。这个解是具有最小有功潮流冲击的最小割， 也就是式(9)的优化解，其割为0.50p.u＝0.22p.u+0.28p.u。但由于没有考 虑发电机分群的约束，这个解中包含了不同步的发电机1和2，所以不能作为孤 岛划分策略。

算例2：IEEE 39节点系统

IEEE 39节点系统如图4所示，利用前述第一阶段的算法，可以得到表1所示 的三个同调机群。第二阶段则得到两个割集，割集1将机群1和其他两个机群分 开，割集2则将机群2和3分开。这两个割集就构成了孤岛划分策略，如表2和图4 中点虚线所示。

为了验证本发明方法的求解质量，本发明求得割集1和割集2的前五个最优 解，用来与本发明方法的结果进行对比。前五个最优解，是指具有最小绝对有 功交换的前五个解列断面。对比结果如表2所示，这里只对比了割集1，割集2因 为只有三个可行解，所以没有进行对比。

表I IEEE39节点的同调机群

表2IEEE 39节点算例结果对比

除了解的质量以外，求解速度也是主动解列算法的一个重要评价指标。对 一个具有n个节点q条线路的电网，其孤岛划分策略的解空间为2^q。求解最小有 功不平衡可以转换为特殊的0-1背包问题，属于NP-hard问题[文献1]。也就是说， 在多项式时间内无法有效求取最优解，其求解的时间复杂度为指数级。

而求解最小有功潮流冲击，可以转换为图分割和最大流/最小割问题，是一 个P类问题，也就是说可以在多项式时间内求解[文献12]。因此，采用最小有功 潮流冲击作为目标函数，可以降低主动解列问题求解的复杂度。但引入成对约 束，特别是Cannot-link约束，将增加聚类问题求解的复杂度[文献16I.Davidson， S.S.Ravi，″The complexity of non-hierarchical clustering with instance and cluster  level constraints，″Data Mining and Knowledge Discovery，vol.14，no.1，pp.25-61， 2007.]。某些情况下，甚至无法在多项式时间内判断是否存在满足所有Cannot-link 约束的解[文献16]。但在二分聚类的情况下，则始终存在着多项式时间内的有效 算法，而本发明采用恰恰是递归二分法[文献16]。

谱聚类算法的计算量主要在于求解拉普拉斯矩阵的前两个特征向量。因此， 本发明方法第一阶段的计算复杂度为O(m³)；第二阶段计算复杂度为O(n³)，由 于矩阵L_S为稀疏矩阵，甚至可以进一步降低到O(n^4/3)[文献7]、[文献12]。

如表3所示，对IEEE 39节点系统，本发明方法仅需0.004s；而在IEEE 118节 点系统上测试，本发明方法仅需0.11s。仿真结果证实本发明方法的求解质量高、 求解速度快，可以有效应用于实时的主动解列。

表3本发明方法的算例计算时间

^a：Pentium 2.4GHz；4G RAM PC；Matlab 7.0代码.

本发明的有益效果是：提出了一种基于归一化谱聚类和约束谱聚类的主动 解列算法。算法的核心是将主动解列问题转换为一个带约束的组合优化问题， 以最小化有功潮流冲击为目标函数，以发电机同调构成约束条件，并利用谱聚 类来求解这个优化问题。首先根据组合优化问题的目标函数来建立系统的动态 图和静态图，分别表示发电机节点间的动态耦合关系和所有节点间的有功交换。 利用归一化谱聚类来对动态图进行分割，获取同调发电机组；然后利用约束谱 聚类来求解在同调机组约束下，具有最小有功潮流冲击的解列断面。所提的主 动解列算法具有求解质量高、求解速度快的优点，满足在线求解主动解列问题 的需要。

附图说明

图1为将状态矩阵A分割为两个子矩阵A₁₁和A₂₂；

图2为本发明在二分情况下的流程图；

图3a为IEEE9节点系统的动态图；

图3b为IEEE9节点系统的静态图；

图4为IEEE39节点算例的单线图。

具体实施方式

图2中，本发明的方法为：

第一阶段，首先根据电力系统的线性化动态模型，构建动态图G_D；这个图 只包含发电机节点，其边的权重为同步系数表示节点i和j之间的动 态耦合；利用归一化谱聚类算法对动态图进行分割，寻找式

$[V_{G1}^{*},V_{G2}^{*}]=\underset{V_{G1},V_{G2}⋐V_G}{\arg \min }\left(\underset{j\in V_{G2}}{\Sigma }\underset{i\in V_{G1}}{\Sigma }(\frac{{\partial P}_{\mathrm{ij}}}{{\partial \delta }_{\mathrm{ij}}}·(\frac{1}{H_i}+\frac{1}{H_j}))\right)$

所示组合优化问题的最优解(同调机群)；这些同调机群将作为第二 阶段的约束条件；

第二阶段，根据潮流数据构建静态图G_S；这个图将包括所有的母线节点， 其权重定义为有功潮流绝对值|P_ij|；利用约束谱聚类对静态图进行分割，寻找式 $\underset{V_1,V_2⋐V}{\min }\left(\underset{i\in V_1,j\in V_2}{\Sigma }\right|P_{\mathrm{ij}}\left|\right)$满足$V_{G1}^{*}⋐V_1,$$V_{G2}^{*}⋐V_2$

所示组合优化问题的最优解，即主动解列的孤岛划分策略。

所述第一阶段的具体步骤为：

1)以作为边的权重来构造动态图G_D；

2)求解广义特征方程得到前两个特征向量

3)以为列向量构成矩阵J，选取J的第i行行向量y_i∈R²对应着图 的节点；

4)利用k-medoids算法将节点y_i∈R²进行聚类，分成V_G1和V_G2两组；

5)假定前m₁个发电机属于群V_G1，接下来m₂个发电机属于群V_G2，则约束 矩阵如式所示：

$U=\left(\begin{array}{ccc}{1}_{m_1}& 1_{m_1}& 0_{m_1\times (n-b)}\\ 1_{m_2}& -1_{m_2}& 0_{m_2\times (n-b)}\\ 1_{n-b}& 0_{n-b}& I_{(n\times b)\times (n-b)}\end{array}\right)$

所述构建动态图G_D的过程为：针对一个包含m个发电机的电力系统，根据 下式来计算其拉普拉斯矩阵，从而构建动态图G_D(V_G)：

${\left[L_D\right]}_{\mathrm{ij}}=\left(\begin{array}{cc}\frac{{\partial P}_{\mathrm{ij}}}{{\partial \delta }_{\mathrm{ij}}}=-\left|V_i\right|\left|V_j\right|B_{\mathrm{ij}}^{\prime }\cos ({\delta }_i-{\delta }_j)& \mathrm{ifi}\ne j\\ -\underset{l=1,l\ne i}{\overset{m}{\Sigma }}{\left[L_D\right]}_{\mathrm{il}}& \mathrm{ifi}=j\end{array}\right)$

所述第二阶段包括以下步骤：

1)以(|P_ij|+|P_ji|)/2作为边的权重来构造静态图G_S；

2)求解广义特征方程得到前两个特征向量

3)以为列向量构成矩阵J，选取J的第i行行向量y_i∈R²对应 着图的节点；

4)利用k-medoids算法将节点y_i∈R²进行聚类，分成V₁和V₂两组；

所述构建静态图G_S的过程为：

针对一个包含n条母线的电力系统，利用潮流数据来构建静态图G_S(V)，表 示节点间的有功交换的绝对值；由于网损的影响，线路两端测到的有功|P_ij|和|P_ji| 是不同的，采用(|P_ij|+|P_ji|)/2作为边的权重，则静态图G_S的拉普拉斯矩阵L_S如 下所示：

${\left[L_S\right]}_{\mathrm{ij}}=\left(\begin{array}{cc}\frac{\left|P_{\mathrm{ij}}\right|+\left|P_{\mathrm{ji}}\right|}{2}=-\left|V_i\right|\left|V_j\right|B_{\mathrm{ij}}\sin ({\delta }_i-{\delta }_j)& \mathrm{ifi}\ne j\\ -\underset{l=1,l\ne i}{\overset{n}{\Sigma }}{\left[L_S\right]}_{\mathrm{il}}& \mathrm{ifi}=j\end{array}\right)$