1送電ネットワークのネットワー
ク分割とその応用について

明治大学
森 啓之

2アウトライン
Ｐａｒｔ １ 状態推定のトポロジー可観測性解析
 Ｐａｒｔ ２ 送電系統拡張計画(設置コスト、ＥＥＮＳ（Ｅｘpected Enegy NotSupplied)ネットワーク分割

系統運用・計画

3

Ｐａｒｔ １： 状態推定のトポロ
ジー可観測性解析

明治大学
森 啓之

4



送電ネットワークの状態推定のトポロジー
可観測解析のための手法を提案する。
（グラフ理論のスパニングツリー＋系統分割）

。

研究背景

5StartData Acquisition& Processing

Measurements

Filtering
Observability
AnalysisState
Estimation

NetworkTopology

Bad Data
Processing

Bus Load
Forecasting

Limit
Checking
Emergency
Control

External
Network Model

Restorative
ControlContingency
Selection

図A セキュリティ
コントロールにおける状態推定の役割
図Contingency
Evaluation

PreventiveControlOn-line
Load Flow

Exit

SecurityControl

6研究背景

スマートグリッド環境下の送電ネットワー
クではー広域連系制御の重要性

海外ではPMU
設置数顕著に増大

ーネットワークの大規模化
PMU(Phasor Mueasurement Unit)の使用

系統解析手法高速化(状態推定に着目）

7

PMUの設置状況
米国： 500台（2014年までに1200台）
 中国： 1717台


8

PMU
PMUの利用により、スマートグリッドの自動化が可能
 例として、PMU情報を利用して－負荷遮断
－負荷制御
－故障検出
● －状態推定
ー安定度解析など
9

PMUを用いた状態推定
従来型の送電ネットワークでは、数分ごとにデータを収集し、状態推定を実施
 他方、スマートグリッド環境下の送電ネット
ワークでは20ｍｓ～１00msごとにデータ収集
状態推定の高速化（まずは1０００ノード目標）10

状態推定の研究分野





不良データの検出と抑制
メータの最適配置
状態推定の高速化アルゴリズム
階層的状態推定ネットワークトポロジーの同定
ロバスト状態推定
トポロジー可観測性解析

11トポロジー可観測性
数値的可観測性

図B

トポロジー可観測性の位置付け

12

トポロジー可観測性解析（TOA)
状態推定を実施する前に,系統状態が状態推定を実施できることが可能かどうかを必ず確認する必要
 具体的には,観測値が少なくとも一つメータに対応しているかを調べる問題。もし,対応している場合は,「ネットワークはトポロジー可観測である」と言う。
トポロジー可観測性解析（TOA）とは？
1324

1

523

観測値
(a) Observable network(b) Unobservable network
Fig. 1. Observable and unobservable networks

4513

14

従来のTOAの研究
Wollenberg:問題の提起
 Clements:グラフ理論
 Monticelli &Wu:行列の行列式
 Quintana: マトロイド理論
 Mori: 最小木トポロジー可観測性解析の定式化（Krumpholz, et al.,’80)n母線から構成される電力系統においてｍ個の観測値集合 観測方程式

ｚ＝h(x) ＋ ｖ




15(１)

線形化すると

ｚ＝H  x＋ｖ(２)

可観測性とはrank(H)=2n-1(３)rank(H Pq )= n-1(６)rank(H QV ) = n-1(７)

PQ分割してトポロジー可観測性解析における評価すべき事項

16

ネットワークがトポロジー可観測であるかどうか ？
 ネットワークにおいて可観測な最大サブネットワーク（最大可観測アイランド）の同定
 ネットワーク全体を可観測にするために必要な擬似観測値が必要なノードの同定

17

可観測アイランド
可観測アイランド
可観測アイランド

最大可観測アイランド

図C 最大化観測アイランドの同定

最小木を用いたトポロジー可観測性解析

18

ネットワークのブランチにメータ設置されている場
合はブランチの重みを０,そうでない場合は1と定義することによってスパニングツリー（張木）の重みの総和を最小化する手法である。
 ここでスパニングツリー（張木）とはグラフ理論において与えられたグラフのノードを全て接続するツリーのことである。最小木を用いたトポロジー可観測性解析手法の数学的定式化は以下のとおりである。
