實(shí)驗(yàn)六：遺傳算法求解TSP問題實(shí)驗(yàn)講解(共24頁)

1、實(shí)驗(yàn)六：遺傳算法求解TSP問題實(shí)驗(yàn)一、 實(shí)驗(yàn)?zāi)康膚熟悉和掌握遺傳算法的原理、流程和編碼策略，并利用遺傳求解函數(shù)優(yōu)化問題，理解求解TSP問題的流程并測試主要參數(shù)對結(jié)果的影響。用遺傳算法對TSP問題進(jìn)行了求解，熟悉遺傳算法地算法流程，證明遺傳算法在求解TSP問題時(shí)具有可行性。二、 實(shí)驗(yàn)內(nèi)容w參考實(shí)驗(yàn)系統(tǒng)給出的遺傳算法核心代碼，用遺傳算法求解TSP的優(yōu)化問題，分析遺傳算法求解不同規(guī)模TSP問題的算法性能。w對于同一個(gè)TSP問題，分析種群規(guī)模、交叉概率和變異概率對算法結(jié)果的影響。w增加1種變異策略和1種個(gè)體選擇概率分配策略，比較求解同一TSP問題時(shí)不同變異策略及不同個(gè)體選擇分配策略對算法結(jié)果的影響。1

2、. 最短路徑問題所謂旅行商問題(Travelling Salesman Problem , TSP)，即最短路徑問題，就是在給定的起始點(diǎn)S到終止點(diǎn)T的通路集合中，尋求距離最小的通路，這樣的通路成為S點(diǎn)到T點(diǎn)的最短路徑。在尋找最短路徑問題上，有時(shí)不僅要知道兩個(gè)指定頂點(diǎn)間的最短路徑，還需要知道某個(gè)頂點(diǎn)到其他任意頂點(diǎn)間的最短路徑。遺傳算法方法的本質(zhì)是處理復(fù)雜問題的一種魯棒性強(qiáng)的啟發(fā)性隨機(jī)搜索算法，用遺傳算法解決這類問題，沒有太多的約束條件和有關(guān)解的限制，因而可以很快地求出任意兩點(diǎn)間的最短路徑以及一批次短路徑。 假設(shè)平面上有n個(gè)點(diǎn)代表n個(gè)城市的位置, 尋找一條最短的閉合路徑, 使得可以遍歷每一個(gè)城市恰

3、好一次。這就是旅行商問題。旅行商的路線可以看作是對n個(gè)城市所設(shè)計(jì)的一個(gè)環(huán)形, 或者是對一列n個(gè)城市的排列。由于對n個(gè)城市所有可能的遍歷數(shù)目可達(dá)(n- 1)!個(gè), 因此解決這個(gè)問題需要0(n!)的計(jì)算時(shí)間。假設(shè)每個(gè)城市和其他任一城市之間都以歐氏距離直接相連。也就是說, 城市間距可以滿足三角不等式, 也就意味著任何兩座城市之間的直接距離都小于兩城市之間的間接距離。2. 遺傳算法遺傳算法是由美國J.Holland教授于1975年在他的專著自然界和人工系統(tǒng)的適應(yīng)性中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。通過模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每

4、次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。遺傳算法在本質(zhì)上是一種不依賴具體問題的直接搜索方法，是一種求解問題的高效并行全局搜索方法。其假設(shè)常描述為二進(jìn)制位串，位串的含義依賴于具體應(yīng)用。搜索合適的假設(shè)從若干初始假設(shè)的群體集合開始。當(dāng)前種群成員通過模仿生物進(jìn)化的方式來產(chǎn)生下一代群體，如隨機(jī)變異和交叉。每一步，根據(jù)給定的適應(yīng)度評估當(dāng)前群體的假設(shè)，而后使用概率方法選出適應(yīng)度最高的假設(shè)作為產(chǎn)生下一代的種子。下面介紹幾個(gè)遺傳算法的幾個(gè)基本概念：（1）染色體（Chromosom

