模擬焼鈍模擬焼鈍
模擬アニーリングこのアルゴリズムは、大きな検索空間内で命題に対する最適な解を見つけるために使用される一般的な確率的アルゴリズムです。
原理
熱力学の理論を統計に適用し、検索空間内の各点を空気中の分子として想像します。分子のエネルギーはそれ自体の運動エネルギーであり、検索空間内の各点も空気分子と同様に「エネルギー」を運びます。この点が命題にどの程度適合しているかを表現します。
このアルゴリズムは、探索空間内の任意の点から始まります。各ステップでは、まず「近傍」を選択し、次に現在の位置から「近傍」に到達する確率を計算します。
基本的な要素
状態空間と状態生成関数
1) 検索空間は状態空間とも呼ばれ、エンコードされた実行可能なソリューションのセットで構成されます。
2) 状態生成関数 (近傍関数) は、生成された候補解が解空間全体を確実にカバーするように努めるべきです。通常、これは 2 つの部分、つまり候補解の生成方法と候補解の確率分布で構成されます。
3) 候補解は、一般に、特定の確率密度関数に従って解空間をランダムにサンプリングすることによって取得されます。
4) 確率分布には一様分布、正規分布、指数分布などがあります。
状態遷移確率
1) 状態遷移確率とは、ある状態から別の状態への遷移確率を指します。
2) 一般に理解されているのは、新しいソリューションを現在のソリューションとして受け入れる確率です。
3) 現在の温度パラメータ T に関連しており、温度が低下するにつれて減少します。
4) 大都市基準が一般的に採用されます。
内部ループの終了基準
1) 目的関数の平均値が安定しているかどうかを確認します。
2) 目標値は、連続するいくつかのステップでわずかに変化します。
3) 一定のステップ数に従ったサンプリング。
アウターループの終了基準
1) 終了温度のしきい値を設定します。
2) 外側のループの反復数を設定します。
3) アルゴリズムによって検索された最適値は、連続するいくつかのステップにわたって変化しません。
4) システムのエントロピーが安定しているかどうかを確認します。
主要な手順
新状態生成機能 → 新状態受け入れ機能 → サンプリング安定性基準 → 脱熱機能 → 焼鈍終了基準
模擬焼鈍のメリット
焼きなましアルゴリズムは、パラメータが適切に設定されているという前提の下で、問題に対する近似最適解を迅速に見つけることができ、探索効率が高くなります。