第 2 章 全点間信頼度と構築コストを考慮した 2 目的ネットワーク設計問題
2.4 ネットワークの性質
パレート最適解が目的関数空間内に構成する曲線はパレートフロントと呼ば れる．本章で提案するアルゴリズムは，パレートフロントを構成する部分ネット ワークの性質に注目して探索空間を制限するものである．はじめに，計算部分ネ ットワークの制限に有効となる部分ネットワークの性質について調査した結果 を述べる．
2.4.1 パレートフロントを構成する解の傾向
ここで，本論文において逆パレート解を下記で定義する．ネットワーク )
( , X
x x に対し，
1
k k
31
① R(x)R(x)かつC(x)C(x)
② R(x)R(x)かつC(x)C(x)
③ R(x)R(x)かつC(x)C(x)
のいずれかを満たす
x
が存在しない時，-x を逆パレート解と呼ぶこととする．提案アルゴリズムでは，部分ネットワーク集合Xkを元にXk1を構成する．そ こで，パレート最適解pxk(PXk)と逆パレート解xk(Xk)に対し次の実験を行 い，エッジを追加した時の全点間信頼度と構築コストの変化を調査した．
例として，ノード数5エッジ本数10のネットワークSX を用いて実験を行った．
の各エッジの信頼度(pi (i1,2,,10))は0.50から0.99の間の一様乱数で，コス ト(ci)は50から99の間の一様乱数でそれぞれ生成した．SX から構成できるエッ ジ本数4のパレート最適解px4と逆パレート解x4に対し，エッジを追加した場合 の解の傾向を確認した．px4とx4から構成できた解を分析した結果，以下の3種 類の傾向を発見した．
(a) px4からはPX5におけるすべてのpx5が構成可能であったが，x4からは px5を構成できない．
(b) PX4におけるそれぞれのpx4 (x1,x2,,x10)において，xi 0であるエッジ eiの構築コストciと信頼度piの比 fi pi/ci の値を求める．6本のxi 0で あるエッジeiにおいて，fi が大きい順で上位エッジと下位エッジに半々に 分け，px4に各エッジを追加する．その結果，指標 fi が上位であるeiを追 加したとき，PX5における全てのpx5が構成される．ただし，i1,2,,10で ある．
(c) エッジ本数kが少ない段階で，パレート最適解PXkとして探索された部分ネットワ ークの連結エッジに着目する． pxk(PXk)に含まれるエッジは，エッジ本数
1
k 以上でパレートフロントを構成する部分ネットワークでも連結エッジとして用 いられる傾向が強い．
SX
32
図2-2 エッジの効率性が解の推移に与える影響
解の傾向(b)について，SXから構成できるあるエッジ本数4のネットワークpx4 に対して，上位エッジを追加した場合と下位エッジを追加した場合の全点間信頼 度と構築コスト合計の変化例を図2-2に示す．指標 fi が上位のエッジを1本追加 した場合を上方への矢印Aで，fi が下位のエッジを1本追加した場合を下方の矢 印Bで示した．
2.4.2 計算対象部分ネットワークの選択基準
1) 解のランク付け
2.4.1項の(a)で示した解の傾向より，次の性質を仮定する．
性質2-1
エッジ本数 k の部分ネットワークpxkにエッジeiを追加したエッジ本数 k1 の部分ネットワークは，pxk1(PXk1) である可能性が高い．
性質2-1をアルゴリズムに実装するために，以下の解のランク[54,75]を定義する．
33
定義（解のランク付け）
ネットワーク集合X において，パレート最適解の定義を満たすX の部分集合 をpareto(X)とする．Xkにおいて次式で定められる PXr,k (r1,2,,R)を，ラン クr の解とする．
)
, (
1k pareto Xk
PX
)
\ (
1
1 ,
,
r
s
k s k
k
r pareto X PX
PX , (r2) (2.1)
図2-3 解のランク付けの過程
上記の定義において，PX1,kはネットワーク集合Xkにおけるパレート最適解集 合PXkを意味する． 図2-3の左図はランク1の解集合PX1,kを示している．ランク
2の解集合PX2,kは，図2-3の右図のように，PX1,kを除いたXkの中でパレート最
適解の定義を満たす解の集合とし，同様の探索によりランクRまでの解集合を探 索する．このランク付けした解集合を提案アルゴリズムにおける部分ネットワー クの選択基準として用いる．
2) パレート最適解の傾き
部分ネットワークの選択基準として，多くの解のランクを考慮すれば，より多くのパレ ート最適解が探索できる．しかし，(2.1)式よりランク付けの過程が増えることになり，計算 負荷が増加すると考えられる．従って，簡易な選択過程でパレートフロントに近い多く の部分ネットワークを選択するために，別の選択基準を検討する．目的関数R(x)と
34
) (x
C を軸とした2次元平面上に部分ネットワークをプロットすると，パレートフロントは図 2-4の四角(■)部分のような曲線を描く．
図2-4 パレートフロントの形状
この傾向に注目し，部分ネットワーク選択基準として，探索領域をパレートフロントの 領域付近に制限する一次関数の傾きを用いる方法[56,76]を提案する．次の 2 つの性 質を仮定し，それぞれ図2-5を用いて説明する．
性質2-2
エ ッ ジ 本 数 k-1 の 部 分 ネ ッ ト ワ ー ク の パ レ ー ト 最 適 解 の 中 で に対し, を満たす にエッジを追加する ことで， を構成できる．
性質 2-2 は，図 2-5(a)に示した より信頼度が高い領域にあるネットワークを選択
対象とすることを指す．図2-5(a) の直線L1の上部領域に相当する．
性質2-3
エ ッ ジ 本 数 k の 部 分 ネ ッ ト ワ ー ク の パ レ ー ト 最 適 解 の 中 で に対して， を満たす にエッジを追加する ことで を構成できる．
) ( max
arg 1
* 1
1 1
k
k PX R
k k
px
px px R(px*k1)R(xk) xk
)
( 1
1
k
k PX
px
*
1
pxk
) (
) min (
" arg
k k k PX
C R
k
k px
px px
px
( )
) ( ) (
) (
k k k
k
C R C
R
x x x
p x
p
xk
)
( 1
1
k
k PX
px
35
図2-5 2つの性質による直線
性質2-3は，図2-5(b) に示したpx"kよりコスト当たりの信頼度増分が大きいネットワー クを選択対象とすることを指す．図2-5(b) の直線L2の左上領域に相当する．
性質 2-2 と性質 2-3 を満たすことにより，対象となる部分ネットワークの存在領域は，
図2-6の2つの直線L1,L2で囲まれた領域となる．
図2-6 パレート最適解の傾きによる制限領域
36
2.4.3 追加するエッジの選択指標
1) エッジの効率性
次に，選択した部分ネットワークxkに対して追加するべきエッジeiの選択指標を検討
する．2.4.1項で示した解の傾向(b)より，パレート最適解は，部分ネットワークに
加えるエッジeiの構築コストciと信頼度piの値に依存することは明らかである．
そこで以下の値を定義する[53]．
定義（エッジの効率性）
エッジ ei において fi( pi /ci) をエッジの効率性とする．
図2-2に示した通り，fiの値が大きいエッジを加えた部分ネットワークは，より早くパ レートフロントに近付く傾向が強いと考えられる．よって本論文では，fiを優先して追加 するエッジeiの判断指標として用いる．
2) 各エッジの利用回数による有効度
2.4.1項で示した解の傾向(c)は，エッジが部分ネットワークを構成することで現 れる特徴である．よって，エッジが持つ信頼度と構築コストの個々の影響に加え，
エッジ相互の連結関係もパレート最適解となる部分ネットワークに影響を与え ている可能性があると考えられる．そこで，pxk(PXk)に対し，各エッジeiのxiの
合計値をeiの有効度vlk(i)[55,77]として下記で定義し，エッジの選択指標として用い
る．
定義（エッジの有効度）
部分ネットワーク集合のパレート最適解PXkに対し，エッジeiの有効度 vlk(i) を次式で定義する．
} {
) (
k
k PX
i
k i x
vl
px
3) ネットワークのトポロジー
エッジの選択方法の 3 つめとして，エッジ相互の連結関係に注目する[53]．全点間 信頼度は，部分ネットワークを構成するエッジの連結関係によって変化する．Jan[26]は，
37
ネットワークの最適構成について考察し，構成するノードがサイクルに含まれる場合に 全点間信頼度が向上することを示している．例えば，図 2-7 の全ノードがサイクルに含 まれるxk,1とその他のネットワークxk,2を比較した場合，全点間信頼度はxk,1が優 位である．すなわちネットワークのサイクルを判断することは，パレート最適解 探索の精度を上げるために有用と考えられる．
図2-7 ネットワークトポロジーと全点間信頼度の関係