第68回 月例発表会（2004年5月） 知的システムデザイン研究室 Ridge関数における温度パラメータの検討 日和 悟
1 はじめに
本報告では，連続最適化問題として，2 次元の Ridge 関数を対象問題とし，シミュレーテッド・アニーリング (Simulated Annealing:SA)を適用する際の，重要温度領 域および温度パラメータの重要性について検討を行う．2 SA とは
2.1 SAの概要 SAは Kirkpatrik らによって提案された最適化問題の ための近似解法の 1 つである．システムの計画や運用 などの効率化を考える場合，多くの問題が組み合わせ最 適化問題として定式化できるが，実際的な問題の多くは 厳密な最適解を求めるのは困難である．そこで，この種 の問題は満足できる解を求める近似解法が適用されてい る．SA は，高温で溶融状態にある金属を徐々に冷やす ことによって，もとの金属より欠陥の少ない優れた結晶 構造を作る物理プロセス (焼きなまし) を計算機上に模 倣した手法である． 2.2 SAにおける温度の重要性 2.2.1 SAにおける温度パラメータとは 連続空間における SA による探索では，エネルギー関 数の山を，温度により改悪を受理して越えなければなら ない．改悪の受理は式 (1) に示す Metropolis 基準によっ て確率的に行われる．なお，∆E は状態遷移におけるエ ネルギーの変化量を示す．4) A(E, E, T ) = exp(−∆E T ) (1) 温度T は，エネルギーが増大する方向への推移確率 に重大な影響を与えるパラメータである．温度が高い場 合は改悪方向への推移確率も大きくなり，反対に温度が 低い場合は改良方向に推移しやすくなる． 2.2.2 重要温度領域とは SAは，広範囲の最適化問題に有効な汎用近似解法で ある．しかしながら，解探索の振る舞いを制御する温 度スケジュールの設定が非常に困難である．温度スケ ジュールに関する研究は数多く行われており，一定温度 のみで探索を行うことにより良好な解が得られることも 示されている．この一定温度の探索で良好な解が得られ る温度領域を重要温度領域と呼ぶ．1)3 重要温度領域の調査
3.1 実験の目的 この実験では，2 次元の Ridge 関数に SA を適用する 際の温度パラメータの重要性を検討する．そのために， 一定温度のアニーリングを行い，Ridge 関数に重要温度 領域が存在するかを調査した． 3.2 パラメータ 2次元 Ridge 関数に重要温度領域が存在するかを調査 するため，最高温度と最低温度の間を等比的に 32 分割 し，一定温度のアニーリングを行った．用いたパラメー タは Table 1 の通りである． Table 1 実験に用いたパラメータ パラメータ 値 総アニーリング数 102400 近傍 1.0 最高温度 10.0 最低温度 0.01 3.3 対象問題 本実験の対象問題は Ridge 関数である．Ridge 関数は 式 (2) で表される． FRidge(x) = n i=1 i j=1 xj 2 (2) (−64 ≤ xi < 64) min(FRidge(x)) = F (0, 0, . . . , 0) = 0 2次元 Ridge 関数のランドスケープと等高線は Fig. 1 のようになる． -64 0 64 0 5000 10000 15000 20000 -64 0 64 -60 -40 -20 0 20 40 60 -60 -40 -20 0 20 40 60 Fig. 1 ランドスケープと等高線 1Fig. 1の通り，Ridge 関数は単峰性の関数であり，設 計変数間に依存関係をもつ． 3.4 実験結果 実験結果を Fig. 2 に示す．グラフの縦軸はエネルギー 値, 横軸は温度である．なお，図中の median，max，min は 100 試行で得られた各温度における最小エネルギー値 の中央値，最大値，最小値である． 1.0E-010 1.0E-009 1.0E-008 1.0E-007 1.0E-006 1.0E-005 1.0E-004 1.0E-003 1.0E-002 1.0E-001
1.0E-002 1.0E-001 1.0E+000 1.0E+001
Energy Temperature max median min Fig. 2 温度とエネルギーの関係 3.5 考察 Fig. 2より，温度を変えても，得られる最適解の精 度に著しい変化が見られる温度領域は見られなかった． よって，Ridge 関数には重要温度領域は存在しないと思 われる．
