提案アルゴリズム

37

ネットワークの最適構成について考察し，構成するノードがサイクルに含まれる場合に 全点間信頼度が向上することを示している．例えば，図 2-7 の全ノードがサイクルに含 まれるx_k,1とその他のネットワークx_k,2を比較した場合，全点間信頼度はx_k,1が優 位である．すなわちネットワークのサイクルを判断することは，パレート最適解 探索の精度を上げるために有用と考えられる．

図2-7 ネットワークトポロジーと全点間信頼度の関係

38

表2-1 ネットワーク性質の組み合わせ

アルゴリズム

ネットワーク

の選択 エッジの選択

ランク 傾き サイクル 効率性 有効度

ARE 〇 〇 〇

ARV 〇 〇 〇

ASE 〇 〇 〇

ASV 〇 〇 〇

2.5.1 解のランクを用いるアルゴリズム

はじめに，部分ネットワークの選択基準に解のランク付けを用いるAREとARV

を示す．AREはエッジの選択指標にエッジの効率性 f_i を，ARVはエッジの有効 度vl_k(i)をそれぞれ用いたアルゴリズムである．

ここで，x(x₁,,0_i,,x_m) に対し，(x₁,,1_i,,x_m)である部分ネットワークを )i

1

(

x と表す．また，選択された部分ネットワークx_kに追加するエッジ数と，部 分ネットワークの選択対象とする解のランク範囲を，それぞれパラメータ ec と Rとして与えるものとする．ec は，1つのx_kから構成されるx_k1(x_k (1)_i)の数で あり，{x_k(1)_i(1),x_k(1)_i(2),,x_k (1)_i(ec)}X_k1となる．

アルゴリズムARE

STEP 1 (初期化)：選択対象とする解のランク範囲Rと，追加するエッジの本数ec を決定し，PX_r,k  (r1,2,,R)とする．kn1 とする．

STEP 2：k n1ならば，部分ネットワークx_kを全て列挙し，その集合X_kを構 成する．

STEP 3 (信頼度・コストの計算)：部分ネットワーク^x_kX_kに対し，改良factmem 法を用いて全点間信頼度を算出し，連結するエッジのコストの合計から構 築コストの計算を行う．

STEP 4 (パレート最適解の探索とネットワークの選択)：

2 ) 1 ( 

 n n

k のとき，

) (

1



^k

n i

Xi

pareto





を求め，計算を終了する．

39

2 ) 1 ( 

 n n

k のとき，_{r1,2,,R}に対して ( \ )

1

1 ,

,



^



 ^r

s

k s k

k

r pareto X PX

PX を求め

る．

STEP 5 (追加エッジの選択と次エッジ数ネットワークの構成)：

STEP5-1：k n1ならばi1,2,,mに対して f_i  p_i/c_iの計算を行う．そして ec

l  とする．

STEP5-2：部分ネットワーク ( )

1



^R , r

k r

k PX





px を選択する．

STEP5-3：x_i 0であるe_iから i E E

e f

imax{ \ }



 を満たすe_iを選択し，

} ) 1 (

1 {

1 k k i

k X

X _  _  px  とする．EE{e_i}，ll1とする．

STEP5-4：l=0 ならばSTEP5-5に進む．それ以外はSTEP5-3に戻る．

STEP5-5：STEP5-2で _{( )}

1



^R , r

k r

k PX



px  の選択を終えたら STEP 5-6 に進む．そ れ以外はl ec,E0とし，STEP5-2に戻る．

STEP 5-6： k = n−1 ならば，サイクルとなる部分ネットワーク集合CX を f_iの

値によらずに構成し，X_k1X_k1CXとする．

STEP 5-7： k k1としてSTEP 3 に戻る．

次にエッジの有効度を算出するパレート最適解のエッジ本数をvとする．エッ ジ本数kvにおいて，エッジの有効度vl_v(i)を用いる方法をARVとする．

アルゴリズムARV

アルゴリズムAREのSTEP 5の過程を，以下に変更する．

STEP 5 (追加エッジの選択と次エッジ数部分ネットワークの構成)：

STEP 5-1：k n1ならば，i1,2,,mに対して，vl_v(i) f_iとする．kv1の

とき，







} {

) (

k

k PX

i

k i x

vl

px

を求めvl_v(i)vl_v(i) f_iとする．l←ecとする．

STEP5-2：部分ネットワーク を選択する．

STEP5-3：x_i 0であるe_iから max ()

)

\ ( vl_v i

E E

e_i  を満たすe_iを選択し，

} ) 1 (

1 {

1 k k i

k X

X _  _  px  とする．EE{e_i}，ll1とする．

STEP5-4：l=0ならば STEP5-5 に進む．それ以外はSTEP5-3に戻る．

STEP5-5：STEP 5-2 で ( )

1



^R , r

k r

k PX



px  の選択を終えたら STEP 5-6 に進む．そ れ以外は，l←ec,E0とし，STEP5-2に戻る．

) (

1



^R , r

k r

k PX



 px

40

STEP 5-6：k = n−1 ならば，サイクルとなる部分ネットワーク集合CX をvl_v(i)の 値によらずに構成し，X_k1X_k1CX とする．

STEP 5-7： k k1，r 1 としてSTEP 3 に戻る．

2.5.2 パレート最適解の傾きを用いるアルゴリズム

次に，部分ネットワークの選択基準にパレート最適解の傾きを用いるアルゴリ ズムを示す．

アルゴリズムASE，ASV

アルゴリズムAREとARVの過程STEP4を下記に置き換えたものを，それぞれ ASE，AS_Vとする．ここで，パレート最適解の傾き基準によってエッジ追加対象 となった部分ネットワークの集合をPX_2,kとする．

STEP 4 (パレート最適解の探索とネットワークの選択)：

STEP4-1：

2 ) 1 ( 

n n

k のとき， ( )

1



^k

n i

Xi

pareto





を求め，計算を終了する．

k<n(n-1) 2

の場合， PX_1,k  pareto(X_k)としてSTEP 4-2へ進む．

STEP 4-2： ^*_{1 arg max ( 1)}

1 1

 

  

 _k

k PX R

k k

px

px px

に対し，^x_kX_kがR(px^*_k1)R(x_k)を満た す場合，PX_2,k PX_2,k{x_k}とする．

STEP 4-3 ：

) (

) min (

" arg

k k k PX

C R

k

k px

px px

px

 に対し，^x_kPX_2,kが

) (

) ( ) (

) (

k k k

k

C R C

R

x x x

p x

p 



 を満たす

ならばPX_2,k PX_2,k\{x_k}とする．

STEP 4-4 ：^x_k (X_k \PX_1,k)を選択し終えたら STEP 5 に進む．それ以外は STEP 4-2に戻る．

41

ドキュメント内 多目的ネットワークシステムの評価指標算出方法 に関する研究 (ページ 41-45)