摘要
本文簡介了模擬退火的基本思想，以于模擬時的主要參數(shù)的選擇根據(jù)，然后給出一個求二維函數(shù)極值的具體問題和解法，并給出C#源代碼。
l 概述
在管理科學、計算機科學、分子物理學和生物學以及超大規(guī)模集成電路設計、代碼設計、圖像處理和電子工程等科技領域中，存在大量組合優(yōu)化瓿。其中許多問題如貨郎擔問題、圖著色問題、設備布局問題以及布線問題等，至今沒有找到有效的多項式時間算法。這些問題已被證明是NP完全問題。
1982年，KirkPatrick將退火思想引入組合優(yōu)化領域，提出一種解大規(guī)模組合優(yōu)化問題的算法，對NP完全組合優(yōu)化問題尤其有效。這源于固體的退火過程，即先將溫度加到很高，再緩慢降溫(即退火)，使達到能量最低點。如果急速降溫(即為淬火)則不能達到最低點.。
在［1］中的解釋為：Simulation Annealing is a technique which can be applied to any minimisation or learning process based on successive update steps (either random or deterministic) where the update step length is proportional to an arbitrarily set parameter which can play the role of a temperature. Then， in analogy with the annealing of metals， the temperature is made high in the early stages of the process for faster minimisation or learning， then is reduced for greater stability.
即：模擬退火算法是一種能應用到求最小值問題或基本先前的更新的學習過程（隨機或決定性的）。在此過程中，每一步更新過程的長度都與相應的參數(shù)成正比，這些參數(shù)扮演著溫度的角色。然后，與金屬退火原理相類似，在開始階段為了更快地最小化或學習，溫度被升得很高，然后才（慢慢）降溫以求穩(wěn)定。
l 模擬退火算法的主要思想
就函數(shù)最小值問題來說，模擬退火的主要思想是：在搜索區(qū)間（二維平面中）隨機游走（即隨機選擇點），再以Metropolis抽樣準則，使隨機游走逐漸收斂于局部最優(yōu)解。而溫度即是Metropolis算法中的一個重要控制參數(shù)，可以認為這個參數(shù)的大小控制了隨時過程向局部或全局最優(yōu)解移動的快慢。
冷卻參數(shù)表、領域結構和新解產(chǎn)生器、接受準則和隨機數(shù)產(chǎn)生器（即Metropolis算法）一起構成算法的三大支柱。
l 重點抽樣與Metroplis算法：
Metropolis是一種有效的重點抽樣法，其算法為：系統(tǒng)從能量一個狀態(tài)變化到另一個狀態(tài)時，相應的能量從E1變化到E2，概率為p = exp[(E2- E1)/kT ]。如果E2 E1，系統(tǒng)接收此狀態(tài)，否則，以一個隨機的概率接收此或丟棄此狀態(tài)。這種經(jīng)常一定次數(shù)的迭代，系統(tǒng)會逐漸趨于一引穩(wěn)定的分布狀態(tài)。
重點抽樣時，新狀態(tài)下如果向下則接受（局部最優(yōu)），若向上（全局搜索），以一定機率接受。模擬退火方法從某個初始解出發(fā)，經(jīng)過大量解的變換后，可以求得給定控制參數(shù)值時組合優(yōu)化問題的相對最優(yōu)解。然后減小控制參數(shù)T的值，重復執(zhí)行Metropolis算法，就可以在控制參數(shù)T趨于零時，最終求得組合優(yōu)化問題的整體最優(yōu)解�？刂茀�(shù)的值必須緩慢衰減。
其中溫度是一個Metropolis的重要控制參數(shù)，模擬退火可視為遞減控制參數(shù)什時Metroplis算法的迭代。開始T值大，可能接受較差的惡化解，隨著T的減小，只能接受較好的惡化解，最后在T趨于0時，就不再接受任何惡化解了。
在無限高溫時，系統(tǒng)立即均勻分布，接受所有提出的變換。T的衰減越小，T到達終點的時間越長；但可使馬可夫鏈越小，到達準平衡分布的時間越短，
l 參數(shù)的選擇：
我們稱調(diào)整模擬退火法的一系列重要參數(shù)為冷卻進度表。它控制參數(shù)T的初值及其衰減函數(shù)，對應的MARKOV鏈長度和停止條件，非常重要。
一個冷卻進度表應當規(guī)定下述參數(shù)：
1． 控制參數(shù)t的初值t0;
2． 控制參數(shù)t的衰減函數(shù)；
3． 馬爾可夫鏈的長度Lk。（即每一次隨機游走過程，要迭代多少次，才能趨于一個準平衡分布，即一個局部收斂解位置）
4． 結束條件的選擇
有效的冷卻進度表判據(jù)：
一．算法的收斂：主要取決于衰減函數(shù)和馬可夫鏈的長度及停止準則的選擇
二．算法的實驗性能：最終解的質(zhì)量和CPU的時間
參數(shù)的選擇：
一）控制參數(shù)初值T0的選取
一般要求初始值t0的值要充分大，即一開始即處于高溫狀態(tài)，且Metropolis的接收率約為1。
二）衰減函數(shù)的選取
衰減函數(shù)用于控制溫度的退火速度，一個常用的函數(shù)為：T(n + 1) = K*T(n)，其中K是一個非常接近于1的常數(shù)。
三）馬可夫鏈長度L的選取
原則是：在衰減參數(shù)T的衰減函數(shù)已選定的前提下，L應選得在控制參數(shù)的每一取值上都能恢復準平衡。
四）終止條件
有很多種終止條件的選擇，各種不同的條件對算法的性能和解的質(zhì)量有很大影響，本文只介紹一個常用的終止條件。即上一個最優(yōu)解與最新的一個最優(yōu)解的之差小于某個容差，即可停止此次馬爾可夫鏈的迭代。
l 例題：
