第三章禁忌搜索-展示頁
2024-10-10 14:44本頁面
【正文】 索 ? 示例 全鄰域搜索 第 2步 N(xbest)={(ACBDE)， (ABCDE)， (ADBCE)， (AEBDC)， (ACDBE)， (ACEDB)， (ACBED)}， 對應目標函數(shù)為 f(x)={43, 45, 44, 59, 59, 58, 43} xbest=(ACBDE) 一 .前言 15 2. 局域搜索 ? 優(yōu)劣性 ① 通用易實現(xiàn)，易于理解 ② 搜索效果依賴于初始點和鄰域結(jié)構(gòu)，極易陷入局優(yōu) 一 .前言 0x0x16 2. 局域搜索 ? 優(yōu)劣性 ① 通用易實現(xiàn)，易于理解 ② 搜索效果依賴于初始點和鄰域結(jié)構(gòu)，極易陷入局優(yōu) 一 .前言 為了獲得好解 ，可以采用的策略 有 (1)擴大鄰域結(jié)構(gòu)，(2)變鄰域結(jié)構(gòu)， (3)多初始點 。 7 練 習 定義鄰域移動為：位值 +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 練 習 定義鄰域移動為： 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 練 習 定義鄰域移動為：位值 +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 練 習 定義鄰域移動為： 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，記錄當前最優(yōu)解xbest=x0, T=N(xbest)； Step 2 當 T\{xbest}=Φ或滿足其他停止運算準則時，停止運算，輸出計算結(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。 例如： 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ī)則互換。 N(x)稱為 x的 鄰域 ， 稱為 x的一個 鄰居 。1 第三章 禁忌搜索 2 第三章 禁忌搜索 一 . 前言 二 . 禁忌搜索 三 . 算法舉例 四 . 短、中、長期表的使用 五 .學習 TS的幾點體會 3 1. 問題描述 一 .前言 m in ( )fx..st ( ) 0gx ?xX?目標函數(shù) 約束條件 定義域 4 2. 局域搜索 ? 鄰域的概念 ① 函數(shù)優(yōu)化問題： 鄰域 (N(x))通常定義為在給定距離空間內(nèi)，以一點 (x)為中心的一個球體。 ② 組合優(yōu)化問題： 且 ，稱為一個 鄰域映射 ，其中 表示 X 所有子集組成的集
教學課件相關推薦
鄂ICP備17016276號-1