2

さまざまな状況でシミュレーテッド アニーリングを使用したいと考えています。ネットのすべてのシミュレートされたアニーリング アルゴリズムは、アルゴリズムに温度の例を提供します。ウィキのように

s ← s0; e ← E(s)                                  // Initial state, energy.
sbest ← s; ebest ← e                              // Initial "best" solution
k ← 0                                             // Energy evaluation count.
while k < kmax and e > emax                       // While time left & not good enough:
 T ← temperature(k/kmax)                         // Temperature calculation.
 snew ← neighbour(s)                             // Pick some neighbour.
 enew ← E(snew)                                  // Compute its energy.
 if P(e, enew, T) > random() then                // Should we move to it?
  s ← snew; e ← enew                            // Yes, change state.
 if enew < ebest then                            // Is this a new best?
   sbest ← snew; ebest ← enew                    // Save 'new neighbour' to 'best found'.
 k ← k + 1                                       // One more evaluation done
return sbest                                      // Return the best solution found.

では、この「T」は一般的に何を表しているのでしょうか? チェスにシミュレートされたアニーリングを使用するとします。このアルゴリズムを使用して、コンピューターの次の動きを見つけます。私は現在の状態（S）を持っており、それは値（e）です。次の状態 (snew) とその値 (enew) があります。では、チェスの「T」は何でしょう? 必要ですか！このアルゴリズムの一般的な形式はありますか? つまり、この温度の例がなくても、基本的なアイデアを得ることができます! 何も見つかりません。助けてください。前もって感謝します......

4

1 に答える 1

3

ネット上のすべての例では、シミュレートされたアニーリングの標準的な用語であるため、温度の例を使用しています。SA は物理学にヒントを得た手法であり、アニーリングと呼ばれる現実世界の現象をモデルにしています。これは、遺伝的アルゴリズムのすべての例で遺伝子と染色体について話しているのとほとんど同じです。

数学を十分にさかのぼると、さまざまな最適化のメタヒューリスティックといくつかの物理プロセスの間にいくつかの魅力的なつながりがあり、通常はエントロピーの概念によって橋渡しされます。

しかし、非常に大まかに言うと、シミュレートされたアニーリングの温度 T は、グローバル (または少なくともより適切なローカル) 最小値を検索する際に、アルゴリズムがローカル最小値から「ジャンプ」する意欲または能力に対応します。温度が高いほどランダム性が高くなり、ジャンプが多くなり、最悪の構成になることさえあります。温度が低いとランダム性が低くなり (最終的には純粋に貪欲なアルゴリズムになります)、どんなに浅くても極小値を逃れることはできません。

そのアイデアをアプリケーションにどのように使用するかについては、そうですね。ほとんどのメタヒューリスティックを正しく機能させるには、ある程度の洞察と創造性が必要です。温度について語らない SA の議論を見つけることは決してないでしょう。

于 2013-06-22T06:09:35.007 に答える