焼きなまし法で最適解を見つけ出せ！初心者のためのアルゴリズム入門
山崎講師こんにちは。ゆうせいです。
みなさんは、山登りをしていて一番高い頂上を目指しているとき、目の前の小さな丘を登り切って満足してしまった経験はありませんか。実は、コンピューターの世界でも同じような問題が起こります。今回は、そんなもどかしい状況を打破するために生まれた、焼きなまし法というユニークなアルゴリズムについてお話しします。
焼きなまし法って一体なに？
焼きなまし法は、金属加工の技術であるアニーリングをヒントに作られた計算手法です。金属を一度熱して、ゆっくり冷やすと構造が安定する性質を、データの解析に応用したものです。
専門用語では、これをシミュレーテッドアニーリングと呼びます。機械学習の分野では、膨大な選択肢の中から最も良い答えを探し出す最適化問題でよく使われます。
想像してみてください。あなたは真っ暗な山脈の中にいて、一番高い場所に旗を立てたいとします。手元にはライトしかありません。とりあえず高い方へ進めば、近くの丘の頂上には着けるでしょう。しかし、そこが本当にこの山脈で一番高い場所だと言い切れるでしょうか。
局所最適解という落とし穴
ここで重要になるのが、局所最適解という言葉です。
これは、自分の周りだけを見れば一番良い状態だけれど、全体で見ればもっと良い答えがある状態を指します。先ほどの山の例で言えば、エベレストに登りたいのに、近所の高尾山の頂上で満足してしまうようなものです。
一方で、本当の正解のことを、大域最適解と言います。普通のアルゴリズムは、少しでも良くなる方向にしか進まないため、一度小さな丘（局所最適解）に登ると、そこから降りることができなくなります。
そこで焼きなまし法の出番です！この手法は、ときにはあえて悪い方向、つまり山を下る方向に進むことを許容します。
焼きなまし法の仕組みと数式
焼きなまし法がどのように動くのか、その心臓部を覗いてみましょう。重要なのは、温度という概念です。
最初は温度を高く設定します。温度が高いときは、エネルギーが溢れているので、今の状態よりも悪くなる方向へも活発に移動します。しかし、時間が経って温度が下がるにつれて、徐々に良い方向にしか動かなくなっていきます。
この移動する確率を決定するのが、以下の考え方です。
今のスコアを 
スコアの差 
この 
温度が高いうちは、多少のマイナスでも移動します。これにより、小さな丘から飛び降りて、もっと高い山を探しに行くことができるのです。
メリットとデメリット
焼きなまし法を使う上での良い点と注意点を確認しておきましょう。
メリット
- 局所最適解に陥りにくい：あえて悪い手を選ぶ柔軟性があるため、視野の狭い判断を避けることができます。
- 複雑な問題に強い：計算式が複雑で、どこに答えがあるか予想もつかないような問題でも、とりあえず動かし始めることが可能です。
デメリット
- 計算時間がかかる：何度も試行錯誤を繰り返しながら、ゆっくり温度を下げる必要があるため、答えが出るまで時間がかかりがちです。
- パラメータ設定が難しい：最初の温度を何度にするか、どれくらいのスピードで冷やすかという設定次第で、結果が大きく変わってしまいます。
焼きなまし法の使いどころ
この手法は、具体的にどのような場面で役立っているのでしょうか。代表的な例が、巡回セールスマン問題です。
複数の都市を最も短い距離で全て回るルートを探す問題ですが、都市が増えると組み合わせは爆発的に増えます。これを力任せに計算すると、スーパーコンピューターでも何年もかかってしまいます。焼きなまし法を使えば、現実的な時間でかなり正解に近いルートを見つけ出すことができます。
勾配降下法との比較
勾配降下法の仕組み：最短ルートで突き進む
勾配降下法は、現在の地点でどちらの方向に地面が傾いているかを調べ、その傾斜を下る方向に一歩ずつ進む手法です。
専門用語では、この傾きを勾配と呼びます。ボールが坂道を転がり落ちるように、スムーズに正解へ近づいていくのが特徴です。
数式で表すと、次のようになります。
新しい位置 
メリット
- 計算が非常に速く、効率的です。
- 正解の方向がはっきりしている問題では、無駄のない動きをします。
デメリット
- 局所最適解（小さな窪み）にはまると、そこから抜け出せません。
- 関数の形がデコボコしていると、本当の正解にたどり着けないことがあります。
焼きなまし法の仕組み：あえて逆走する勇気
これに対して焼きなまし法は、前の記事でもお話しした通り、確率を使って探索します。
今のスコア 
もし 
ここで
メリット
- 小さな窪みを飛び越えて、広い範囲を探索できます。
- 大域最適解（本当の正解）を見つける能力が高いです。
デメリット
- とにかく計算に時間がかかります。
- 温度の下げ方などの設定が難しく、職人芸のような調整が必要です。
二つの手法を比較してみよう
それぞれの特徴を表にまとめてみました。
| 特徴 | 勾配降下法 | 焼きなまし法 |
| 進む方向 | 常に良くなる方向のみ | ときどき悪くなる方向も許容 |
| 得意な形 | 滑らかなすり鉢状のグラフ | 複雑でデコボコしたグラフ |
| 探索の速さ | とても速い | じっくり時間をかける |
| 正解の質 | 近くの正解（局所解）になりがち | 最高の正解（大域解）を狙える |
どちらを選べばいいの？
結論から言うと、ディープラーニングのような膨大なデータを扱う場合は勾配降下法（またはその進化系）が主流です。なぜなら、計算速度が命だからです。
一方で、工場の勤務シフト作成や、配送ルートの最適化など、組み合わせが複雑で「絶対に失敗したくない」というパズル的な問題には焼きなまし法が輝きます。
あなたが今取り組んでいる問題は、スピード重視ですか。それとも、じっくり時間をかけてでも最高の結果を求めていますか。
まとめと今後の学習指針
焼きなまし法は、急がば回れを地で行くような、非常に人間味のあるアルゴリズムだと思いませんか。
完璧な答えを求めすぎて動けなくなるのではなく、まずは高い温度で自由に探索し、徐々に冷静になって答えを絞り込んでいく。このプロセスは、私たちの人生のキャリア形成や、新しいアイデア出しにも通じるものがあります。
もしあなたがこれから機械学習を深く学びたいのであれば、まずは以下のステップを試してみてください。
- 巡回セールスマン問題を、焼きなまし法を使って解くプログラムを書いてみる。
- 温度を下げるスピード（冷却スケジュール）を変えて、結果がどう変わるか実験する。
- 遺伝的アルゴリズムなど、他の最適化手法と比較して、それぞれの得意不得意を体感する。
まずは簡単なシミュレーションから始めて、このアルゴリズムの面白さを肌で感じてみてください。
セイ・コンサルティング・グループでは新人エンジニア研修のアシスタント講師を募集しています。
投稿者プロフィール
