第68回 月例発表会（2004年05月） 知的システムデザイン研究室 シミュレーテッドアニーリングにおける温度パラメータの検討 藤田 佳久
1 はじめに
シミュレーテッドアニーリング（Simulated Anneal-ing：SA）とは， 金属の焼きなましを計算機上に模範 した手法で，組合せ最適化問題のための近似解法の１ つである．良好な解探索能力を得るためには適切なパラ メータを設定する必要がある. また， 適切なパラメー タは対象問題に依存する. そこで， 本報告では， SA を Schwefel 関数の連続最適化問題に適用し， 温度パラ メータが解探索能力に与える影響について検討を行う.2 実験概要
2.1 対象問題 対象問題は，Equ.(1) で表される Schwefel 関数であ る.Schwefel 関数は，全ての設計変数が 420.968750 の 時，”-418.982887 ×次元数 ”の最適解を得られるとさ れる多峰性関数である．最適解の周辺に準最適解が存在 しないため，探索プロセスの早い段階において大域的な 解探索がなされなければ，局所的最適解に収束する.Fig. 1に 2 次元の場合の外形とエネルギーの等高線を示す. FSchwefel(x) = n i=1 −xisin |xi| (1) (−512 ≤ xi< 512) ·n Fig. 1 Schwefel関数（2 次元） 2.2 検討パラメータ 本報告では，SA の温度パラメータについて実験を行 う．検討方法として，以下の 3 点について検討を行った． • 最低温度を固定し最高温度を変化させ，最高温度 が解探索に与える影響を検討 • 最高温度を固定し最低温度を変化させ，最低温度 が解探索に与える影響を検討 • 最高温度と最低温度を同じ値（一定温度）にし，ど の温度が解探索に影響を与えるかを検討 温度は，次の状態への推移を受理するか否かの判定に 用いられるパラメータである．温度が高い場合は，改悪 方向への推移が大きくなる．反対に低い場合は，改悪方 向への推移が小さくなる．しかし，どのような温度でも 改悪方向への推移確率が 0 になるわけではない． 2.3 実験方法 本実験で実装した SA は，近傍に一様分布を用い，受理 判定の確率には Fig. 2 に示す Metropolis 基準を用いた． Fig. 2 Metropolis基準 パラメータの初期値は，Table1 に示す値に設定し検 討を行った． Table 1 パラメータの初期値 パラメータ 値 最高温度 10.0 最低温度 0.01 近傍幅 100.0 クーリング周期 10000 総アニーリング数 320000 また，本実験ではエネルギー値が-837 以下のとき，最 適解領域に達したとする．3 数値実験
3.1 温度パラメータに関する実験結果 • 最高温度 最高温度を 5∼200 の間で 5 刻みに変化させ，最 高温度が解探索に与える影響を検討した．その他 のパラメータは Table1 の値を用いた．最高温度 と最良エネルギーの関係を Fig. 3 に示す．Fig. 3 は，各最高温度に対する 100 回試行の最良エネル ギーの中央値を示したものである．縦軸に最良エ ネルギー，横軸に最高温度を示した． 1Fig. 3 最高温度と最良エネルギーの関係 Fig. 3より，最高温度を上げることによって最良 エネルギーが低くなり，最高温度が 80 以上で最適 解領域に到達することが分かった． • 最低温度 最低温度を 0.0001,0.001,0.01,0.1,1.0 と 5∼195 の 間で 5 刻みに変化させ，最低温度が解探索に与え る影響を検討した．その他のパラメータは Table1 の値を用いた．また，最高温度は局所的最適解に 陥らない為に，上記の最高温度の検討結果を踏ま えて 200 とした．最低温度と最良エネルギーの関 係を Fig. 4 に示す．Fig. 4 は，各最低温度に対す る 100 回試行の最良エネルギーの中央値を示した ものである．縦軸に最良エネルギー，横軸に最低 温度を示した． Fig. 4 最低温度と最良エネルギーの関係 Fig. 4より，最低温度は解探索に影響がないこと が分かった． 3.2 温度と近傍パラメータの兼合いに関する実験結果 • 最高温度と近傍 最高温度と近傍パラメータを変化させ，最高温度 と近傍の兼合いが解探索に与える影響を検討した． 検討を行った最高温度は 5∼200（5 刻み），近傍 は 10，100，200 である．その他のパラメータは Table1の値を用いた．最高温度と近傍と最良エネ ルギーの関係を Fig:4 に示す．Fig. 5 では各近傍 において各最高温度に対する 100 回試行の最良エ ネルギーの中央値を示したものである．縦軸に最 良エネルギー，横軸に最高温度を示した． Fig. 5 最高温度と近傍と最良エネルギーの関係 Fig. 5より，近傍を大きくすることによって，低 い最高温度で最適解領域に到達することが分かっ た．また，同じ最高温度では，近傍が大きいほど より良い解に到達することが分かった． • 最低温度と近傍 最低温度と近傍パラメータを変化させ，最低温度 と近傍の兼合いが解探索に与える影響を検討した． 検討を行った最低温度は 5∼195（5 刻み），近傍 は 10，100，200 である．その他のパラメータは Table1の値を用いた．最低温度と近傍と最良エネ ルギーの関係を Fig. 6 に示す．Fig. 6 では各近傍 において各最低温度に対する 100 回試行の最良エ ネルギーの中央値を示したものである．縦軸に最 良エネルギー，横軸に最低温度を示した． Fig. 6 最低温度と近傍と最良エネルギーの関係 Fig. 6より，近傍を 100 以上にすることによって， 最低温度が解探索に影響を与えないことが分かっ た．また，最低温度を 20 以上にすることによって， 最低温度が解探索に影響を与えないことが分った． 2
• 一定温度と近傍 一定温度と近傍パラメータを変化させ，温度と近 傍の兼合いが解探索に与える影響を検討した. 検 討を行った温度は 5∼200（5 刻み），近傍は 10， 100，200 である. その他のパラメータは Table1 の 値を用いた. 温度と近傍と最良エネルギーに関す る検討結果を Fig. 7 に示す.Fig. 7 ではそれぞれ の近傍における中央値の解探索履歴の比較を行っ た.Fig. 7 の縦軸にエネルギー値， 横軸に温度を 示した. Fig. 7 温度を固定した際の近傍と最良エネルギーの関係 Fig. 5と Fig. 7 を比較すると，温度を下げない方 が，より低い最高温度で最適解領域に到達するこ とが分かった．また，近傍 10 の場合においては， Fig. 5では最適解領域に到達しなかったが，Fig. 7では最適解領域に到達した．つまり，温度を下げ ない方が，より良い解が得られることが分かった．
