模擬退火

當物件數量變得龐大時，某些最佳化問題會變得難以使用組合方法處理。一個典型的例子是旅行推銷員問題，它屬於 NP-完全 問題類。 對於這些問題，有一種非常有效的實用演算法，稱為模擬退火（之所以這樣命名，是因為它模仿了金屬中錯位原子在加熱然後緩慢冷卻時所經歷的過程）。雖然這種技術不太可能找到最優解，但即使在存在噪聲資料的情況下，它通常也能找到非常好的解。

旅行推銷員問題可以用作模擬退火的應用示例。在這個問題中，推銷員必須訪問大量城市，同時最大限度地減少旅行的總里程。如果推銷員從隨機行程開始，他可以成對交換城市訪問的順序，希望每次交換都能減少里程。這種方法的困難在於，雖然它可以快速找到區域性最小值，但它無法從那裡到達全域性最小值。

模擬退火透過引入兩個技巧改進了這種策略。第一個是所謂的“Metropolis 演算法”（Metropolis et al. 1953），其中一些不會降低里程的交換被接受，因為它們有助於求解器“探索”更多可能的解空間。 允許使用以下標準接受此類“壞”交換：

其中 是交換所暗示的距離變化（“好”交換為負；“壞”交換為正）， 是“合成溫度”， 是區間 中的隨機數。 被稱為“成本函式”，對應於金屬退火情況下的自由能（在這種情況下，溫度引數實際上是 ，其中 是玻爾茲曼常數， 是物理溫度，單位為開爾文絕對溫標）。如果 很大，則會接受許多“壞”交換，並且可以訪問大部分解空間。 要交換的物件通常是隨機選擇的，儘管可以使用更復雜的技術。

第二個技巧再次類似於金屬的退火，是降低“溫度”。在進行多次交換並觀察到成本函式僅緩慢下降後，人們會降低溫度，從而限制允許的“壞”交換的大小。 在將溫度多次降低到較低值後，人們可以“淬火”該過程，僅接受“好”交換，以便找到成本函式的區域性最小值。 有各種“退火計劃”用於降低溫度，但結果通常對細節不太敏感。

還有另一種更快的策略，稱為閾值接受（Dueck 和 Scheuer 1990）。 在這種策略中，所有好的交換都被接受，任何使成本函式升高幅度小於固定閾值的壞交換也被接受。 然後定期降低閾值，就像退火中降低溫度一樣。 這消除了玻爾茲曼標準中的求冪和隨機數生成。 因此，這種方法在計算機模擬中可以更快。 模擬退火實現為NMinimize[f, vars,Method -> "SimulatedAnnealing"].