第68回 月例発表会（2004年5月） 知的システムデザイン研究室 シミュレーテッドアニーリングにおけるアニーリングステップの検討 織田 博子
1 はじめに
シミュレーテッドアニーリング（Simulated Anneal-ing：SA）は，金属の焼きなましをシミュレートしたも のであり，与えられた初期状態から探索を始め，状態を 遷移させて探索を続けることで最終的にはエネルギー が最小となる状態，すなわち目的関数の大域的最適解を 発見する最適化手法である．SA では良好な解探索を行 うために適切なパラメータを設定する必要があり，よっ て各パラメータが探索に与える影響を把握することが必 要となる．そこで本報告では，SA を Ridge 関数の連続 最適化問題に適用し，SA のパラメータの１つであるア ニーリングステップが解探索能力に与える影響について 検討を行う.2 数値実験
2.1 対象問題 対象問題は式 (1) に示される 2 次元 Ridge 関数であ る. Ridge 関数は，設計変数間に依存関係を持つ単峰性 関数という特徴を持つ．Fig. 1 に 2 次元の場合の外形と エネルギーの等高線を示す. FRidge(x) = n i=1 i j=1 xj 2 (1) (−64 ≤ xi< 64) min(FRidge(x)) = F (0, 0, . . . , 0) = 0 C ᄖᒻ D ╬㜞✢ Fig. 1 Ridge関数（2 次元) 2.2 実験概要 本実験では，アニーリングステップについて検討を行 う. アニーリングステップ以外のパラメータに関しては 最高温度 10.0，最低温度 0.01，近傍 1.0，次元数 2，クー リングステップ 32 と固定し，アニーリングステップの みを変化させることによって，アニーリングステップが 解探索に与える影響について検討する． 2.3 実験結果 アニーリングステップを N 回とし，100 回測定を行っ た．全試行における最良エネルギーの中央値を Fig. 2 に 示す．縦軸はエネルギー値，横軸はアニーリングステッ プを示している． Fig. 2 中央値 (1024≤N≤13312) Fig. 2よりアニーリングステップが少ない場合には最 良エネルギー値の変化は大きいものの，アニーリングス テップを増やすにつれて，解は収束しているように見え る．そこで，さらに指数的にアニーリングステップを増 やし測定を行った．結果を Fig. 3 に示す． Fig. 3 中央値 (29≤N≤224) Fig. 3よりアニーリングステップを増やすほど最良エ ネルギー値がさらに下がっていくことが確認できた．3 考察
本実験結果から，Ridge 関数ではアニーリングステッ プを増加させると，最良エネルギー値が小さくなること が確認できた．ただし，アニーリングステップの増加に 伴う最良エネルギー値の変化量は，次第に小さいものと なる．参考文献
1) 昌山 智，ISDL Reports No.20030711003