5、e）：在使用遺傳算法時(shí)，需要把問題的解編成一個(gè)適合的碼子。這種具有固定結(jié)構(gòu)的符號串既是染色體，符號串的每一位代表一個(gè)基因。符號串的總位數(shù)成為染色體的長度，一個(gè)染色體就代表問題的一個(gè)解，每個(gè)染色體也被稱為一個(gè)個(gè)體。（2）群體（Population）：每代所產(chǎn)生的染色體總數(shù)成為群體，一個(gè)群體包含了該問題在這一代的一些解的集合。（3）適應(yīng)度（Fitness）：對群體中每個(gè)染色體進(jìn)行編碼后，每個(gè)個(gè)體對應(yīng)一個(gè)具體問題的解，而每個(gè)解對應(yīng)于一個(gè)函數(shù)值。該函數(shù)值即適應(yīng)函數(shù)，就是衡量染色體對環(huán)境適應(yīng)度的指標(biāo)，也是反映實(shí)際問題的目標(biāo)函數(shù)在前一代群體的基礎(chǔ)上產(chǎn)生新一代群體的工作成為遺傳操作，基本的遺傳操作有：（1）

6、選擇（Select）：按一定的概率從上代群體中選擇M對個(gè)體作為雙親，直接拷貝到下一代，染色體不發(fā)生變化。（2）交叉（Crossover）：對于選中進(jìn)行繁殖的兩個(gè)染色體X，Y，以X，Y為雙親作交叉操作，從而產(chǎn)生兩個(gè)后代X1，Y1.（3）變異（Mutation）：對于選中的群體中的個(gè)體（染色體），隨機(jī)選取某一位進(jìn)行取反運(yùn)算，即將該染色體碼翻轉(zhuǎn)。用遺傳算法求解的過程是根據(jù)待解決問題的參數(shù)集進(jìn)行編碼，隨機(jī)產(chǎn)生一個(gè)種群，計(jì)算適應(yīng)函數(shù)和選擇率，進(jìn)行選擇、交叉、變異操作。如果滿足收斂條件，此種群為最好個(gè)體，否則，對產(chǎn)生的新一代群體重新進(jìn)行選擇、交叉、變異操作，循環(huán)往復(fù)直到滿足條件。遺傳算法原型：GA(Fit

7、ness,Fitness_threshold,p,r,m)Fitness:適應(yīng)度評分函數(shù),為給定假設(shè)賦予一個(gè)評估分?jǐn)?shù)Fitness_threshold:指定終止判據(jù)的閾值p:群體中包含的假設(shè)數(shù)量r:每一步中通過交叉取代群體成員的比例m:變異率初始化群體:P隨機(jī)產(chǎn)生的p個(gè)假設(shè)評估:對于P中的每一個(gè)h,計(jì)算Fitness(h)當(dāng)maxFitness(h)<Fitness_threshold,做產(chǎn)生新的一代Ps:(1)選擇:用概率方法選擇P的(1-r)p個(gè)成員加入Ps.從P中選擇假設(shè)hi的概率用下面公式計(jì)算:(2)交叉:根據(jù)上面給出的,從P中按概率選擇r(p/2)對假設(shè).對于每對假設(shè)<h

8、1，h2>,應(yīng)用交叉算子產(chǎn)生兩個(gè)后代.把所有的后代加入Ps(3)變異:使用均勻的概率從Ps中選擇m%的成員.對于選出的每個(gè)成員,在它表示中隨機(jī)選擇一個(gè)為取反(4)更新:PPs(5)評估:對于P中的每個(gè)h計(jì)算Fitness(h)從P中返回適應(yīng)度最高的假設(shè)3. TSP問題的遺傳算法設(shè)計(jì)與實(shí)現(xiàn)對于n個(gè)城市的問題，每個(gè)個(gè)體即每個(gè)解的長度為n，用s行, t列的pop矩陣，表示初始群體，s表示初始群體的個(gè)數(shù)，t為n+1，矩陣的每一行的前n個(gè)元素表示城市編碼，最后一個(gè)元素表示這一路徑的長度。城市的位置可以手動(dòng)輸入，使用一個(gè)N×N矩陣D存儲(chǔ)，D（i，j）代表城市i和城市j之間的距離。 D（i，

