TSP问题求解实验报告

更新时间：2023-10-24 23:48:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

tsp问题求解方法推荐度：
相关推荐

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 \ #include #include #include #include #include

#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; i

//打印距离矩阵

for (j = i + 1; j

distance[i][j] = rand() % 100; distance[j][i] = distance[i][j];

}

printf(\城市的距离矩阵如下\\n\); for (i = 0; i

for (j = 0; j

printf(\, distance[i][j]); printf(\);

//随机产生初试群 void groupproduce() {

int i, j, t, k, flag;

for (i = 0; i

group[i].city[j] = -1; srand((unsigned)time(NULL)); for (i = 0; i

//打印种群基因

printf(\初始的种群\\n\); for (i = 0; i

for (j = 0; j

printf(\, group[i].city[j]); //产生10个不相同的数字 for (j = 0; j

t = rand() % cities; flag = 1;

for (k = 0; k

if (flag) { }

group[i].city[j] = t; j++;

if (group[i].city[k] == t) { }

flag = 0; break;

}

printf(\);

//评价函数,找出最优染色体 void pingjia() { } //选择 void xuanze() {

int i, j; int n1, n2;

int sumdistance, biggestsum = 0; double biggestp = 0; for (i = 0; i

//计算染色体的幸存能力,路劲越短生存概率越大 for (i = 0; i

for (i = 0; i

group[i].p = group[i].p / biggestp; //在种群中的幸存概率,总和为1 //求最佳路劲 bestsolution = 0; for (i = 0; i

if (group[i].p>group[bestsolution].p)

bestsolution = i; //打印适应度

for (i = 0; i

printf(\染色体%d的路径之和与生存概率分别为M %.4f\\n\, i, group[i].adapt, group[i].p = 1 - (double)group[i].adapt / (double)biggestsum; biggestp += group[i].p; sumdistance = 0;

for (j = 1; j

group[i].adapt = sumdistance; //每条染色体的路径总和 biggestsum += sumdistance; //种群的总路径

n1 = group[i].city[j - 1]; n2 = group[i].city[j];

sumdistance += distance[n1][n2];

group[i].p);

printf(\当前种群的最优染色体是%d号染色体\\n\, bestsolution);

int i, j, temp;

double gradient[num];//梯度概率

double xuanze[num];//选择染色体的随机概率 int xuan[num];//选择了的染色体 //初始化梯度概率 for (i = 0; i

gradient[0] = group[0].p; for (i = 1; i

gradient[i] = gradient[i - 1] + group[i].p; srand((unsigned)time(NULL)); //随机产生染色体的存活概率 for (i = 0; i

//选择能生存的染色体 for (i = 0; i

//拷贝种群

for (i = 0; i

//数据更新

for (i = 0; i

temp = xuan[i];

grouptemp[i].adapt = group[i].adapt; grouptemp[i].p = group[i].p; for (j = 0; j

grouptemp[i].city[j] = group[i].city[j]; for (j = 0; j

if (xuanze[i]

xuan[i] = j; //第i个位置存放第j个染色体 break;

xuanze[i] = (rand() % 100); xuanze[i] /= 100; gradient[i] = 0.0; xuanze[i] = 0.0;

}

group[i].adapt = grouptemp[temp].adapt; group[i].p = grouptemp[temp].p; for (j = 0; j

group[i].city[j] = grouptemp[temp].city[j];

//用于测试

printf(\); for(i=0;i

for(j=0;j

printf(\,group[i].city[j]); printf(\);

printf(\染色体%d的路径之和与生存概率分别}

为M %.4f\\n\,i,group[i].adapt,group[i].p);

//交配,对每个染色体产生交配概率,满足交配率的染色体进行交配 void jiaopei() {

int i, j, k, kk;

int t;//参与交配的染色体的个数 int point1, point2, temp;//交配断点 int pointnum; int temp1, temp2;

int map1[cities], map2[cities];

double jiaopeip[num];//染色体的交配概率 int jiaopeiflag[num];//染色体的可交配情况 for (i = 0; i

jiaopeiflag[i] = 0; //随机产生交配概率

srand((unsigned)time(NULL)); for (i = 0; i

//确定可以交配的染色体 t = 0;

for (i = 0; i

if (jiaopeip[i]

jiaopeiflag[i] = 1; jiaopeip[i] = (rand() % 100); jiaopeip[i] /= 100;

}

t++;

t = t / 2 * 2;//t必须为偶数 //产生t/2个0-9交配断点 srand((unsigned)time(NULL)); temp1 = 0;

//temp1号染色体和temp2染色体交配 for (i = 0; i

point1 = rand() % cities; point2 = rand() % cities; for (j = temp1; j

for (j = temp1 + 1; j

//进行基因交配

if (point1>point2) //保证point1<=point2 { }

memset(map1, -1, sizeof(map1)); memset(map2, -1, sizeof(map2)); //断点之间的基因产生映射

for (k = point1; k <= point2; k++) { }

//断点两边的基因互换 for (k = 0; k

temp = group[temp1].city[k];

group[temp1].city[k] = group[temp2].city[k]; map1[group[temp1].city[k]] = group[temp2].city[k]; map2[group[temp2].city[k]] = group[temp1].city[k]; temp = point1; point1 = point2; point2 = temp; temp2 = j; break; temp1 = j; break;

}

group[temp2].city[k] = temp;

for (k = point2 + 1; k

//处理产生的冲突基因 for (k = 0; k

for (k = point2 + 1; k

for (k = 0; k

for (k = point2 + 1; k

for (kk = point1; kk <= point2; kk++)

if (group[temp2].city[k] == group[temp2].city[kk]) { }

group[temp2].city[k] = map2[group[temp2].city[k]]; break;

for (kk = point1; kk <= point2; kk++)

if (group[temp2].city[k] == group[temp2].city[kk]) { }