PDF《电力系统主动解列断面搜索方法与孤岛调整策略》

2 图划分与谱聚类算法 系统主动解列断面搜索可看成一个图划分问 题, 本节将概述图划分的基本理论与其求解算法. 2.

1 图划分的基本理论 假设图G=( V, E) 为无向边权图, 其中V 为图 的点集, E 为图的边集.给定图G 中每条边e i j的权 值为 wi j, 定义其加权邻接矩阵W 和度矩阵D 中的 元素及图规模Vg( G) 如下: Wi j= wi j e i j∈E

0 e i j?E { (

1 ) Di j = ∑ j wi j i= j

0 i≠j { (

2 ) Vg( G) =∑ i∈V Di i (

3 ) 图划分本质上是按照给定的划分准则将图中的 某些边断开, 从而把图分割成若干独立的子图, 这些 断开边的权值之和即为割值.如果将图 G 分割成 两个独立的子图G1 和G2, 则G1 和G2 的割定义如 下: C( G1, G2) = ∑ i∈G1 , j∈G2 wi j (

4 ) 常见的图划分准则包括最小割准则、 规范割准 则和比例割准则等.为避免图划分时产生孤立节 点, 这里采用规范割准则, 其可用下式描述[

2 1 ] : Nc( G1, G2, ?, Gk) =∑ k i=1 C( Gi, G - i) Vg( Gi) (

5 ) 式中: Nc( G1, G2, ?, Gk) 表示将图G 划分成k 个独 立子图G1, G2, ?, Gk 的规范割准则;

G - i 为子图Gi 相对于图G 的补图. 上述规范割准则通过在分母中引入子图规模 Vg( Gi) , 避免了孤立节点子图的产生, 能对图进行 有效划分.在确定图划分准则后, 图划分问题即可 描述为 Nc( G1, G2, ?, Gk ) 的最小值问 题.然而, 此问题是一个 N P 完全问题, 计算时间随问题复杂 程度呈指数增长.谱聚类算法[

2 2] 可将该 N P 难的 图划分问题转化为特征值求解问题, 这样即可采用 求解特征值的一些有效算法来解决图划分问题, 大 大加快了求解效率. 2.

2 谱聚类算法 谱聚类算法是一种以谱图理论为基础的聚类算 法, 该算法通过求解并筛选图的 L a p l a c i a n 矩阵的 部分特征向量, 将原图数据通过谱分析投影到由所 选取特征向量生成的新样本空间上, 再对新样本空 间内的数据集进行聚类后即可得到原图划分结果. 为求得式( 5) 所表示的 Nc( G1, G2, ?, Gk ) 的最小

8 3

2 0

1 7,

4 1 (

1 9 ) ?学术研究? h t t p : / / ww w. a e p s G i n f o . c o m 值, 定义n* k 阶的指标矩阵H, 其矩阵元素为: Hi j=

1 Vg( Gj) i∈Gj

0 i?Gj ì ? í ? ? ? ? (

6 ) 式中: i=1, 2, ?, n, 其中, n 为图G 中的节点个数;

j=1, 2, ?, k. 经相关数学推导, 式(

5 ) 的最小化问题可等价于 求解式(

7 ) 所描述的约束优化问题[

2 2 ] : m i n G1 , G2 , ?, G k T r ( HT L H) s . t . HT DH= I { (

7 ) 式中: T r ( ?) 为迹函数;

I 为单位矩阵;

L 为未规范 化的 L a p l a c i a n矩阵, L=D-W. 定义规范化的 L a p l a c i a n矩阵 Lr w =D-1 L, 将H松弛到实数范围, 允许其取任意实数, 并根据RayleighGRitz定理[

2 3] , 即可证得 H 由Lr w 的前k 个 最小特征值对应的特征向量组成.在对 指标矩阵 H 的行向量采用一定的聚类算法进行聚类划分后, 其聚类结果即为原图划分方案.综上所述, 谱聚类 算法可将图划分问题转化为图的相应矩阵的特征向 量求解问题, 从而将 N P完全问题转化为 P问题, 有 效降低了计算复杂性.采用谱聚类算法求解图划分 问题的原理图见附录 A 图A1.

3 基于约束谱聚类算法的解列断面搜索 3.

1 含约束谱聚类算法 采用上述谱聚类算法虽然可以求得图的最小规 范割, 但无法保证主动解列问题所需满足的发电机 组同调约束.为此, 需要考虑主动解列问题的特征, 改进谱聚类算法, 以计及发电机组同调约束.这里 将机组同调约束引入到谱聚类算法中, 利用约束条 件监督聚类过程并限制可行解空间, 从而获得满足 约束条件的解列断面. 令无向边权图G=( V, E) 表征n 节点的电力系 统, Pi j为线路i j 上从节点i 流向节点j 的潮流, 则 系统加权邻接矩阵W 的元素为: Wi j= | Pi j |+| Pj i |