数値実験による評価

Jan[26]は，kn1,n,n1の場合の全点間信頼度の最大値算出式を示したが，

2

n

k の場合，ネットワークのエッジパターン数が多く全点間信頼度の最大値 算出式の導出は非常に困難である．そのため，Jan[26]はノードiの次数d_iに着目 した全点間信頼度の上限値算出式を次式((1.5)式再掲)で与えた．

  











  











 ⁿ

i

i

mi k

dk mi

k

dk di

p p

p R

1

1

1 1

1} {1 (1 ) }

) 1 ( 1 { )

1 ( 1 )

(x (3.16)

しかし，上記の式により算出される全点間信頼度の上限は非常に幅が広い．上 記式により算出される全点間信頼度が大きくなると，制約条件のR₀を満たす最小 エッジ数_k^が，真の値より小さく算出され，問題P_n(k)を解く回数の増加に繋がる．

よってR₀を満たす最小エッジ数_k^による探索領域の制限が必ずしも有効に機能 するとは限らなくなる．

そこで，最適構成の全点間信頼度を適用するエッジ本数kの範囲が異なる3通 りのアルゴリズムProgram J，Program J+，Program J++を考え，問題MPを解く実 験を行う．表3-5に，各アルゴリズムで最適構成の全点間信頼度と，(3.16)式によ る信頼度の上限値を用いるエッジ本数kの範囲をまとめた．表3-5の最大信頼度 が，最適構成の全点間信頼度を適用するエッジ本数kの範囲である．そして，計 算時間を比較し，kn2，kn3の場合の最適構成の最大全点間信頼度によ り解の探索が制限されていることを確認する．

表3-5 各アルゴリズムでの最適構成信頼度と信頼度上限値の適用範囲

Program J Program J+ Program J++

最大信頼度 n1kn1 n1k n2 n1k n3 信頼度上限値 k n2 k n3 kn4

以下に，各アルゴリズムにおけるR₀を満たす最小エッジ数 _k^を算出する手順 を示す．

70

R0を満たす最小エッジ数_k^の算出過程

【Program J】

STEP 1 ：エッジ数n1kn3の最適構成の全点間信頼度を計算し，それぞれ )

*(

R xk とする．

STEP 2：(3.16)式により，エッジ数

2 ) 1 2  ( 

 n n

k

n における全点間信頼度の上 限値を算出し，それぞれR x( _k)とする．

STEP 3 ：最小エッジ数k^計算

STEP3-1：R^*(x_k)R₀であればk^kとし計算を終了する．それ以外はSTEP3-2 へ進む

STEP3-2：k n1であればk k 1としてSTEP3-3へ進む．それ以外は

1

k

k としてSTEP3-1へ戻る．

STEP3-3：R(x_k)R₀であれば

k

^

 k

とし計算を終了する．それ以外はk k1

としSTEP3-3を繰り返す．

【Program J+】

Program JのSTEP3-2を下記に置き換える．

STEP3-2：k n2であればk k1としてSTEP3-3へ進む．それ以外は

1

k

k としてSTEP3-1へ戻る．

【Program J++】

Program JのSTEP3-2を下記に置き換える．

STEP3-2：k n3であればk k1としてSTEP3-3へ進む．それ以外は

1

k

k としてSTEP3-1へ戻る．

71

実験に際し，C言語を用いて実装し，Visual Studio 2010にてコンパイルした実 行プログラムを用いて計算を行った．計算環境は，CPU Intel Core i7-4770 3.40GHz,

Memory 16GB, OS Windows 8.1を実装したPCを用いた．実験は，ノード数6，総

エッジ数15のネットワークで行った．各エッジのコストの値は 1から100の範 囲で発生させた一様乱数を用いた．

エッジの信頼度がp0.70,0.75,0.80である3通りのネットワークにおいて，制

約条件R₀を0.70から0.95(0.05刻み)とした場合の計算時間の結果を次の表3-6に

示す．また，3つのアルゴリズムで算出したR₀を満たす最小エッジ数k^の結果を 表3-7にまとめた．

表 3-7 において，問題MPの解となったネットワークのエッジ数より，アルゴ リズムにより算出されたk^が小さいものには*をつけた．表3-6と表3-7から，k^ が問題MPの最適解のエッジ数と等しくなる場合，計算時間が短縮されているこ とがわかる．この効果は，最適構成での信頼度をより多く考慮している Program J++に最も表れている．

表3-6 各アルゴリズムにおける計算時間

p R0 計算時間(秒)

Program J Program J+ Program J++

0.70 0.70 1.112 0.001 0.001

0.75 1.087 0.006 0.005

0.80 0.180 0.178 0.178

0.85 1.870 1.868 0.007

0.90 0.001 0.010 0.011

0.95 1.156 1.164 1.156

0.75 0.70 0.001 0.002 0.001

0.75 0.003 0.002 0.003

0.80 1.130 0.001 0.001

0.85 1.135 0.010 0.010

0.90 1.862 1.861 0.001

0.95 1.898 1.897

2.5201

1.893

0.80 0.70 0.009 0.009 0.009

0.75 0.002 0.003 0.002

0.80 0.004 0.003 0.004

0.85 0.001 0.001 0.001

0.90 1.123 0.004 0.004

0.95 1.918 1.919 0.029

72

この効果の例外として，p0.8，R₀ 0.7の場合がある．制約条件のR₀を満た す最小エッジ本数_k^はいずれのアルゴリズムにおいても 7 本と算出されたもの の，エッジ本数k 8のネットワークに，k7の構成よりコストが小さくなる構 成が存在した．そのため表3-7のように_k^が最適解のエッジ本数と異なる結果と なった．この場合，k 7の段階でR₀を満たす全点間信頼度を持つネットワーク が探索されており，k 8においては，k7で探索されたR₀を満たすネットワー クのコストより小さなコストの構成しか探索していないため，計算時間が短くな ったと考えられる．

表3-7 各アルゴリズムにおける算出最小エッジ数

p

R

0 ^解の

エッジ数

アルゴリズムによる_k^

Program J Program J+ Program J++

0.70 0.70 9 *8 9 9

0.75 9 *8 9 9

0.80 9 9 9 9

0.85 10 *9 *9 10

0.90 11 11 11 11

0.95 13 *12 *12 *12

0.75 0.70 8 8 8 8

0.75 8 8 8 8

0.80 9 *8 9 9

0.85 9 *8 9 9

0.90 10 *9 *9 10

0.95 12 *11 *11 *11

0.80 0.70 8 *7 *7 *7

0.75 7 7 7 7

0.80 8 8 8 8

0.85 8 8 8 8

0.90 9 *8 9 9

0.95 10 *9 *9 10

73

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