TSP問題求解實驗報告

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

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

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

4、四）實驗代碼#include"stdafx.h"#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#include <time.h>#definecities10 / 城市的個數(shù)#defineMAXX100 / 迭代次數(shù)#definepc 0.8 / 交配概率#definepm0.05/ 變異概率#definenum10 /種群的大小intbestsolution;/ 最優(yōu)染色體intdistancecities cit

5、ies ; / 城市之間的距離structgroup/染色體的結(jié)構(gòu)intcitycities ; / 城市的順序intadapt;/適應(yīng)度double p; / 在種群中的幸存概率groupnum, grouptemp num;/ 隨機產(chǎn)生 cities 個城市之間的相互距離void init()inti, j;memset(distance, 0,sizeof (distance);srand( unsigned )time(NULL);for (i = 0; i<cities; i+)for (j = i + 1; j<cities; j+)distanceij = rand(

6、) % 100;distanceji = distanceij;/ 打印距離矩陣printf(" 城市的距離矩陣如下n" );for (i = 0; i<cities; i+)for (j = 0; j<cities; j+)printf("%4d", distanceij);printf("n" );/ 隨機產(chǎn)生初試群void groupproduce()inti, j, t, k, flag;for (i = 0; i<num; i+)/ 初始化for (j = 0; j<cities; j+)groupi

7、.cityj = -1;srand( unsigned )time(NULL);for (i = 0; i<num; i+)/ 產(chǎn)生 10 個不相同的數(shù)字for (j = 0; j<cities;)t = rand() %flag = 1;cities;for (k = 0; k<j; k+)if(groupi.cityk = t)flag = 0;break ;if(flag)groupi.cityj = t;j+;/ 打印種群基因printf(" 初始的種群 n" );for (i = 0; i<num; i+)for (j = 0; j<

8、printf(cities; j+)"%4d", groupi.cityj);printf("n" );/ 評價函數(shù) , 找出最優(yōu)染色體void pingjia()inti, j;intn1, n2;intsumdistance, biggestsum = 0;double biggestp = 0;for (i = 0; i<num; i+)sumdistance = 0;for (j = 1; j<cities; j+)n1 = groupi.cityj - 1;n2 = groupi.cityj;sumdistance += dista

9、ncen1n2;groupi.adapt = sumdistance;/ 每條染色體的路徑總和biggestsum += sumdistance;/ 種群的總路徑/ 計算染色體的幸存能力 , 路勁越短生存概率越大for (i = 0; i<num; i+)groupi.p = 1 - ( double )groupi.adapt / ( biggestp += groupi.p;double )biggestsum;for (i = 0; i<num; i+)groupi.p = groupi.p / biggestp;/ 在種群中的幸存概率, 總和為1/ 求最佳路勁bestsol

10、ution = 0;for (i = 0; i<num; i+)if(groupi.p>groupbestsolution.p)bestsolution = i;/ 打印適應(yīng)度for (i = 0; i<num; i+)printf(" 染色體 %d的路徑之和與生存概率分別為%4d %.4fn", i, groupi.adapt,groupi.p);printf(" 當前種群的最優(yōu)染色體是%d號染色體n" , bestsolution);/ 選擇void xuanze()inti, j, temp;double gradientnum;

11、 / 梯度概率double xuanze num; / 選擇染色體的隨機概率intxuan num; / 選擇了的染色體/ 初始化梯度概率for (i = 0; i<num; i+)gradienti = 0.0;xuanzei = 0.0;gradient0 = group0.p;for (i = 1; i<num; i+)gradienti = gradienti - 1 + groupi.p;srand( unsigned )time(NULL);/ 隨機產(chǎn)生染色體的存活概率for (i = 0; i<num; i+)xuanzei = (rand() % 100);x

12、uanzei /= 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+)grouptempi.adapt = groupi.adapt;grouptempi.p = groupi.p;for (j = 0; j<cities; j+)grouptempi.cityj = groupi.cityj;/ 數(shù)據(jù)更新for (i = 0; i&l

13、t;num; i+)temp = xuani;groupi.adapt = grouptemptemp.adapt;groupi.p = grouptemptemp.p;for (j = 0; j<cities; j+)groupi.cityj = grouptemptemp.cityj;/ 用于測試printf("<->n");for (i=0;i<num;i+)for (j=0;j<cities ;j+)printf("%4d",groupi.cityj);printf("n" );printf(&q

14、uot; 染色體 %d的路徑之和與生存概率分別為%4d %.4fn" ,i,groupi.adapt,groupi.p);/ 交配 , 對每個染色體產(chǎn)生交配概率 , 滿足交配率的染色體進行交配voidjiaopei()inti, j, k, kk;intt; / 參與交配的染色體的個數(shù)intpoint1, point2, temp;/ 交配斷點intpointnum;inttemp1, temp2;intmap1 cities, map2 cities ;double jiaopeipnum;/ 染色體的交配概率intjiaopeiflagnum;/ 染色體的可交配情況for (i

15、= 0; i<num; i+)/ 初始化jiaopeiflagi = 0;/ 隨機產(chǎn)生交配概率srand( unsigned )time(NULL);for (i = 0; i<num; i+)jiaopeipi = (rand() % 100);jiaopeipi /= 100;/ 確定可以交配的染色體t = 0;for (i = 0; i<num; i+)if(jiaopeipi<pc)jiaopeiflagi = 1;t+;t = t / 2 * 2;/t必須為偶數(shù)/ 產(chǎn)生 t/2 個 0-9 交配斷點srand( unsigned )time(NULL);tem

