実験結果

PSO^{の適用結果を表}3.3^{に示す．また},I62に対するレイアウト結果を図3.4^に示す．

表3.3 PSO適用結果まとめ

問題

PSO

OFV CPU time ^{実行不可能解}

の割合(%)

O9 373.8 14944.9 96.8

VC10 29069.3 15561.3 98.3

Ba15 7431.6 23410.3 96.6

M15a 48004.9 24489.5 96.8

AB20 6182.4 32419.3 96.4

SC30 4047.9 48339.1 99.7

SC35 6031.2 55052.4 96.1

I62 1324.0 96851.3 95.1

−20 0 20 40 60 80 100 120 140 160 180

−20 0 20 40 60 80 100 120

図3.4 I62に対するPSO適用後のアウトプット

I62に対する適用結果をみると,建屋内に収まっており物流量の多い物同士が近くに配置されている事 がわかる．しかしながら,^{計算時間を見ると}36時間と非常に多くの時間がかかっている事がわかる．こ の点を考察すると下記の理由が考えられる：

1. ^{実行不可能解が多い．}

2. 初期収束が見られる．

「1.実行不可能解が多い．」については,表3.3より実行不可能解の割合が9割を超えている事から確認 できる．この原因としては,解の更新の過程で多くの職場同士の重複が見られる事が原因であると考えら れる．PSO^{の解更新を再掲すると}

r^k_t+1=r_t^k+wv^p,k−1+c1(rpbp−r^p,k) +c2(rgb−r^p,k)

により行われるが,単純のため,w=c1= 0とし,Gbestへの模倣ベクトルc2(rgbest−r^k_t)のみ考える事と する(^{これを図示すると}3.5^{の様になる})^{．この際に},c2= 0.5とした時の実際の移動の様子を表すと図3.6 の様になる．この様に,全職場が同時に移動するため探索の過程で重複が発生し実行不可能解が増加して しまっている．これが時間がかかっている原因の1つであると考えられる．この傾向は職場数が増加する につれ大きくなると考えられる．

第3章 カオスアニーリングの職場レイアウト問題への適用性 37

図3.5 個体kのt回目の解r^k_t とGbest.

図3.6 個体kのt+ 1回目の解r^k_t+1(w=c1= 0, c2= 0.5).

「2.初期収束が見られる．」については,PSOの解更新の構造に起因する問題であると考えられる．PSO の収束度合いを示すためには,^{速度ベクトル}v_t^{kの大きさ}|v^kt|を観察すればよい．なぜならば,v_t^{kと収束状} 態には下記の関係があるからである．

個体k^{が収束している} ⇐⇒ r^k_t 'r_t+1^k

⇐⇒ r^k_t 'r_t^k+v^k_t

⇐⇒ v_t^k'0

この関係を利用して,収束状況の推移を観察したものが図3.7^{である．図}3.7^は,I62^{の問題に対して各個} 体の|v_t^k|^の平均値|v¯_t^k|の時系列推移を表したものである．図の結果より,^僅か50^{回程度の探索で既に収} 束が発生してしまっている事がわかる．実験条件の元で,50回の探索に要する時間を計測したところ,48.2 秒であった．また50回探索後のレイアウトを図3.8に示した．図3.8を見てわかる通り,レイアウトとし ては重なりやはみ出しが多く職場同士の距離もかなり離れてしまっている．この様に,初期収束している ため解の更新がほとんど行われないにも関わらず,レイアウトとしてはまだ改善の余地があるため終了条 件が満たされない状況に陥ってしまう．これにより,計算時間が非常に長くかかってしまっていると考え られる．

この様に初期収束してしまう原因を更に調査するために,50回探索後のある1個体の座標を表3.4に示 す．これを見ると,Pbestへのベクトル(r^k_pbest−r^k_t)とGbestへのベクトル(rgbest−r_t^k)が符号が逆のほ ぼ同じ値になっている事がわかる．従って,^{更新式（再掲）}

r^k_t+1=r_t^k+v^k_t+1

v_t+1^k =wv_t^k₋₁+c1(rpbk−r^k_t) +c2(rgb−r^k_t)

の第2項及び第3項が相殺されてしまっている事がわかる．この理由を考えてみると,収束後の状態とし てv_t^k= 0^を仮定し,

v_t+1^k =c1(rpbp−r^p,k) +c2(rgb−r^p,k)

0 10 20 30 40 50 60 70 80 90 100 0

500 1000 1500 2000 2500 3000 3500

図3.7 個体kのt+ 1回目の解r^k_t+1(w=c1= 0, c2= 0.5).

−20 0 20 40 60 80 100 120 140 160 180

−20 0 20 40 60 80 100 120

図3.8 個体kのt+ 1回目の解r^k_t+1(w=c1= 0, c2= 0.5).

これはPSOの更新式がPbestとGbestの内分点(c1:c2)へと移動する様なベクトルである事を表し,ひ とたび内分点に到達すると先に示した様に二つの項は相殺される様になる事がわかる．また,^{前述したと} おり収束後は速度ベクトルv^k_t ^{も限りなく}0^{に近づく．以上より},v_t+1^{k が限りなく}0^{に近くなってしまい}, 収束が発生してしまうと解釈できる．また以上の考察より,^{パラメータ設定}w, c1, c2を変化させたとして も,ひとたび内分点に辿り着いた場合には収束から逃れる事はできない事もわかる．

以上の１,２原因より,最終アウトプットは優れたものを導出できるものの,PSOの更新式の構造上,計 算時間が長くなる事は避けられないという事がわかった．

第3章 カオスアニーリングの職場レイアウト問題への適用性 39

表3.4 50回探索後のある1個体のx座標

成分 r rpb rgb r−rpb r−rgb 成分 r rpb rgb r−rpb r−rgb

x1 85.7 101.2 70.2 -15.5 15.5 x32 71.9 0.2 143.7 71.7 -71.7

x2 120.3 111.5 129.1 8.8 -8.8 x33 7.4 0.5 14.3 6.9 -6.9

x3 66.4 62.7 70.0 3.6 -3.6 x34 9.2 13.1 5.3 -3.9 3.9

x4 74.9 75.1 74.7 -0.2 0.2 x35 86.0 39.1 132.9 46.9 -46.9

x5 80.7 88.2 73.1 -7.5 7.5 x36 20.2 3.4 37.0 16.8 -16.8

x6 30.3 26.1 34.4 4.1 -4.1 x37 32.5 63.6 1.3 -31.1 31.1

x7 61.1 109.3 12.8 -48.2 48.2 x38 86.7 51.2 122.2 35.5 -35.5 x8 45.1 80.1 10.1 -35.0 35.0 x39 51.1 81.2 21.1 -30.1 30.1 x9 85.6 38.0 133.3 47.6 -47.7 x40 135.5 138.9 132.0 -3.5 3.5 x10 86.3 137.6 35.0 -51.3 51.3 x41 29.5 44.8 14.3 -15.2 15.2 x11 121.5 113.7 129.2 7.8 -7.8 x42 51.8 50.7 52.9 1.1 -1.1 x12 119.9 133.1 106.8 -13.1 13.1 x43 109.0 128.9 89.0 -20.0 20.0 x13 70.6 10.3 130.9 60.3 -60.3 x44 69.4 51.1 87.8 18.4 -18.4 x14 84.1 27.5 140.7 56.6 -56.6 x45 60.4 20.7 100.2 39.7 -39.7 x15 65.8 110.6 21.0 -44.8 44.8 x46 86.7 76.2 97.2 10.5 -10.5 x16 81.8 104.5 59.1 -22.7 22.7 x47 96.8 128.5 65.0 -31.7 31.7 x17 131.8 116.5 147.1 15.3 -15.3 x48 39.3 57.6 21.0 -18.3 18.3 x18 86.0 75.3 96.7 10.7 -10.7 x49 108.6 104.4 112.8 4.2 -4.2 x19 99.1 63.8 134.5 35.3 -35.3 x50 65.2 94.2 36.3 -29.0 29.0

x20 82.0 91.7 72.3 -9.7 9.7 x51 82.6 67.6 97.6 15.0 -15.0

x21 65.2 128.4 2.1 -63.1 63.1 x52 99.8 71.0 128.6 28.8 -28.8 x22 97.0 100.6 93.4 -3.6 3.6 x53 77.6 142.5 12.7 -64.9 64.9 x23 56.6 78.5 34.7 -21.9 21.9 x54 79.2 12.5 145.8 66.6 -66.6 x24 62.0 44.8 79.1 17.1 -17.1 x55 23.3 42.0 4.7 -18.6 18.6 x25 107.2 105.6 108.7 1.6 -1.6 x56 96.2 67.1 125.3 29.1 -29.1 x26 74.2 57.2 91.1 16.9 -16.9 x57 106.7 88.1 125.4 18.6 -18.6

x27 86.7 85.2 88.3 1.6 -1.6 x58 69.6 131.6 7.5 -62.1 62.1

x28 99.1 133.2 65.0 -34.1 34.1 x59 76.1 70.4 81.9 5.8 -5.8 x29 81.5 126.4 36.6 -44.9 44.9 x60 103.5 65.6 141.5 37.9 -37.9 x30 99.6 134.8 64.3 -35.2 35.2 x61 80.1 111.9 48.2 -31.9 31.9

x31 71.2 140.9 1.5 -69.7 69.7 x62 44.7 46.8 42.6 -2.1 2.1