TSP问题求解实验报告(共13页)

1、TSP问题求解（1） 实验目的熟悉和掌握遗传算法的原理，流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。（2） 实验原理巡回旅行商问题给定一组n个城市和俩俩之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。TSP问题也称为货郎担问题，是一个古老的问题。最早可以追溯到1759年Euler提出的骑士旅行的问题。1948年，由美国兰德公司推动，TSP成为近代组合优化领域的典型难题。TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题。 近年来，有很多解决该问题的较为有效的算法不断被推出，例如Hopfield神经网络方

2、法，模拟退火方法以及遗传算法方法等。TSP搜索空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!/2。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多计算困难。借助遗传算法的搜索能力解决TSP问题，是很自然的想法。基本遗传算法可定义为一个8元组：（SGA）=（C，E，P0，M，）C 个体的编码方法，SGA使用固定长度二进制符号串编码方法；E 个体的适应度评价函数；P0初始群体；M 群体大小，一般取20100；选择算子，SGA使用比例算子；交叉算子，SGA使用单点交叉算子；变异算子，SGA使用基本位变异算子；算法终止条件，一般终止进化代数为100500

3、；问题的表示 对于一个实际的待优化问题，首先需要将其表示为适合于遗传算法操作的形式。用遗传算法解决TSP，一个旅程很自然的表示为n个城市的排列，但基于二进制编码的交叉和变异操作不能适用。路径表示是表示旅程对应的基因编码的最自然，最简单的表示方法。它在编码，解码，存储过程中相对容易理解和实现。例如：旅程（5-1-7-8-9-4-6-2-3）可以直接表示为（5 1 7 8 9 4 6 2 3） （三）实验内容N=8。随即生成N个城市间的连接矩阵。指定起始城市。给出每一代的最优路线和总路线长度。以代数T作为结束条件，T=50。（4） 实验代码#include stdafx.h#include#inc

4、lude#include#include#include#define cities 10 /城市的个数#define MAXX 100/迭代次数#define pc 0.8 /交配概率#define pm 0.05 /变异概率#define num 10/种群的大小int bestsolution;/最优染色体int distancecitiescities;/城市之间的距离struct group /染色体的结构int citycities;/城市的顺序int adapt;/适应度double p;/在种群中的幸存概率groupnum, grouptempnum;/随机产生cities个城

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、;/随机产生初试群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+)/产生10个不相同的数字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);/评价函数,找出最优染色体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; /种群的总路径/计算染色体的幸存能力,路劲越短生存概率越大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;/打印适应度for (i = 0; inum; i+)printf(染色体%d的路径之和与生存概率分别为%4d %.4fn, i, groupi.adapt, groupi.p);printf(当前种群的最优染色体是%d号染色体n, bestsolution);/选择void xuanze()int i, j, temp;double gradientnum;/梯度概率double xuanzenum;/选择染色体的随机概率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);/随机产生染色体的存活概率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个位置存放第j个染色体break;/拷贝种群for (i = 0; inum; i+)grouptempi.adapt = groupi.adapt;grouptempi.p = groupi.p;for (j = 0; jcities; j+)grouptempi.cityj = groupi.cityj;/数据更新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;/用于测试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);/交配,对每个染色体产生交配概率,满足交配率的染色体进行交配void jiaopei()int i, j, k, kk;int t;/参与交配的染色体的个数int point1, point2, temp;/交

13、配断点int pointnum;int temp1, temp2;int map1cities, map2cities;double jiaopeipnum;/染色体的交配概率int jiaopeiflagnum;/染色体的可交配情况for (i = 0; inum; i+)/初始化jiaopeiflagi = 0;/随机产生交配概率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必须为偶数/产生t/2个0-9交配断点srand(unsigned)time(NULL);temp1 = 0;/temp1号染色体和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);/断点之间的基因产生映射for (k = point1; k = point2; k+)map1grouptemp1.cityk = grouptemp2.cityk;map2grouptemp2.cityk = grouptemp1.cityk;/断点两边的基因互换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;/处理产生的冲突基因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;/随机产生变异概率srand(unsigned)time(NULL);for (i = 0; inum; i+)bianyipi = (rand() % 100);bianyipi /= 100;/确定可以变异的染色体t = 0;for (i = 0; inum; i+)if (bianyipip