📄 ga-tsp.cpp
字号:
//23020061152452 陈魁
#include <iostream.h>
#include <time.h>
#include <stdio.h>
#include <iomanip>
#include <fstream.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int increase; //交叉时增加的个体数
double nfit=0; //设定总适应度＝0
#define MaxCityNum 50 //设定最大城市数目为50
int dist[MaxCityNum][MaxCityNum] ;
typedef struct TSP
{ int road[50]; //road 数组来表示一个回路即是一个染色体,最大设定50
double fit; //fit为这个染色体的适应度
};
//-------------------------随机数发生器的类定义-----------------------------------------------
const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;
class RandomNumber
{ private:
//当前种子
unsigned long randSeed;
public:
//构造函数，缺省值为0表示由系统自动产生种子
RandomNumber(unsigned long s=0);
//产生0～(n-1)之间的随机整数
unsigned short Random(unsigned long n);
//产生[0,1)之间的随机实数
double fRandom(void);
};
//产生种子
RandomNumber::RandomNumber(unsigned long s)
{ if(s==0)
randSeed=time(0); //用系统时间产生种子
else
randSeed=s; //由用户提供种子
}
//产生0～(n-1)之间的随机整数
unsigned short RandomNumber::Random(unsigned long n)
{ randSeed=multiplier*randSeed+adder;
return (unsigned short)((randSeed>>16)%n);
}
//产生[0,1)之间的随机实数
double RandomNumber::fRandom(void)
{ return Random(maxshort)/double(maxshort);
}
//-------------------------随机数发生器的类定义---------------------------------------------------
//----------------------------------------适应度计算-----------------------------------------------
double Calfit(int g[],int City_Num) //g为一个染色体
{
double w=0; //权值
double fit;
int s,e;
// for(int k=1;k<=11;k++) 调试用
// cout<<"g["<<k<<"]="<<g[k]<<endl;
for(int i=1;i<=City_Num;i++)
{ s=g[i]; e=g[i+1];
w = w + dist[s][e] ;
}
fit=w;
return double(100000)/fit; //修改
}
//-----------------------------------------适应度计算-------------------------------------------
//-----------------------------------------存在判定---------------------------------------------
bool exist(int t,int e[],int cl1,int cl2)
{ bool flag = false;
for(int i=cl1;i<=cl2;i++)
{ if(e[i]==t) flag = true;
}
return flag;
}
//-----------------------------------------存在判定----------------------------------------------
class GA
{
friend bool Letstry(int City_Num,int popsize,int generation,double pc,double pm,bool show);
public:
int popsize; // 种群大小
double pc; // 交叉率
double pm; // 变异率
int flag; // 是否显示种群个体
TSP *x; // 进化中间过程中进行处理
TSP *y; // 存放每代进化完成的结果
TSP *Bestnow(TSP t[],int size); // 寻找当前最优的个体
TSP *Initialize(int City_Num,int size,int show); // 初始化种群
TSP *Crossover(int City_Num,TSP y[],int size); //交叉操作
TSP *Mutation(int City_Num,TSP t[],int size); //变异操作
TSP *Select(TSP t[],int size); //选择操作
};
//-----------------------------------------GA类定义-----------------------------------------------
//----------------------------------------种群初始化----------------------------------------------
TSP *GA::Initialize(int City_Num, int size,int show) //size种群规模。初始化size个可行解
{
static RandomNumber R;
TSP *t=new TSP[size+1];
int i=1;
int b;
// int temp;//tempchange;
for(int k=0;k<=size;k++) //初始化种群数组，全部设为0
{ for(int n=0;n<=City_Num+1;n++)
t[k].road[n]=0;
}
t[0].fit=0;
while(i<=size)
{ int s[MaxCityNum+1];
for(int k=1;k<City_Num+1;k++) s[k]=0;
for(int j=1;j<City_Num+1;j++)
{
b=R.Random(City_Num)+1;
while(s[b]!=0)
{b=R.Random(City_Num)+1;
}
t[i].road[j] = b;
s[b]=1;
}
/*for(int k=1;k<=City_Num;k++)
{ t[i].road[k] = k; } //填充数组
for(int n=1;n<City_Num;n++) //随机交换
{
temp = R.Random(City_Num)+1;
tempchange = t[i].road[n]; t[i].road[n] = t[i].road[temp]; t[i].road[temp] = tempchange;
}*/
t[i].road[City_Num+1] = t[i].road[1]; //回到出发位置
t[i].fit = Calfit(t[i].road, City_Num);
i++;
}
if(show)
{ cout<<"初始化的种群为："<<endl; //输出初始种群
for (k=0;k<=size;k++)
{ for( int j=1;j<=City_Num+1;j++)
{ cout<<t[k].road[j]<<" "; }
cout<<" t["<<k<<"].fit: "<<t[k].fit<<endl;
cout<<endl<<endl;
}
}
return t;
}
//----------------------------------------种群初始化----------------------------------------------
//-------------------------------------寻找当前最优解---------------------------------------------
TSP *GA::Bestnow(TSP t[],int size)
{
int best=0;
double bestfit=t[0].fit;
for(int i=1;i<=popsize;i++)
{ if(t[i].fit>bestfit)
{ bestfit=t[i].fit;
best=i;
}
}
t[0]=t[best];
return t;
}
//-------------------------------------寻找当前最优解---------------------------------------------
//-------------------------------------交叉操作----------------------------------------------------
TSP *GA::Crossover(int City_Num,TSP y[],int size) // 按相对顺序进行交叉
{
increase = 1;
static RandomNumber R;
double p1;
int cl1,cl2,tempchange; //cl为crosslocation 即交叉位置（随机选取）
int co; //co为crossobject 即交叉对象（随机选取）
TSP *x=new TSP[1000];
for(int k=0;k<=size;k++)
{ x[k]=y[k];}
for(k=0;k<=size;k++)
{ //cout<<"k="<<k<<endl;
p1=R.fRandom(); //生成随机数p1
if(p1<pc) //随机数比交叉率小，则执行交叉操作
{
cl1 = R.Random(City_Num)+1; //交叉位置的随机选取
cl2 = R.Random(City_Num)+1;
while(cl1==cl2) cl2 = R.Random(City_Num)+1;
if(cl1>cl2) { tempchange=cl1; cl1=cl2;cl2=tempchange;} //保证cl1<cl2
do{ co=R.Random(size+1); //交叉对象的随机选取（不是本身）
}while(co==k);
for(int i=1;i<=City_Num;i++) //先产生2个和父代一样的个体
{
x[size+increase].road[i] = x[k].road[i];
x[size+increase+1].road[i] = x[co].road[i];
}
for(i=1;i<cl1;i++) //将要赋予新值的位置设置成0
{
x[size+increase].road[i] = 0;
x[size+increase+1].road[i] = 0;
}
for(i=cl2+1;i<=City_Num;i++)
{
x[size+increase].road[i] = 0;
x[size+increase+1].road[i] = 0;
}
int n=1,s=1;
for(int m=1;m<City_Num+1;m++) // 副本父代2个个体交叉变换
{
if(!exist(x[co].road[m],x[k].road,cl1,cl2))
{
while(x[size+increase].road[n]!=0) {n++;}
// cout<<"n="<<n<<endl;
x[size+increase].road[n] = x[co].road[m];
}
if(!exist(x[k].road[m],x[co].road,cl1,cl2))
{
while(x[size+increase+1].road[s]!=0) {s++;}
//cout<<"n="<<n<<endl;
x[size+increase+1].road[s] = x[k].road[m];
}
}//for(m)
x[size+increase].road[City_Num+1] = x[size+increase].road[1];
x[size+increase+1].road[City_Num+1] =x[size+increase+1].road[1];
x[size+increase].fit=Calfit(x[size+increase].road,City_Num );
x[size+increase+1].fit=Calfit(x[size+increase+1].road,City_Num);
increase = increase+2;
}//if(p1<pc)
}//for(k)
increase = increase-1;
delete y;
return x;
}//Crossover
//-------------------------------------交叉操作--------------------------------------------------
//-------------------------------------变异操作---------------------------------------------------
TSP *GA::Mutation(int City_Num,TSP x[],int size)
{
TSP *t=new TSP[1000];
static RandomNumber R;
double p2;
int ml1,ml2;
int temp;
for (int k=0;k<=size+increase;k++)
{
t[k]=x[k];
}
delete x;
t[k]=t[0]; //把当前最优解赋值给最后一元素，并参加变异过程
increase = increase + 1;
for (k=1;k<=size+increase;k++) //t[0]本身不参加变异过程，保留当前最优，但是它的复制体参加
{
p2=R.fRandom();
if(p2<pm)
{
for(int i=1;i<=City_Num+1;i++)
{ t[size+increase+1]=t[k]; }
ml1 = R.Random(City_Num)+1; //变异位置
ml2 = R.Random(City_Num)+1;
while(ml1==ml2) ml2= R.Random(City_Num)+1;
temp=t[k].road[ml1]; t[k].road[ml1] = t[k].road[ml2];
t[k].road[ml2] = temp;
t[k].road[City_Num+1] = t[k].road[1];
t[k].fit=Calfit(t[k].road,City_Num);
}
}
return t;
}
//-------------------------------------变异操作---------------------------------------------------
//-------------------------------------选择操作---------------------------------------------------
TSP *GA::Select(TSP t[],int size)
{
static RandomNumber R;
double point;
double sumfit=0;
int i;
TSP *s=new TSP[size+1];
s[0]=t[0];
for(int k=1;k<=size+increase;k++) //准备计算相对适应度
{
sumfit=sumfit+t[k].fit;
}
double *relative_fit=new double[size+increase+1];
for(k=1;k<=size+increase;k++)
{
relative_fit[k]=double(t[k].fit)/sumfit;
}
for(k=2;k<=size+increase;k++)
{
relative_fit[k]=relative_fit[k-1]+relative_fit[k];
}
for(k=1;k<=size;k++)
{
point=R.fRandom();
i=0;
while(point>relative_fit[i]) { i++; }
s[k]=t[i];
}
return s;
}
//-------------------------------------选择操作---------------------------------------------------
//-------------------------------------友元函数---------------------------------------------------
bool Letstry(int City_Num,int popsize,int generation,double pc,double pm,int show)
{
GA G;
G.popsize=popsize;
G.pc=pc;
G.pm=pm;
int flag;
flag=show;
G.flag=show;
G.y=G.Initialize(City_Num,G.popsize,G.flag );
G.y=G.Bestnow(G.y,G.popsize);
for(int g=1;g<=generation;g++)
{
G.x=G.Crossover(City_Num,G.y,G.popsize );
G.x=G.Mutation(City_Num,G.x,G.popsize );
G.x=G.Bestnow(G.x,G.popsize);
G.y=G.Select(G.x,G.popsize);
if(flag)
{ cout<<endl;
cout<<"第"<<g<<"代种群为："<<endl;
for(int k=0;k<=popsize;k++)
{ for( int l=1;l<=City_Num+1;l++)
{cout<<G.y[k].road[l]<<" ";}
cout<<" y["<<k<<"].fit: "<<G.y[k].fit<<endl;
cout<<endl;
}
}
increase=1;
cout<<endl<<"当前近似最优解="<<double(100000)/(G.y[0].fit)<<endl;
}
G.y=G.Bestnow(G.y,G.popsize);
cout<<endl<<"近似最优解="<<double(100000)/(G.y[0].fit)<<endl;
for(int k=1;k<=City_Num+1;k++)
cout<<G.y[0].road[k]<<" ";
cout<<endl;
//cout<<"nfit="<<nfit<<endl;
nfit=nfit+G.y[0].fit;
// cout<<"nfit="<<nfit<<endl;
return true;
}
//-------------------------------------友元函数---------------------------------------------------
void main()
{
int City_Num;
int popsize;
int generation;
double pc;
double pm;
int show;
int runtime;
// double avefit;
ifstream datafile;
char fileName[10];
cout<<"请输入城市的数目（29 or 42）：";
cin>>fileName;
City_Num=atoi(fileName);
for(int k=0;k<City_Num+1;k++) //初始化邻接矩阵
for(int t=0;t<City_Num+1;t++)
dist[k][t]=0;
datafile.open(strcat(fileName,".txt")); //打开文件
for(int i=1;i<City_Num+1;i++) //输入数据到矩阵
{ for(int j=1;j<City_Num+1;j++)
{ datafile>>dist[i][j];
//dist[j][i]=dist[i][j];
}
}
// for( k=1;k<City_Num+1;k++)
// for(int l=1;l<City_Num+1;l++)
// cout<<"dist["<<k<<"]["<<l<<"]="<<dist[k][l]<<" ";
cout<<endl;
cout<<"请输入要初始的种群大小的规模（100～200）:";
cin>>popsize;
cout<<endl;
cout<<"请输入算法进行进化的代数:";
cin>>generation;
cout<<endl;
do {
cout<<"请输入要设置的交叉率pc（0.5～0.9）:";
cin>>pc;
} while(pc>=1||pc<=0);
cout<<endl;
do {
cout<<"请输入要设置的变异率pm（0.01-0.2）:";
cin>>pm;
} while(pm>=1||pm<=0);
cout<<endl;
do{
cout<<"是否显示每代的种群（0－否，1－是）：";
cin>>show;
}while((show!=1)&&(show!=0));
cout<<endl;
do{
cout<<"请输入要执行的次数：（1）";
cin>>runtime;
}while(runtime<=0);
for(int n=1;n<=runtime;n++)
{
Letstry(City_Num,popsize,generation,pc,pm,show);
}
// cout<<"nfit="<<nfit<<endl;
// avefit = double(runtime)/nfit;
//cout<<"路径最小值平均为："<<avefit<<endl;
}
//23020061152452 陈魁⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -