tsp问题求解实验报告.docVIP

TSP问题求解 实验目的 熟悉和掌握遗传算法的原理，流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。 实验原理 巡回旅行商问题 给定一组n个城市和俩俩之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。 TSP问题也称为货郎担问题，是一个古老的问题。最早可以追溯到1759年Euler提出的骑士旅行的问题。1948年，由美国兰德公司推动，TSP成为近代组合优化领域的典型难题。 TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题。 近年来，有很多解决该问题的较为有效的算法不断被推出，例如Hopfield神经网络方法，模拟退火方法以及遗传算法方法等。 TSP有哪些信誉好的足球投注网站空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!/2。在如此庞大的有哪些信誉好的足球投注网站空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多计算困难。借助遗传算法的有哪些信誉好的足球投注网站能力解决TSP问题，是很自然的想法。 基本遗传算法可定义为一个8元组： （SGA）=（C，E，P0，M，Φ，Г，Ψ，Τ） C ——个体的编码方法，SGA使用固定长度二进制符号串编码方法； E ——个体的适应度评价函数； P0——初始群体； M ——群体大小，一般取20—100； Ф——选择算子，SGA使用比例算子； Г——交叉算子，SGA使用单点交叉算子； Ψ——变异算子，SGA使用基本位变异算子； Т——算法终止条件，一般终止进化代数为100—500； 问题的表示 对于一个实际的待优化问题，首先需要将其表示为适合于遗传算法操作的形式。用遗传算法解决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。 实验代码 #include stdafx.h #includestdio.h #includestring.h #includestdlib.h #includemath.h #includetime.h #define cities 10 //城市的个数 #define MAXX 100//迭代次数 #define pc 0.8 //交配概率 #define pm 0.05 //变异概率 #define num 10//种群的大小 int bestsolution;//最优染色体 int distance[cities][cities];//城市之间的距离 struct group //染色体的结构 { int city[cities];//城市的顺序 int adapt;//适应度 double p;//在种群中的幸存概率 }group[num], grouptemp[num]; //随机产生cities个城市之间的相互距离 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++) { distance[i][j] = rand() % 100; distance[j][i] = distance[i][j]; } } //打印距离矩阵 printf(城市的距离矩阵如下\n); for (i = 0; icities; i++) { for (j = 0; jcities; j++) printf(%4d, distance[i][j]); printf(\n); } } //随机产生初试群 void groupproduce() { int i, j, t, k, flag; for (i = 0; inum; i++) //初始化 for (j = 0; jcities; j++) group[i].city[j] = -1; srand((unsigned)time(NULL)); for (i = 0; inum; i++) { //产生10个不相同的数字 for (j = 0; jcities;) { t = rand() % cities; flag = 1; for