切替え手順を考慮した事故復旧目標系統の最適化

(1)

中央大学理工学部情報工学科卒業研究論文

切替え手順を考慮した事故復旧目標系統の最適化

学籍番号 00D8101026F 野津誠

指導教員田口東教授 2004 年 3 月

(2)

あらまし

本論文では配電系統の事故復旧目標系統作成問題を扱う．事故復旧目標系統作成問題とは，配電系統において送電線の事故などにより系統の一部に供給支障が起きた際に，区間開閉器を切替えることで供給支障がなくなる系統を再構成する問題である．配電系統を電圧などの条件を除いた簡単なグラフとし，モデル化することで問題を定式化する．事故復旧目標系統作成問題は，組合せ最適化問題として定式化することができ，その解法として遺伝的アルゴリズムを適用する．

事故復旧処理操作として，区間開閉器の切替え手順を考慮しながら，復旧目標系統を作成する手法を提案する．提案した手法を用いて事故復旧目標系統作成問題を解いた結果を示し，提案手法の有用性を示す．

キーワード：事故復旧目標系統作成問題，切替え手順，遺伝的アルゴリズム

(3)

近年，配電系統を扱う分野では，配電系統を構成する際の自動化が積極的に推進されている．その一つとして，事故時の復旧操作があげられる．しかし，復旧目標系統作成問題や，切替え手順決定問題などで構成される事故復旧処理操作は，多くの範囲を人の判断に頼っているのが現状である．これまでの研究で事故復旧処理操作は，復旧目標系統作成問題を先に解き復旧目標系統を決定した後，切替え手順決定問題を解くというように，別々の問題を組み合わせて解かれていた．

本論文では，復旧目標系統作成問題と切替え手順決定問題をこれまでのように別々に最適化するのではなく，復旧目標系統を作成する過程で切替え手順を考慮に入れることで，

復旧目標系統と切替え手順を同時に最適化する手法を提案する．

(5)

第 2 章事故復旧目標系統作成問題

事故復旧目標系統作成問題とは，事故などで配電系統の一部に供給支障が起きた際に，

系統の区間開閉器を切替えることで，供給支障がなくなる系統を再構成する問題である．

この問題は区間開閉器の開閉状態を変えることにより，最適な系統を再構成する組合せ最適化問題として定式化することができる．

本論文では，区間開閉器の切替え手順を考慮するため，事故復旧目標系統作成問題を，

事故等により供給支障が発生した系統から供給支障が解消された系統へ切替えるまでの供給支障電力量の最小化問題として定義する．

2.1 配電系統のグラフ表現

配電系統は，工事，事故等により系統が一部停電した場合に備えて，他の系統から電力を融通できるようにメッシュ状の構成をしている．通常は区間開閉器をオン，オフすることによりループを作らない放射状系統のネットワーク構成で運用されている．

20

5

10 5 負荷量

25

15

10

50 30 30

60

50 50 30

40 60

20

線路容量

電源

on 20

off

図

2.1

配電系統モデル

本論文では配電系統を図

2.1

のようなグラフとして扱う．系統はループを作らない放射状の系統でなくてはならない．各ノードにはそれぞれ需要（負荷）がついている．各ブランチは区間開閉器と送電線を兼ねるものとし，線路容量の制約があるものとする．電源から流れる電流は各ブランチの線路容量を超えて流れることはできず，各需要点を通ったときに需要点の負荷量だけ電力は消費されるものとする．電源の容量は，電源と直接つながっているブランチの線路容量の和で表される．

(6)

2.2 供給支障電力と供給支障電力量

供給支障電力

供給支障が起こるパターンとして以下の二つの場合がある．

1.

物理的に電源から遮断されている場合

この場合は，送電線で事故が起こった直後のように電源からの供給が物理的に遮断されていることになり，供給支障電力は物理的に遮断されている需要点の負荷量の合計となる．

2.

物理的にはつながっているが線路容量により電力が供給されない場合

ブランチの切替えを行う過程で起こりうる．この場合の供給支障電力は線路容量により電流が流れないブランチの下位にある需要点の負荷量の合計となる．

本論文の系統モデルに対して，電源からの最大フローを計算し，各需要点の負荷量の合計との差をとることで上記の二つの場合に対して供給支障電力が計算できる．よって，本論文での供給支障電力の定義は以下のものとする．

供給支障電力各需要点の負荷量の合計値と電源からの最大フローとの差

供給支障電力量

供給支障電力量の定義は以下のものとする．

供給支障電力量供給支障電力と供給支障時間の積とする．ただし，各切替え操作に要する時間は同じとし，これを一単位時間と定義する．

図

2.2

に供給支障電力が区間開閉器を切替えることにより減少していく様子を示す．

ブランチの切替えブランチの切替え

供給支障電力量供給支障電力︵

M W

︶

事故発生

1回 2回 3回 4回

供給支障時間

(7)

2.3 問題の定式化

供給支障電力量を表す目的関数が最小になるように復旧系統を作成する．

_{[目的関数]}

最小化

∑

（但し）

= K

+

i

P

h

0

max i

i

N f

h = −

h

_i：切替え

i

回目の系統状態での供給支障電力（MW），

K

^{：切替え回数}

max

f