9、j）=sqrt(（Xi-Xj）.2+(Yi-Yj).2)。在TSP的求解中，可以直接用距離總和作為適應(yīng)度函數(shù)。個(gè)體的路徑長度越小，所得個(gè)體優(yōu)越，距離的總和越大，適應(yīng)度越小，進(jìn)而探討求解結(jié)果是否最優(yōu)。選擇就是從群體中選擇優(yōu)勝個(gè)體、淘汰劣質(zhì)個(gè)體的操作，它是建立在群體中個(gè)體適應(yīng)度評估基礎(chǔ)上。這里采用方法是最優(yōu)保存方法。本實(shí)例中交叉采用部分匹配交叉策略，先隨機(jī)選取兩個(gè)交叉點(diǎn)，然后將兩交叉點(diǎn)中間的基因段互換，將互換的基因段以外的部分中與互換后基因段中元素沖突的用另一父代的相應(yīng)位置代替，直到?jīng)]有沖突。變異操作是以變異概率Pm對群體中個(gè)體串某些基因位上的基因值作變動(dòng)，若變異后子代的適應(yīng)度值更加優(yōu)異，則保留子

10、代染色體，否則，仍保留父代染色體。這有助于增加種群的多樣性，避免早熟收斂（非全局最優(yōu)）。判斷結(jié)束準(zhǔn)則是固定指定了迭代的次數(shù)當(dāng)算法達(dá)到迭代次數(shù)時(shí)，算法結(jié)束，輸出當(dāng)前的最優(yōu)解。在根據(jù)適配值計(jì)算并選擇的時(shí)候，記錄下來的當(dāng)前最優(yōu)值，在變異后加入跟新的群體，保證新的迭代循環(huán)中TSP解越來越好（不會(huì)變差）。 在選擇的一種操作是拿最優(yōu)的K個(gè)替換最差的K個(gè)個(gè)體，本例是按適配值選擇，并使群體數(shù)目變少，當(dāng)每次變異操作后，產(chǎn)生隨機(jī)路徑補(bǔ)充群體是群體數(shù)目不變，再次循環(huán)，一定程度上防止因初始群體的選擇問題而陷入局部最優(yōu)。4. TSP問題的遺傳算法的具體步驟解最短路徑的遺傳算法如下：Generatep(n);表示程序開始

11、時(shí)要首先產(chǎn)生一個(gè)群體，群體個(gè)數(shù)為nEvaluatep(h);表示計(jì)算每個(gè)個(gè)體適應(yīng)度，h是種群中的一個(gè)個(gè)體Repeat roof Generations times;重復(fù)下面的操作，直到滿足條件為止Select p(h) from p(n-1);表示從前一代群體中選擇一對雙親，用于交叉、變異 操作，P(n)代表第n代群體Crossover and mutation p(n);進(jìn)行交叉和變異操作Learningp(n);自學(xué)習(xí)過程Evaluatep(h);計(jì)算新生成的種群中每個(gè)個(gè)體的適應(yīng)度End;具體流程圖如下所示：流程圖5.遺傳算法求解不同規(guī)模的TSP問題的算法性能（1） 遺傳算法執(zhí)行方式說明：

12、l 適應(yīng)度值計(jì)算方法：當(dāng)前路線的路徑長度l 個(gè)體選擇概率分配方法：適應(yīng)度比例方法l 選擇個(gè)體方法：輪盤賭選擇l 交叉類型：PMX交叉l 變異類型: 兩點(diǎn)互換變異（2）實(shí)驗(yàn)?zāi)M結(jié)果：城市個(gè)數(shù)時(shí)間（ms）51692510166301518833202259625241593030289353523940386084540032504375755477466058143655994270643617571417圖1-1（3）分析由圖1-1可知，遺傳算法執(zhí)行時(shí)間隨著TSP問題規(guī)模的增大而增大，并且大致為線性增長。五、不同參數(shù)下的計(jì)算結(jié)果對比（1）種群規(guī)模對算法結(jié)果的影響實(shí)驗(yàn)次數(shù)：10最大迭代步數(shù):10

13、0交叉概率：0.85變異概率：0.15表1-1種群規(guī)模適應(yīng)度值最優(yōu)路徑1025.2644-5-8-7-6-3-1-0-9-22026.34282-9-1-0-3-6-7-5-8-43025.16521-3-6-7-5-8-4-2-9-05025.16520-1-3-6-7-5-8-4-2-98025.16529-0-1-3-6-7-5-8-4-210025.16521-0-9-2-4-8-5-7-6-315025.16525-8-4-2-9-0-1-3-6-720025.16521-3-6-7-5-8-4-2-9-025025.16523-1-0-9-2-4-8-5-7-630025.1652

14、5-8-4-2-9-0-1-3-6-7如表1-1所示，顯然最短路徑為25.1652m,最優(yōu)路徑為1-0-9-1-3-6-7-5-8-4-2或3-1-0-9-2-4-8-5-7-6，注意到這是一圈，順時(shí)針或者逆時(shí)針都可以。當(dāng)種群規(guī)模為10，20時(shí)，并沒有找到最優(yōu)解。（2）交叉概率對算法結(jié)果的影響實(shí)驗(yàn)次數(shù)：15種群規(guī)模：25最大迭代步數(shù):100變異概率：0.15實(shí)驗(yàn)結(jié)果：表1-2交叉概率最好適應(yīng)度最差適應(yīng)度平均適應(yīng)度最優(yōu)解運(yùn)行時(shí)間0.00128.044736.656732.60029-2-6-0-5-4-8-7-3-13100.0127.093534.994332.14957-8-3-1-9-2-

15、6-0-5-42600.128.044735.303331.93727-3-1-9-2-6-0-5-4-83000.1528.044734.117531.21830-5-4-8-7-3-1-9-2-62700.228.710833.951230.90353-1-9-2-6-5-0-4-7-82800.2528.044735.162330.74561-3-7-8-4-5-0-6-2-92600.327.093531.994129.94288-3-1-9-2-6-0-5-4-72900.3527.093532.808530.99459-1-3-8-7-4-5-0-6-22700.427.09353

16、2.531330.15341-3-8-7-4-5-0-6-2-92790.4527.093533.201430.17578-3-1-9-2-6-0-5-4-74560.528.093433.630730.90265-0-2-6-9-1-3-8-7-46630.5527.093533.523329.13041-9-2-6-0-5-4-7-8-35200.627.093533.251230.78363-1-9-2-6-0-5-4-7-85460.6528.044733.700330.93715-4-8-7-3-1-9-2-6-05960.727.093532.092729.95029-1-3-8-

17、7-4-5-0-6-25710.7528.044732.448830.36990-5-4-8-7-3-1-9-2-65590.827.093532.155129.93827-4-5-0-6-2-9-1-3-83580.8527.093534.539930.35945-0-6-2-9-1-3-8-7-43600.927.093532.627330.696-0-5-4-7-8-3-1-9-23750.9527.093532.467229.9196-2-9-1-3-8-7-4-5-0476（注:紅色表示非最優(yōu)解）在該情況下，交叉概率過低將使搜索陷入遲鈍狀態(tài)，得不到最優(yōu)解。（3）變異概率對算法結(jié)果的影

18、響實(shí)驗(yàn)次數(shù)：10種群規(guī)模：25最大迭代步數(shù):100交叉概率：0.85實(shí)驗(yàn)結(jié)果：表1-3變異概率最好適應(yīng)度最差適應(yīng)度平均適應(yīng)度最優(yōu)解運(yùn)行時(shí)間0.00129.471734.73232.49110-6-2-1-9-3-8-7-4-52450.0129.044634.659132.37148-4-5-0-2-6-9-1-3-72740.128.093434.01130.94175-0-2-6-9-1-3-8-7-42500.1527.093532.09330.25686-0-5-4-7-8-3-1-9-22460.227.093532.234930.31448-7-4-5-0-6-2-9-1-3282

19、0.2527.093532.71830.15724-5-0-6-2-9-1-3-8-72450.327.093532.448830.28540-5-4-7-8-3-1-9-2-62520.3527.093533.316730.77481-3-8-7-4-5-0-6-2-92660.429.044634.370531.30412-0-5-4-8-7-3-1-9-63620.4527.093531.37429.68162-6-0-5-4-7-8-3-1-94380.527.093532.375230.22112-9-1-3-8-7-4-5-0-64310.5527.093533.381930.66

20、231-3-8-7-4-5-0-6-2-94920.628.093433.251230.361-3-8-7-4-5-0-2-6-94170.6527.093532.749130.02013-1-9-2-6-0-5-4-7-84340.728.710832.423830.7851-3-8-7-4-0-5-6-2-94320.7527.093531.892830.24511-9-2-6-0-5-4-7-8-34750.828.093431.613530.34719-1-3-8-7-4-5-0-2-63270.8529.66233.239231.15852-9-1-3-7-8-4-0-5-63140

21、.928.044732.038730.41520-5-4-8-7-3-1-9-2-63960.9528.044731.303630.00679-1-3-7-8-4-5-0-6-2436又表1-3可知，當(dāng)變異概率過大或過低都將導(dǎo)致無法得到最優(yōu)解。注：（2）（3）的實(shí)驗(yàn)數(shù)據(jù)與（1）的實(shí)驗(yàn)數(shù)據(jù)不同，詳見附錄。六、不同變異策略和個(gè)體選擇概率分配策略對算法結(jié)果的影響（1）兩點(diǎn)互換變異與插入變異的比較：l 試驗(yàn)次數(shù)（CASNUM）：10l 城市數(shù)(POINTCNT):10l 種群規(guī)模(POPSIZE)：100l 最大迭代步數(shù)(GENERATIONS):100l 交叉概率(PC)：0.85l 變異概率(PM

22、):0.15l 選擇個(gè)體方法：輪盤賭選擇l 交叉類型：PMX交叉l 個(gè)體選擇概率分配方法：適應(yīng)度比例方法a. 變異類型: 兩點(diǎn)互換變異表1-4兩點(diǎn)互換變異程序結(jié)果序號最好適應(yīng)度最差適應(yīng)度平均適應(yīng)度最優(yōu)解運(yùn)行時(shí)間128.093430.422929.08916-2-0-5-4-7-8-3-1-91199227.093531.141728.98414-5-0-6-2-9-1-3-8-71678327.093530.422829.06040-5-4-7-8-3-1-9-2-61940427.093530.370328.87871-3-8-7-4-5-0-6-2-91756527.093531.0619

23、29.07553-1-9-2-6-0-5-4-7-81885627.093531.158929.39422-6-0-5-4-7-8-3-1-91936728.044731.061929.76486-2-9-1-3-7-8-4-5-01772829.044631.347529.84154-5-0-2-6-9-1-3-7-81980927.093530.614329.0590-6-2-9-1-3-8-7-4-519401027.093530.558529.08119-2-6-0-5-4-7-8-3-118721127.093531.017129.42640-5-4-7-8-3-1-9-2-6151

24、71227.093531.303629.24141-9-2-6-0-5-4-7-8-315411327.093532.025529.07890-6-2-9-1-3-8-7-4-515171427.093531.51628.89060-6-2-9-1-3-8-7-4-513451527.093530.422829.02266-0-5-4-7-8-3-1-9-213771627.093530.408128.90810-6-2-9-1-3-8-7-4-518531727.093530.408129.33167-8-3-1-9-2-6-0-5-415221827.093530.020328.52431

