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

1、TSP問(wèn)題求解（1） 實(shí)驗(yàn)?zāi)康氖煜ず驼莆者z傳算法的原理，流程和編碼策略，并利用遺傳求解函數(shù)優(yōu)化問(wèn)題，理解求解TSP問(wèn)題的流程并測(cè)試主要參數(shù)對(duì)結(jié)果的影響。（2） 實(shí)驗(yàn)原理巡回旅行商問(wèn)題給定一組n個(gè)城市和倆倆之間的直達(dá)距離，尋找一條閉合的旅程，使得每個(gè)城市剛好經(jīng)過(guò)一次且總的旅行距離最短。TSP問(wèn)題也稱為貨郎擔(dān)問(wèn)題，是一個(gè)古老的問(wèn)題。最早可以追溯到1759年Euler提出的騎士旅行的問(wèn)題。1948年，由美國(guó)蘭德公司推動(dòng)，TSP成為近代組合優(yōu)化領(lǐng)域的典型難題。TSP是一個(gè)具有廣泛的應(yīng)用背景和重要理論價(jià)值的組合優(yōu)化問(wèn)題。 近年來(lái)，有很多解決該問(wèn)題的較為有效的算法不斷被推出，例如Hopfield神經(jīng)網(wǎng)絡(luò)方

2、法，模擬退火方法以及遺傳算法方法等。TSP搜索空間隨著城市數(shù)n的增加而增大,所有的旅程路線組合數(shù)為(n-1)!/2。在如此龐大的搜索空間中尋求最優(yōu)解，對(duì)于常規(guī)方法和現(xiàn)有的計(jì)算工具而言，存在著諸多計(jì)算困難。借助遺傳算法的搜索能力解決TSP問(wèn)題，是很自然的想法?；具z傳算法可定義為一個(gè)8元組：（SGA）=（C，E，P0，M，）C 個(gè)體的編碼方法，SGA使用固定長(zhǎng)度二進(jìn)制符號(hào)串編碼方法；E 個(gè)體的適應(yīng)度評(píng)價(jià)函數(shù)；P0初始群體；M 群體大小，一般取20100；選擇算子，SGA使用比例算子；交叉算子，SGA使用單點(diǎn)交叉算子；變異算子，SGA使用基本位變異算子；算法終止條件，一般終止進(jìn)化代數(shù)為100500

3、；問(wèn)題的表示 對(duì)于一個(gè)實(shí)際的待優(yōu)化問(wèn)題，首先需要將其表示為適合于遺傳算法操作的形式。用遺傳算法解決TSP，一個(gè)旅程很自然的表示為n個(gè)城市的排列，但基于二進(jìn)制編碼的交叉和變異操作不能適用。路徑表示是表示旅程對(duì)應(yīng)的基因編碼的最自然，最簡(jiǎn)單的表示方法。它在編碼，解碼，存儲(chǔ)過(guò)程中相對(duì)容易理解和實(shí)現(xiàn)。例如：旅程（5-1-7-8-9-4-6-2-3）可以直接表示為（5 1 7 8 9 4 6 2 3） （三）實(shí)驗(yàn)內(nèi)容N=8。隨即生成N個(gè)城市間的連接矩陣。指定起始城市。給出每一代的最優(yōu)路線和總路線長(zhǎng)度。以代數(shù)T作為結(jié)束條件，T=50。（4） 實(shí)驗(yàn)代碼#include stdafx.h#include#inc

4、lude#include#include#include#define cities 10 /城市的個(gè)數(shù)#define MAXX 100/迭代次數(shù)#define pc 0.8 /交配概率#define pm 0.05 /變異概率#define num 10/種群的大小int bestsolution;/最優(yōu)染色體int distancecitiescities;/城市之間的距離struct group /染色體的結(jié)構(gòu)int citycities;/城市的順序int adapt;/適應(yīng)度double p;/在種群中的幸存概率groupnum, grouptempnum;/隨機(jī)產(chǎn)生cities個(gè)城