i ：切替え

i

回目の系統状態での最大フロー，

N

：全ての需要点の負荷量の合計

P

：ペナルティ

ただし，

i = 0

は事故直後の系統状態とする．

[制約条件]

1.

放射状制約：系統がループを作らず放射状にならなくてはならない．

各負荷への供給電源は一つでなくてはならない．

2.

線路容量制約：電源から流れる電流は，ブランチの線路容量を超えて流れることはできない．

3. 電源容量制約：各電源の部分系統の負荷量の総和は，電源の容量を超えてはなら

ない．

一般には，電圧降下の制約条件も考慮する必要があるが，本論文では対象外とする．

ペナルティが加えられる場合

1.

切替えの途中で供給支障電力が増えた場合．

供給支障電力が増えるたびにペナルティとして目的関数に

20

を加える．

2.

切替え操作を最後まで終えた状態の系統の供給支障電力が

0(MW)でない場合．

残っている供給支障電力

× 10

だけ目的関数に加える．

(8)

第 3 章解法アルゴリズム

本章では，本論文で対象とする問題を解くために用いるアルゴリズムを説明する．扱う問題は組合せ最適化問題であり，大規模な配電系統においては探索空間が膨大になり，求解が非常に困難となる．そこで本論文では組合せ最適化問題を解く手法として遺伝的アルゴリズムを適用した．

3.1

で遺伝的アルゴリズムについて説明し，放射状系統を作成するアルゴリズムと最大フローを計算するアルゴリズムを

3.2，3.3

で説明する．3.2，3.3については参考文献[5]から引用した．

3.1 遺伝的アルゴリズム

遺伝的アルゴリズムの概要

遺伝的アルゴリズムは

1960

年代に

John Holland

によって考案された，生物の進化を工学的に模倣して構築されたアルゴリズムである．遺伝的アルゴリズムでは，個体によって状態空間の要素を表現する．通常は一つの個体が一つの状態を表し，複数の状態を表すために個体集団を形成する．この集団のことを母集団と呼ぶ．母集団の中で環境に適した個体ほど次世代に残されやすくすることにより，段階的に最適解を求めるのが遺伝的アルゴリズムの特徴である．

遺伝的アルゴリズムでは，個体を設計変数の値がコード化された染色体という文字列で表現する．染色体をデコード化することによって設計変数を読み出し，目的関数の値を計算する．このとき染色体の構造のことを遺伝子型，これによって定まる個体の形質を表現型と呼ぶ．遺伝的アルゴリズムの遺伝子操作はコード化された染色体に対して行う．

遺伝的操作

遺伝的アルゴリズムでは，主に次のような遺伝的操作を用いる．

Ⅰ. 選択

世代

t

^{の個体集合中の各個体}

i

^{について，その適合度} に応じて，次の世代に残す個体を選択する．トーナメント選択やルーレット選択などがある．また，最も適合度の高い個体を無条件に次世代に残すというエリート保存戦略がある．

g

i

(9)

ルーレット選択

母集団内の各個体の適合度とその合計を求めて，適合度の合計に占める各個体の適合度の割合を選択確率として個体を選択する．

エリート保存戦略

遺伝的アルゴリズムによる探索では，良い個体が一度発見されたとしても，それが交叉や突然変異などで失われることが少なくない．探索の効率化という観点からすると，最良の個体を残しておいて，そのまわりを集中的に探索することが好ましい．そこで各世代の個体集団の中で，最大の適合度を持つ個体に関しては交叉や突然変異の対象とはせずに無条件で次世代に残すという戦略が用いられる．

Ⅱ. 交叉

個体集合内の個体をランダムに

2

個ずつ組み合わせ，ある確率（交叉率）で，二つの個体の遺伝子を部分的に交換する．一点交叉や多点交叉，一様交叉などがある．

Ⅲ. 突然変異

各個体について，ある確率（突然変異率）で，各遺伝子座の遺伝子を他の対立遺伝子と入れ替える．突然変異により，交叉だけでは生成できない子を生成して個体群の多様性を維持することができる．

遺伝的アルゴリズムのパラメータ

・世代数

解の収束が遅い問題では大きく設定しなければならないが，早く収束する問題では世代数が大きいと無駄な計算を繰り返すことになる．

・母集団サイズ（個体数）

遺伝的アルゴリズムは多点探索であり，その探索点にあたるのが個体である．個体数が多ければ広い範囲を探索することが可能になるが，多すぎると収束が遅くなるため計算負荷が高くなる．また，少なすぎると広い範囲を探索できないため局所解に落ち込む可能性が高くなる．

(10)

・エリート個体数

エリート保存戦略で無条件に次世代に残す個体の数．エリート個体が多すぎると，その遺伝子が母集団の中で急速に広がって局所解に陥る可能性がある．

・交叉率

選び出した二つの個体同士がどの程度の確率で交叉するかを交叉率と呼ぶ．0.5〜1.0 が一般的である．

・突然変異率

染色体の各遺伝子座がどの程度の確率で突然変異するかを突然変異率と呼ぶ．

0.1

以下が一般的である．

終了条件

交叉選択

突然変異

NO

YES

評価

終了初期個体

の生成

図

3.1 遺伝的アルゴリズムの流れ