25、-3-8-7-4-5-0-6-2-916011928.044731.140429.5672-9-1-3-7-8-4-5-0-616092027.093531.141729.53597-4-5-0-6-2-9-1-3-81311平均值27.336130.878229.18771657b. 變異類型: 插入變異表1-5插入變異程序結(jié)果序號最好適應(yīng)度最差適應(yīng)度平均適應(yīng)度最優(yōu)解運(yùn)行時(shí)間127.093531.475328.84532-6-0-5-4-7-8-3-1-91388227.093529.66228.91685-0-6-2-9-1-3-8-7-41355327.093529.663128.902

26、1-9-2-6-0-5-4-7-8-31637428.044730.524129.51194-5-0-6-2-9-1-3-7-81164527.093531.057529.46822-6-0-5-4-7-8-3-1-91245627.093529.66228.55462-6-0-5-4-7-8-3-1-91222728.044730.820529.7483-1-9-2-6-0-5-4-8-71148827.093530.524129.39071-9-2-6-0-5-4-7-8-31742927.093530.42328.68780-6-2-9-1-3-8-7-4-520641027.09353

27、0.408128.725-0-6-2-9-1-3-8-7-415181127.093531.37429.32824-5-0-6-2-9-1-3-8-712401227.093530.52328.55441-3-8-7-4-5-0-6-2-912041327.093530.820529.05080-6-2-9-1-3-8-7-4-517341427.093531.117729.59050-5-4-7-8-3-1-9-2-615321527.093530.52329.19044-5-0-6-2-9-1-3-8-714831627.093530.408128.80615-0-6-2-9-1-3-8-

28、7-412821727.093531.763929.45916-0-5-4-7-8-3-1-9-214851827.093531.158929.16144-5-0-6-2-9-1-3-8-716011927.093530.408128.59742-6-0-5-4-7-8-3-1-915072027.093530.614328.80363-1-9-2-6-0-5-4-7-81234平均值27.1886230.646529.06431439分析：兩點(diǎn)互換變異20次模擬中，4次得到非最優(yōu)解；而插入變異只有2次；插入變異的最好適應(yīng)度平均值比兩點(diǎn)互換變異小0.14755，最差適應(yīng)度平均值和總的適應(yīng)度平均

29、值都比兩點(diǎn)互換下，并且在Release下，運(yùn)行時(shí)間前者比后者快218.3ms。可見在該條件下（交叉概率，變異概率，種群規(guī)模等），插入變異比兩點(diǎn)互換變異的算法效果要好。（2）個(gè)體選擇分配策略l 試驗(yàn)次數(shù)（CASNUM）：10l 城市數(shù)(POINTCNT):10l 種群規(guī)模(POPSIZE)：100l 最大迭代步數(shù)(GENERATIONS):100l 交叉概率(PC)：0.85l 變異概率(PM):0.15l 選擇個(gè)體方法：輪盤賭選擇l 交叉類型：PMX交叉l 變異類型: 兩點(diǎn)互換變異a. 個(gè)體選擇概率分配方法：適應(yīng)度比例方法同表1-4b. 個(gè)體選擇概率分配方法：非線性排序方式表1-6非線性排序方

30、式程序結(jié)果序號最好適應(yīng)度最差適應(yīng)度平均適應(yīng)度最優(yōu)解運(yùn)行時(shí)間127.093532.172130.09041-9-2-6-0-5-4-7-8-3824228.044731.29729.99794-5-0-6-2-9-1-3-7-8865328.093432.168330.56012-0-5-4-7-8-3-1-9-6895427.093532.097330.34723-1-9-2-6-0-5-4-7-81067527.093531.51629.85314-5-0-6-2-9-1-3-8-7887627.093531.40829.46375-0-6-2-9-1-3-8-7-4727727.093531.374229.94763-1-9-2-6-0-5-4-7-8651829.523131.800930.55430-5-4-7-8-1-3-9-2-6901927.093532.714730.3910-5-4-7-8-3-1-9-2-67491029.523131.568830.23859-3-1-8-7-4-5-0-6-28401128.044731.763930.26173-7-8-4-5-0-6-2-9-110441228.044731.630830.32671-3-7-8-4-5-0-6-2-97321327.093531.568829.43320-5-4-7-8