最小木を用いたトポロジー可観測性解析(グラフ理論の応用）
最小木を用いたトポロジー可観測性解析
手法の数学的定式化は以下のとおりである。
ｗ（T Pq）＝ｗｂi min(８)但し, w(・): スパンニングツリー ・の重みの総和,：グラフGPqのスパンニングツ
リー,bi: ブランチi,ｗｂi: ブランチiの重み

19

20

参考文献
H. Mori and S. Tuzuki, "A Fast Method
for Topological Observability Analysis
Using a Minimum Spanning TreeTechnique," IEEE Trans. on PowerSystems, Vol. 6, No. 2, pp. 491500(1991).

21

従来の系統分割の研究
手法

カットセッ
ノード数均実行可能解
ト数最等化のチェック
小化

ネットワークロバスト化

Iirving○○

X

X

Mori○○

○

X

提案法

○○○

○

22

参考文献


M.R, Sterling and W.H.R. Sterling,"Optimal Network Teariniｇ SimulatedAnnealing“, IEE Proceeding, 137, Pt.
C, No. 1, pp. 69-72,Jan , 1988.
H. Mori and K. Takeda, “SimulatedAnnealing for Power System
Decomposition," IEEE Trans. on
Power Systems, Vol. 9, No. 2, pp.
789-795, May. 1994.

23

提案法
ネットワークを複数のサブネットワークに分割し,それぞれのサブネットワークにおいて最小木を用いたトポロジー可観測性解析を行うことを提案する。
 ただし,ネットワークの分割法として,サブネットワーク間のカットセット数最小化および各サブネットワークにおけるノード数均等化を最適化することを考える。
24

提案法のアルゴリズム
Step 1: 初期設定する。
 Step 2: ネットワーク分割を行う。
 Step 3: 得られたサブネットワークにおいて最小木を用いたトポロジー可観測性解析を行い,サブネットワークのトポロジー可観測性を評価する。
25

ネットワーク分割
ネットワーク分割して得られたサブネットワークはほぼ同一のノード数を持つべきである。
 サブネットワーク間のカットセット数は最小化されるべきである。
 得られたサブネットワークは実行可能解であるべきである。
26

ネットワーク分割の数学的定式化
目的関数：
KH



nk2  b 2  k 1

制約条件：
…

K

 p  min（14）kk 1K ni  N.

(15）

k 1

但し,nk:サブネットワークkのノード数,K:サブネットワークの総数,ｂ：サブネットワーク
間のカットセット数,β：係数, N: ネットワーク全体のノード数

27

ネットワーク分割の数学的定式化
実行可能解がある場合

pｋ＝１/ Πdet(GiTGi)
実行可能解がない場合

pｋ＝１００００Isolated Node
Subnetwork 2

Subnetwork 1

図D IEEE14母線系統における非実行可能解

28

29

シミュレーション
条件
Part 1: スパンニングツリーの評価手法：
グラフ理論のクルスカル法
例題系統：IEEE 118母線、235母線,586母線、1169母線
Part 2：系統分割の最適化手法
山登り法(ハミング距離２）
例題系統： W&H 6母線、IEEE１４母線系統
IEEE 30母線, Garver 46母線
初期条件： １０００個の乱数で最良値評価

30

図E IEEE1１８母線系統

31

最小木(クルスカル法)の計算時間評価
600

CPU Time(ms)

１１８母線
２３５母線
５７５母線
１１４９母線

ほぼ線形！

500
400
300
200
100
00200400600

ノード数800

1000

1200

1400

図F最小木の計算時間評価図A32

各例題系統における系統分割のコスト

Systems

Cost

620

1410130455

461064

33１４３６５２

図G Ward & Hale 6 母線において得られた解34

図H IEEE14母線系統において得られた解35

図I IEEE30母線系統において得られた解36

図J Garber 46母線系統において得られた解37

本稿では,電力系統静的状態推定のトポロ
ジー可観測性解析のための並列化手法を提案した。
 提案する手法は,最適分割された複数のサブネットワークにおいてグラフ理論の最小木を用いたトポロジー可観測性解析を行い, ネットワーク全体がトポロジー可観測であるかどうかを評価する手法である。
38

38

Ｐａｒｔ ２ 送電系統拡張計画のための送電系統分割

森 啓之
明治大学

3939

概要

目的
背景
提案法
シミュレーション
まとめ

4040目的

送電系統拡張計画のための系統分割のための多目的MemeticAlgorithm手法を開発する。

41

41

研究背景


送電系統拡張計画手法の動向－設置コスト削減手法
ー多目的メタヒューリスティクス応用（パレート解）を直接求める手法－負荷の不確定を考慮した手法(ノード間の相関性を考慮したモンテカルロシミュレーション）－Ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｒｅｌｉａｂｉｌｉｔｙ（確率的信頼度） ＥＥ
ＮＳ（Ｅｘｐｅｃｔｅｄ Ｅｎｅｇｙ Ｎｏｔ Ｓｕｐｐｌｉｅｄ）を考慮した手法－階層的最適化した手法

42

42

研究背景
系統分割とは

43

43

研究分割
 従来法

単一目的最適化

Ｆ＝ｗ１ｆ１＋ｗ２ｆ２
1
2

1 m
2
f1    ni  nmean    f 0  minm if 2  n cut   f 0  min

従来法- SA (Simulated Annealing) (Irving and Sterling, ‘90)
- PSA (Parallel Simulated Annealing) (Mori and Takeda, ‘94)
- ACO (Ant Colony Optimization) (Mori and Komatsu, ‘06)

44

44

多目的最適化-- 欠点 -単一目的最適化

 重み付けが経験的
 目的関数間の関係が明瞭でない

f = w1 * f1 + w2 * f2 + w3 * f3 → min
重み付総和法

多目的最適化
f1 → minf2 → minf3 → min

スカラー化手法
 別の問題に変換する

ε制約法
Minmax法

多目的メタヒューリスティクス
 解を直接探索し、評価する

45

45

提案法
多目的メタ：

SPEA2

山登り法

• Memtic Algorithm( MOMH+ Local Search )の開発

46

46

Background(4/4)
SPEA2

f2bdominatedadominate

f1

Meiji University

Drawbacks of GASearch

47fCase 1: Inappropriate
Parameter Setting
The Insufficient Iterations ofGenerations

0: GA searchxFig. C. Concept of Case

Meiji University

48fCase 2: Local Minimum
The Inappropriate
Genetic Operators Suchas Mutation andCrossover
In Practice, It is Hard toTune up the Parametersin Large-scale problems.

x0: GA search

Fig. D. Concept of Case

Meiji University49f

MA (Memetic Algorithm )( Moscato, et al., ‘89 )- To Enhance Solution
Qualities of Set in GA
Search in a Way That
Combines GA with LSx：Search of LS：Search of GAFig. E. Concept of MAMeiji University

50

Integration Strategies of MA
GA then LS- To Carry out LS After GA
GA with LS- To Carry out LS at Each GA Search
InitialSolution
Setcrossoverselection

Local
search

Output theSolution
set

Fig. F. Flowchart of GA then LS

51

51

提案法
• 定式化
Objective Function：
12

1 m
2
f1    ni  nmean    f 0  minm i

ノード数均等化

f 2  n cut   f 0  min

カットセット数最小化

12

1 m2
f 3    ri  rave    f 0  min
m i


発電と負荷のバランス

但し，m: No. of Subnetworks, ni: No. of Nodes, nct: No. of Cut Sets, ri: Difference
Between Generation And Load, f0: Penalty Function Related to Connected(Connected： 0, Disconnected： 1), α: Penalty Coefficient of f0

5252

提案法
Flowchart5353

シミュレーション条件
Test System : 46-node Network with 87
Branches [6] No. of Subnetworks : 4
 No. of Combinations : 2.063×1026


5454

シミュレーション条件
Parameters
Parameter

Value

Population Size

200

Archive Size

100

Crossover Rate

1.00

Mutation Rate

0.05

Generations

5000

5555

シミュレーション結果

BalanceNo. of Bus

Cut Set5656

シミュレーション結果Methodf1
f2f3
Best cost function 0.5
10 0.102
Worst cost function 12.46 30 20.289
Average
6.30 14.89 8.42
SPEA2
No. of Pareto
100
solutions
CPU time
346.5[s]Best cost function 0.5
10 0.102
Worst cost function 12.46 30 20.29
Average
6.06 14.81 8.44
Proposed
No. of Pareto
100
solutions
CPU time
662.0[s]57

シミュレーション結果

57

5858

シミュレーション結果
RNI(Raito of Non-dominated Individuals)

CTS(Convergence of Two Set)

MS(Maximum Spread)UD(Uniformly Distribution)

59

59

シミュレーション結果
SS#1

SS#2

SS#3

SS#4

60

60

まとめ

系統分割のための多目的MAを開発した。
例題系統に適用し、従来法のSPEA2と比較し、良好な結果を得た。