【正文】 44 2. 中期表 頻數(shù) 表 ? 頻數(shù)表的作用： 頻數(shù)表是用來記憶不同方向的移動次數(shù)，從而加以懲罰（比如 2Opt，記錄每對交換的發(fā)生次數(shù)），從而提高搜索方向的多樣性 在鄰域選優(yōu)公式中，令 其中， E(s(x))表示移動 s(x)的出現(xiàn)頻數(shù)， α為懲罰因子 四 .短、中、長期表的使用 ? ?? ? ? ? ? ?? ?? ?? ? ? ?? ? ? ? ? ?? ?,\m i n , \O pt C s x s x N x TC s x E s x s x N x T??? ? ?注：懲罰因子 α的取值一般應(yīng)遠(yuǎn)小于目標(biāo)值（ 1%目標(biāo)值或 1‰ 目標(biāo)值）， α越大分散性越好，廣域搜索能力強，但會損壞鄰域搜索。 二 .禁忌搜索 20 2. 構(gòu)成要素 ? 鄰域及鄰域移動 ① 定義鄰域移動 s，例如，在函數(shù)優(yōu)化問題中鄰域移動可以定義為給定步長和移動方向；在組合優(yōu)化問題中鄰域移動可以定義為某種排練序列置換。 一 .前言 : ( ) 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中的兩個元素進行對換， N(x)中共包含 x的 Cn2=n(n1)/2個鄰居和 x本身。 18 1. TS（ Tabu Search）的提出 ? 人類在選擇過程中具有記憶功能，比如走迷宮時，當(dāng)發(fā)現(xiàn)有可能又回到某個地點的時候總會有意識地避開先前選擇的方向而選擇其他的可能性，這樣就可以確定性的避開迂回搜索。 ? ? \N x T ??26 3. 算法流程 Step 3 若 且 ，令 ，轉(zhuǎn) Step 5； Step 4 若 ，令 ； 二 .禁忌搜索 ? ?? ? ? ?? ? ? ? ? ?? ?,LC s x O p t C s x s x N x??? ?? ? ( , )LC s x A s x? ()Lx s x?注： Step 3的作用破禁檢查 ? ?? ? ? ?? ? ? ? ? ?? ?,\KC s x O p t C s x s x N x T??()Kx s x?注： Step 4的作用鄰域選優(yōu) 27 3. 算法流程 Step 5 若 ，令 ， ， ； Step 6 更新 T表，轉(zhuǎn) Step 2 ； 二 .禁忌搜索 注： Step 5的作用更新歷史最好解及渴望水平 ? ? ? ?C x C x ?? xx? ? ? ? ? ?C x C x? ?? ? ? ?,A s x C x ??注： x存入 T表中的第一個位置 28 4. TS克服局優(yōu)分析 ? 從鄰域搜索的方法看 移向 N(x)\T中最好的解，而不與當(dāng)前解比較， 是 N(x)\T中的最好點，但 可能劣于 二 .禁忌搜索 ? ? ? ? ? ? ? ?? ?,\Ks x O pt s x s x N x T??? ?Ksx ? ?? ?KC s x? ?*Cx29 4. TS克服局優(yōu)分析 ? 從選優(yōu)規(guī)則看 始終保持歷史最優(yōu)解，不以當(dāng)前解為最優(yōu) ? 從停止規(guī)則上看 不以最優(yōu)判據(jù)為停止規(guī)則，而是指定最大迭代步數(shù)為停止條件，這樣不能保證最優(yōu)性。路徑選擇的目標(biāo)是要求得的路徑長度為所有路徑之中的最小值。正常設(shè)置為 T表長度 鄰域大小。 17 2. 局域搜索 ? 優(yōu)劣性 ① 通用