単位超立方体領域を一般化した直積集合領域での大域的最適化

∆T ≈ 0.009付近で，後者では∆T ≈ 0.004付近で有界な探索領域全体を通過するように なる．ただし，バウンダリクライシスが，前者のモデルでA，CおよびDを初期点とし た軌道に生じ，後者のモデルでB，CおよびDを初期点とした軌道に生じる．

したがって，6.4.1節に示した通常型カオス徐冷法を適用すると，図6.10の結果にもあ らわれているように，前者では局所的最適解Bに，後者では局所的最適解Aに引き込ま れる．

他方，問題(6.25)で，非線形作用素勾配系の離散化モデルに，ハイブリッド型カオス徐 冷法を適用した結果を図6.11(a)に示す．試行条件として，受理関数p(∆E)には(6.19)式 を使用したTA法を適用し，閾値e = 1.0および徐冷のパラメータT = 20，TN.R. = 5と し，初期点は制約領域内で一様に与えた100個を用いた．通常型の結果と異なり，ハイブ リッド型は大域的分岐図のプロットとは全く異なる経路を経て，大域的最適解Cへ到達 できるようになった．さらに，初期点を1×10⁵個に増やし，各局所的最適解への収束率 を求めると，A：6.34%，B：7.01%，C：85.56%，D：1.09%のようになり，大域的最適解 Cへ至る割合が極めて高かった．

同じ条件のもと，非線形変数変換勾配系の離散化力学系モデルを用いてハイブリッド型 カオス徐冷法を適用した結果を図6.11(b)に示す．この場合，局所的最適解Aまたは大域 的最適解Cへ到達した．1×10⁵個の初期点から開始した場合，各局所的最適解への収束 率は，A：4.59%，C：95.41%となり，やはり大域的最適解Cへ至る割合が最も高かった．

eの値を変えて求めた収束の割合は表6.4となる．

また，受理関数p(∆E)として(6.25)式を用いたMP法，および(6.26)式を用いたSA法 での徐冷法適用結果を表6.5，表6.6に示す．表6.4の結果ともあわせて，2種類の離散化 勾配系モデルともに，3種類の受理関数p(∆E)の選択に大きく依存することなく，パラ メータeを比較的小さめの値(0.1〜1.0)に設定すれば，比較的高い割合で大域的最適解が 得られることがわかる．

-200 -150 -100 -50 0 50 100 150 200 250 300

-4 -2 0 2 4

E(x)

x A(x=-4.66)

B(x=-2.46)

C(x=1.92)

D(x=4.24)

図 6.8: 問題(6.25)の大域的構造

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

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

図 6.9: 問題(6.25)に対する離散化勾配系モデルの大域的分岐図

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

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

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

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

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

図 6.11: TA法を用いたハイブリッド型カオス徐冷法の適用結果

表 6.4: TA法を用いたハイブリッド型カオス徐冷法の収束率 (a) 非線形作用素勾配系

e A B C D

0.1 5.16% 9.87% 83.77% 1.20%

0.5 5.36% 8.31% 85.28% 1.07%

1.0 6.34% 7.01% 85.56% 1.09%

5.0 15.50% 2.37% 81.09% 1.04%

10.0 25.23% 2.68% 71.14% 0.96%

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

e A B C D

0.1 5.55% 0.00% 94.45% 0.00%

0.5 4.70% 0.00% 95.30% 0.00%

1.0 4.59% 0.00% 95.41% 0.00%

5.0 31.75% 0.00% 68.26% 0.00%

10.0 100.00% 0.00% 0.00% 0.00%

表 6.5: MP法を用いたハイブリッド型カオス徐冷法の収束率 (a) 非線形作用素勾配系

T A B C D

0.1 5.34% 9.49% 84.06% 1.11%

0.5 6.14% 6.97% 85.58% 1.03%

1.0 7.05% 5.35% 86.58% 1.03%

5.0 4.29% 34.76% 60.13% 0.82%

10.0 0.73% 57.95% 40.51% 0.81%

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

T A B C D

0.1 5.36% 0.00% 94.64% 0.00%

0.5 4.68% 0.00% 95.32% 0.00%

1.0 5.78% 0.00% 94.22% 0.00%

5.0 99.82% 0.00% 0.17% 0.01%

10.0 100.00% 0.00% 0.00% 0.00%

表 6.6: SA法を用いたハイブリッド型カオス徐冷法の収束率 (a) 非線形作用素勾配系

T A B C D

0.1 5.25% 9.50% 84.19% 1.07%

0.5 5.29% 7.30% 85.87% 1.01%

1.0 6.55% 5.63% 86.78% 1.04%

5.0 4.34% 30.96% 63.89% 0.82%

10.0 0.77% 54.64% 43.82% 0.77%

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

T A B C D

0.1 5.67% 0.00% 94.33% 0.00%

