Chaos-Annealing

最適化を力学系のカオス挙動を応用した最適化手法の1^{つである．}CAでは離散化勾配系とよばれる漸 化式に従い解更新を行う．

rt+1=rt+h∆rt with ∆rt=−∇rt (3.24) 但し,hはステップ幅,∆rは探索方向ベクトルを表す．また∇rt は勾配ベクトルであり,探索方向∆rtは 目的関数値が最も小さくなる方向を示す(最急降下方向).

ここで，Armijo基準などを用いて直線探索によりステップ幅 ht を決定した場合，最急降下法 (^即

ち,NLP^{を用いた解法})となる．しかしながら，前述のとおりFLP^{の非凸性から},^{降下方向にのみ探索を} 行うために局所解へと停留してしまう(^{初期解に依存する})^．

これを回避するために，CAでは系にカオス軌道を発生させ大域的探索を行う．具体的には，ステップ 幅ht を十分大きくとるとカオス軌道が発生する事が徳田[1]らの研究により知られている．これを利用 し探索の序盤ではhtを大きく取りカオス軌道を発生させ大域的な探索を行う．そして，探索の終盤に向 かうにつれ,htを小さくし局所的探索を行う．

3.8.1 アルゴリズムの流れ

アルゴリズムの流れを以下に示す. アルゴリズムの流れ

given t= 0,^初期点r0,^冷却率β∈[0,1],^{繰返し回数}Tp

repeat 1-4:

1. 探索方向計算:∆rt =−∇f(rt).

2. ^解更新：rt+1=rt+h∆rt

3. ^時刻更新t→t+ 1,t⁰→t⁰+ 1

4. ^{ステップ幅更新}: t⁰> Tpならばht →βht, t⁰= 0 until 終了条件

序盤は大域的探索,終盤は局所的探索を行うため,^{ステップ幅}htを一定回数Tp超過するたびに冷却(^減 少)^させる．t⁰はステップ幅冷却のためのカウンターであり,冷却後にリセットされる．

3.8.2 探索方向

探索方向∆rt =−∇fe(rt)^{は勾配ベクトルであり},^関数f(re t)の値を最も減少させる方向である．ここ で,勾配ベクトルの線形性より下記の様に書く事ができる．

∆rt=−∇fe(rt)

=−∇f(rt)− ∇P(rt)

従って,^第1項は目的関数値を最も減少させる方向,^第2項はペナルティ関数値を最も減少させる方向と 解釈する事ができる．これらを成分で書くと,^式(3.25),(3.26)^{の様になる．}

図3.19 CAにおける探索序盤(ht: 小)と探索終盤(ht: 大)の軌道の違い

∆r^f =

∑N i=1

∑N i<j

fij×sign

([xj−xi

yj−yi

])

(3.25)

∆r^P =p×

∑N i=1

∑N i<j

([2X_ij²Yijsign(xi−xj) 2XijY_ij²sign(yi−yj) ]

+

[sign(wi−xi) sign(hi−yi) ]

+

[sign(xi−(W −wi)) sign(yi−(H−hi))

]) (3.26) sign(u) =

{ 1 (if u >0)

−1 (if u <0) (3.27)

但し,∆r^f,∆r^{P は},目的関数・ペナルティ関数の勾配ベクトルから導出される項である．目的関数に関 する部分に関してはfij が大きい程,大きな移動ベクトルが生じる事がわかる．これにより物流量の強い 職場同士が引き合う事がわかる．ペナルティ関数に関する部分に関しては,Xij, Yij が大きい程,^大きな移 動ベクトルが生じる事がわかる．重なり部分の大きい職場同士が離れやすくなる事がわかる．

3.8.3 ステップ幅

CAでは,初期状態でステップ幅を大きく設定し徐々に冷却(減少)する事により，探索の序盤は大域的 探索を，終盤は局所的探索を実現する事で大域的最適解を得る事を指向する．図3.19^{に探索序盤と探索} 終盤の軌道の違いを示した．探索序盤では,ステップ幅が大きいので職場同士の相対位置関係が変化しや すく様々な組合せを探索する事ができる(^{大域探索フェーズ})^．一方,探索終盤ではステップ幅が小さいた め同じ相対位置関係を維持したまま隙間の除去,職場同士の重なり・はみ出しの除去を行いレイアウトの 調整を行う(局所探索フェーズ)．

3.8.4 実験結果

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

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

表3.10 CA適用結果まとめ

問題

CA

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

の割合(%)

O9 304 18.2 1.3

VC10 20021 21.3 0.9

Ba15 5137 31.7 11.1

M15a 30375 31.6 5.4

AB20 5869 39.1 29.7

SC30 3915 62.5 22.7

SC35 5228 72.9 1.4

I62 1139 132.3 18.3

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

−20 0 20 40 60 80 100 120

図3.20 I62に対するCA適用後のアウトプット