5、市之間的相互距離void init()int i, j;memset(distance, 0, sizeof(distance);srand(unsigned)time(NULL);for (i = 0; icities; i+)for (j = i + 1; jcities; j+)distanceij = rand() % 100;distanceji = distanceij;/打印距離矩陣printf(城市的距離矩陣如下n);for (i = 0; icities; i+)for (j = 0; jcities; j+)printf(%4d, distanceij);printf(n)

6、;/隨機(jī)產(chǎn)生初試群void groupproduce()int i, j, t, k, flag;for (i = 0; inum; i+) /初始化for (j = 0; jcities; j+)groupi.cityj = -1;srand(unsigned)time(NULL);for (i = 0; inum; i+)/產(chǎn)生10個(gè)不相同的數(shù)字for (j = 0; jcities;)t = rand() % cities;flag = 1;for (k = 0; kj; k+)if (groupi.cityk = t)flag = 0;break;if (flag)groupi.cit

7、yj = t;j+;/打印種群基因printf(初始的種群n);for (i = 0; inum; i+)for (j = 0; jcities; j+)printf(%4d, groupi.cityj);printf(n);/評(píng)價(jià)函數(shù),找出最優(yōu)染色體void pingjia()int i, j;int n1, n2;int sumdistance, biggestsum = 0;double biggestp = 0;for (i = 0; inum; i+)sumdistance = 0;for (j = 1; jcities; j+)n1 = groupi.cityj - 1;n2 =

8、groupi.cityj;sumdistance += distancen1n2;groupi.adapt = sumdistance; /每條染色體的路徑總和biggestsum += sumdistance; /種群的總路徑/計(jì)算染色體的幸存能力,路勁越短生存概率越大for (i = 0; inum; i+)groupi.p = 1 - (double)groupi.adapt / (double)biggestsum;biggestp += groupi.p;for (i = 0; inum; i+)groupi.p = groupi.p / biggestp; /在種群中的幸存概率,總

9、和為1/求最佳路勁bestsolution = 0;for (i = 0; igroupbestsolution.p)bestsolution = i;/打印適應(yīng)度f(wàn)or (i = 0; inum; i+)printf(染色體%d的路徑之和與生存概率分別為%4d %.4fn, i, groupi.adapt, groupi.p);printf(當(dāng)前種群的最優(yōu)染色體是%d號(hào)染色體n, bestsolution);/選擇void xuanze()int i, j, temp;double gradientnum;/梯度概率double xuanzenum;/選擇染色體的隨機(jī)概率int xuannu

10、m;/選擇了的染色體/初始化梯度概率for (i = 0; inum; i+)gradienti = 0.0;xuanzei = 0.0;gradient0 = group0.p;for (i = 1; inum; i+)gradienti = gradienti - 1 + groupi.p;srand(unsigned)time(NULL);/隨機(jī)產(chǎn)生染色體的存活概率for (i = 0; inum; i+)xuanzei = (rand() % 100);xuanzei /= 100;/選擇能生存的染色體for (i = 0; inum; i+)for (j = 0; jnum; j+)

11、if (xuanzeigradientj)xuani = j; /第i個(gè)位置存放第j個(gè)染色體break;/拷貝種群for (i = 0; inum; i+)grouptempi.adapt = groupi.adapt;grouptempi.p = groupi.p;for (j = 0; jcities; j+)grouptempi.cityj = groupi.cityj;/數(shù)據(jù)更新for (i = 0; inum; i+)temp = xuani;groupi.adapt = grouptemptemp.adapt;groupi.p = grouptemptemp.p;for (j =

12、0; jcities; j+)groupi.cityj = grouptemptemp.cityj;/用于測(cè)試printf(n);for(i=0;inum;i+)for(j=0;jcities;j+)printf(%4d,groupi.cityj);printf(n);printf(染色體%d的路徑之和與生存概率分別為%4d %.4fn,i,groupi.adapt,groupi.p);/交配,對(duì)每個(gè)染色體產(chǎn)生交配概率,滿足交配率的染色體進(jìn)行交配void jiaopei()int i, j, k, kk;int t;/參與交配的染色體的個(gè)數(shù)int point1, point2, temp;/交

13、配斷點(diǎn)int pointnum;int temp1, temp2;int map1cities, map2cities;double jiaopeipnum;/染色體的交配概率int jiaopeiflagnum;/染色體的可交配情況for (i = 0; inum; i+)/初始化jiaopeiflagi = 0;/隨機(jī)產(chǎn)生交配概率srand(unsigned)time(NULL);for (i = 0; inum; i+)jiaopeipi = (rand() % 100);jiaopeipi /= 100;/確定可以交配的染色體t = 0;for (i = 0; inum; i+)if

14、(jiaopeipipc)jiaopeiflagi = 1;t+;t = t / 2 * 2;/t必須為偶數(shù)/產(chǎn)生t/2個(gè)0-9交配斷點(diǎn)srand(unsigned)time(NULL);temp1 = 0;/temp1號(hào)染色體和temp2染色體交配for (i = 0; it / 2; i+)point1 = rand() % cities;point2 = rand() % cities;for (j = temp1; jnum; j+)if (jiaopeiflagj = 1)temp1 = j;break;for (j = temp1 + 1; jpoint2) /保證point1=p

15、oint2temp = point1;point1 = point2;point2 = temp;memset(map1, -1, sizeof(map1);memset(map2, -1, sizeof(map2);/斷點(diǎn)之間的基因產(chǎn)生映射for (k = point1; k = point2; k+)map1grouptemp1.cityk = grouptemp2.cityk;map2grouptemp2.cityk = grouptemp1.cityk;/斷點(diǎn)兩邊的基因互換for (k = 0; kpoint1; k+)temp = grouptemp1.cityk;grouptemp

16、1.cityk = grouptemp2.cityk;grouptemp2.cityk = temp;for (k = point2 + 1; kcities; k+)temp = grouptemp1.cityk;grouptemp1.cityk = grouptemp2.cityk;grouptemp2.cityk = temp;/處理產(chǎn)生的沖突基因for (k = 0; kpoint1; k+)for (kk = point1; kk = point2; kk+)if (grouptemp1.cityk = grouptemp1.citykk)grouptemp1.cityk = map

17、1grouptemp1.cityk;break;for (k = point2 + 1; kcities; k+)for (kk = point1; kk = point2; kk+)if (grouptemp1.cityk = grouptemp1.citykk)grouptemp1.cityk = map1grouptemp1.cityk;break;for (k = 0; kpoint1; k+)for (kk = point1; kk = point2; kk+)if (grouptemp2.cityk = grouptemp2.citykk)grouptemp2.cityk = ma

18、p2grouptemp2.cityk;break;for (k = point2 + 1; kcities; k+)for (kk = point1; kk = point2; kk+)if (grouptemp2.cityk = grouptemp2.citykk)grouptemp2.cityk = map2grouptemp2.cityk;break;temp1 = temp2 + 1;/變異void bianyi()int i, j;int t;int temp1, temp2, point;double bianyipnum; /染色體的變異概率int bianyiflagnum;/染色體的變異情況for (i = 0; inum; i+)/初始化bianyiflagi = 0;/隨機(jī)產(chǎn)生變異概率srand(unsigned)time(NULL);for (i = 0; inum; i+)bianyipi = (rand() % 100);bianyipi /= 100;/確定可以變異的染色體t = 0;for (i = 0; inum; i+)if (bianyipip