第三章禁忌搜索(已修改)
2024-10-14 14:44 本頁面
【正文】 1 第三章 禁忌搜索 2 第三章 禁忌搜索 一 . 前言 二 . 禁忌搜索 三 . 算法舉例 四 . 短、中、長期表的使用 五 .學(xué)習(xí) TS的幾點體會 3 1. 問題描述 一 .前言 m in ( )fx..st ( ) 0gx ?xX?目標(biāo)函數(shù) 約束條件 定義域 4 2. 局域搜索 ? 鄰域的概念 ① 函數(shù)優(yōu)化問題： 鄰域 (N(x))通常定義為在給定距離空間內(nèi)，以一點 (x)為中心的一個球體。 ② 組合優(yōu)化問題： 且 ，稱為一個 鄰域映射 ，其中 表示 X 所有子集組成的集合。 N(x)稱為 x的 鄰域 ， 稱為 x的一個 鄰居 。 一 .前言 : ( ) 2 XN x X N x? ? ?()x N x? 2X()y N x?5 2. 局域搜索 ? 鄰域的概念 例： TSP問題 解的一種表示方法為 D={x=(i1,i2,…, in)| i1,i2,…, in是 1,2,…, n的排列 }，定義它的鄰域映射為 2opt，即 x中的兩個元素進(jìn)行對換， N(x)中共包含 x的 Cn2=n(n1)/2個鄰居和 x本身。 例如： x=(1,2,3,4)， 則 C42=6， N(x)={(1,2,3,4), (2,1,3,4), (3,2,1,4), (4,2,3,1), (1,3,2,4), (1,4,3,2), (1,2,4,3)} 一 .前言 6 2. 局域搜索 ? 鄰域的概念 例： 解的鄰域映射可由 2opt，推廣到 kopt，即對 k個元素按一定規(guī)則互換。 一 .前言 鄰域的構(gòu)造依賴于解的表示，鄰域的結(jié)構(gòu)在智能優(yōu)化算法中起重要的作用。 7 練 習(xí) 定義鄰域移動為：位值 +1或 1 對整數(shù)編碼 [2 2 3 5 3]，下列編碼是否在其鄰域內(nèi)： [2 3 3 5 3] [2 3 2 5 3] [2 2 3 5 5] [2 2 3 4 3] [2 2 2 5 3] [2 2 3 4 4] 8 練 習(xí) 定義鄰域移動為： 2opt 對順序編碼 [4 2 3 5 1]，下列編碼是否在其鄰域內(nèi)： [4 3 2 5 1] [4 3 5 1 2] [4 3 3 5 1] [5 2 3 4 1] [1 2 3 5 4] [3 4 2 5 1] 9 練 習(xí) 定義鄰域移動為：位值 +1或 1 對整數(shù)編碼 [2 2 3 5 3]，下列編碼是否在其鄰域內(nèi)： [2 3 3 5 3] [2 3 2 5 3] [2 2 3 5 5] [2 2 3 4 3] [2 2 2 5 3] [2 2 3 4 4] 是 否 否 是 是 否 10 練 習(xí) 定義鄰域移動為： 2opt 對順序編碼 [4 2 3 5 1]，下列編碼是否在其鄰域內(nèi)： [4 3 2 5 1] [4 3 5 1 2] [4 3 3 5 1] [5 2 3 4 1] [1 2 3 5 4] [3 4 2 5 1] 是 否 否 是 是 否 11 2. 局域搜索 ? 算法流程 Step 1 選定一個初始可行解 x0，記錄當(dāng)前最優(yōu)解xbest=x0, T=N(xbest)； Step 2 當(dāng) T\{xbest}=Φ或滿足其他停止運(yùn)算準(zhǔn)則時，停止運(yùn)算，輸出計算結(jié)果；否則，轉(zhuǎn) Step 3； Step 3 從 T中選一個集合 S，得到 S中的最好解 xnow；若 f (xnow)f(xbest)，則 xbest= xnow， T=N(xbest)；否則， T=T\S，轉(zhuǎn) Step 2。 一 .前言 若 S=T，則稱為全鄰域搜索 12 2. 局域搜索 ? 示例 例： 五個城市的對稱 TSP問題 一 .前言 初始解為 xbest=(ABCDE)， f(xbest)=45，定義鄰域映射為對換兩個城市位置
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1