焼きなまし法

最適化問題を解くための探索アルゴリズムの1つに焼きなまし法というものがある。

最急降下法のように、値が小さくなる方向に少しずつ探索を進めていくアルゴリズムでは、その出発点に依存して局所最適解に陥ることが多い。
その結果として、大域的最適解が求まらないという問題がある。

この問題を解決して、最終的に大域的最適解が求まりやすくなるように改良したのが焼きなまし法


考え方は単純で、「たまには解から遠ざかる方向にも進んでみよっか」というもの。

常に値が小さくなる方向ではなくて、たまには逆向きに進んでみると、もっとよい解が見つかるのではないか、と考える。

しかしながら、この「たまには」という言葉はあいまいすぎるので、確率pで、という具合に確率の話で説明する必要がある。

焼きなまし法では、この確率pは、値の変化量にも影響を受けるけど(解から大きく遠ざかる方向には、あまり行かないように確率pを小さくする)、もうひとつ、温度パラメータTにも依存するようにする。

温度パラメータって??

温度パラメータTは、最初は大きく、時間が経つにつれて小さくなるようなパラメータで、これが焼きなまし法の名前の由来となっている(最初は熱いけど、次第に熱が冷めていく)。

温度パラメータTが大きいときは、逆向きに進む確率が大きくなり、温度パラメータTが小さい時は逆向きに進む確率が小さくなるように確率pの式を設定する。


さて、以上をまとめると、焼きなまし法は次のような探索アルゴリズムだと言える。

「値が小さくなる方向に少しずつ探索を進めていくけど、たまには(最初のうちは頻繁に、後半は稀に)解から遠ざかる方向にも進んでみる。」

応用に役立つ50の最適化問題 (応用最適化シリーズ)

応用に役立つ50の最適化問題 (応用最適化シリーズ)

数学は最善世界の夢を見るか?――最小作用の原理から最適化理論へ

数学は最善世界の夢を見るか?――最小作用の原理から最適化理論へ