シミュレーテッドアニーリングアルゴリズムでの近隣選択

Question

ネイバーを選択するとき、アルゴリズムの温度を考慮する必要がありますか？例えば隣人を選ぶときに温度が高い場合、順列を作るべきですか？あるいは、温度は受容確率にのみ影響しますか？

Answer 1

後者は真です：許容確率だけが温度の影響を受けます。温度が高ければ高いほど、より「悪い」動きが局所最適値から逃れるために受け入れられる。エネルギー値の低い隣人をあらかじめ選択しておけば、Simulated Annealingの考え方と基本的に矛盾し、貪欲な検索に変わります。 Wikipediaから

擬似コード：

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. 

Answer 2

私も同じ質問があったが、私は別のポストBasics of Simulated Annealing in Pythonからの答えはTは非常に合理的である隣人を選ぶことに関連することができます示唆していると思います。

また、隣人を選択することも問題によって異なります。近所を制限する主な理由は、まともな解決策を見つけたら、後で悪い解決策に移行しても、少なくとも近所にとどまることです。直感は、最も客観的な機能がやや滑らかであるため、良い解決策が他の良い解決策の近くにあるということです。だからあなたは良いソリューションの近くにあなたを保つのに十分小さいが、あなたがそれらをすばやく見つけることができるほど十分な大きさの近所が必要です。あなたが試みることの1つは、時間の経過とともに近傍を減少させることです（温度に比例させるなど）。 - hunse Nov 4 '13 at 20:58

Answer 3

ここでは、いくつかの問題について実際に温度を計算する必要があると記載されているwikipediaの説明があります。

効率的な候補生成

ヒューリスティックのより正確なステートメントは、1つの（T、E（S、E（S）Pは））第1の候補状態sを試みるべきであることです大。上記の「標準」受理関数Pについては、E（s '）-E（s）がT以下のオーダーであることを意味する。したがって、上記の巡回セールスマンの例では、1つのこの暗示ない都市ペアを選択する確率はT.超えての距離が増加するにつれて

を消滅2つのランダムな都市をスワップ（）関数、隣人を使用することができその温度は隣人を決定する際の関連要因となり得る。隣人関数を作成する方法について

もっと便利な読書：How to efficiently select neighbour in 1-dimensional and n-dimensional space for Simulated Annealing