第三章禁忌搜索(參考版)
2024-10-02 14:44本頁(yè)面
【正文】 路徑選擇的目標(biāo)是要求得的路徑長(zhǎng)度為所有路徑之中的最小值。 52 TSP問(wèn)題 旅行商問(wèn)題，即 TSP問(wèn)題（ Traveling Salesman Problem）又譯為旅行推銷員問(wèn)題、貨郎擔(dān)問(wèn)題，是運(yùn)籌學(xué)領(lǐng)域著名問(wèn)題之一。 46 頻數(shù)表： TabuSize=7 四 .短、中、長(zhǎng)期表的使用 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 四 .短、中、長(zhǎng)期表的使用 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. 長(zhǎng)期表 多階段 TS ? 長(zhǎng)期表的作用： 長(zhǎng)期表用來(lái)記錄每個(gè)階段的初始解，在下一階段產(chǎn)生初始解時(shí)，使之盡可能與已有的初始解有較大的距離 四 .短、中、長(zhǎng)期表的使用 1x2x3x4x5x 6x7x8x9x49 2. 長(zhǎng)期表 多階段 TS ? 公式 其中 B是已選初始解的集合，這種方法的目的是使 初始解充分分散到可行域的不同部分。 45 2. 中期表 頻數(shù) 表 ? 頻數(shù)表的記錄方法 ① 建立 n n的數(shù)組，對(duì)上半部分每做一步搜索將所有 0的數(shù)減 1； ② 對(duì)數(shù)組上半部分，給新發(fā)生的移動(dòng)所對(duì)應(yīng)的數(shù)組元加上 TabuSize； ③ 下半部分用來(lái)記頻數(shù)，每次 (i,j) (ij)交換，對(duì)應(yīng)的 ((j,i)+1)來(lái)記憶頻數(shù)。 39 1. 短期表 T表 ? T表的主要指標(biāo)： 禁忌對(duì)象： T表中被禁忌的那些變化元素 禁忌長(zhǎng)度： T表的長(zhǎng)度，禁忌對(duì)象的最大值 四 .短、中、長(zhǎng)期表的使用 40 1. 短期表 T表 ? T表的主要指標(biāo)： 禁忌對(duì)象： T表中被禁忌的那些 變化元素 禁忌長(zhǎng)度： T表的長(zhǎng)度，禁忌對(duì)象的最大值 四 .短、中、長(zhǎng)期表的使用 變化因素 解的變化 解分量的變化 函數(shù)值的變化 41 1. 短期表 T表 ? T表的主要指標(biāo)： 禁忌對(duì)象 ： T表中被禁忌的那些變化元素 禁忌長(zhǎng)度： T表的長(zhǎng)度，禁忌對(duì)象的最大值 四 .短、中、長(zhǎng)期表的使用 禁忌對(duì)象 解 移動(dòng) 函數(shù)值 42 1. 短期表 T表 ? T表的主要指標(biāo)： 禁忌對(duì)象 ： T表中被禁忌的那些變化元素 禁忌長(zhǎng)度： T表的長(zhǎng)度，禁忌對(duì)象的最大值 四 .短、中、長(zhǎng)期表的使用 受禁范圍：解的變化 鄰域移動(dòng) 函數(shù)值 計(jì)算時(shí)間：函數(shù)值 鄰域移動(dòng) 解的變化 擺脫局優(yōu)：函數(shù)值 鄰域移動(dòng) 解的變化 43 1. 短期表 T表 ? T表的主要指標(biāo)： 禁忌對(duì)象： T表中被禁忌的那些變化元素 禁忌長(zhǎng)度 ： T表的長(zhǎng)度，禁忌對(duì)象的最大值 ① 設(shè)為常數(shù)，易于實(shí)現(xiàn) ② 設(shè)為變化的數(shù)，在 之間變化 四 .短、中、長(zhǎng)期表的使用 m in m ax[ , ]tt禁忌長(zhǎng)度過(guò)短，一旦陷入局部最優(yōu)點(diǎn)，出現(xiàn)循環(huán)無(wú)法跳出； 禁忌長(zhǎng)度過(guò)長(zhǎng)，造成計(jì)算時(shí)間較大，也可能造成計(jì)算無(wú)法繼續(xù)下去。 禁忌對(duì)象為鄰域移動(dòng)方式； T表長(zhǎng)度設(shè)為 3， NG設(shè)為 5。交換 4和 5。 ? ? \N x T ??26 3. 算法流程 Step 3 若 且 ，令 ，轉(zhuǎn) Step 5； Step 4 若
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1