遺傳算法求解TSP問(wèn)題實(shí)驗(yàn)報(bào)告

1、人工智能實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)六 遺傳算法實(shí)驗(yàn)II、實(shí)驗(yàn)?zāi)康?熟悉和掌握遺傳算法的原理、流程和編碼策略，并利用遺傳求解函數(shù)優(yōu)化問(wèn)題，理解求解TSP問(wèn)題的流程并測(cè)試主要參數(shù)對(duì)結(jié)果的影響。二、實(shí)驗(yàn)原理：旅行商問(wèn)題，即TSP問(wèn)題(Traveling Salesman Problem)是數(shù)學(xué)領(lǐng)域中著名問(wèn)題之一。假設(shè)有一個(gè)旅行商人要拜訪(fǎng)n 個(gè)城市， 他必須選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪(fǎng)一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。TSP問(wèn)題是一個(gè)組合優(yōu)化問(wèn)題。該問(wèn)題可以被證明具有 NPC十算復(fù)雜性。因此，任何能使該問(wèn)題的求解得以簡(jiǎn)化的方法，都將受到高度

2、的評(píng)價(jià)和關(guān)注。遺傳算法的基本思想正是基于模仿生物界遺傳學(xué)的遺傳過(guò)程。它把問(wèn)題的參數(shù)用基因代表，把問(wèn)題的解用染色體代表(在計(jì)算機(jī)里用二進(jìn)制碼表示)，從而得到一個(gè)由具有不同染色體的個(gè)體組成的群體。這個(gè)群體在問(wèn)題特定的環(huán)境里生存競(jìng)爭(zhēng)，適者有最好的機(jī)會(huì)生存和產(chǎn)生后代。后代隨機(jī)化地繼承了父代的最好特征，并也在生存環(huán)境的控制支配下繼續(xù)這一過(guò)程。群體的染色體都將逐漸適應(yīng)環(huán)境，不斷進(jìn)化，最后收斂到一族最適應(yīng)環(huán)境的類(lèi)似個(gè)體，即得到問(wèn)題最優(yōu)的解。要求利用遺傳算法求解TSP問(wèn)題的最短路徑。三、實(shí)驗(yàn)內(nèi)容：1、參考實(shí)驗(yàn)系統(tǒng)給出的遺傳算法核心代碼，用遺傳算法求解TSP的優(yōu)化問(wèn)題，分析遺傳算法求解不同規(guī)模 TSP問(wèn)題的算法

3、性能。2、對(duì)于同一個(gè)TSP問(wèn)題，分析種群規(guī)模、交叉概率和變異概率對(duì)算法結(jié)果的影響。3、增加1種變異策略和1種個(gè)體選擇概率分配策略，比較求解同一TSP問(wèn)題時(shí)不同變異策略及不同個(gè)體選擇分配策略對(duì)算法結(jié)果的影響。4 、上交源代碼。5 / 5四、實(shí)驗(yàn)報(bào)告要求:1、畫(huà)出遺傳算法求解 TSP問(wèn)題的流程圖。NO輸入適應(yīng)度最高的解2、分析遺傳算法求解不同規(guī)模的 TSP問(wèn)題的算法性能。規(guī)模越大，算法的性能越差，所用時(shí)間越長(zhǎng)3、對(duì)于同一個(gè)TSP問(wèn)題，分析種群規(guī)模、交叉概率和變異概率對(duì)算法結(jié)果的影響。(1)種群規(guī)模對(duì)算法結(jié)果的影響x01.13.537844.592y1.13245.1844.592實(shí)驗(yàn)次數(shù)：10 最

4、大迭代步數(shù)：100 交叉概率：0.85 變異概率：0.15種群規(guī)模平均適應(yīng)度值最優(yōu)路徑1025.2644-5-8-7-6-3-1-0-9-2 12026.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-36720025.16521-3-6-7-5-8-4-2-9-025025.16523-1-0-9-2-4-8-5-7-613

5、0025.16525-8-4-2-9-0-1-3-6-7如表所示，顯然最短路徑為 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í)，并沒(méi)有找到最優(yōu)解。因此并不是種群規(guī)模越小越好。(2)交叉概率對(duì)算法結(jié)果的影響x91.13.53.57844.532y1.13145.1318.591實(shí)驗(yàn)次數(shù)：15 種群規(guī)模：25 最大迭代步數(shù)：100 變異概率：0.15 實(shí)驗(yàn)結(jié)果：交叉概率最好適應(yīng)度最差適應(yīng)度平均適應(yīng)度最優(yōu)解0.00128.044736.656732.60029-

6、2-6-0-5-4-8-7-3-10.0127.093534.994332.14957-8-3-1-9-2-6-0-5-40.128.044735.303331.93727-3-1-9-2-6-0-5-4-80.1528.044734.117531.21830-5-4-8-7-3-1-9-2-60.228.710833.951230.90353-1-9-2-6-5-0-4-7-80.2528.044735.162330.74561-3-7-8-4-5-0-6-2-90.327.093531.994129.94288-3-1-9-2-6-0-5-4-70.3527.093532.808530.9

7、9459-1-3-8-7-4-5-0-6-20.427.093532.531330.15341-3-8-7-4-5-0-6-2-90.4527.093533.201430.17578-3-1-9-2-6-0-5-4-70.528.093433.630730.90265-026-9-1-3-8-7-40.5527.093533.523329.13041-9-2-6-0-5-4-7-8-30.627.093533.251230.78363-1-9-2-6-0-5-4-7-80.6528.044733.700330.93715-4-8-7-3-1-9-2-6-00.727.093532.092729

8、.95029-1-3-8-7-4-5-0-6-20.7528.044732.448830.36990-5-4-8-7-3-1-9-2-60.827.093532.155129.93827-4-5-0-6-2-9-1-3-80.8527.093534.539930.35945-0-6-2-9-1-3-8-7-40.927.093532.627330.696-0-5-4-7-8-3-1-9-20.9527.093532.467229.9196-2-9-1-3-8-7-4-5-0(注:紅色表示非最優(yōu)解)在該情況下，交叉概率過(guò)低將使搜索陷入遲鈍狀態(tài)，得不到最優(yōu)解。(3)變異概率對(duì)算法結(jié)果的影響x91.

9、13.53.57844.532y1.13145.1318.591實(shí)驗(yàn)次數(shù)：10 種群規(guī)模：25 最大迭代步數(shù)：100 交叉概率：0.85 實(shí)驗(yàn)結(jié)果：變異概率最好適應(yīng)度最差適應(yīng)度平均適應(yīng)度最優(yōu)解0.00129.471734.73232.49110-6-2-1-9-3-8-7-4-50.0129.044634.659132.37148-4-5-0-2-6-9-1-3-70.128.093434.01130.94175-0-2-6-9-1-3-8-7-40.1527.093532.09330.25686-0-5-4-7-8-3-1-9-20.227.093532.234930.31448-7-4-5

10、-0-6-2-9-1-30.2527.093532.71830.15724-5-0-6-2-9-1-3-8-70.327.093532.448830.28540-5-4-7-8-3-1-9-2-60.3527.093533.316730.77481-3-8-7-4-5-0-6-2-90.429.044634.370531.30412-0-5-4-8-7-3-1-9-60.4527.093531.37429.68162-6-0-5-4-7-8-3-1-90.527.093532.375230.22112-9-1-3-8-7-4-5-0-60.5527.093533.381930.66231-3-

11、8-7-4-5-0-6-2-90.628.093433.251230.361-3-8-7-4-5-0-2-6-90.6527.093532.749130.02013-1-9-2-6-0-5-4-7-80.728.710832.423830.7851-3-8-7-4-0-5-6-2-90.7527.093531.892830.24511-9-2-6-0-5-4-7-8-30.828.093431.613530.34719-1-3-8-7-4-5-0-2-60.8529.66233.239231.15852-9-1-3-7-8-4-0-5-60.928.044732.038730.41520-5-4-8-7-3-1-9-2-60.9528.044731.303630.00679-1-3-7-8-4-5-0-6-2從該表可知，當(dāng)變異概率過(guò)大或過(guò)低都將導(dǎo)致無(wú)法得到最優(yōu)解。4、增加1種變異策略和1種個(gè)體選擇概率分配策略，比較求解同一TSP問(wèn)題時(shí)不同變異策略及不同個(gè)體選擇分配策略對(duì)算法結(jié)果的影響。不同變異策略和不同個(gè)體選擇分配策略幾