性能評価

性能評価に関しては，まずアルゴリズムの特徴や性質を詳細に分析するために項5.4.1 にて処理ステップ毎の実行時間の傾向を調査し，次に項5.4.2 にて入力したルール毎の実 行時間を調査，最後に項 5.4.3 にて各ルールと処理ステップの関係について調査する．

5.4.1 各処理ステップの実行時間の比較

まず200 台規模を想定した際の大まかな傾向を把握するため，複数のルール(基本ルー

ル 1，基本ルール2，及びテンプレート 1〜9)を同時に入力した際に算出した実行時間を

図 5.4 にまとめた．横軸は構成要素数，縦軸は実行時間 (秒) を表す．

0 80 160 240 320

6 15 24 33 42 51 60 69 78 87 96 105 114 123 132 141 150 159 168 177 186 195 Time Step1 Time Step2 Time Step3

313.631

0.023 0.003 4.296

図 5.4: 各処理ステップの実行時間の比較

構成要素数が増えるにつれ，STEP1 (ルール詳細化)の実行時間が大きく上昇する傾向 が把握できる．ルール詳細化アルゴリズムは全ての組合わせを探索する都合上，指数時間 の計算量になっており，評価実験でもその性質が現れたと分かる．

一方で，STEP2 (回避策推論) 及び STEP3 (最適回避策提示法) は規模が増大した場合 でも極めて短時間で実行を終えていることが分かる．

5.4.2 入力したルール毎の実行時間の比較

ルール毎に要した実行時間を比較するため，掛かった時間を片対数グラフで示したもの を図 5.5 に示す．横軸は構成要素数，縦軸は実行時間(秒)を表す．最大規模は約100 台．

テンプレート集ではほとんど計算時間の増加傾向が掴めないが，その他の 4 つの基本 ルールに関しては，いずれも程度は大きく異なるものの指数的な計算時間の増加を見せて

0.001 0.01 0.1 1 10 100 1000 10000

6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99

Rules T1-9 Rule B1 Rule B2 Rule B3 Rule B4

図 5.5: 各ルールの実行時間の比較

いる事がわかる．なお，0.01 前後の値には細かい増減が見受けられるが，通常のパーソ ナルコンピューターで実行している都合上，この程度の増減は誤差と考えられる．

5.4.3 ルールと処理ステップの関係

更に詳しく分析するために，ルールの特徴に応じた各処理ステップの実行時間の増加 傾向を調査した．ルール毎の各処理ステップの実行時間の比較を片対数グラフにまとめ，

並べたものを図 5.6 に示す．横軸は構成要素数，縦軸は実行時間 (秒) を表す．なお，項

5.4.2にてテンプレート集の実行時間の傾向が想定した規模では把握できないほど小さかっ

たことを踏まえ，テンプレート集に限り 1,000 台規模まで想定を拡大した再実験を行い，

その結果をグラフにした．なお，各グラフの対数目盛りは揃えてある．

元々処理時間の大半が STEP1 で占められているため，項 5.4.2 同等の傾向が STEP1 の傾向にそのまま現れている．しかし複雑性の高いルールである基本ルール 3, 4 に限っ

ては STEP2の増加傾向も確認できる．規模を拡大したテンプレート集に関しては，ゆる

やかな増加傾向が STEP1, STEP2 において初めて確認できた．STEP3 に関しては，全 てのルールで目立った傾向は確認できなかった．

0.001 0.01 0.1 1 10 100 1000

69121518212427303336394245485154576063666972757881848790939699

Rule B2

Step1 Step2 Step3

0.001 0.01 0.1 1 10 100 1000

69121518212427303336394245485154576063666972757881848790939699

Rule B1

Step1 Step2 Step3

0.001 0.01 0.1 1 10 100 1000

69121518212427303336394245485154576063666972757881848790939699

Rule B3

Step1 Step2 Step3

0.001 0.01 0.1 1 10 100 1000

69121518212427303336394245485154576063666972757881848790939699

Rule B4

Step1 Step2 Step3

0.001 0.01 0.1 1 10 100 1000

6 21 36 51 66 81 96 111 126 141 156 171 186 201 216 231 246 261 276 291 306 321 336 351 366 381 396 411 426 441 456 471 486 501 516 531 546 561 576 591 606 621 636 651 666 681 696 711 726 741 756 771 786 801 816 831 846 861 876 891 906 921 936 951 966 981 996

Rules T1-9

Step1 Step2 Step3

図 5.6: ルール毎の各処理ステップの実行時間の比較