(11)

3.2 最小全域木作成のアルゴリズム

配電系統は一般に放射状で運用されている．放射状系統を作成するアルゴリズムとして最小全域木を求める

Kruskal

のアルゴリズムを用いる．

最小全域木問題

連結な無向グラフ

G = ( V , E ), V = n , E = m

の各辺

e ∈ E (G )

^{に非負の重み} ^が割り当てられているネットワーク

) (e w )

, ( G w

N =

において，すべての点を連結にする部分グラフのうちで，重み最小のものを求める問題を最小全域木問題という．最小全域木を求める

Kruskal

のアルゴリズムを以下に示す．

Kruskal

のアルゴリズム

1. E ( G ) = { e

₁

, e

₂

, L , e

_m

}

を

w ( e

₁

) ≤ w ( e

₂

) ≤ L ≤ w ( e

_m

)

と，重みの小さい順に並べる．

φ

= :

T

とおく（最終的に求まる

T

は最小全域木の辺集合を表す）．

2. i := 1

から

1

ずつ増やして

m

になるまで

(a )

を繰り返す．

)

(a

T ∪ { e

_i

}

が閉路を含まなければ，

T : = T ∪ { e

_i

}

と更新する．

2.

ので求まる

T

が本の辺を含むとき，

T

^{は本の辺からなる}

G

^{の閉路を含まない}

部分グラフのうちで重みが最小のものになっていることが示せるので，最終的に求まる全域木

)

(a k k

T

は

n − 1

本

( n = V ( G ) )

の辺からなるの閉路を含まない部分グラフのうちで重みが最小のものになっている．

G

3.3 Ford-Fulkerson の最大フローアルゴリズム

最大フローを求める

Ford-Fulkerson

のアルゴリズムは，ゼロフローから出発してフローを更新していくが，その際フローの残余容量ネットワークを用いて入口から出口

t

へのパス

f f N ( f ) s

P

を求め，そのパス

P

に沿ってできるだけフローを流してを増加し更新して，最終的ににからへのパスがなくなるまで繰り返す，というものである．

f )

( f

N s t

フローに関する残余容量ネットワークは，以下のように定義される残余容量が正の辺からなるネットワークである．各辺

f N ( f )

) ( ) ,

( v w E G

e = ∈

^{に対して，} ^なら

ばさらにだけ流せるので，それが

) ( )

( e cap e f <

) ( ) ( )

( e cap e f e

cap

_f

= − e = ( v , w )

の残余容量であり，

(12)

0 ) ( e >

f

ならばだけ減らせるので逆向きの仮想的な辺を考え，その辺

に沿ってだけ流せるので辺の残余容量はと

なる．したがって，仮想的な辺の全体をとすると，フローに関

する残余容量ネットワークは

) (e

f e

^R

= ( w , v )

) , ( w v

e

^R

= f (e ) e

^R

= ( w , v ) cap

_f

( e

^R

) = f ( e ) )}

(

| { )

( G e e E G

E

^R

=

^R

∈ f

) , , ), ( ( )

( f G f cap s t

N =

_f

) 0 ) ( ( ) ( ) (

, )) ( )

( ( ) ( ) ( )

(

}, 0 ) (

| ) ( {

)}

( )

