第10章模擬退火與禁忌搜索1整理課件Contents模擬退火算法思想

1模擬退火基本流程

2模擬退火應(yīng)用舉例

3禁忌搜索算法思想4禁忌搜索基本流程

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