模擬退火 simulatedannealing 算法是局部搜索算法的擴展 它源于對固體退火過程的模擬 采用Metropolis接受準則 并用一組稱為冷卻進度表的參數控制算法進程 使算法在多項式時間里給出一個近似最優解 模擬退火算法最早的思想由Metropolis在1953年提出 Kirkpatrick在1983年成功地應用在組合最優化問題中 第2章模擬退火算法 一固體退火過程 退火是一種物理過程 固體退火是先將固體加熱至熔化 再徐徐冷卻使之凝固成規整晶體的熱力學過程 退火過程中 系統在每一溫度下達到平衡態 系統狀態的分布滿足一定的概率分布 即在溫度T 系統達到平衡態后 分子停留在狀態r滿足波茲曼 Boltzmann 概率分布 2 1模擬退火算法及模型 其中 E r 為狀態r的能量 kB 0為波茲曼常數 為分子能量的一個隨機變量 稱為波茲曼因子 Z T 為概率分布的標準化因子 先研究由 2 1 確定的函數隨T變化的趨勢 選定兩個能量E1 E2 在同一個溫度T 有 D為狀態空間 在同一個溫度 2 2 表示分子停留在能量小狀態的概率比停留在能量大狀態的概率要大 當溫度相當高時 2 1 的概率分布使得每個狀態的概率基本相同 接近平均值1 D D 為狀態空間D 中狀態的個數 此時 具有最低能量狀態的波茲曼概率接近并超出平均值1 D 當rmin是D中具有最低能量的狀態時 得 由 所以 關于溫度T是單調下降的 又有 其中 D0是具有最低能量的狀態集合 因此得到 當T趨向于0時 當溫度趨向于0時 2 1 決定的概率漸近 由此可以得到 在溫度趨向于0時 分子停留在最低能量狀態的概率趨向1 綜合上面的討論 分子在最低能量狀態的概率變化趨勢由圖 a 表示 對于非能量最小的狀態 由 2 2 和分子在能量最小狀態的概率是單調減小的事實 在溫度較高時 分子在 使 2 1 決定的概率在 0 t 是單調升的 再由 2 4 可知 當溫度趨于0時 2 1 定義的概率趨于0 概率變化曲線見圖 b 從上面的討論得到 在溫度很低時 能量越低的狀態的概率值越高 在極限狀況 只有能量最低的點概率不為 即有 1 系統在T平衡時 系統狀態的概率分布趨于 2 1 式 例2 1簡化概率分布 2 1 為 其中q t 為標準化因子 設共有四個能量點x 1 2 3 4 率分布變化 二 Metropolis準則 固體在恒定溫度下達到熱平衡的過程可以進行模擬 1953年 Metropolis等提出重要性采樣法 他們用下述方法產生固體的狀態序列 先給定以粒子相對位置表征的初始狀態i 作為固體的當前狀態 該狀態的能量是Ei 然后用攝動裝置使隨機選取的某個粒子的位移隨機地產生一微小變化 得到一個新狀態j 新狀態的能量是Ej 如EjEi 則考慮熱運動的影響 該新狀態是否重要狀態 要依據固體處于該狀態的幾率來 判斷 由 2 1 知 固體處于i和j的概率的比值等于相應Boltzmann因子的比值 即 r是一個小于1的數 用隨機數發生器產生一個 0 1 區間的隨機數 若r 則新狀態j作為重要狀態 否則舍去 若新狀態j是重要狀態 就以j取代i成為當前狀態 否則仍以i為當前狀態 再重復以上新狀態產生過程 在大量固體狀態的變換后 系統趨于能量較低的平衡狀態 固體狀態的概率分布趨于 2 1 式的Boltzmann概率分布 由 式可知 高溫下可接受與當前狀態能差較大的新狀態為重要狀態 而在低溫下只能接受與當前狀態能差較小的新狀態為重要狀態 這與不同溫度下熱運動的影響完全一致 在溫度趨與零時 就不能接受任一Ej Ei的新狀態j了 上述接受新狀態的準則稱為Metropolis準則 相應的算法稱為Metropolis算法 這種算法的計算量顯著減少 三 模擬退火算法 對固體退火過程的研究給人們以新的啟示 1982年 Kirkpatrick等首先意識到固體退火過程與組合優化問題之間存在的類似性 Metropolis等對固體在恒定溫度下達到熱平衡的模擬也給他們以啟迪 應該把Metropolis準則引入到過程中來 最終他們得到一種對Metropolis算法進行迭代的組合優化算法 這種算法模擬固體退火過程 稱之為模擬退火算法 我們可以將組合優化問題同金屬物體退火進行類比 組合優化問題 金屬物體 假設算法用以解決如下組合優化問題 解 費用 目標 函數 最優解 狀態 能量 能量最低的狀態 模擬退火算法 Step1任選一個初始解x0 xi x0 k 0 Step2若在該溫度達到內循環條件 則到step3 Step3tk 1 d tk k k 1 若滿足停止條件 終 t0 tmax 初始溫度 否則 從鄰域N xi 中隨機選一xj 計算 fij f xj f xi 若 fij 0 則xi xj 否則若exp fij tk random 0 1 時 則xi xj 重復step2 止計算 否則 回到step2 產生一個0與1之間的一個隨機數 1 隨算法進程遞減其值的控制參數t擔當固體退火過程中的溫度T的角色 2 對t的每一取值 算法持續進行 產生新解 判斷 接受 舍棄 的迭代過程就對應著固體在某一恒定溫度下趨于熱平衡的過程 也就是執行了一次Metropolis算法 模擬退火算法從某個初始解出發 經過大量解的變換后 可以求得給定控制參數值時組合優化問題的相對最優解 然后減小t的值 重復執行Metropolis算法 就可以在t趨于零時 最終求得整體最優解 3 由于退火必須 徐徐 降溫 t也必須緩慢衰減 才能確保模擬退火算法最終趨于組合優化問題的整體最優解集 4 模擬退火算法依據Metropolis準則接受新解 因此除接受優化解外 還在一個限定范圍內接受惡化解 這正是模擬退火算法與局部搜索算法的本質區別所在 開始時t值大 可能接受較差的惡化解 隨著t的減小 只能接受較好的惡化解 最后在t值趨于零時 就不再接受任何惡化解了 這就使算法既可以從局部最優的陷阱中跳出 更有可能求得組合優化問題的整體最優解 又不失簡單性和通用性 因此對大多數組合優化問題而言 模擬退火算法要優于局部搜索算法 模擬退火算法的數學模型可以描述為 在給定鄰域結構后 模擬退火過程是從一個狀態到另一個狀態不斷地隨機游動 我們可用馬爾可夫鏈描述這一過程 當溫度t為一確定值時 兩個狀態的轉移概率定義為 Gij t 稱為從i到j的產生概率 Gij t 表示在狀態i時 j狀態被選取的概率 比較容易理解的是j是i的鄰居 如果在鄰域中等概率選取 則j被 選中的概率為 Aij t 稱為接受概率 Aij t 表示在狀態i產生j后 接受j的概率 如在模擬退火算法中接受的概率是 2 5 2 6 2 7 為模擬退火算法的主要模型 模擬退火算法主要可以分為兩類 第一類為齊次算法 在 2 5 中對每一個固定的t 計算對應的馬爾可夫鏈變化 直至達到一個穩定狀態 然后再使溫度下降 第二類是非齊次算法 由一個馬爾可夫鏈組成 要求在兩個相鄰的轉移中 溫度t是下