(

| ) ( { )) ( (

>

=

<

−

=

>

∈

∪

<

∈

=

e f e f e cap

e cap e

f e f e cap e

cap

e f G E e e cap e f G E e f G E

R f f

R R

と定義できる．

以下に

Ford-Fulkerson

の最大フローアルゴリズムを示す．

Ford-Fulkerson

の最大フローアルゴリズム

1. f := 0

（すなわち，各辺

e ∈ E

に対して，

f ( e ) : = 0

）とおく．

2. (a )

f

に関する残余容量ネットワーク

N ( f )

を作る．

)

(b

N ( f )

^において

s

から

t

へのパスを求める．そのようなパスが存在しないときはは最大フローになり終了する．

P

f s

から

t

へのパス

P

が存在するときは，

0 }

| ) ( min{

)

( = ∈ >

∆ P cap

_f

a a P

^を求め， ^{上の各辺の流量を} ^だけ増加する．すなわち，

P ∆ (P )

⎩ ⎨

⎧

∈

∆

−

∈

∆

= +

) (

) ( )

) ( (

P e P e f

P e P e e f

f

R

と更新して

(a )

に戻る．

(13)

第 4 章問題の解法

本章では，事故復旧目標系統作成問題を提案手法で解く流れを説明する．本論文では遺伝的アルゴリズムを二つの段階に分けて用いる．それらを第

1

段階と第

2

段階と呼ぶことにする．第

1

段階は目標系統を決定する組合せ最適化問題であり，第

2

段階は最適な切替え手順を決定する順列決定問題である．

4.1 解法の流れ

1. 第 1

段階では復旧目標系統を探索する．初期個体として仮の目標系統を個体数分だけ

生成する．この目標系統の評価値は，第

2

段階で得ることになる．

2. 第 2

段階では第

1

段階で得た仮の目標系統と初期系統から，切替対象のブランチの集

合を得て最適な切替え手順を決定する．この切替え手順から供給支障電力量を計算し，それを第

1

段階の仮の目標系統の評価値とする．

3. 第 1

段階でその評価値をもとにより良い仮の目標系統を探索する．

4. 2, 3

を指定した回数だけ繰り返す．

ここで，初期系統とは事故が起こる前の通常運用している系統のことである．

第1段階第2段階

初期個体の生成

選択

突然変異交叉終了条件

初期系統と仮の目標系統から初期個体を生成

仮の目標系統

評価

NO

終了条件

選択

交叉

突然変異

評価値

NO YES

YES

終了

図

4.1

解法の流れ

(14)

4.2 第 1 段階の解法

第

1

段階では，仮の目標系統を決定する組合せ最適化問題に，遺伝的アルゴリズムを適用する．初期個体の生成，交叉，突然変異に

Kruskal

のアルゴリズムを利用する．

第

1

段階の流れ

1.

初期個体をランダムに個体数

M

₁だけ生成する．

2. M

₁個の個体をそれぞれ第

2

段階へ受け渡し評価値を得る．

3.

評価値に従ってルーレット選択により交叉，突然変異を行う個体を選択する．

4.

交叉率に従って交叉を行う．

5.

突然変異率に従って突然変異を行う．

6.

次世代の個体を選択する．

2.から 6.の操作を決められた回数だけ行う．

第 1 段階の遺伝的アルゴリズム

第

1

段階の遺伝的アルゴリズムでは，遺伝子の表現方法に

Raidl

らによって提案されたエッジセット[1]を用いる．エッジセットは木を構成する枝（ブランチ）の集合により全域木を表現するもので，交叉や突然変異に最小全域木作成アルゴリズムを用いることで致死遺伝子を生成しない利点がある．

遺伝子の表現方法

各ブランチに対応して，ブランチがオン（閉状態）ならば

1，ブランチがオフ（開状態）

ならば

0

が格納された配列で表現する．

0

状態

ブランチ番号

1 2 3 1 0 0

20 21 22 23

図

4.2

遺伝子表現

0 1 1 1

1

(15)

初期個体の生成方法

1.

事故が起きたブランチの重みを非常に大きな値

(>> 1000 )

とする．

2.

その他のブランチの重みを

1

から

1000

までのランダムな値とする．

3. Kruskal

のアルゴリズムにより全域木を生成する．

4. 1. 2. 3.の操作を個体数の数だけ繰り返す．

上記の操作により，事故が起きたブランチを含まない，ランダムな放射状系統の個体が個体数分だけ生成できる．これらの個体を初期個体とする．

評価

第

2

段階へ個体の情報を受け渡し，評価値を得る．

交叉

Kruskal

のアルゴリズムを利用して交叉を行う．

交叉後の子の性質

・両方の親がオンであるブランチは必ず含まれる．

・両方の親がオフであるブランチは必ず含まれない．

・どちらかの親がオンであるブランチはランダムに含まれる．

交叉の方法

1. 0

から

1

までの一様乱数を発生させ，その値が交叉率よりも小さければ交叉を行い，

そうでなければ交叉は行わない．すなわち，値が交叉率よりも小さければ以下の

2

から

7

の操作を行い，そうでなければ交叉が終了となる．

2.

両方の親のブランチがオンであるブランチの集合を集合

A，どちらかの親のブランチ

がオンであるブランチの集合を集合

B，両方の親のブランチがオフであるブランチの

集合を集合

C

とし，集合

A，集合 B，集合 C

をそれぞれ求める．

3.

集合

A

のブランチの重みを

0

とする．

4.

集合

B

のブランチの重みを

1

から

1000

5.

集合

C

のブランチの重みを非常に大きな値

(>> 1000 )

とする．

6. Kruskal

7. 2

個の個体を生成する為に，2から

6

の操作を

2

回行う．

上記の操作により，集合

A

のブランチが優先的に全域木を構成するブランチとして選ば

(16)

れ，次に集合

B

からランダムにブランチが選ばれ全域木が生成される．

突然変異

Kruskal

のアルゴリズムを利用して突然変異を行う．

突然変異の方法

1.

ブランチがオンのブランチの集合を集合

D，ブランチがオフのブランチの集合を集合 E

として，集合

D，集合 E

2.

集合

E

に含まれているブランチの重みを

1

から

1000

3.

集合

D

の各ブランチに対し，

0

から

1

までの一様乱数を発生させ，その値が突然変異率よりも小さければ，ブランチの重みを非常に大きな値とし，そうでなければブランチの重みを

0

とする．

) (>> 1000

4.

事故が起きたブランチの重みを非常に大きな値

(>> 1000 )

とする．

5. Kruskal

突然変異の対象は状態がオンである各ブランチであり突然変異が起こるとそのブランチはオフになる．すなわち，突然変異が起きなかったブランチは優先的に全域木を構成するブランチとして選ばれるが，突然変異が起きたブランチは全域木を構成するブランチに選ばれなくなる．

選択

ルーレット選択を採用する．

評価値となる供給支障電力量は値が小さいほうが良いので評価値の逆数をとして以下の選択確率により選択を行う．は個体とする．

) (s f

P s

∑

=

_N

i i

i

f s

s P f

1

( )

)

(

N

は個体数

次世代の個体の選択

世代での個体集合をとする．にルーレット選択を適用し，その個体に交叉，

突然変異を行った個体集合をとする．と

i X (i ) X (i )

) (i

X ′ X (i ) X ′ (i )

の中から，評価値が良いものから順に次世代の個体として個体数分だけ選択し

X ( i + 1 )

を得る．

(17)

4.3 第 2 段階の解法

第

2

段階では事故直後の系統から目標系統への切替え手順を決定する．切替え手順から供給支障電力量が求まり，それが第

1

段階の各個体に対する評価値となる．目標系統とは第

1

段階から受け渡された系統のことである．

切替え対象となるブランチは，初期系統と目標系統で状態が異なっているブランチとなる．すなわち，初期系統ではオンのブランチが目標系統ではオフ，または，初期系統ではオフのブランチが目標系統ではオンになっているブランチが切替え対象のブランチとなる．

これは各ブランチへの切替え操作が高々一回であるという仮定に基づいている．

第

2

段階の流れ

1.

第

1

段階から目標系統を受け取り，初期系統と比べ，初期系統がオフで目標系統がオンであるブランチの集合（集合

F

とする）と，初期系統がオンで目標系統がオフであるブランチの集合（集合

G

とする）とに分ける．

2.

個体数だけ集合

F

のブランチに

1

から

1000

までのランダムな整数値を与える．

これが第

2

段階の初期個体となる．

M

2

3.

切替え手順を決定し，手順に従って切替えを行い供給支障電力の合計を得て，それを評価値とする．

4.

評価値に従ってルーレット選択により個体を選択する．

5.

交叉率に従って交叉を行う．

6.

突然変異率に従って突然変異を行う．

3.から 6.の操作を決められた回数行い評価値を第 1

段階の個体へ受け渡す．

第 2 段階の遺伝的アルゴリズム

第

2

段階の遺伝的アルゴリズムでは遺伝子の表現に

Bean

らによって提案されているランダムキー[2]を用いる．ランダムキーによる順列表現では，各々の要素にあらかじめ決められた範囲内の値が与えられ，それらの値の数値列を考える．要素の値をキーとして昇順，

あるいは降順に整列した場合の要素番号の並びで順列を表すものである．

遺伝子の表現方法にランダムキーを用いることで，交叉，突然変異を行っても致死遺伝子が発生しない利点がある．

(18)

遺伝子の表現方法

初期系統がオフで目標系統がオンであるブランチの配列で表現する．それぞれのブランチには

1

から

1000

までの整数値がランダムに与えられている．

6

ランダムな値

ブランチ番号

14 17 19 22 500 300 150 100

250

図

4.3 遺伝子表現

初期個体の生成方法

1.

ブランチの集合，集合

F

と集合

G

2.

集合

F

の各ブランチに

1

から

1000

のランダムな整数値を与える．この操作を個体数分だけ行う．

個体

1

個体

M

2

6 14 17 19 22 500 300 150 100

250 6 14 17 19 22 20 970 550 750

400

図

4.4 初期個体

評価

切替え手順の決定

切替え手順は，集合

F

のブランチと集合

G

のブランチを組み合わせることで決定する．

ただし，切替え作業中においても放射状制約は満たされるものとする．しかし，系統は放射状構成になっているので，ブランチをオンにする際に，事故によって遮断されている区間をつなぐブランチをオンにする場合以外では必ずループを形成することになる．そこで本論文では，ループが形成された場合，そのループを形成しているブランチのいずれかをオフにすることにし，ループができていた時間を

0

と考える．すなわち，この

2

回の切替え（オン→オフ）にかかる時間を

1

回の切替え時間とみなす．

(19)

1.

集合

F

を与えられたキーが小さい順にソートし，ブランチをオンにする手順を決定する．

2.

集合

F

の手順に従いブランチをオンにする．

3.

ブランチをオンにしたことでループが形成された場合，ループを形成しているブランチを集合

G

から選び出し，選ばれたブランチをオフにする．

4.

集合

F

のブランチを全てオンにするまで

2. 3.

を繰り返す．

図

4.5

に切替え手順が決定される様子を示す．集合

F

のキーがソートされ，集合

F

の切替え順序が決定する．集合

F

の切替え順序に従って，まずはブランチ番号

14

を

on

にする．

ブランチ番号

14

を

on

にした結果ループは形成されなかった．このことは，ブランチ番号

14

は事故により遮断された区間をつなぐブランチであったことを示す．次にブランチ番号

6

を

on

にした結果ループを形成した．そこで集合

G

からループを形成しているブランチ番号

9

が選ばれた．以下同様に切替え手順が決定される．

6 14 17 19 500 300 100

250

ソート

17 19 6 14

順序決定

17 19 6

14 4 9 29

集合F 集合G

14 6 9 19 4 17 29

on on on on off off off

切替え手順

ループを形成したので集合Gからループを形成するブランチを選ぶ

図

4.5 切替え手順の決定

評価の方法

初期系統から目標系統へ，切替え手順に従ってブランチを切替えるごとに最大フローを計算して供給支障電力の合計を得る．

(20)

1.

初期系統を起点とし，事故が起きたブランチをオフにして，供給支障電力を求める．この値が初期供給支障電力となる．

2.

上記で決定した切替え手順に従って，ブランチを切替えるごとに供給支障電力を求める．

3. 1. 2.

で求めた供給支障電力を合計し，評価値とする．

ただし，以下の場合にはペナルティを設ける．

・ブランチを切替えることで供給支障電力が増える場合．

・最終的な供給支障電力が

0

にならない場合．

交叉

交叉の方法

1. 0

から

1

までの一様乱数を発生させ，その値が交叉率よりも小さければ交叉を行い，

そうでなければ交叉は行わない．すなわち，値が交叉率よりも小さければ以下の操作を行い，そうでなければ交叉は終了となる．

2.

交叉点をランダムに決める．

3.

交叉点で一点交叉を行う．

6 250

14 17 19 22 100 500 300 150

6 14 17 19 22 200 600 400

図

4.6 交叉の例

交叉子1

子2

6 250

14 17 19 22 100 500 600 200

6 14 17 19 22 400 300 150 700

50 700

50

親1

親2

突然変異

突然変異の方法

(21)

1.1 0

から

1

までの一様乱数を発生させ，その値が突然変異率よりも小さければそのブランチのキーの値を

1

から

1000

までのランダムな値で置き換える．

6 14 17 19 22 500 300 150 100

250 6 14 17 19 22 500 300 150 400

250

突然変異

図

4.7 突然変異の例

選択

ルーレット選択とエリート保存戦略を用いる．

ルーレット選択では第

1

段階と同様に選択確率

P

を求め選択を行う．

エリート保存戦略では，エリート個体数を

1

つに設定した．エリート保存戦略により，

各世代で最も良い解は必ず次世代に残る．

(22)

第 5 章提案手法適用の結果

本章では，図

5.1

に示す系統モデルに提案手法を適用し，最適な復旧目標系統と切替え手順を求める．ケース

1

を，ブランチ番号

12

に事故が起きた場合，ケース

2

を，ブランチ番号

0

に事故が起きた場合として二つの問題を解いた結果を示す．

5.1 使用する系統モデル

図

5.1

に示すような，ノード数

28，ブランチ数 40

の系統を系統モデルとして使用する．

各ノード内の数字が各ノードの需要（負荷）を表し，各ブランチに付いている黒の数字がブランチの番号を，赤の数字が線路容量を表す．三つの赤いノードは電源を表す．図の状態は事故が起きる前の初期系統を表す．

本論文ではブランチ番号

12

に事故が起きた場合と，ブランチ番号

0

に事故が起きた場合の二つのケースの問題を，提案手法を適用し解く．

図

5.1 使用する系統モデル

(23)

5.2 提案手法による計算機実験の結果

5.2.1 ケース 1 （ブランチ番号 12 に事故が起きた場合）

初期系統の状態から，ブランチ番号

12

に事故が起きた場合の最適な復旧目標系統と切替え手順を求める．

[遺伝的アルゴリズムにおける各パラメータ]

遺伝的アルゴリズムにおける各パラメータは，以下のとおりである．

第

1

段階

世代個体数：20

交叉率：0.4，0.6，0.8，1.0 突然変異率：0.03，0.06，0.10 終了世代数：50

第

2

段階

世代個体数：8 エリート個体数：1 交叉率：0.8 突然変異率：0.10 終了世代数：5

[最適解の保証]

ケース

1

において，分枝限定法を用いて解の全探索を行った．供給支障電力が一様に減少し，最終的に供給支障電力が

0(MW)になる解のうち供給支障電力量が 50

以下になる解を全て列挙する．

供給支障電力量切替え手順

46.0：

23 19 18 21 17 34 26

47.0：

23 19 18 34 26 21 17

50.0：

23 34 26 19 18 21 17 50.0：

19 23 18 21 17 34 26

49.0：

23 19 18 21 17 7 3 34 26

49.0：

23 19 18 21 17 7 6 34 26

49.0：

23 19 18 21 17 7 9 34 26

(24)

49.0：

23 19 18 21 17 7 10 34 26

49.0：

23 19 18 21 17 8 3 34 26

49.0：

23 19 18 21 17 8 6 34 26

49.0：

23 19 18 21 17 8 15 34 26

49.0：

23 19 18 21 17 16 14 34 26

49.0：

23 19 18 21 17 16 27 34 26

49.0：

23 19 18 21 17 28 14 34 26

49.0：

23 19 18 21 17 28 35 34 26

49.0：

23 19 18 21 17 29 27 34 26

供給支障電力量が

46

で，切替え手順が（23，19，18，21，17，34，26）の組合せが，

ケース

1

の最適解である．

[最適解が求まるまでの平均世代数]

表

5.1

は，第

1

段階の交叉率，突然変異率の各組合せにおいて，最適解が求まるまでの平均世代数と，最適解が求まらなかった回数を示したものである．それぞれのケースにおいて

10

回試行した．50世代までに最適解が求まらなかった場合は世代数

50

としている．

表

5.1 最適解が求まるまでの平均世代数と最適解が求まらなかった回数

突然変異率

交叉率

0.03 0.06 0.10

0.4 31.2 2

回

26.6 0

回

24.6 0

回

0.6 23.1 1

回

20.6 0

回

26.2 0

回

0.8 24.7 1

回

16.3 0

回

21.4 0

回

1.0 21.1 0

回

19.7 0

回

22.8 0

回

交叉率，突然変異率が共に最小の組合せである，交叉率

0.4，突然変異率 0.03

の場合が平均世代

31.2

と他の場合に比べて大きくなったが，原因として

50

世代までに最適解が求まらなかったことが

2

度あったことが挙げられる．突然変異率

0.03

の場合のみ，最適解が求まらないケースがあった．

(25)

[解の収束の様子]

交叉率

0.8，突然変異率 0.06

の組合せで問題を解いた．試行は

20

回行ったが全てのケースで

50

世代までに最適解が得られた．図

5.2

に

20

回試行を行った結果の一つを示す．図

5.2

のケースでは

15

世代目で最適解の

46

に到達した．

0 50 100 150 200 250 300 350

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 世代数

目的関数(MW)

各世代で一番良い解各世代の解の平均値

図

5.2 解の収束の様子

[復旧目標系統作成問題と切替え手順決定問題を別々に解いた場合]

ブランチ番号

12

に事故が起きた場合に，復旧目標系統作成問題だけを解くと，切替え回数が

7

回で作成できる供給支障電力

0(MW)の系統が一種類のみ求まる．それを図 5.3

に示す．図

5.3

の系統は事故復旧操作全体を通しての最適な復旧目標系統である為，提案手法で解いた場合と同じ最適解が求まる．

図

5.4

に最適な切替え手順で切替えを行った場合の供給支障電力が減少する様子を示す．

事故が起きた直後の系統の供給支障電力は

23(MW)であり，ブランチ番号 23

を

on

にすることで供給支障電力が

13(MW)に減少する．2

回目の切替えで，ブランチ番号

19

を

on

に

18

を

off

7(MW)に減少する．3

回目の切替えで，ブランチ番号

21

を

on

に

17

を

off

3(MW)に減少する． 4

回目の切替えで，

ブランチ番号

34

を

on

に

26

を

off

0(MW)となり終了する．

(26)

図

5.3 最適な復旧目標系統

23をon

19をon，18をoff

21をon，17をoff

34をon，26をoff

供給支障電力︵

M W

︶

事故発生

0 13 23

1回 2回 3回 4回

7

3

供給支障時間（切替え回数）

図

5.4 図 5.3

の系統の供給支障電力が減少する様子

(27)

5.2.2 ケース 2 （ブランチ番号 0 に事故が起きた場合）

初期系統の状態からブランチ番号

0

に事故が起きた場合の最適な復旧目標系統と切替え手順を求める．この場合では，復旧目標系統作成問題と切替え手順決定問題を別々に最適化する従来の方法では事故復旧操作全体を通しての最適解が求まらない可能性がある．

[遺伝的アルゴリズムにおける各パラメータ]

遺伝的アルゴリズムにおける各パラメータはケース

1

と同様である．

[最適解の保証]

ケース

2

において，分枝限定法を用いて解の全探索を行った．供給支障電力が一様に減少し，最終的に供給支障電力が

0(MW)になる解のうち供給支障電力量が 90

以下になる解を全て列挙する．

供給支障電力量切替え手順

86.0：

7 29 4 22 15 25 31 88.0：

7 29 4 19 15 23 20 90.0：

29 7 4 22 15 25 31

87.0：

7 29 4 22 15 33 31 34 39

90.0：

7 29 4 22 15 28 27 25 31

90.0：

7 29 4 22 15 34 26 25 31

90.0：

7 29 4 22 15 34 39 25 31

90.0：

7 29 4 22 15 34 39 33 31

88.0：

7 29 4 22 15 33 31 28 27 34 39

89.0：

7 29 4 22 15 33 31 28 27 16 3 34 39

89.0：

7 29 4 22 15 33 31 28 27 16 5 34 39

供給支障電力量が

86

で，切替え手順が（7，29，4，22，15，25，31）の組合せがケース

2

の最適解である．

[最適解が求まるまでの平均世代数]

表

5.2

は，表

5.1

と同様に，最適解が求まるまでの平均世代数と，最適解が求まらなかった回数を示したものである．それぞれのケースにおいて

10

回試行した．

50

世代までに最適解が求まらなかった場合は世代数

50

としている．

(28)

表

5.2 最適解が求まるまでの平均世代数と最適解が求まらなかった回数

突然変異率

交叉率

0.03 0.06 0.10

0.4 45.2 6

回

34.6 3

回

44.5 6

回

0.6 42.4 5

回

41.6 3

回

44.1 5

回

0.8 32.1 2

回

34.2 4

回

45.9 7

回

1.0 39.5 3

回

44.4 6

回

43.4 4

回

ケース

1

の場合と比べると最適解が求まるまでの平均世代数と，最適解が求まらなかった回数が共に増えた．ブランチ番号

0

は電源と系統を直接つなぐブランチなので，ブランチ番号

0

に事故が起きるとその電源は系統に電力を供給できなくなる．そのため，残りの二つの電源で系統を構成しなくてはならなくなり，より複雑な切替えが必要となっていることが，最適解が求まるまでの平均世代数と，最適解が求まらない回数が増えた原因としてあげられる．

[解の収束の様子]

交叉率

0.8，突然変異率 0.03

の組合せで問題を解いた．試行は

20

回行い，最適解が得られないケースは

5

回であった．図

5.5

に

20

回試行を行った結果の一つを示す．図

5.5

のケースでは

43

世代目で最適解の

86

に到達した．

0 100 200 300 400 500 600 700

1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49

世代数

目的関数(MW)

各世代で一番良い解各世代の解の平均値

図

5.5 解の収束の様子

(29)

[復旧目標系統作成問題と切替え手順決定問題を別々に解いた場合]

ブランチ番号

0

に事故が起きた場合に，復旧目標系統作成問題だけを解くと，切替え回数が

7

回で作成できる供給支障電力

0(MW)の系統が，図 5.6

と図

5.7

の二種類できる．図

5.6

の系統は事故復旧操作全体を通しての最適な復旧系統で，切替えが終了するまでの供給支障電力量が

86

であるが，図

5.7

の系統は切替え手順を考慮に入れると，切替えが終了するまでの供給支障電力量は

88

となり図

5.6

の系統よりも供給支障電力量が大きくなる．もし，復旧目標系統作成問題で図

5.7

の系統が解として与えられた場合，その系統に対して切替え手順決定問題を解いても最適解は得られない．図

5.8

は，図

5.6

の復旧系統を最適な切替え手順で切替えた場合の供給支障電力量が減少する様子を示し，図

5.9

は，図

5.7

の復旧系統を最適な切替え手順で切替えた場合の供給支障電力量が減少する様子を示す．

提案手法では復旧系統を作成する段階で切替え手順を考慮に入れているので，復旧系統を作成する過程で図

5.6

と図

5.7

の系統を比べることができる為，上記のような問題は起こらずに，事故復旧操作全体を通しての最適解が求まる．

(30)

図

5.6 切替え手順を考慮に入れた上での最適な復旧系統

図

5.7 切替え手順を考慮に入れた上での最適でない復旧系統

(31)

7をon

29をon，4をoff

22をon，15をoff

25をon，31をoff

M

︶

W

事故発生

1回 2回 3回 4回

45

26 4 11

0

図

5.8 図 5.6

6 7をon

29をon，4をoff

19をon，15をoff

23をon，20をoff

M

︶

W

11

事故発生

0 26 45

1回 2回 3回 4回

図

5.9 図 5.7

(32)

第 6 章おわりに

6.1 まとめ

本論文では，復旧目標系統を作成する過程で切替え手順を考慮に入れることで，復旧目標系統と切替え手順を同時に最適化する手法を提案した．配電系統の事故復旧操作である復旧目標系統作成問題について説明し，配電系統を簡単なグラフで表し問題の定式化を行った．復旧目標系統作成問題と切替え手順を決定する問題に遺伝的アルゴリズムを用いた．

遺伝的アルゴリズムを適用する際に，致死遺伝子を発生させない遺伝子表現であるエッジセットとランダムキーを用いることで，アルゴリズムの効率化を図った．

配電系統を簡単なグラフとして表した系統モデルに提案手法を適用した．事故が起きるブランチが違う二つのケースにおいて問題を解いた結果を示し，従来の方法では最適解が得られない場合にも提案手法を用いることで最適解が得られることを示した．

6.2 今後の課題

今後の課題を以下に示す．

・より大規模な配電系統の系統モデルや，本論文では無視した電圧降下の条件を加えた系統モデルに対して提案手法を適用し，その有用性を計る．

・解法のアルゴリズムを改良し，最適解がより効率よく求まるようにする．

(33)

謝辞

本研究を進めるにあたり，多くのご指導ご助言をいただいた中央大学理工学部情報工学科の田口東教授に深く感謝いたします．また，多くの協力と助言をいただいた田口研究室の大学院生，学部生の皆様に深く感謝いたします．

また，研究のテーマの決定から，研究内容まで多くのご指導ご助言をいただいた電力中央研究所の渡邊勇氏をはじめとする皆様に深く感謝いたします．

参考文献

[1] Gunter R. Raidl and Bryant A. Julstrom，”Edge Sets: An Effective Evolutionary Coding of spanning Trees，” IEEE Transactions on evolutionary computation，vol.7，

no.3，pp.225-239，June 2003．

[2] J.C Bean， ”Genetic algorithms and random keys for sequencing and optimization， ” ORSA Computing，vol.6，no.2，pp.154-160，1994．

[3] 栗原郁夫，松本一道，田中敏幸， “二次系統の供給信頼度解析システムの開発，”

電

気学会論文誌

B，vol.117-B，no.4，pp.585-593，1997．

[4] 澤敏之，古川俊行，小林康弘，田村滋， “遺伝的アルゴリズムを用いた最適な放射状

系統の作成手法，” 電気学会論文誌

C，vol.121-C，no.11，pp.1780-1787，2001．

[5] 浅野孝夫，今井浩，計算とアルゴリズム，オーム社，東京，2000．

[6] 三宮信夫，喜多一，玉置久，岩本貴司，遺伝アルゴリズムと最適化，システム制御情

報ライブラリー17，朝倉書店，東京，1998．

切替え手順を考慮した事故復旧目標系統の最適化

中央大学理工学部情報工学科 卒業研究論文