第10章模擬退火與禁忌搜索 1 Contents 模擬退火算法思想 1 2 10 1模擬退火算法思想 模擬退火算法是什么 是怎樣提出來(lái)的 模擬退火算法 SimulatedAnnealing SA 是一種模擬物理退火的過(guò)程而設(shè)計(jì)的優(yōu)化算法 它的基本思想最早在1953年就被Metropolis提出 但直到1983年Kirkpatrick等人才設(shè)計(jì)出真正意義上的模擬退火算法并進(jìn)行應(yīng)用 模擬退火算法的基本思想是怎樣的 模擬退火算法采用類似于物理退火的過(guò)程 先在一個(gè)高溫狀態(tài)下 相當(dāng)于算法隨機(jī)搜索 然后逐漸退火 在每個(gè)溫度下 相當(dāng)于算法的每一次狀態(tài)轉(zhuǎn)移 徐徐冷卻 相當(dāng)于算法局部搜索 最終達(dá)到物理基態(tài) 相當(dāng)于算法找到最優(yōu)解 3 10 1模擬退火算法思想 4 10 2模擬退火基本流程 5 模擬退火算法基本要素和設(shè)定方法 6 10 3模擬退火應(yīng)用舉例 例10 1已知背包的裝載量為c 8 現(xiàn)有n 5個(gè)物品 它們的重量和價(jià)值分別是 2 3 5 1 4 和 2 5 8 3 6 試使用模擬退火算法求解該背包問(wèn)題 寫出關(guān)鍵的步驟 求解 假設(shè)問(wèn)題的一個(gè)可行解用0和1的序列表示 例如i 1010 表示選擇第1和第3個(gè)物品 而不選擇第2和第4個(gè)物品 用模擬退火算法求解例10 1的關(guān)鍵過(guò)程如圖所示 7 運(yùn)行步驟 8 10 4禁忌搜索算法思想 禁忌搜索算法是什么 禁忌搜索算法 TabuSearch TS 是Glover于1986年提出的一種全局搜索算法 禁忌搜索算法的基本思想是怎樣的 禁忌搜索是屬于模擬人類智能的一種優(yōu)化算法 它模仿了人類的記憶功能 在求解問(wèn)題的過(guò)程中 采用了禁忌技術(shù) 對(duì)已經(jīng)搜索過(guò)的局部最優(yōu)解進(jìn)行標(biāo)記 并且在迭代中盡量避免重復(fù)相同的搜索 但不是完全隔絕 從而獲得更廣的搜索區(qū)間 有利于尋找到全局最優(yōu)解 9 10 4禁忌搜索相關(guān)概念 禁忌表 TabuList TL 是用來(lái)存放 記憶 禁忌對(duì)象的表 它是禁忌搜索得以進(jìn)行的基本前提 禁忌表本身是有容量限制的 它的大小對(duì)存放禁忌對(duì)象的個(gè)數(shù)有影響 會(huì)影響算法的性能 禁忌對(duì)象 TabuObject TO 是指禁忌表中被禁的那些變化元素 禁忌對(duì)象的選擇可以根據(jù)具體問(wèn)題而制定 例如在旅行商問(wèn)題 TravelingSalesmanProblem TSP 中可以將交換的城市對(duì)作為禁忌對(duì)象 也可以將總路徑長(zhǎng)度作為禁忌對(duì)象 10 10 4禁忌搜索相關(guān)概念 禁忌期限 TabuTenure TT 也叫禁忌長(zhǎng)度 指的是禁忌對(duì)象不能被選取的周期 禁忌期限過(guò)短容易出現(xiàn)循環(huán) 跳不出局部最優(yōu) 長(zhǎng)度過(guò)長(zhǎng)會(huì)造成計(jì)算時(shí)間過(guò)長(zhǎng) 渴望準(zhǔn)則 AspirationCriteria AC 也稱為特赦規(guī)則 當(dāng)所有的對(duì)象都被禁忌之后 可以讓其中性能最好的被禁忌對(duì)象解禁 或者當(dāng)某個(gè)對(duì)象解禁會(huì)帶來(lái)目標(biāo)值的很大改進(jìn)時(shí) 也可以使用特赦規(guī)則 11 10 5禁忌搜索基本流程 12 10 6禁忌搜索應(yīng)用舉例 例10 2已知一個(gè)旅行商問(wèn)題為四城市 a b c d 問(wèn)題 城市間的距離如矩陣D所示 為方便起見(jiàn) 假設(shè)鄰域映射定義為兩個(gè)城市位置對(duì)換 而始點(diǎn)和終點(diǎn)城市都是a 請(qǐng)分析使用禁忌搜索算法求解該問(wèn)題的前面三代的過(guò)程與主要步驟 13 10 6禁忌搜索應(yīng)用舉例 分析 這是一個(gè)簡(jiǎn)單的問(wèn)題 利用枚舉也可以找到最優(yōu)的答案 但是 找到答案不是我們的目的 我們主要是想通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)理解禁忌搜索是如何進(jìn)行工作的 從距離矩陣D可以看到 這是一個(gè)非對(duì)稱的TSP問(wèn)題 但是這并不影響算法的執(zhí)行 由于題目假設(shè)了鄰域構(gòu)造的方式 而且規(guī)定了始點(diǎn)和終點(diǎn)都是城