📄 tsp.cpp
字号:
// TSP.cpp : Defines the entry point for the console application.
/************************************************************************
旅行商(TSP)问题的遗传算法求解
染色体编码方法采用Grefenstette在《Genetic Algorithms for the Traveling Salesman Problem》
提出的编码方法。访问完一个城市，就从城市列表中去掉该城市。
例：假设有三个城市(A,B,C)，染色体编码为(2,2,1)，第一次城市列表为(A,B,C),
2表示访问(A,B,C)中第2个城市B；然后城市列表变为(A,C)，第二次访问2表示(A,C)
中的第2个城市C；第三次访问城市列表中只有一个城市A；访问城市序列为B->C->A。
同理(3,1,2)表示访问序列为C->A-B，(1,2,1)表示访问序列为A->C->B。
作者：章舜仲，zszws@jlonline.com。(版权所有)
************************************************************************/
#include "stdafx.h"
#include "stdlib.h"
#include "time.h"
#include <conio.h>
#define POPSIZE 1000
#define CITYCOUNT 30 /*城市个数*/
#define CHROMLENGTH CITYCOUNT /*染色体长度即城市个数*/
int PopSize=900; //种群规模
int MaxGeneration=800; //进化代数
double Pc=0.8; //交叉概率
double Pm=0.08; //变异概率
int CitySet[CITYCOUNT]; /*城市集合*/
int WorkSet[CITYCOUNT]; /*染色体解码时的临时工作数组，存放还未访问的城市序列*/
int TempCitySet[CITYCOUNT]; /*存放染色体解码完成后所经过的城市序列*/
/************************************************************************
城市之间的距离矩阵，本例中出发城市固定，来回相等
城市矩阵使用网页getCityMartix.htm产生。
************************************************************************/
int CityDistance[CITYCOUNT][CITYCOUNT]={
{0,170,92,37,205,167,222,158,221,131,138,76,36,85,234,232,102,149,233,157,63,211,202,58,35,217,97,105,33,195},
{170,0,131,133,85,65,113,15,60,48,51,114,206,85,68,80,69,29,68,35,130,41,58,138,204,60,104,90,170,26},
{92,131,0,75,199,164,225,116,190,83,129,112,114,67,198,209,74,102,198,102,114,166,183,35,112,190,125,40,118,156},
{37,133,75,0,171,134,191,122,185,96,103,49,73,49,198,196,66,113,196,122,43,175,167,44,71,181,69,75,46,158},
{205,85,199,171,0,38,29,96,57,122,72,130,240,137,72,43,126,109,68,118,146,89,32,194,240,48,110,161,190,75},
{167,65,164,134,38,0,61,72,69,92,35,93,203,100,86,69,90,82,83,94,110,87,42,157,202,62,74,127,154,68},
{222,113,225,191,29,61,0,124,80,150,96,146,257,160,94,60,151,137,90,147,161,116,59,217,256,72,125,188,204,103},
{158,15,116,122,96,72,124,0,74,34,50,107,194,73,82,94,57,14,82,23,122,53,71,124,192,74,98,76,160,40},
{221,60,190,185,57,69,80,74,0,108,84,155,257,140,17,25,125,89,13,92,172,39,28,196,256,9,138,150,215,36},
{131,48,83,96,122,92,150,34,108,0,60,93,165,47,116,127,31,20,116,26,106,85,102,92,163,107,91,42,138,74},
{138,51,129,103,72,35,96,50,84,60,0,70,175,65,99,93,55,55,97,69,87,86,64,123,173,79,56,93,130,67},
{76,114,112,49,130,93,146,107,155,93,70,0,111,54,170,161,64,103,167,116,17,154,132,88,110,149,21,95,61,135},
{36,206,114,73,240,203,257,194,257,165,175,111,0,120,270,268,137,183,269,191,96,247,239,82,2,253,132,135,56,231},
{85,85,67,49,137,100,160,73,140,47,65,54,120,0,152,154,17,64,150,73,63,126,126,58,119,137,61,41,91,111},
{234,68,198,198,72,86,94,82,17,116,99,170,270,152,0,34,136,96,4,97,187,37,45,206,269,25,154,158,229,42},
{232,80,209,196,43,69,60,94,25,127,93,161,268,154,34,0,140,109,30,114,178,64,29,211,267,21,143,169,222,59},
{102,69,74,66,126,90,151,57,125,31,55,64,137,17,136,140,0,47,135,57,76,110,113,71,135,123,66,39,107,95},
{149,29,102,113,109,82,137,14,89,20,55,103,183,64,96,109,47,0,96,14,118,65,85,112,182,89,98,62,153,54},
{233,68,198,196,68,83,90,82,13,116,97,167,269,150,4,30,135,96,0,98,184,38,41,205,267,21,151,158,227,42},
{157,35,102,122,118,94,147,23,92,26,69,116,191,73,97,114,57,14,98,0,130,64,93,116,189,93,111,63,164,56},
{63,130,114,43,146,110,161,122,172,106,87,17,96,63,187,178,76,118,184,130,0,171,149,85,96,166,36,102,44,152},
{211,41,166,175,89,87,116,53,39,85,86,154,247,126,37,64,110,65,38,64,171,0,57,177,245,45,142,126,211,20},
{202,58,183,167,32,42,59,71,28,102,64,132,239,126,45,29,113,85,41,93,149,57,0,183,238,20,114,143,193,44},
{58,138,35,44,194,157,217,124,196,92,123,88,82,58,206,211,71,112,205,116,85,177,183,0,80,193,105,55,83,164},
{35,204,112,71,240,202,256,192,256,163,173,110,2,119,269,267,135,182,267,189,96,245,238,80,0,252,131,133,56,229},
{217,60,190,181,48,62,72,74,9,107,79,149,253,137,25,21,123,89,21,93,166,45,20,193,252,0,132,150,209,38},
{97,104,125,69,110,74,125,98,138,91,56,21,132,61,154,143,66,98,151,111,36,142,114,105,131,132,0,102,80,122},
{105,90,40,75,161,127,188,76,150,42,93,95,135,41,158,169,39,62,158,63,102,126,143,55,133,150,102,0,121,116},
{33,170,118,46,190,154,204,160,215,138,130,61,56,91,229,222,107,153,227,164,44,211,193,83,56,209,80,121,0,193},
{195,26,156,158,75,68,103,40,36,74,67,135,231,111,42,59,95,54,42,56,152,20,44,164,229,38,122,116,193,0},
};
struct individual /*定义个体*/
{
int chrom[CHROMLENGTH]; //染色体编码
double value; //value值表示路径长度
double fitness; //适应度
};
int generation;
struct individual bestindividual; /*某一代群体中最优个体，*/
struct individual currentbest; /*到目前为止的最优个体*/
struct individual population[POPSIZE];
void GenerateInitialPopulation(); /* 初始化群体*/
void GenerateNextPopulation(); /* 生成下一代群体 */
void DecodeChromosome(int *chrom,int *Result); /*解码染色体Chrom，存于Result中 */
void DeleteOneCity(int *workset,int pos,int n); /* 从城市序列中删去一个体 */
void FindBestIndividual(); /* 寻找最优个体 */
void Select(int start,int stop,struct individual *newpopulation);
void SelectionOperator(); /* 选择算子 */
void CrossoverOperator(); /* 交叉算子 */
void MutationOperator(); /* 变异算子 */
void OutputTextReport(); /* 输出结果 */
void CalculateFitness(); /* 计算适应度 */
/* 选择算子 */
void Select(int start,int stop,struct individual *newpopulation)
{
int i,index;
double p,sum=0.0;
double cfitness[POPSIZE];
for(i=start;i<stop;i++)
{
sum+=population[i].fitness;
}
for(i=start;i<stop;i++)
{
cfitness[i]=population[i].fitness/sum;
}
for(i=start+1;i<stop;i++)
{
cfitness[i]=cfitness[i-1]+cfitness[i];
}
for(i=start;i<stop;i++)
{
p=rand()%1000/1000.0;
index=0;
while(p>cfitness[index])
{
index++;
}
newpopulation[i]=population[index];
}
for(i=start;i<stop;i++)
{
population[i]=newpopulation[i];
}
}
void SelectionOperator(void)
{
struct individual newpopulation[POPSIZE];
int start,stop;
start=0;
stop=(int)(PopSize/3);
Select(start,stop,newpopulation);
start=stop+1;
stop=(int)(2*PopSize/3);
Select(start,stop,newpopulation);
start=stop+1;
stop=PopSize;
Select(start,stop,newpopulation);
}
int random(int randmax)
{
return rand()%randmax;
}
/* 交叉算子 */
void CrossoverOperator(void)
{
int i,j;
int index[POPSIZE];
int point,temp;
double p;
int CityNo;
for(i=0;i<PopSize;i++)
{
index[i]=i;
}
for(i=0;i<PopSize;i++)
{
point=random(PopSize-i);
temp=index[i];
index[i]=index[point+i];
index[point+i]=temp;
}
for(i=0;i<PopSize-1;i+=2)
{
p=rand()%1000/1000.0;
if(p<Pc)
{
point=random(CHROMLENGTH-1)+1;
for(j=point;j<CHROMLENGTH;j++)
{
CityNo=population[index[i]].chrom[j];
population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
population[index[i+1]].chrom[j]=CityNo;
}
}
}
}
/* 变异算子 */
void MutationOperator(void)
{
int i,j;
double p;
for(i=0;i<PopSize;i++)
{
for(j=1;j<CHROMLENGTH;j++) /* 染色体第一个元素为1，不能变异*/
{
p=rand()%1000/1000.0;
if(p<Pm)
{
population[i].chrom[j]=random(CITYCOUNT-j)+1;
}
}
}
}
/* 生成第一代群体*/
void GenerateInitialPopulation(void)
{
int i,j;
for(i=0;i<PopSize;i++)
{
CitySet[i]=i+1;
}
srand( (unsigned)time( NULL ) );
for(i=0;i<PopSize;i++)
{
population[i].chrom[0]=1; /*第一个城市是出发点，所以第一个元素为1 */
for(j=1;j<CITYCOUNT;j++)
population[i].chrom[j]=random(CITYCOUNT-j)+1;
}
}
/* 生成下一代群体 */
void GenerateNextPopulation(void)
{ SelectionOperator();
CrossoverOperator();
MutationOperator();
}
/* 从城市序列中删去一个体 */
void DeleteOneCity(int *workset,int pos,int n) /* 数组有n个元素，删去第pos个 */
{ int i;
for(i=pos-1;i<n-1;i++)
workset[i]=workset[i+1];
}
/*对染色体Chrom解码，结果在Result中 */
void DecodeChromosome(int *chrom,int *Result)
{ int *p; /* p指向即将访问的城市 */
int i,n;
p=chrom; /* 即将访问城市初值为染色体第一个元素 */
for(i=0;i<CITYCOUNT;i++) WorkSet[i]=CitySet[i]; /* 工作数组初始化 */
n=CITYCOUNT; /* n为未访问的城市个数 */
for(i=0;i<CITYCOUNT;i++)
{
Result[i]=WorkSet[*p-1]; /* 工作数组中第*p个元素是即将访问的城市 */
DeleteOneCity(WorkSet,*p,n); /* 从未访问的n个城市中删去刚访问的第*p个 */
n--; /* 未访问城市个数减1 */
p++; /* 即将访问城市指向下一个 */
}
}
/* 输出结果 */
void OutputTextReport(void)
{ int i;
DecodeChromosome(currentbest.chrom,TempCitySet);
printf("Generation=%d, Best Value=%f:\n",generation,currentbest.value);
printf("个体编码：");
for(i=0;i<CHROMLENGTH;i++)
printf("(%d)",currentbest.chrom[i]);
printf("\n访问顺序：");
for(i=0;i<CHROMLENGTH;i++)
printf("(%d)",TempCitySet[i]);
printf("\n\n");
}
/* 计算适应度 */
void CalculateFitness()
{ int i,j;
double TotalDistance=0.0;
for(i=0;i<PopSize;i++)
{
DecodeChromosome(population[i].chrom,TempCitySet);
for(j=1;j<CITYCOUNT;j++)
TotalDistance=TotalDistance
+CityDistance[TempCitySet[j-1]-1][TempCitySet[j]-1];
TotalDistance=TotalDistance+CityDistance[TempCitySet[CITYCOUNT-1]-1][0];
population[i].value=TotalDistance;
TotalDistance=0.0;
}
for(i=0;i<PopSize;i++)
{
population[i].fitness=CITYCOUNT/population[i].value;
}
}
/* 寻找最优个体 */
void FindBestIndividual(void)
{ int i;
bestindividual=population[0];
for(i=1;i<PopSize;i++)
{
if(population[i].fitness>bestindividual.fitness)
bestindividual=population[i];
}
if(generation==0)
{
currentbest=bestindividual;
}
else
{
if(bestindividual.fitness>currentbest.fitness)
{
currentbest=bestindividual;
OutputTextReport(); /* 每更新一次当前最优值，输出结果 */
}
}
}
void main()
{
system("cls");
generation=0;
GenerateInitialPopulation();
CalculateFitness();
FindBestIndividual();
OutputTextReport();
while(generation<MaxGeneration)
{
generation++;
GenerateNextPopulation();
CalculateFitness();
FindBestIndividual();
}
printf("\n完成");
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -