9

隣人を選ぶとき、アルゴリズムの温度を考慮する必要がありますか? たとえば、隣人を選ぶときに温度が高い場合、順列を作成する必要がありますか? それとも、温度は受け入れ確率にのみ影響しますか?

4

3 に答える 3

5

これはウィキペディアからの説明であり、いくつかの問題について実際に温度を計算する必要があると述べています。

効率的な候補生成

ヒューリスティックのより正確なステートメントは、P(E(s), E(s'), T) が大きい最初の候補状態 s' を試す必要があるということです。上記の「標準」受け入れ関数 P の場合、E(s') - E(s) が T 以下のオーダーであることを意味します。したがって、上記の巡回セールスマンの例では、2 つのランダムな都市を交換する neighbour() 関数を使用できます。この場合、都市のペアを選択する確率は、距離が T を超えると消えます。

これは、近隣を決定する際に温度が関連する要因になる可能性があることを意味します。

近隣関数の書き方に関するより有用な読み物:シミュレーテッド アニーリングのために 1 次元および n 次元空間で近隣を効率的に選択する方法

于 2015-06-11T20:27:34.330 に答える
5

後者は真です。受け入れ確率のみが温度の影響を受けます。温度が高ければ高いほど、ローカル最適から逃れるために「悪い」動きが受け入れられます。エネルギー値の低い隣人を事前に選択すると、基本的にシミュレーテッド アニーリングの考え方に反し、貪欲な検索に変わります。

ウィキペディアの疑似コード:

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.
于 2013-04-06T17:44:04.743 に答える