📄 tsp.cpp
字号:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define popsize 150 //种群大小
#define lchrom 15 //染色体的维数(即城市的个数)
#define termgen 5000 //进化终止代数
///////***** 全局变量的定义 *****///////
//////*****************************///////
struct individual //定义个体+
{ unsigned chrom[lchrom]; //一条旅程（城市序列）
double fitness; //个体适应度（即旅程距离）
};
struct //最优个体
{ unsigned chrom[lchrom]; //最优个体的染色体
double bestfitness; //最优个体适应度（即旅程距离的倒数）
int generation; //最优个体生成代
}bestvidual;
double shortdis;//最短距离
struct individual pop[popsize]; //定义种群
struct individual tempop[popsize]; //选择、交叉操作时，用于临时存储种群
/*///20个城市
double x[lchrom]={5.294,4.286,4.719,4.185,0.915,4.771,1.524,3.447,3.718,2.649,
4.399,4.660,1.232,5.036,2.710,1.072,5.855,0.194,1.762,2.682};
double y[lchrom]={1.558,3.622,2.774,2.230,3.821,6.041,2.871,2.111,3.665,2.556,
1.194,2.949,6.440,0.244,3.140,3.454,6.203,1.862,2.693,6.097};
*////
///15个城市
double x[lchrom]={5.294,4.286,4.719,4.185,0.915,4.771,1.524,3.447,3.718,2.649,
4.399,4.660,1.232,5.036,2.710};
double y[lchrom]={1.558,3.622,2.774,2.230,3.821,6.041,2.871,2.111,3.665,2.556,
1.194,2.949,6.440,0.244,3.140};
///////
double dis[lchrom][lchrom];//任意两个城市间的距离(dis[i][j]表示城市[i]到城市[j]的距离)
double sumfitness; //当前种群中个体适应度累计（总适应度）
double avgfitness; //当前种群的平均适应度
double maxfitness; //当前种群的最大适应度
int cur_generation=0; //当前世代数
unsigned portion=80; //均匀分布表在种群中占的百分比
float pc=0.65; //交叉率
float pm=0.03; //变异率
FILE *fp;
/////////////////////////////////////////////////////////////////
////计算任意两个城市间的距离，存放在数组dis[lchrom][lchrom]中////
/////////////////////////////////////////////////////////////////
void dis_two()
{ int i,j;
for(i=0; i<lchrom-1; i++)
{ dis[i][i]=0.0;
for(j=i+1; j<lchrom; j++)
{ dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
dis[j][i]=dis[i][j];
}
}
dis[lchrom-1][lchrom-1]=0.0;
}
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
//// 求种群中每个个体的适应度fitness（即一条旅程的距离的倒数）//
////////////////////////////////////////////////////////////////
void fit()
{ int i,j;
for(i=0;i<popsize;i++)
{ pop[i].fitness=0.0;
for(j=0;j<lchrom-1;j++)
pop[i].fitness+=dis[pop[i].chrom[j]][pop[i].chrom[j+1]];
pop[i].fitness=1/(pop[i].fitness+dis[pop[i].chrom[lchrom-1]][pop[i].chrom[0]]);//回路
//pop[i].fitness=1/pop[i].fitness; //不回路
}
}
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
/////////////// 随机生成初始种群 ////////////
////////////////////////////////////////////////////////////////
//均匀分布表法
void inipop_table()
{ int table[lchrom][lchrom]
={
/* {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19},
{0,2,4,6,8,10,12,14,16,18,1,3,5,7,9,11,13,15,17,19},
{0,3,6,9,12,15,18,1,4,7,10,13,16,19,2,5,8,11,14,17},
{0,4,8,12,16,1,5,9,13,17,2,6,10,14,18,3,7,11,19,15},
{0,5,10,15,2,7,12,17,4,9,14,19,1,6,11,16,3,8,13,18},
{0,6,12,18,1,7,13,19,2,8,14,3,9,15,4,10,16,5,11,17},
{0,7,14,5,12,19,3,10,17,1,8,15,6,13,4,11,18,2,9,16},
{0,8,16,1,9,17,2,10,18,3,11,19,4,12,5,13,6,14,7,15},
{0,9,18,4,13,8,17,3,12,7,16,2,11,6,15,1,10,19,5,14},
{0,10,7,17,4,14,1,11,8,18,5,15,2,12,9,19,6,16,3,13},
{0,11,10,9,8,19,7,18,6,17,5,16,4,15,3,14,2,13,1,12},
{0,12,1,13,2,14,3,15,4,16,5,17,6,18,7,19,8,9,10,11},
{0,13,3,16,6,19,9,12,2,15,5,18,8,11,1,14,4,17,7,10},
{0,14,5,19,10,1,15,6,11,2,16,7,12,3,17,8,13,4,18,9},
{0,15,7,14,6,13,5,12,4,19,11,3,18,10,2,17,9,1,16,8},
{0,16,9,2,18,11,4,13,6,15,8,1,17,10,3,19,12,5,14,7},
{0,17,11,5,16,10,4,15,9,3,14,8,2,19,13,7,1,18,12,6},
{0,18,13,8,3,16,11,6,1,19,14,9,4,17,12,7,2,15,10,5},
{0,19,15,11,7,13,18,14,10,6,2,17,3,9,5,1,16,12,8,4},
{0,17,14,11,8,5,2,19,16,13,10,7,4,1,18,15,12,9,6,3},
}; //均匀分布表 */
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14},
{0,2,4,6,8,10,12,14,1,3,5,7,9,11,13},
{0,3,6,9,12,1,4,7,10,13,2,5,8,11,14},
{0,4,8,12,3,7,11,2,6,10,14,1,5,9,13},
{0,5,10,3,8,13,1,6,11,4,9,14,2,7,12},
{0,6,12,1,7,13,2,8,14,3,9,4,10,5,11},
{0,7,14,4,11,1,8,5,12,2,9,6,13,3,10},
{0,8,7,6,14,5,13,4,12,3,11,2,10,1,9},
{0,9,1,10,2,11,3,12,4,13,5,14,6,7,8},
{0,10,3,13,6,9,2,12,5,8,1,11,4,14,7},
{0,11,5,10,4,9,3,14,8,2,13,7,1,12,6},
{0,12,7,2,14,9,4,11,6,1,13,8,3,10,5},
{0,13,9,5,1,14,10,6,2,11,7,3,12,8,4},
{0,14,11,8,5,2,13,10,7,4,1,12,9,6,3},
{0,13,11,9,7,5,3,1,14,12,10,8,6,4,2}};
int num,tablenum; //num:由均匀分布表生成的个体数
bool mask[lchrom]; //mask[i]=0表示城市i还未产生过；mask[i]=1表示城市i还已产生
int randnum[lchrom]; //存放生成的随机数
int i,j,r,n,t;
void delete_repeat();
// printf("请输入均匀分布表在种群中占的百分比(0,20,40,60,80,100)：");
//scanf("%d",&portion);
// printf("\n");
for (n=0;n<popsize;n++) //约定旅程起点为0号城市
pop[n].chrom[0]=0;
mask[0]=1; //起点城市0是固定的
num=popsize*portion/100;
tablenum=num/lchrom;
if(tablenum) //将种群的前lchrom个个体赋值为均匀分布表
{ for(i=0;i<lchrom;i++)
for(j=1;j<lchrom;j++)
pop[i].chrom[j]=table[i][j];
}
//由均匀分布表生成num个个体
srand((unsigned)time(NULL)); //每次执行输出的结果不一样
for(i=1;i<tablenum;i++)//生成tablenum-1个不同的随机序列(每个序列19个数),完成由均匀分布表生成的个体
{ for(j=1;j<lchrom;j++)
mask[j]=0;
for(j=1;j<lchrom;j++) //生成19个不同数(旅程起点0固定)构成一个随机序列
{ r=rand()%lchrom;
while(mask[r])
r=rand()%lchrom;
mask[r]=1;
randnum[j]=r;
}
//lchrom个个体一组,即i循环一次就生成lchrom个个体
int m;
m=lchrom*i;
for(j=0;j<lchrom;j++) //先将整个均匀变化表整个的复制过去
for(n=0;n<lchrom;n++)
pop[m+j].chrom[n]=table[j][n];
for(j=1;j<lchrom;j++) //从取随机数randnum[j]，将均匀变化表中值为j的位置替换成randnum[j]
{ //第一列城市0是固定的，故j从1开始
for(n=0;n<lchrom;n++)//取一次数遍历一次均匀变化表(即每次要遍历lchrom个个体)
for(t=1;t<lchrom;t++)
if(j==table[n][t])
{pop[m+n].chrom[t]=randnum[j]; break;}
}
}
//随机生成剩余的popsize-num个个体
for (n=num;n<popsize;n++)
{ for (i=1;i<lchrom;i++) //将数组初始化为0，当产生的随机数等于数组下标后，将此数组对应的值变为1.
mask[i]=0;
for (i=1;i<lchrom;i++) //随机产生19个不同的随机数，与起点城市0共同代表一条旅程;
{ j=rand()%lchrom;
while(mask[j])
j=rand()%lchrom;
mask[j]=1;
pop[n].chrom[i]=j;
}
}//至此，最初的popsize个初始种群完全生成
fit(); //计算适应度
delete_repeat();
}
///////////////////////////////////////////////
//判断种群中是否有相同的个体，若有，则删除相同的而再产生新的个体；直至种群中的个体各不相同
void delete_repeat()
{ bool same; //same=1说明有相同的；same=0则没有相同的
bool mask[lchrom]; ////mask[i]=0表示城市i还未产生过；mask[i]=1表示城市i还已产生
int i,j,r,m;
mask[0]=1; //旅程的起点城市0是固定的
for(i=1;i<popsize;i++)
{ do
{ same=0;
for(j=0;j<i;j++) //pop[i]与其前的(i-1)个个体进行比较看是否有相同的
{ if(pop[i].fitness==pop[j].fitness)
{ same=1;
for(m=1;m<lchrom;m++)
if(pop[i].chrom[m]!=pop[j].chrom[m])
{ same=0; break;}
}
if(same) //若有相同的，则重新产生个体,退出此次j循环的比较
{ //以下重新产生个体
pop[i].fitness=0;
for (m=1;m<lchrom;m++) //将数组初始化为0，当产生的随机数等于数组下标后，将此数组对应的值变为1.
mask[m]=0;
for (m=1;m<lchrom;m++) //随机产生19个不同的随机数，与起点城市0共同代表一条旅程;
{ r=rand()%lchrom;
while(mask[r])
r=rand()%lchrom;
mask[r]=1;
pop[i].chrom[m]=r;
pop[i].fitness+=dis[pop[i].chrom[m-1]][pop[i].chrom[m]]; //不回路
}
pop[i].fitness=1/pop[i].fitness;
break; //退出此次j循环的比较
}
}
}while(same);
}
}
void inipop()
{ bool mask[lchrom]; //标志数组，以保证产生的19个随机数不重复
int counter; //计数器，用来控制产生300个不同的个体
int i,j,m,n;
for (n=0;n<popsize;n++) //约定旅程起点为0号城市
pop[n].chrom[0]=0;
mask[0]=1;
srand((unsigned)time(NULL));
for (i=1;i<lchrom;i++) //将数组初始化为0，当产生的随机数等于数组下标后，将此数组对应的值变为1.
mask[i]=0;
for (i=1;i<lchrom;i++) //随机产生19个不同的随机数，此序列代表一条旅程;
{ j=rand()%lchrom;
while(mask[j])
j=rand()%lchrom;
mask[j]=1;
for (n=0;n<popsize;n++) //将300个个体赋相同的值
pop[n].chrom[i]=j;
}
counter=1;
while(counter<popsize) //随机产生要交换的位置号，产生不同的个体
{
mask[0]=0; //上述产生19个不同的随机数后，mask的值均变成了1；在此，再
mask[1]=0; //次利用它产生不同的随机数。mask[i]的值为0说明i已产生过。
j=rand()%lchrom;
while(mask[j]==0)
j=rand()%lchrom;
mask[j]=0;
if(j>=17)
{ for(i=1;i<=10;i++)
for(m=i+1;m+1<j-4 ;m=m+2)
{ pop[counter].chrom[i]=pop[0].chrom[j];
pop[counter].chrom[j]=pop[0].chrom[i];
pop[counter].chrom[j-2]=pop[0].chrom[m];
pop[counter].chrom[m]=pop[0].chrom[j-2];
pop[counter].chrom[j-4]=pop[0].chrom[m+1];
pop[counter].chrom[m+1]=pop[0].chrom[j-4];
counter++;
if(counter==popsize) break;
}
if(counter==popsize) break;
}
else
{
for(i=1;i<j;i++)
{
for(m=i+j,n=lchrom-1; (m<18)&&(m<n);m++,n--)
{ pop[counter].chrom[i]=pop[0].chrom[j];
pop[counter].chrom[j]=pop[0].chrom[i];
pop[counter].chrom[n]=pop[0].chrom[m];
pop[counter].chrom[m]=pop[0].chrom[n];
pop[0].chrom[m+1]=pop[counter].chrom[m+1];
pop[counter].chrom[m+1]=pop[counter].chrom[m+2];
pop[counter].chrom[m+2]=pop[0].chrom[m+1];
counter++;
if(counter==popsize) break;
}
if(counter==popsize) break;
}
}
}
/////////////////////
// 直接循环产生
/*for (n=0;n<popsize;n++)
{ do
{ for (i=1;i<lchrom;i++) //将数组初始化为0，当产生的随机数等于数组下标后，将此数组对应的值变为1.
mask[i]=0;
for (i=1;i<lchrom;i++) //随机产生19个不同的随机数，此序列代表一条旅程;
{ j=rand()%lchrom;
while(mask[j])
j=rand()%lchrom;
mask[j]=1;
pop[n].chrom[i]=j;
}
for (j=0;j<n;j++) //确保刚生成的个体n与以前所有的个体均不同
{ same=1;
for(i=1;i<lchrom;i++)
if(pop[n].chrom[i]!=pop[j].chrom[i])
{ same=0; break;}
if(same) break; //若有相同的，则退出比较重新产生个体
}
}while(same)
}
*/
fit(); //计算适应度
////////////////////
/* fprintf(fp,"随机生成的初始种群为：\n");
for (i=0;i<popsize;i++) //输出初始种群
{for (j=0;j<lchrom;j++)
fprintf(fp,"%d ",pop[i].chrom[j]);
fprintf(fp,"\n");
}*/
}
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////***** 求当前种群的总适应度sumfitness *****//////////
////////***** 及平均适应度avgfitness *****//////////
//////***** 及最优个体bestvidual的染色体和适应度 ******/////
////////////////////////////////////////////////////////////////
void sum_avgfit(struct individual population[popsize])
{ int i,j;
sumfitness=0;
for(i=0;i<popsize;i++)
{ sumfitness+=population[i].fitness; //总适应度
if(population[i].fitness>bestvidual.bestfitness) //求最优个体
{ bestvidual.generation=cur_generation;
bestvidual.bestfitness=population[i].fitness;
for(j=0;j<lchrom;j++)
bestvidual.chrom[j]=population[i].chrom[j];
}
}
avgfitness=sumfitness/popsize; //平均适应度
///(测试)
// fprintf(fp,"\n总适应度为:%f; 平均适应度为：%f\n",sumfitness,avgfitness);
///
}
////////////////////////////////////////////////////////////////
///////**** 选择操作（轮盘赌方法）select() ***/////////
///////**** 选择后的个体转移到了种群tempop中 ***/////////
////////////////////////////////////////////////////////////////
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -