1、本文格式為Word版，下載可任意編輯 10個城市的tsp問題 人工智能測驗報告 測驗六 遺傳算法測驗II 一、測驗目的： 熟諳和掌管遺傳算法的原理、流程和編碼策略，并利用遺傳求解函數(shù)優(yōu)化問題，理解求解TSP問題的流程并測試主要參數(shù)對結果的影響。 二、測驗原理： 旅行商問題，即TSP問題（Traveling Salesman Problem）是數(shù)學領域中出名問題之一。假設有一個旅行商人要訪問n個城市，他務必選擇所要走的路徑，路經的限制是每個城市只能訪問一次，而且結果要回到原來啟程的城市。路徑的選擇目標是要求得的路徑路程為全體路徑之中的最小值。TSP問題是一個組合優(yōu)化問題。該問題可以被證明具有NP

2、C計算繁雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。 遺傳算法的根本思想正是基于模仿生物界遺傳學的遺傳過程。它把問題的參數(shù)用基因代表，把問題的解用染色體代表（在計算機里用二進制碼表示），從而得到一個由具有不同染色體的個體組成的群體。這個群體在問題特定的環(huán)境里生存競爭，適者有最好的機遇生存和產生后代。后代隨機化地繼承了父代的最好特征，并也在生存環(huán)境的操縱支配下持續(xù)這一過程。群體的染色體都將逐步適應環(huán)境，不斷進化，結果收斂到一族最適應環(huán)境的類似個體，即得到問題最優(yōu)的解。要求利用遺傳算法求解TSP問題的最短路徑。 三、測驗內容： 1、參考測驗系統(tǒng)給出的遺傳算法核心代碼，

3、用遺傳算法求解TSP的優(yōu)化問題，分析遺傳算法求解不同規(guī)模TSP問題的算法性能。 2、對于同一個TSP問題，分析種群規(guī)模、交錯概率和變異概率對算法結果的影響。 3、增加1種變異策略和1種個體選擇概率調配策略，對比求解同一TSP問題時不同變異策略及不同個體選擇調配策略對算法結果的影響。 4、上交源代碼。 四、測驗報告要求： 1、畫出遺傳算法求解TSP問題的流程圖。 2、 分析遺傳算法求解不同規(guī)模的TSP問題的算法性能。 規(guī)模越大，算法的性能越差，所用時間越長。 3、對于同一個TSP問題，分析種群規(guī)模、交錯概率和變異概率對算法結果的影響。 （1） 種群規(guī)模對算法結果的影響 x 0 1.1 3.5 3

4、 7 8 4 4.5 9 2 y 1.1 3 2 4 5.1 8 4 4.5 9 2 測驗次數(shù)：10 最大迭代步數(shù):100 交錯概率：0.85 變異概率：0.15 種群規(guī)模 平均適應度值 最優(yōu)路徑 10 25.264 4-5-8-7-6-3-1-0-9-2 20 26.3428 2-9-1-0-3-6-7-5-8-4 30 25.1652 1-3-6-7-5-8-4-2-9-0 50 25.1652 0-1-3-6-7-5-8-4-2-9 80 25.1652 9-0-1-3-6-7-5-8-4-2 100 25.1652 1-0-9-2-4-8-5-7-6-3 150 25.1652 5-8

5、-4-2-9-0-1-3-6-7 200 25.1652 1-3-6-7-5-8-4-2-9-0 250 25.1652 3-1-0-9-2-4-8-5-7-6 300 25.1652 5-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，留神到這是一圈，順時針或者逆時針都可以。當種群規(guī)模為10，20時，并沒有找到最優(yōu)解。因此并不是種群規(guī)模越小越好。 （2） 交錯概率對算法結果的影響 x 9 1.1 3.5 3.5 7 8 4 4.5 3 2 y 1.1 3 1 4 5.1

6、 3 1 8.5 9 1 測驗次數(shù)：15 種群規(guī)模：25 最大迭代步數(shù):100 變異概率：0.15 測驗結果： 交錯概率 最好適應度 最差適應度 平均適應度 最優(yōu)解 0.001 28.0447 36.6567 32.6002 9-2-6-0-5-4-8-7-3-1 0.01 27.0935 34.9943 32.1495 7-8-3-1-9-2-6-0-5-4 0.1 28.0447 35.3033 31.9372 7-3-1-9-2-6-0-5-4-8 0.15 28.0447 34.1175 31.2183 0-5-4-8-7-3-1-9-2-6 0.2 28.7108 33.9512 3

7、0.9035 3-1-9-2-6-5-0-4-7-8 0.25 28.0447 35.1623 30.7456 1-3-7-8-4-5-0-6-2-9 0.3 27.0935 31.9941 29.9428 8-3-1-9-2-6-0-5-4-7 0.35 27.0935 32.8085 30.9945 9-1-3-8-7-4-5-0-6-2 0.4 27.0935 32.5313 30.1534 1-3-8-7-4-5-0-6-2-9 0.45 27.0935 33.2022 30.1757 8-3-1-9-2-6-0-5-4-7 0.5 28.0934 33.6307 30.9026 5-

8、0-2-6-9-1-3-8-7-4 0.55 27.0935 33.5233 29.1304 1-9-2-6-0-5-4-7-8-3 0.6 27.0935 33.2512 30.7836 3-1-9-2-6-0-5-4-7-8 0.65 28.0447 33.7003 30.9371 5-4-8-7-3-1-9-2-6-0 0.7 27.0935 32.0927 29.9502 9-1-3-8-7-4-5-0-6-2 0.75 28.0447 32.4488 30.3699 0-5-4-8-7-3-1-9-2-6 0.8 27.0935 32.1551 29.9382 7-4-5-0-6-2

9、-9-1-3-8 0.85 27.0935 34.5399 30.3594 5-0-6-2-9-1-3-8-7-4 0.9 27.0935 32.6273 30.69 6-0-5-4-7-8-3-1-9-2 0.95 27.0935 32.4672 29.919 6-2-9-1-3-8-7-4-5-0 （注:紅色表示非最優(yōu)解） 在該處境下，交錯概率過低將使探尋陷入遲鈍狀態(tài)，得不到最優(yōu)解。 （3） 變異概率對算法結果的影響 x 9 1.1 3.5 3.5 7 8 4 4.5 3 2 y 1.1 3 1 4 5.1 3 1 8.5 9 1 測驗次數(shù)：10 種群規(guī)模：25 最大迭代步數(shù):100 交錯

10、概率：0.85 測驗結果： 變異概率 最好適應度 最差適應度 平均適應度 最優(yōu)解 0.001 29.4717 34.732 32.4911 0-6-2-1-9-3-8-7-4-5 0.01 29.0446 34.6591 32.3714 8-4-5-0-2-6-9-1-3-7 0.1 28.0934 34.011 30.9417 5-0-2-6-9-1-3-8-7-4 0.15 27.0935 32.093 30.2568 6-0-5-4-7-8-3-1-9-2 0.2 27.0935 32.2349 30.3144 8-7-4-5-0-6-2-9-1-3 0.25 27.0935 32.71

11、8 30.1572 4-5-0-6-2-9-1-3-8-7 0.3 27.0935 32.4488 30.2854 0-5-4-7-8-3-1-9-2-6 0.35 27.0935 33.3167 30.7748 1-3-8-7-4-5-0-6-2-9 0.4 29.0446 34.3705 31.3041 2-0-5-4-8-7-3-1-9-6 0.45 27.0935 31.374 29.6816 2-6-0-5-4-7-8-3-1-9 0.5 27.0935 32.3752 30.2211 2-9-1-3-8-7-4-5-0-6 0.55 27.0935 33.3819 30.6623

12、1-3-8-7-4-5-0-6-2-9 0.6 28.0934 33.2512 30.36 1-3-8-7-4-5-0-2-6-9 0.65 27.0935 32.7491 30.0201 3-1-9-2-6-0-5-4-7-8 0.7 28.7108 32.4238 30.785 1-3-8-7-4-0-5-6-2-9 0.75 27.0935 31.8928 30.2451 1-9-2-6-0-5-4-7-8-3 0.8 28.0934 31.6135 30.3471 9-1-3-8-7-4-5-0-2-6 0.85 29.662 33.2392 31.1585 2-9-1-3-7-8-4-0-5-6 0.9 28.0447 32.0387 30.4152 0-5-4-8-7-3-1-9-2-6 0.95 28.0447 31.3036 30.0067 9-1-3-7-8-4-5-0-6-2 從該表可知，當變異概率過大或過低都將導致無法得到最優(yōu)解。 4、增加1種變異策略和1種個體選擇概率調配策略，對比求解同一TSP問題時不同變異策略及不同個體選擇調配策略對算法結果的影響。