0.5 5.05% 0.00% 94.95% 0.00%

1.0 5.83% 0.00% 94.16% 0.00%

5.0 99.59% 0.00% 0.38% 0.04%

10.0 100.00% 0.00% 0.00% 0.00%

さらに，以下3通りの例題を考え，同様にハイブリッド型カオス徐冷法を適用して大域 的最適解を求めた結果を示す．

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

minx E(x) =π(Bsin²(πy) + (y−A)²) (6.26a)

where y= 1.0 + 10.0(x−0.25) (6.26b)

subject to |x|<2.5 (6.26c)

A = 1，B = 5としたとき，問題(6.26)式の形状は図6.12のようであり，x = 0.25が 大域的最適解である．徐冷パラメータT = 5およびT_N.R. = 20を定め，eを変えてハイ ブリッド型カオス徐冷法を適用したときの大域的最適解への収束率を表6.7に示す．なお，

離散化勾配系の分岐構造を考慮して，温度初期値を∆T₀ = 0.01に設定し，d= ∆T₀/500 により与えた．

例3 （2変数Griewank問題）[96]

minx E(x) = −cos(x₁) cos µ x₂

√2

¶

+ x²₁ +x²₂

200 (6.27a)

subject to |x₁|<25, |x₂|<25 (6.27b)

問題(6.27)の形状は図6.13のようであり，(0.0,0,0)が大域的最適解である．カオスの大 域的分岐特性を考慮し，非線形作用素勾配系では∆T₀ = 1.0，非線形変数変換勾配系では

∆T₀ = 0.5としてハイブリッド型カオス徐冷法を適用した結果は，表6.8の通りである．

例4 （2変数Wood-Colville問題）[75]

minx E(x) = 100(2.5−x²₁)²+ (1.0−x₁)²+ 90.0(2.5−x²₂)²+ (1.0−x₂)² (6.28a) subject to |x₁|<2.5, |x₂|<2.5 (6.28b)

問題(6.28)式の形状は図6.14のようであり，(1.58,1.58)が大域的最適解である．非線形 作用素勾配系では∆T = 0.0025，非線形変数変換勾配系では∆T0 = 0.015としてハイブ リッド型カオス徐冷法を適用した結果は表6.9のようになった．

すべての結果から，大域的最適解への収束率に支配的であるのはパラメータeの値であ り，受理関数p(∆E)の選択にはあまり依らないことがわかる．したがって，次項以降の 数値例では単純なTA法の適用結果のみを示すことにする．

0 100 200 300 400

-0.5 0 0.5 1

E(x)

x

Global Minimum (x=0.25)

図 6.12: 問題(6.26)の大域的構造

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

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

e TA法 MP法 SA 法

0.1 100.00% 100.00% 100.00%

0.5 100.00% 99.78% 99.73%

1.0 99.94% 97.19% 95.76%

5.0 99.35% 92.88% 88.40%

10.0 91.82% 92.41% 82.35%

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

e TA法 MP法 SA 法

0.1 100.00% 100.00% 93.24%

0.5 99.99% 99.60% 92.11%

1.0 99.83% 92.21% 84.94%

5.0 68.12% 67.06% 55.69%

10.0 52.83% 56.74% 50.39%

-10 -5x1 0 5 10 -10 -5 0 5 10 -1 x2

0 1 2 3 4 5

E(x)

Global Minimum: (0.0,0.0)

図 6.13: 問題(6.27)の大域的構造

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

T TA法 MP法 SA 法

0.1 64.73% 72.03% 71.57%

0.5 86.82% 89.14% 89.38%

1.0 88.73% 85.84% 85.03%

5.0 84.08% 84.35% 83.49%

10.0 83.95% 84.36% 83.99%

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

e TA法 MP法 SA 法

0.1 44.65% 32.05% 31.07%

0.5 10.04% 0.02% 0.02%

1.0 0.10% 0.00% 0.00%

5.0 0.00% 0.00% 0.00%

10.0 0.00% 0.00% 0.00%

-2 -1 0

1 2

x1 -2 -1 0 1 2

0 x2 500 1000 1500 2000 2500 3000

E(x) Global Minimum:(1.58,1.58)

図 6.14: 問題(6.28)の大域的構造

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

T TA法 MP法 SA 法

0.1 90.57% 90.35% 90.70%

0.5 90.41% 90.37% 90.62%

1.0 89.99% 86.48% 86.16%

5.0 48.61% 26.86% 27.64%

10.0 20.11% 12.47% 12.28%

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

e TA法 MP法 SA 法

0.1 32.76% 33.28% 33.17%

0.5 33.91% 34.43% 32.94%

1.0 33.47% 33.46% 33.04%

5.0 32.47% 31.77% 32.15%

10.0 30.68% 30.30% 30.26%

ドキュメント内 多様体上の非線形力学系による 制約条件付最適化に関する研究 (ページ 148-162)