計算智能模擬退火與禁忌搜索ppt課件

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