?? 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; //交叉時增加的個體數(shù)
double nfit=0; //設定總適應度＝0
#define MaxCityNum 50 //設定最大城市數(shù)目為50
int dist[MaxCityNum][MaxCityNum] ;
typedef struct TSP
{ int road[50]; //road 數(shù)組來表示一個回路即是一個染色體,最大設定50
double fit; //fit為這個染色體的適應度
};
//-------------------------隨機數(shù)發(fā)生器的類定義-----------------------------------------------
const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;
class RandomNumber
{ private:
//當前種子
unsigned long randSeed;
public:
//構(gòu)造函數(shù)，缺省值為0表示由系統(tǒng)自動產(chǎn)生種子
RandomNumber(unsigned long s=0);
//產(chǎn)生0～(n-1)之間的隨機整數(shù)
unsigned short Random(unsigned long n);
//產(chǎn)生[0,1)之間的隨機實數(shù)
double fRandom(void);
};
//產(chǎn)生種子
RandomNumber::RandomNumber(unsigned long s)
{ if(s==0)
randSeed=time(0); //用系統(tǒng)時間產(chǎn)生種子
else
randSeed=s; //由用戶提供種子
}
//產(chǎn)生0～(n-1)之間的隨機整數(shù)
unsigned short RandomNumber::Random(unsigned long n)
{ randSeed=multiplier*randSeed+adder;
return (unsigned short)((randSeed>>16)%n);
}
//產(chǎn)生[0,1)之間的隨機實數(shù)
double RandomNumber::fRandom(void)
{ return Random(maxshort)/double(maxshort);
}
//-------------------------隨機數(shù)發(fā)生器的類定義---------------------------------------------------
//----------------------------------------適應度計算-----------------------------------------------
double Calfit(int g[],int City_Num) //g為一個染色體
{
double w=0; //權(quán)值
double fit;
int s,e;
// for(int k=1;k<=11;k++) 調(diào)試用
// 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; // 存放每代進化完成的結(jié)果
TSP *Bestnow(TSP t[],int size); // 尋找當前最優(yōu)的個體
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種群規(guī)模。初始化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++) //初始化種群數(shù)組，全部設為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; } //填充數(shù)組
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]; //回到出發(fā)位置
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;
}
//----------------------------------------種群初始化----------------------------------------------
//-------------------------------------尋找當前最優(yōu)解---------------------------------------------
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;
}
//-------------------------------------尋找當前最優(yōu)解---------------------------------------------
//-------------------------------------交叉操作----------------------------------------------------
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(); //生成隨機數(shù)p1
if(p1<pc) //隨機數(shù)比交叉率小，則執(zhí)行交叉操作
{
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++) //先產(chǎn)生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]; //把當前最優(yōu)解賦值給最后一元素，并參加變異過程
increase = increase + 1;
for (k=1;k<=size+increase;k++) //t[0]本身不參加變異過程，保留當前最優(yōu)，但是它的復制體參加
{
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;
}
//-------------------------------------選擇操作---------------------------------------------------
//-------------------------------------友元函數(shù)---------------------------------------------------
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<<"當前近似最優(yōu)解="<<double(100000)/(G.y[0].fit)<<endl;
}
G.y=G.Bestnow(G.y,G.popsize);
cout<<endl<<"近似最優(yōu)解="<<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;
}
//-------------------------------------友元函數(shù)---------------------------------------------------
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<<"請輸入城市的數(shù)目（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++) //輸入數(shù)據(jù)到矩陣
{ 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<<"請輸入要初始的種群大小的規(guī)模（100～200）:";
cin>>popsize;
cout<<endl;
cout<<"請輸入算法進行進化的代數(shù):";
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<<"請輸入要執(zhí)行的次數(shù)：（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 + -