第三章禁忌搜索(存儲版)
【正文】 0x0x16 2. 局域搜索 ? 優(yōu)劣性 ① 通用易實(shí)現(xiàn)，易于理解 ② 搜索效果依賴于初始點(diǎn)和鄰域結(jié)構(gòu)，極易陷入局優(yōu) 一 .前言 為了獲得好解 ，可以采用的策略 有 (1)擴(kuò)大鄰域結(jié)構(gòu)，(2)變鄰域結(jié)構(gòu)， (3)多初始點(diǎn) 。 二 .禁忌搜索 19 2. 構(gòu)成要素 ? 解的表達(dá) ① 編碼方法：用數(shù)學(xué)的形式來表示問題的解。 A(s,x)一般選取為歷史上所能達(dá)到的最優(yōu)函數(shù)值。 禁忌對象為鄰域移動方式； T表長度設(shè)為 3， NG設(shè)為 5。 52 TSP問題 旅行商問題，即 TSP問題（ Traveling Salesman Problem）又譯為旅行推銷員問題、貨郎擔(dān)問題，是運(yùn)籌學(xué)領(lǐng)域著名問題之一。 46 頻數(shù)表： TabuSize=7 四 .短、中、長期表的使用 T表 1 3， 4 2 1， 7 3 5， 6 4 3， 7 5 2， 6 6 4， 5 7 1， 3 \ 1 2 3 4 5 6 7 1 \ 1 6 2 \ 3 3 1 \ 7 4 4 1 \ 2 5 1 \ 5 6 1 1 \ 7 1 1 \ 47 頻數(shù)表： TabuSize=7 四 .短、中、長期表的使用 T表 1 1， 3 2 3， 4 3 1， 7 4 5， 6 5 3， 7 6 2， 6 7 4， 5 \ 1 2 3 4 5 6 7 1 \ 7 5 2 \ 2 3 2 \ 6 3 4 1 \ 1 5 1 \ 4 6 1 1 \ 7 1 1 \ 48 2. 長期表 多階段 TS ? 長期表的作用： 長期表用來記錄每個階段的初始解，在下一階段產(chǎn)生初始解時，使之盡可能與已有的初始解有較大的距離 四 .短、中、長期表的使用 1x2x3x4x5x 6x7x8x9x49 2. 長期表 多階段 TS ? 公式 其中 B是已選初始解的集合，這種方法的目的是使 初始解充分分散到可行域的不同部分。交換 4和 5。 21 2. 構(gòu)成要素 ? 禁忌表 禁忌表 (T表 )的作用：防止搜索出現(xiàn)循環(huán) ① 將移動、移動分量或適值作為禁忌對象 ② 表的長度稱為 TabuSize，可以用來控制局域搜索和廣域搜索 ③ 表是動態(tài)更新的：把最新的解記入，最老的解從表中釋放（解禁） 二 .禁忌搜索 22 2. 構(gòu)成要素 ? 選擇策略 選擇策略的作用：保證 TS具有跳出局優(yōu)的能力 當(dāng)前解 x每一步總是移動到鄰域 N(x)中未被禁忌的最優(yōu)解，即若 則令 ，本次移動到鄰域 N(x)中未被禁忌的最優(yōu)解 二 .禁忌搜索 ? ? ? ? ? ? ? ?? ?( ) ( ) , \kC s x O pt C s x s x N x T??()kx s x?()ksx23 2. 構(gòu)成要素 ? 渴望水平 渴望水平 A(s,x)是一個取決于 s和 x的值，若有 成立，則 s(x)不受 T表限制。 ? Glover在 1977年提出 TS。 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í) 定義鄰域移
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1