検索に移動この項目では、確率的メタアルゴリズムについて説明しています。金属の熱処理については「焼きなまし」をご覧ください。汎用の乱択アルゴリズムである。広大な探索空間内の与えられた関数の大域的最適解に対して、よい近似を与える。その名称は、金属工学における焼きなましから来ている。焼きなましは、金属材料を熱した後で徐々に冷やし、結晶を成長させてその欠陥を減らす作業である。熱によって原子は初期の位置(内部エネルギーがローカルな極小状態)から離され、よりエネルギーの高い状態をうろつく。冷却することで、原子は初期状態よりも内部エネルギーがさらに極小な状態を得る可能性が多くなる。T(温度を意味する)が影響する。前述の物理過程との相似によって、T(温度)の値は徐々に小さくなっていく。このため、最初はTが大きいので、解は大胆に変化するが、Tがゼロに近づくにつれて収束していく。最初は簡単に勾配を上がっていけるので、山登り法で問題となるようなローカルな極小に陥ったときの対処を考える必要がない。物理状態の「内部エネルギー」に対応する。従って、目標はシステムを任意の「初期状態」からできる限りエネルギーが最小の状態にすることである。ままがよいか、いずれかの近傍状態に遷移するのがよいかを確率的に決定する。その際、システムが最終的にエネルギーの低い状態へ向かうよう考慮する。このステップは、十分よい結果が得られるまで、あるいは予定された計算時間が尽きるまで繰り返される。状態近傍[編集]各状態の近傍は、アプリケーション固有の方法で、通常ユーザーによって指定される。巡回セールスマン問題において、個々の状態は、一般に「ツアー」(訪問する都市の順列)と呼ばれる。その場合、近傍とは、都市の順列の中で一箇所だけ都市の順番を入れ替えた順列と考えることができる。「温度」に相当し、時間と共に変化するグローバルなパラメータである。ときにゼロでない値を返さなければならないという点があげられる。これは、ときには「悪い」と思われる状態(エネルギーの高い状態)へもシステムが遷移可能であることを意味する。これは「ローカルな極小状態」に張り付いてしまうのを防ぐ機能である。「ローカルな極小状態」とは、そのエネルギーが真の極小には程遠いが、近傍とだけ比べれば極小であるような状態を意味する。あればその値を大きくする。これにより、Tが十分に小さくなれば、システムは極小に向かい、逆の動きは封じられる。なると、山登り法を使うことで近傍の極小に確実に向かわせることもできる。値が増大する際には確率を減らす値を返すように設定される。したエネルギー上昇の向こうに極小がある可能性の方が、どんどん上昇している場合よりも高いという考え方である。この条件は必ずしも必須ではなく、上記の必須条件が満たされていればよい。小さくなるとゆるやかに変化する。焼きなましスケジュール[編集]焼きなまし法のもうひとつの本質的な機能は、シミュレーションが進むにつれて、温度が徐々に下がっていく点である。最初Tは高い(あるいは無限大の)値に設定され、何らかの「焼きなましスケジュール」に従って、ステップを経るにつれて減少していく。なって終わらなければならない。このようにすると、システムは最初のうちはエネルギー関数の小さな変化を無視して最適解を求めて探索空間の広い領域をさまよい、徐々にエネルギーの低い領域に向かって探索範囲を狭めていき、最終的に最急降下法のヒューリスティックに従って最もエネルギーの低い状態に降りていくのである。近づくことが知られている。理論上どうであれ、焼きなまし法で意味のある結果を得るには、解空間を十分に探索するための時間が必要ということである。きなましスケジュールなどを指定しなければならない。これらの選択はこの方法の有効性に大きく影響する。すべての問題に最善の選択というものは無い。このことは、ノーフリーランチ定理としてしられている。与えられた問題に最善の選択を見つける一般的方法も存在しない。焼きなまし法を適用することは、科学というよりも技能と言えるものであることが観察されている。状態近傍[編集]近傍の選択方法は、特に重要である。「探索グラフ」としてモデル化できる場合もある。状態を点とし、近傍となる点との間に線が引かれる。初期状態からこのグラフ上の相対的に短いパスを通って「十分によい」状態となる可能性は極めて高く、そのようなパスを焼きなまし法の繰り返しで辿ることもほぼ間違いない。同じエネルギーの状態群を置く様に探索グラフを作成し、この手法を適用する場合を考える。したがって、巡回セールスマン問題なら、経路上隣接する2つの都市の順序を入れ替えることで近傍を生成した方が、任意の都市を入れ替えた経路を生成するよりもエネルギーの変化が小さい。回の入れ替えを必要とする。替えではエネルギーの変化は小さい。上述の条件を満たしている限り、状態近傍グラフほど重要ではない。依存するが、実際には同じ確率関数をどんな問題にも適用し、焼きなましスケジュールで問題固有の調整を行うことが多い。返すよう定義されている(すなわち下りの移動は必ず実行される)。この数式は、ガスの分子のエネルギー配布を表すマクスウェル分布からサンプルを生成するために使われたメトロポリス法から出てきたものといわれている。焼きなまし法でこの特定の数式を使うという数学的正当性はまったくない。物理的な相似さえ誤解を招く。遷移する実際の確率はその式とは全く関係ない。焼きなましスケジュール[編集]焼きなましスケジュールは、近傍関数ほど重要ではないが、注意して選択する必要がある。初期温度は、上りと下りの遷移確率をほぼ同じにする程度に大きく設定しなければならない。なるかを予測しておく必要がある。なるまで減少していく。一般的には、指数関数的に減少するようスケジュールする。掛けることで減少させる。以下になる解が見つかるまで動作する。評価値(エネルギー状態)。近傍をランダムに1つ生成する。TEMPERATURE(r)焼きなましスケジュール。使用すべき温度を返す。