ハイブリッド型カオス徐冷法

ラメータ∆T を一定にしたまま上記の過程を一定期間繰り返すことは，悪化受理法の状態 遷移先侯補を，その分岐パラメータに対応した大域性と粗さで連続空間から抽出する作用 に相当し，これまた連続空間に適用した悪化受理法にとっても効率を改善していることに なる．なお，いずれの関数においても，パラメータeの値を大きくするほど，目的関数値 が悪化しても解候補として受理される割合が高まり，大域的探索における解候補空間の絞 り込みをゆるやかに行うことを意味する．

ハイブリッド型カオス徐冷法のアルゴリズムを以下に示す．このなかで，カオス軌道が 生成する状態をx(t)，悪化受理により選択された解侯補をx(t)˜ として区別していること に注意されたい．

アルゴリズム6.4 （ハイブリッド型カオス徐冷法のアルゴリズム）

Step 1 通常型カオス徐冷法のアルゴリズムStep 1の操作に加え，初期解侯補を

˜

x(0) = x(0) とする．悪化受理法の閾値eを設定し，非受理連続回数の上 限T_N.R.（Number of Rejections）を定める．

Step 2 通常型カオス徐冷法のアルゴリズムStep 2と同じ．

Step 3 通常型カオス徐冷法のアルゴリズムStep 3と同じ．

Step 4 目的関数値の増加量

∆E(t) = E(x(t+ 1))−E(˜x(t)) (6.22) を求め，

x(t˜ + 1) =





x(t+ 1) with probability p(∆E(t)) x(t)˜ with probability 1−p(∆E(t))

(6.23)

にしたがって解候補を更新する．

Step 5 Step 4で探索点が解候補として受理されないことがT_N.R.回連続して起き るか，前回の冷却からT ステップ経過したら，冷却∆T = ∆T−dを行う．

そうでなければStep 6へ．

Step 6 t =t+ 1とおき直してStep 2へ戻る．

図6.6の結果に対する簡単な比較として，ハイブリッド型カオス徐冷アルゴリズムを適 用した結果を図6.7に示す．図では，解候補x(t)˜ の徐冷時刻における通過点を，∆T の値 に対応づけて示している．ここで，アルゴリズム6.4中の条件として，受理関数にはTA 法の(6.19)式を用い，閾値e= 0.1およびTN.R.= 20としている．その他のパラメータは，

図6.6を与えたときの条件と共通である．

図6.7では，各勾配系モデルでも，徐冷の初期段階で軌道の存在できる領域が局所的最

適解の近傍にしぼり込まれる．徐冷の過程で，より目的関数値の低い局所的最適解への遷 移，および一定割合で許容される局所的最適解からの脱出を経て，軌道は大域的最適解の 近傍へ集中することが確認される．非線形作用素勾配系では，大域的最適解にすべての軌 道が収束した（収束率100%）．非線形変数変換勾配系では，図6.6の局所的最適解のほか，

大域的最適解へも到達することができるようになり，その割合は42.85%であった．

なお，ハイブリッド型カオス徐冷法における，徐冷速度やパラメータ設定と大域的最適 解への収束率との関係は，次節のシミュレーション結果で述べる．

(a) 非線形作用素勾配系への適用結果

(b) 非線形変数変換勾配系への適用結果 図 6.7: ハイブリッド型カオス徐冷法の適用結果