16、p1 = 0;/temp1 號染色體和temp2 染色體交配for (i = 0; i<t / 2; i+)point1 = rand() %point2 = rand() %for (j = temp1; j<if(jiaopeiflagj = 1)cities;cities;num; j+)temp1 = j;break ;for (j = temp1 + 1; j<if(jiaopeiflagj = 1)num; j+)temp2 = j;break ;/ 進行基因交配if(point1>point2)/ 保證point1<=point2temp = poi

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

18、yk = grouptemp2.cityk;grouptemp2.cityk = temp;for (k = point2 + 1; k<cities; k+)temp = grouptemp1.cityk;grouptemp1.cityk = grouptemp2.cityk;grouptemp2.cityk = temp;/ 處理產(chǎn)生的沖突基因for (k = 0; k<point1; k+)for (kk = point1; kk <= point2; kk+)if(grouptemp1.cityk = grouptemp1.citykk)grouptemp1.city

19、k = map1grouptemp1.cityk;break ;for (k = point2 + 1; k<cities; k+)for (kk = point1; kk <= point2; kk+)if(grouptemp1.cityk = grouptemp1.citykk)grouptemp1.cityk = map1grouptemp1.cityk;break ;for (k = 0; k<point1; k+)for (kk = point1; kk <= point2; kk+)if(grouptemp2.cityk = grouptemp2.cityk

20、k)grouptemp2.cityk = map2grouptemp2.cityk;break ;for (k = point2 + 1; k<cities; k+)for (kk = point1; kk <= point2; kk+)if(grouptemp2.cityk = grouptemp2.citykk)grouptemp2.cityk = map2grouptemp2.cityk;break ;temp1 = temp2 + 1;/ 變異void bianyi()inti, j;intt;inttemp1, temp2, point;double bianyipnum;/ 染色體的變異概率intbianyiflagnum; /染色體的變異情況for (i = 0; i<num; i+)/ 初始化bianyiflagi = 0;/ 隨機產(chǎn)生變異概率srand( unsigned )time(NULL);for (i = 0; i<num; i+)bianyipi = (rand() % 100);bianyipi /= 100;/ 確定可以變異的染色體t = 0;for (i = 0; i<num; i+)if(bianyipi<pm)bianyiflagi