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

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