模擬退火算法第一節(jié).ppt

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