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

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