単位シンプレックス上領域での大域的最適化

過程で通過した点をプロットして得た結果を図6.17に示す．通常のカオス徐冷法では，冷 却の際分岐パラメータの大きい領域で速やかに安定化する局所的最適解に引き込まれる ため，(a)，(b)各結果とも軌道が(0.0,1.0)，(0.2,0.8)，(0.8,0.2)，(1.0,0.0)のいずれかに 収束し，大域的最適解にはバウンダリクライシスを経なければならないため到達しないこ とを示している．

一方，前述した徐冷条件に加え，非受理連続回数の上限をT_N.A= 10，悪化受理法の閾

値をe = 0.01としてハイブリッド型カオス徐冷法を適用した結果を図6.18に示す．ハイ

ブリッド型カオス徐冷法では，徐冷のさい大域的最適解近傍を軌道が通過したとき閉じ込 め効果がはたらくとともに，若干の悪化を認めることから局所的最適解を脱出する可能 性を認めているため，2つの大域的最適解にも軌道が収束し得ることを確認することがで きる．

さらに，悪化受理法の閾値パラメータeの値に対するハイブリッド型カオス徐冷法の依 存性を調べた結果を表6.10に示す．この際，2種類の勾配法離散化写像について初期点を ランダムに与えた10000本の軌道の中で，ハイブリッド型カオス徐冷法を適用して2つの 大域的最適解のいずれかに収束した軌道の割合を百分率で示している．

非線形作用素勾配系によるカオス軌道を用いると，高い割合で大域的最適解が得られて いる．一方，無制約化変数変換勾配法によるカオス軌道を用いたときは，大域的最適解収 束率が高いとはいいがたいが，図6.16でみたように前者では大域的最適解を含む領域を 軌道が大域的に通過するカオスが生じるのに対し，後者ではそれが生じないため，カオス 軌道自体に大域的最適解近傍への到達のしやすさに顕著な差があることが原因となって いる．

0 0.2 0.4

0.6 0.8 1

x

0 0.2 0.4 0.6 0.8 1 x

10 0

20 30 40 50

E(x)

図 6.15: 目的関数(6.29a)の形状（n= 2の場合）

(a) 非線形作用素勾配系の場合

(b) 非線形変数変換勾配系の場合

(a) 非線形作用素勾配系の場合

(b) 非線形変数変換勾配系の場合

図 6.17: 問題(6.29)に対する通常型カオス徐冷法の適用結果

(a) 非線形作用素勾配系の場合

(b) 非線形変数変換勾配系の場合

図 6.18: 問題(6.29)に対するハイブリッド型カオス徐冷法の適用結果

ところで，問題(6.29)では，等式制約(6.29b)式のもとで不等式制約(6.29c)式を考える と，0 ≤ x₁ ≤ 1，0 ≤ x₂ ≤ 1がなりたつ．そこで，非負制約(6.29c)式のかわりに区間 (0,1)²の上下限制約を考えて決定変数を有界領域へ閉じ込めるとともに，等式条件(6.29b) を障壁法の考え方により目的関数に組み込んだ問題

minx E(x) = 10n+ Xn

i=1

©x²_i −10 cos(10πxi)ª +s

à _n X

j=1

xj−1

!2

(6.30a)

subject to 0≤x_i ≤1, i= 1,· · · , n (6.30b)

を考え，上下限制約付最適化問題として解くことが可能であるか検討する．(6.30a)式に おける係数を十分大きな値s = 1.0×10⁶に設定し，(2.16)式のシグモイド関数を用いた 非線形作用素勾配系および非線形変数変換勾配系の分岐図を図6.19に示す．なお，決定変 数xの初期点は(0.4,0.6)，(0.6,0.4)とし，対応する内部状態量uの初期値は(2.17)式を 用いて与えた．

この結果から，分岐現象にともない，正規化等式条件を侵害する領域が存在することが わかる．非線形変数変換勾配系では制約条件を侵害するパラメータ領域は限定的である が，非線形作用素勾配系では分岐ののち(0,0)もしくは(1,1) へ収束し，等式条件は完全 に無視される．

