焼きなまし法 焼きなまし法の概要

ウィキペディア

焼きなまし法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/31 09:18 UTC 版)

この項目では、確率的メタアルゴリズムについて説明しています。金属の熱処理については「焼きなまし」をご覧ください。

その名称は、金属工学における焼きなましから来ている。焼きなましは、金属材料を熱した後で徐々に冷やし、結晶を成長させてその欠陥を減らす作業である。熱によって原子は初期の位置（内部エネルギーがローカルな極小状態）から離され、よりエネルギーの高い状態をうろつく。ゆっくり冷却することで、原子は初期状態よりも内部エネルギーがさらに極小な状態を得る可能性が多くなる。

SAアルゴリズムは、解を繰り返し求め直すにあたって、現在の解のランダムな近傍の解を求めるのだが、その際に与えられた関数の値とグローバルなパラメータ T（温度を意味する）が影響する。そして、前述の物理過程との相似によって、T（温度）の値は徐々に小さくなっていく。このため、最初はTが大きいので、解は大胆に変化するが、Tがゼロに近づくにつれて収束していく。最初は簡単に勾配を上がっていけるので、山登り法で問題となるようなローカルな極小に陥ったときの対処を考える必要がない。

概要

焼きなまし法では、探索空間の各点「s」は物理システムの「状態」に対応し、最小化すべき関数 E(s) は物理状態の「内部エネルギー」に対応する。従って、目標はシステムを任意の「初期状態」からできる限りエネルギーが最小の状態にすることである。

基本的反復

各ステップでは、SAのヒューリスティックは、現在状態 s のいくつかの近傍 s' を検討し、現在状態 s のままがよいか、いずれかの近傍状態に遷移するのがよいかを確率的に決定する。その際、システムが最終的にエネルギーの低い状態へ向かうよう考慮する。このステップは、十分よい結果が得られるまで、あるいは予定された計算時間が尽きるまで繰り返される。

状態近傍

各状態の近傍は、アプリケーション固有の方法で、通常ユーザーによって指定される。たとえば、巡回セールスマン問題において、個々の状態は、一般に「ツアー」（訪問する都市の順列）と呼ばれる。その場合、近傍とは、都市の順列の中で一箇所だけ都市の順番を入れ替えた順列と考えることができる。

遷移確率

現在状態 s から新たな状態候補 s' への遷移確率は、二つの状態のエネルギー e = E(s) と e' = E(s' ) の関数 P(e, e' , T) で与えられる。ここで T は「温度」に相当し、時間と共に変化するグローバルなパラメータである。

遷移確率 P の基本的な必須条件として、e' > e のときにゼロでない値を返さなければならないという点があげられる。これは、ときには「悪い」と思われる状態（エネルギーの高い状態）へもシステムが遷移可能であることを意味する。これは「ローカルな極小状態」に張り付いてしまうのを防ぐ機能である。「ローカルな極小状態」とは、そのエネルギーが真の極小には程遠いが、近傍とだけ比べれば極小であるような状態を意味する。

一方で、Tが 0に近くなるにつれて、e' > e であれば P(e, e' , T) の値をゼロに近づけ、e' < e であればその値を大きくする。これにより、Tが十分に小さくなれば、システムは極小に向かい、逆の動きは封じられる。特に T が 0 になると、山登り法を使うことで近傍の極小に確実に向かわせることもできる。

関数 P は e' −e の値が増大する際には確率を減らす値を返すように設定される。つまり、ちょっとしたエネルギー上昇の向こうに極小がある可能性の方が、どんどん上昇している場合よりも高いという考え方である。しかし、この条件は必ずしも必須ではなく、上記の必須条件が満たされていればよい。

これらの特性により、状態 s の変化は温度 T に大きく依存する。大まかに言えば、sの変化は T が大きいときには劇的に変化し、T が小さくなるとゆるやかに変化する。

焼きなましスケジュール

焼きなまし法のもうひとつの本質的な機能は、シミュレーションが進むにつれて、温度が徐々に下がっていく点である。最初Tは高い（あるいは無限大の）値に設定され、何らかの「焼きなましスケジュール」に従って、ステップを経るにつれて減少していく。そのスケジュールは、ユーザーが指定する場合もあるが、予定された時間には T =0 になって終わらなければならない。このようにすると、システムは最初のうちはエネルギー関数の小さな変化を無視して最適解を求めて探索空間の広い領域をさまよい、徐々にエネルギーの低い領域に向かって探索範囲を狭めていき、最終的に最急降下法のヒューリスティックに従って最もエネルギーの低い状態に降りていくのである。

最適解への収束

任意の有限な問題に焼きなまし法を適用する場合、焼きなましスケジュールを調整してやれば、グローバルな最適解を得る確率が 1 に近づくことが知られている。しかし、理論上どうであれ、焼きなまし法で意味のある結果を得るには、解空間を十分に探索するための時間が必要ということである。