TSP問題求解實驗報告(word文檔良心出品)

1、TSP問題求解（一）實驗目的 熟悉和掌握遺傳算法的原理，流程和編碼策略，并利用遺傳 求解函數優(yōu)化問題，理解求解 TSP問題的流程并測試主要參數對結果的影響。（二）實驗原理 巡回旅行商問題 給定一組n個城市和倆倆之間的直達距離，尋找一條閉合的 旅程，使得每個城市剛好經過一次且總的旅行距離最短。TSP問題也稱為貨郎擔問題，是一個古老的問題。最早可以追溯到1759年Euler提出的騎士旅行的問題。1948年，由 美國蘭德公司推動，TSP成為近代組合優(yōu)化領域的典型難題。TSP是一個具有廣泛的應用背景和重要理論價值的組合優(yōu)化問題。近年來，有很多解決該問題的較為有效的算法不斷被推出，例如Ho pfield

2、神經網絡方法，模擬退火方法以及 遺傳算法方法等。TSP搜索空間隨著城市數 n的增加而增大，所有的旅程路線組合數為（n-1）!/2。在如此龐大的搜索空間中尋求最優(yōu)解，對 于常規(guī)方法和現有的計算工具而言，存在著諸多計算困難。借助遺傳算法的搜索能力解決TSP問題，是很自然的想法?；具z傳算法可定義為一個 8元組:(SGA = (C, E, PO, M ，r , ¥ , T)C個體的編碼方法，SGA使用固定長度二進制符號串編 碼方法;E 個體的適應度評價函數;P0初始群體;M群體大小,般取 20 100;一一選擇算子,SGA使用比例算子;r交叉算子,SGA使用單點交叉算子;¥變異算

3、子,SGA使用基本位變異算子;算法終止條件，一般終止進化代數為100500;問題的表示 對于一個實際的待優(yōu)化問題，首先需要將其表示為適合于遺傳算法操作的形式。用遺傳算法解決TSP, 個旅程很自然 的表示為n個城市的排列，但基于二進制編碼的交叉和變異 操作不能適用。路徑表示是表示旅程對應的基因編碼的最自然，最簡單的表 示方法。它在編碼，解碼，存儲過程中相對容易理解和實現。例如：旅程（5-1-7-8-9-4-6-2-3）可以直接表示為（5 1 7（三）實驗內容N>=&隨即生成N個城市間的連接矩陣。指定起始城市。給出每一代的最優(yōu)路線和總路線長度。以代數T作為結束條件，T>=50。

4、（四）實驗代碼#i nclude "stdafx.h"#inelude <stdio.h>#inelude <string.h>#inelude <stdlib.h>#inelude <math.h>#inelude <time.h>#define cities 10/ 城市的個數#define MAXXI00 / 迭代次數#define pc 0.8 / 交配概率#define pm0.05 / 變異概率#define num10 /種群的大小int bestsolution; / 最優(yōu)染色體int distan

5、cecities cities ; / 城市之間的距離struct group /染色體的結構int eity cities ; / 城市的順序int adapt; / 適應度double p; /在種群中的幸存概率group num, grouptemp num;/隨機產生cities個城市之間的相互距離void init()int i, j;memset(distanee, 0, sizeof (distanee);srand( unsigned )time( NULL);for (i = 0; i< cities ; i+)for (j = i + 1; j<cities ;

6、 j+)dista nceij = ran dQ % 100;dista nceji = dista nceij;/打印距離矩陣printf（"城市的距離矩陣如下n"）;for (i = 0; i< cities ; i+) for (j = 0; jy cities ; j+)p ri ntf( "%4d", dista nceij);printf( "n");/隨機產生初試群void groupproduce()int i, j, t, k, flag;for (i = 0; iynum i+)/ 初始化for (j = 0

7、; jycities ; j+)group i.cityj = -1;srand( unsigned )time( NULL);for (i = 0; i< num i+) /產生10個不相同的數字 for (j = 0; j< cities ;)t = ran d() % cities ;flag = 1;for (k = 0; kvj; k+)jif (groupi.cityk = t)flag = 0;break; if (flag)grou pi.cityj = t; j+;ij打印種群基因.printf( “初始的種群n" )Jfor (i = 0; iy nu

8、m i+) for (j = 0; jy cities ; j+)printf( "n");/評價函數，找岀最優(yōu)染色體 void pingjia()int i, j;int n1, n2;int sumdistanee, biggestsum = 0;double biggest p = 0;for (i = 0; i< num i+)sumdista nee = 0;for (j = 1; j< cities ; j+)n1 = grou pi.cityj - 1;n2 = grou pi.cityj;/每條染色體的路徑總和sumdista nee += di

9、sta nce n1 n2;grou pi.ada pt = sumdista nee;biggestsum += sumdistanee;/ 種群的總路徑/計算染色體的幸存能力，路勁越短生存概率越大for (i = 0; i<num i+)groupi.p = 1 - (double )groupi.adapt / (double )biggestsum;biggest p += grou pi. p;for (i = 0; i< num i+)grou pi.p = grou pi. p / biggest p;/求最佳路勁/在種群中的幸存概率，總和為1bestsoluti o

10、n = 0;for (i = 0; i< num i+)if (groupi.p>groupbestsolution.p) bestsoluti on = i;/打印適應度for (i = 0; i< num i+)printf（“染色體1的路徑之和與生存概率分別為4d %.4fn" , i, groupi.adapt,grou pi. p）;printf（"當前種群的最優(yōu)染色體是 d#染色體n" , bestsolution）;/選擇void xuanze()int i, j, temp;double gradient num； / 梯度概率d

11、ouble xuanze nun; /選擇染色體的隨機概率 int xuan num; 選擇了的染色體初始化梯度概率"for (i = 0; i< num i+) gradie nti = 0.0; xua nzei = 0.0;亍gradie nt0 = grou p 0. p; for (i = 1; i< num i+)gradie nti = gradie nti - 1 + grou pi. p; srand( unsigned )time( NULL);隨機產生染色體的存活概率for (i = 0; i< num i+).xuan zei = (ran

12、d() % 100);xuan zei /= 100;選擇能生存的染色體for (i = 0; i<num i+)for (j = 0; j<num j+)if (xuanzei<gradientj)xuani = j; /第i個位置存放第j個染色體 break;/拷貝種群for (i = 0; i< num i+)£grou ptemp i.ada pt = grou pi.ada pt;grou ptem p i. p = grou pi. p;for (j = 0; j< cities ; j+)grou ptempi .cityj = grou

13、pi.cityj;/數據更新for (i = 0; i< num i+)temp = xua ni;grou pi.ada pt = grou ptemp te mp .ada pt;grou pi. p = grou ptemp te mp . p;for (j = 0; j< cities ; j+)grou pi.cityj = grou ptemp te mp .cityj;/用于測試>n")；printf("<for (i=0;i< numi+)for (j=0;j< cities ;j+)pri ntf( "%4d&

14、quot;,grou pi.cityj);printf( "n");printf("染色體d的路徑之和與生存概率分別為%4d %.4fn" ,i,groupi.adapt,groupi.p);_jj交配，對每個染色體產生交配概率，滿足交配率的染色體進行交配void jia op ei()int i, j, k, kk;int t; /參與交配的染色體的個數int point1, point2, temp;/ 交配斷點int pointnum;int tempi, temp2;int map 1 cities , map2 cities ;double j

15、iaopeipnum; 染色體的交配概率int jiaopeiflagnum; 染色體的可交配情況for (i = 0; i< num i+) / 初始化jia op eiflagi = 0;/隨機產生交配概率srand( unsigned )time( NULL); for (i = 0; i< num i+)jia opeipi = (ran d() % 100);jiao pei pi /= 100;/確定可以交配的染色體 t = 0;for (i = 0; i< num i+)if (jiaopeipi<pc)jia op eiflagi = 1;t+;/t必須

16、為偶數t = t / 2 * 2;產生t/2'個0-9交配斷點srand( unsigned )time( NULL);temp1 = 0;/temp1號染色體和temp2染色體交配 for (i = 0; i<t / 2; i+)point1 = ran d() %cities ;point2 = ran d() %cities ;for (j = tempi; j< num j+) if (jiaopeiflagj = 1),temp1 = j;break;for (j = temp1 + 1; j< num j+) if (jiaopeiflagj = 1) t

17、emp2 = j;break;/進行基因交配if (point1>point2)/ 保證 point1<=point2temp = p oi nt1;p oi nt1 = p oi nt2;p oi nt2 = temp;memset(mapi, -1, sizeof (mapi); memset(map2, -1, sizeof (map2);/斷點之間的基因產生映射 for (k = point1; k <= point2; k+)map 1grou pte mp 1.cityk = grou pte mp 2.cityk;map 2grou pte mp 2.cityk

18、 = grou pte mp 1.cityk;/斷點兩邊的基因互換 for (k = 0; k<point1; k+) temp = grou pte mp 1.cityk;grou pte mp 1.cityk = grou pte mp 2.cityk;grou pte mp 2.cityk = temp;for (k = point2 + 1; k<cities ; k+)'temp = grou pte mp 1.cityk;grou pte mp 1.cityk = grou pte mp 2.cityk;grou pte mp 2.cityk = temp;fo

19、r (kk = point1; kk <= point2; kk+) if (grouptemp 1.cityk = grouptemp1.citykk) grou pte mp 1.cityk = map 1grou pte mp 1.cityk;break;for (k = point2 + 1; k< cities ; k+) for (kk = point1; kk <= point2; kk+)if (grouptemp 1.cityk = grouptemp 1.citykk)grou pte mp 1.cityk = map 1grou pte mp 1.cit

20、yk;break;for (kk = point1; kk <= point2; kk+) if (grouptemp2.cityk = grouptemp2.citykk) grou pte mp 2.cityk = map 2grou pte mp 2.cityk;break;for (k = point2 + 1; k<cities ; k+)for (kk = point1; kk <= point2; kk+)if (grouptemp2.cityk = grouptemp2.citykk)grou pte mp 2.cityk = map 2grou pte mp

21、 2.cityk; break;temp1 = temp2 + 1;變異void bianyK)int i, j;int t;int temp1, temp2, point;double bianyip num; 染色體的變異概率 int bianyiflagnum; 染色體的變異情況for (i = 0; i< num i+) / 初始化bia nyiflagi = 0;隨機產生變異概率srand( unsigned )time( NULL);for (i = 0; i< num i+)bia nyip i = (ra ndO % 100);bia nyi pi/= 100;/確

22、定可以變異的染色體t = 0;for (i = 0; i< num i+)if (bianyipi<pn)bia nyiflagi = 1;t+;/變異操作，即交換染色體的兩個節(jié)點 srand( unsigned )time( NULL);for (i = 0; i< num i+)dif (bianyiflagi = 1)temp1 = ran d() % 10; temp2 = ran d() % 10;point = grou pi.cityte mp 1;grou pi.cityte mp1 = grou pi.cityte mp 2;grou pi.cityte m

23、p2 = point;int main()int i, j, t;ini t();grou ppr oduceO;初始種群評價pin gjia(); t = 0;while (t+< MAXX xua nze();/ jiaop ei();bia nyi();pin gjia();/最終種群的評價printf（ "n輸岀最終的種群評價n"）;for (i = 0; i<num i+)for (j = 0; j< cities ; j+) printf( "%4d", grou p i.cityj);prints" ada pt

24、:%4d, p :%.4fn", grou pi.ada pt, grou pi. p);printf("最優(yōu)解為 c號染色體 n" , bestsolution);system("Pause");（五）實驗結果截圖崇色件B的路徑二和M生存概車n別Vq19296345 設色體乂的路徑之和與生存概率分別為 19800245 親色體2的路徑之和與生存概率分別為 10333345 迢體3的路徑之和與生存概率分別為 10333345 染色體4的路徑之和與生存概率分別為 46222351 染色體5的路徑之和與生存概率分別為 84366351 ，邑體6的路

25、徑之和與生存概率分別為 84366351 染色體2的路徑之和與生存概率分別為 10333345 柔色伽的路徑之和與生存概率分別為 10333345 卞邑件9的筑#之和與生存槪李亍別為 Um的躋fe之和勺生存疑孚分別為 抵孚分別為 旣軍n別為 別巧 僦車n別為艱S仲昭注巻雀怪色佯1的潛仝之祖m生存 ，電色2的站卷之知三生存 十剛*的路生存 沖#4的路fez和m生存嚴亍“ 涇色*5的曲fez和m 土存fe李分別4856214852992994465555552992994324373620.098570.09507 0-098570.103370.103370.099570.096770.0967

26、70.103370.10330-09940.09920.09620.10300.10300.1013F C:UserAAdminfetratoDesktopMl»S：fhlAZ«BaSWtt»1TSPigaDebugW 1° 問146800251卜色體1的路徑之和與生存概率分別為 I 84366351 嚷色體2的路徑之和與生存概率分別為 I 10333345 空色體3的路徑之和與生存概率分別為 I 10333345 哽免體4的路徑之和與生存概率分別為 I 19396245 冷色體5的路徑之和與生存概率分別為 119222245 冷電體6的路徑之和與生存概率分別為 19222245 染色體7的路徑之和與生存概率分別為 I 10333345 黃色體8的路徑之和與生存概率分別為 10333345 ，色佯9的跆徑之和m生存槪率吩另I為 W邑如的路fez和勻生存既李分別為 丄憶心叫仝之和與生存甩孚分別為-'占生存嘅至弈別為 TDS生存既車弓笄I為 輕之杓勻生存旣辜詢?yōu)?fez和生存愚率分另卜冷色仔1的跆工厶&