そのため，カオス徐冷法を適用しても制約領域からの逸脱が起きることが予想され，制 約条件をすべて考慮した非線形作用素モデルもしくは非線形変数変換モデルを用いるこ とが必要であると考えられる．

表 6.10: 問題(6.29)に対するハイブリッド型カオス徐冷法の大域的最適解収束率

e 非線形作用素勾配系 非線形変数変換勾配系

0.001 68.57% 7.43%

0.005 69.45% 7.23%

0.01 68.36% 6.60%

0.05 65.05% 6.13%

0.1 45.61% 1.83%

(b) 非線形変数変換勾配系の場合

図 6.19: 上下限制約付問題(6.30)に対する離散化勾配系モデルの大域的分岐図

ほかの多峰性関数に対する制約条件付最適化問題として，

例2 （Levy-Montalvo問題）[47]

minx E(x) = π n

(

Bsin²(πy₁) +

n−1

X

i=1

(y_i−A)²(1 +Bsin²(πy_i+1)) + (y_n−A)² )

(6.31a) where y_i = 1.0 + 10.0(x_i−0.25)

subject to Xn

i=1

x_i = 1 (6.31b)

xi ≥0, i= 1,· · · , n (6.31c)

を考える．ただし，パラメータはA= 1.0，B = 5.0とする．また，目的関数の多峰性を確 認するため，参考としてn= 2とした場合の形状を図6.20に示しておく．n = 4とした場 合，制約条件(6.31b)，(6.31c)のもとで(6.31a)式の大域的最小点は(0.25,0.25,0.25,0.25) である．

4変数関数(6.31a)式の単位シンプレックス上における大域的最小点を初期点として，2

種類の離散化勾配系モデル写像のそれぞれに対し，十分時間が経過した9500< t <10000 における通過点を，x1 からx₄ の各成分に関してプロットして描いた大域的分岐図を図

6.21に示す．この問題では，非線形変数変換勾配系の軌道が∆T ≈1.7×10⁻²付近で大域

的カオスを生じるのに対し，非線形作用素勾配系の軌道には大域的カオスを生じない．し たがって，この問題では後者の写像の大域的最適化能力を評価することにする．

非線形変数変換勾配系で初期点をランダムに与えた100本のカオス軌道に対して，ハイ ブリッド型カオス徐冷法のアルゴリズムを適用した結果を図6.22に示す．ただし，温度パ ラメータ初期値を∆T₀ = 1.6×10⁻³，1回の冷却による減少量をd= ∆T₀/200，冷却周期 をT = 20としたのに加え，非受理連続回数の上限をT_N.A.= 10，TA法の閾値をe= 0.01 としている．

この例でも，ハイブリッド型カオス徐冷法を適用したときは冷却の初期段階ですでに軌 道が大域的最適解近傍への絞り込みが始まり，また軌道の収束先も大域的最適解もしくは その近傍に限られていることがわかる．

さらに，通常型カオス徐冷法，およびハイブリッド型カオス徐冷法でTA法の閾値eを さまざま変えた場合の，大域的最適解への収束率を求めた結果を表6.11に示す．通常型カ オス徐冷法では，大域的最適解への収束率は7.10%にとどまっているが，ハイブリッド型 カオス徐冷法を適用すると，多くの条件で80%を越える割合で軌道が大域的最適解へ収 束しており，あらためてハイブリッド型カオス徐冷法の顕著な有効性を確認する結果が得 られた．

図 6.20: 目的関数(6.31a)の形状（n= 2の場合）

(a) 非線形作用素勾配系の場合

(b) 非線形変数変換勾配系の場合

図 6.21: (6.31a)式に対するカオス軌道の大域的分岐図

図 6.22: (6.31a)式に対するハイブリッド型カオス徐冷法の適用結果

表 6.11: カオス徐冷法による大域的最適解収束率

徐冷法の型 e 大域的最適解収束率

通常 - 7.10%

ハイブリッド 0.001 80.66%

ハイブリッド 0.01 80.45%

ハイブリッド 0.1 81.21%

ハイブリッド 1.0 19.02%