第三章禁忌搜索-資料下載頁
2024-09-28 14:44本頁面
【導(dǎo)讀】為中心的一個球體。所有子集組成的集合。N稱為x的鄰域，稱為x的一個鄰居。例：TSP問題解的一種表示方法為D={x=(i1,i2,…,n的排列}，定義它的鄰域映射為。的Cn2=n(n-1)/2個鄰居和x本身。素按一定規(guī)則互換。在智能優(yōu)化算法中起重要的作用。止運算，輸出計算結(jié)果；否則，轉(zhuǎn)Step3；從T中選一個集合S，得到S中的最好解xnow；為對換兩個城市位置的2-opt，選定A城市為起點。變鄰域結(jié)構(gòu)，多初始點。但這些策略依然無。法保證算法具備跳出局優(yōu)的能力。人類在選擇過程中具有記憶功能，比如走迷宮。能性，這樣就可以確定性的避開迂回搜索。借鑒人類的智能思考特性，采用禁忌策略盡量避免迂回搜索就構(gòu)成了TS算法。Glover在1977年提出TS。相對于LS，TS的優(yōu)點。開始受到廣泛的關(guān)注。法產(chǎn)生一個可行解。f作為評價函數(shù)。夠達到的所有解構(gòu)成的集合。
【正文】 易于實現(xiàn) ② 設(shè)為變化的數(shù)，在 之間變化 四 .短、中、長期表的使用 m in m ax[ , ]tt禁忌長度過短，一旦陷入局部最優(yōu)點，出現(xiàn)循環(huán)無法跳出； 禁忌長度過長，造成計算時間較大，也可能造成計算無法繼續(xù)下去。 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)遠小于目標值（ 1%目標值或 1‰ 目標值）， α越大分散性越好，廣域搜索能力強，但會損壞鄰域搜索。 45 2. 中期表 頻數(shù) 表 ? 頻數(shù)表的記錄方法 ① 建立 n n的數(shù)組，對上半部分每做一步搜索將所有 0的數(shù)減 1； ② 對數(shù)組上半部分，給新發(fā)生的移動所對應(yīng)的數(shù)組元加上 TabuSize； ③ 下半部分用來記頻數(shù)，每次 (i,j) (ij)交換，對應(yīng)的 ((j,i)+1)來記憶頻數(shù)。 四 .短、中、長期表的使用 頻數(shù)表的優(yōu)點：同一數(shù)組作為 T表和頻數(shù)表共同使用，方便操作又 節(jié)省時間 。 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是已選初始解的集合，這種方法的目的是使 初始解充分分散到可行域的不同部分。 四 .短、中、長期表的使用 ? ? ? ?1nkliiL B iD k x x??????? ? ? ? ? ?21nkliiL B iK ArgM ax D k D k x x???????? ? ???????50 1. TS的記憶功能 — 短、中、長期表要靈活使用 2. TS局域搜索能力強，但全局搜索能力較弱； 3. 改善 TS的全局搜索能力，提高 TS的分散性的方法 ? 用長期表 ? 加大 T表長度 ? 加大對頻數(shù)的懲罰 4. TS仍是一種啟發(fā)式，不能保證最優(yōu)性 5. TS的理論工作較少 五 .學(xué)習(xí) TS的幾點體會 51 實 驗 中國 TSP問題 要求： 1） 利用百度地圖獲取數(shù)據(jù)； 2） 設(shè)計一種 TS求解算法； 3） 利用 1） 中數(shù)據(jù)進行算法仿真實驗，著重說明設(shè)計算法獲得的最好解，并分析 T表長度對算法性能的影響程度。 52 TSP問題 旅行商問題，即 TSP問題（ Traveling Salesman Problem）又譯為旅行推銷員問題、貨郎擔(dān)問題，是運籌學(xué)領(lǐng)域著名問題之一。假設(shè)有一個旅行商人要拜訪 n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑選擇的目標是要求得的路徑長度為所有路徑之中的最小值。 返回
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1