📄 tspgt.cpp
字号:
// TSPGT.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdlib.h"
#include "time.h"
#include "math.h"
#define CITIES 51
#define CELLNUM 100
#define FILENAME "tsp30.txt"
void RanInit(unsigned int Seed);
double Random(double m_Start,double m_End);
int Random(int i,int j);
void RanInit();
int EvalNum =0;
class CCell
{
public:
double Fitness;
bool InverPos(int CityPos1,int CityPos2);
int GetCityPos(int City);
void Print();
double Evaluate();
bool ValidCell();
CCell & operator=(CCell & m_1);
CCell();
int City[CITIES];
};
//CCell Best;
//void InitCell(int index);
double CityMatrix[CITIES][CITIES];
CCell CellSet[CELLNUM];
CCell TempCell;
void InitCityMatrix();
double zuobiao[CITIES][2];
void GetData();
//void InitCellSet();
//bool Inver(int index1,int index2);
//bool VerCell(int index1,int City1,int City2);
//int Evaluate (int index);
//void InverTemp(int City1Pos,int City2Pos);
//int EvaluateTemp ();
//void PrintTempCell();
//bool ValidTemp();
CCell Best;
int main(int argc, char* argv[])
{
char tmpbuf[128];
_strtime( tmpbuf );
FILE *fp;
fp= fopen("result.txt","w");
if (fp==NULL)
{
printf("FILE OPEN ERROR\n");
return 0;
}
RanInit();
GetData();
InitCityMatrix();
Best.Evaluate ();
for (int kk=0;kk<CELLNUM;kk++)
CellSet[kk].Evaluate();
// InitCellSet();
int i=0;
/*
int Count = 0;
double preBestF=Best.Fitness;*/
while(EvalNum <1000000)
{
TempCell= CellSet[i];
i++;
if (i==CELLNUM) i=0;
//REPEAT
int C1Pos =Random(0,CITIES-1);
int C1= TempCell.City[C1Pos];
int C2;
int C2Pos;
while(1)
{
if (Random(0.0,1.0)<0.02 )
{
C2 = Random(0,CITIES-1);
if (C1==C2){C2=(C2+1)%CITIES;};
}
else
{
int P=Random(0,CELLNUM-1);
if (P==i)P=(P+1)%CELLNUM;
C1Pos= CellSet[P].GetCityPos(C1);
C2=CellSet[P].City[(C1Pos+1)%CITIES];
}
//判是否在其中
// Get C1 Position
C1Pos= TempCell.GetCityPos(C1);
if ((TempCell.City [(C1Pos+1)%CITIES]==C2)||(TempCell.City [(C1Pos-1+CITIES)%CITIES]==C2))
break;
else //对TempCell倒置
{
C2Pos=TempCell.GetCityPos(C2);
TempCell.InverPos(C1Pos,C2Pos);
// if (!TempCell.ValidCell())
// printf("daozhi zuo!\n");
}
C1=C2;
//把郭涛算法的一段向上移动.
TempCell.Evaluate();
if (TempCell.Fitness <CellSet[i].Fitness)
{
CellSet[i]=TempCell;
// printf("TEMP_________________\n");
// TempCell.Print();
// printf("Eval:%d\n",TempCell.Fitness);
};
}
//下面的位置是郭涛算法原来位置。
TempCell.Evaluate();
if (TempCell.Fitness <CellSet[i].Fitness)
{
CellSet[i]=TempCell;
// printf("TEMP_________________\n");
// TempCell.Print();
// printf("Eval:%d\n",TempCell.Fitness);
};
if (TempCell.Fitness<Best.Fitness )
{
Best =TempCell ;
printf("BEST***********************EvalNum:%d\n",EvalNum);
Best.Print();
printf("Eval:%.5f\n",Best.Fitness);
}
/*
preBestF = Best.Fitness;
if (TempCell.Fitness<Best.Fitness )
{
Best =TempCell ;
printf("BEST***********************EvalNum:%d\n",EvalNum);
Best.Print();
printf("Eval:%.5f\n",Best.Fitness);
}
if(preBestF!=Best.Fitness)
{
Count = 0;
}
else
{
Count++;
}*/
}
for(i=0;i<CITIES;i++)
{
fprintf(fp,"%d ",Best.City[i]);
}
fprintf(fp,"%.6f",Best.Evaluate());
fprintf(fp,"\r\n");
fclose(fp);
printf( "BEGIN OS time:\t\t\t\t%s\n", tmpbuf );
_strtime( tmpbuf );
printf( "END OS time:\t\t\t\t%s\n", tmpbuf );
return 0;
}
/*
void InverTemp(int City1Pos,int City2Pos)
{
if ((City1Pos >CITIES-1)||(City1Pos >CITIES-1))
{
printf("CITYPOS ERROR!");
printf("CityPos1:%d,CITYPOS2:%d\n",City1Pos,City2Pos);
PrintTempCell();
}
if (City1Pos<City2Pos)
{
City1Pos= City1Pos+1;
while(1)
{
int kk=TempCell[City1Pos];
TempCell[City1Pos]=TempCell[City2Pos];
TempCell[City2Pos]=kk;
if ((City2Pos-City1Pos)<=2) break;
City1Pos=(City1Pos+1);
City2Pos=(City2Pos-1);
}
}
else if (City1Pos>City2Pos)
{
City1Pos= City1Pos-1;
while(1)
{
int kk=TempCell[City1Pos];
TempCell[City1Pos]=TempCell[City2Pos];
TempCell[City2Pos]=kk;
if ((City1Pos-City2Pos)<=2) break;
City1Pos=(City1Pos-1);
City2Pos=(City2Pos+1);
}
}
return;
}*/
/*void InitCell(int index)
{
int Temp[CITIES];
for (int i=0;i<CITIES;i++)
Temp[i]=i;
for (int j=0;j<CITIES;j++)
{
int RndNum =Random(0,CITIES-1);
int SelectedCity;
SelectedCity=-1;
while (SelectedCity==-1)
{
SelectedCity=Temp[RndNum%CITIES];
RndNum++;
}
Temp[(RndNum-1+CITIES)%CITIES]=-1;
CellSet[index][j]=SelectedCity;
TempCell[j]=SelectedCity;
}
}*/
/*void InitCellSet()
{
for (int i=0;i<CELLNUM;i++)
InitCell(i);
}
void PrintTempCell()
{
for (int k=0;k<CITIES;k++)
{
printf("TEMPGene%d: %d\n",k,TempCell[k]);
};
printf("Eval:%d\n",EvaluateTemp());
}
bool ValidTemp()
{
int Temp[CITIES];
for (int i=0;i<CITIES;i++)
Temp[i]=i;
for (i=0;i<CITIES;i++)
{
Temp[TempCell[i]]=-1;
}
for (i=0;i<CITIES;i++)
if (Temp[i]!=-1)
{
printf("Temp Error\n");
return false;
}
return true;
}*/
void InitCityMatrix()
{
for(int i=0;i<CITIES;i++)
for(int j=0;j<CITIES;j++)
{
CityMatrix[i][j]=sqrt((zuobiao[i][0]-zuobiao[j][0])*(zuobiao[i][0]-zuobiao[j][0])+
(zuobiao[i][1]-zuobiao[j][1])*(zuobiao[i][1]-zuobiao[j][1]));
CityMatrix[i][j]=(int)(CityMatrix[i][j]+0.5);
}
}
/*int Evaluate (int index)
{
int temp=0;
for(int i=0;i<CITIES;i++)
{
temp+=CityMatrix[CellSet[index][i]][CellSet[index][(i+1)%CITIES]];
}
return temp;
}
int EvaluateTemp ()
{
int temp=0;
for(int i=0;i<CITIES;i++)
{
temp+=CityMatrix[TempCell[i]][TempCell[(i+1)%CITIES]];
}
return temp;
}
*/
#include "time.h"
void RanInit(unsigned int Seed)
{
srand(Seed);
}
double Random(double m_Start,double m_End)
{
if ((m_End - m_Start ) <0.00000000001)
return 0.0;
return (m_Start + (m_End - m_Start) * rand() /RAND_MAX);
}
int Random(int i,int j)
{
return (i + rand() % (j -i+1));
}
void RanInit()
{
srand(time(NULL));
}
/*
bool Inver(int index1,int index2)
{
int RndNum= Random(0,CITIES-1);
if(index1==index2)
{
int RndNum2= Random(0,CITIES-1);
if(RndNum==RndNum2)RndNum2++;
return VerCell(index1,RndNum,RndNum2);
}
int City2;
for (int i=0;i<CITIES;i++)
{
if (CellSet[index2][i]==RndNum)
{
City2=CellSet[index2][i+1];
break;
}
}
return VerCell(index1,RndNum,City2);
}
bool VerCell(int index1,int City1,int City2)
{
for (int k=0;k<CITIES;k++)
TempCell[k]=CellSet[index1][k];
int i=0;
int j=0;
while (TempCell[i]!=City1) i++;
while (TempCell[j]!=City1) j++;
if((i==j+1)||(i=j-1)) return true;
if (i>j)
{
i--;
while(i-- > j++)
{
int kk=TempCell[i];
TempCell[i]=TempCell[j];
TempCell[j]=kk;
}
}
if (i<j)
{
j--;
while(i++ > j--)
{
int kk=TempCell[i];
TempCell[i]=TempCell[j];
TempCell[j]=kk;
}
}
return false;
}
*/
CCell::CCell()
{
int Temp[CITIES];
for (int i=0;i<CITIES;i++)
Temp[i]=i;
for (int j=0;j<CITIES;j++)
{
int RndNum =Random(0,CITIES-1);
int SelectedCity;
SelectedCity=-1;
while (SelectedCity==-1)
{
SelectedCity=Temp[RndNum%CITIES];
RndNum++;
}
Temp[(RndNum-1+CITIES)%CITIES]=-1;
this->City[j]=SelectedCity;
}
}
bool CCell::ValidCell()
{
int Temp[CITIES];
for (int i=0;i<CITIES;i++)
Temp[i]=i;
for (i=0;i<CITIES;i++)
{
Temp[City[i]]=-1;
}
for (i=0;i<CITIES;i++)
if (Temp[i]!=-1)
{
printf("Temp Error\n");
return false;
};
return true;
}
double CCell::Evaluate()
{
EvalNum++;
double temp=0;
for(int i=0;i<CITIES;i++)
{
temp+=CityMatrix[City[i]][City[(i+1)%CITIES]];
}
Fitness= temp;
return temp;
}
void CCell::Print()
{
for (int k=0;k<CITIES;k++)
{
printf("Gene%d: %d\n",k,this->City[k]);
};
}
int CCell::GetCityPos(int mCity)
{
for (int i=0;i<CITIES;i++)
{
if (this->City[i]==mCity) return i;
}
printf("CITYPOS ERROR");
return -1;
// ASSERT(FALSE);
}
bool CCell::InverPos(int CityPos1, int CityPos2)
{
/* if ((City1Pos >CITIES-1)||(City1Pos >CITIES-1))
{
printf("CITYPOS ERROR!");
printf("CityPos1:%d,CITYPOS2:%d\n",City1Pos,City2Pos);
Print();
}
*/
if (CityPos1<CityPos2)
{
CityPos1= CityPos1+1;
while(1)
{
int kk=this->City[CityPos1];
this->City[CityPos1]=this->City[CityPos2];
this->City[CityPos2]=kk;
if ((CityPos2-CityPos1)<=2) break;
CityPos1=(CityPos1+1);
CityPos2=(CityPos2-1);
}
}
else if (CityPos1>CityPos2)
{
CityPos1= CityPos1-1;
while(1)
{
int kk=this->City[CityPos1];
this->City[CityPos1]=this->City[CityPos2];
this->City[CityPos2]=kk;
if ((CityPos1-CityPos2)<=2) break;
CityPos1=(CityPos1-1);
CityPos2=(CityPos2+1);
}
}
return true;
}
CCell & CCell::operator =(CCell &m_1)
{
for (int i=0;i<CITIES;i++)
this->City[i]= m_1.City[i];
this->Fitness = m_1.Fitness ;
return *this;
}
void GetData()
{
double tt[10000];
FILE *fp;
fp= fopen(FILENAME,"rt");
if (fp==NULL)
{
printf("FILE OPEN ERROR\n");
return ;
}
char *FileContence=new char[100000];
int i=0;
char ch;
while((ch=fgetc(fp))!=EOF)
{
FileContence[i++]=ch;
}
fclose(fp);
int top=0;
i=0;
double a;
ch=FileContence[top++];
while (ch!='t')
{
if (ch=='-')
{
ch=FileContence[top++];
if (ch>='0' && ch<='9')
{
a=ch-'0';
ch=FileContence[top++];
while (ch>='0' && ch<='9')
{
a=a*10+ch-'0';
ch=FileContence[top++];
}
if (ch=='.')
{
int k=1;
ch=FileContence[top++];
while (ch>='0' && ch<='9')
{
a=a+(ch-'0')/(10.00*k); //有错误，无法得到小数
k=k*10;
ch=FileContence[top++];
}
}
if (ch=='e' || ch=='E')
{
ch = FileContence[top++];
if (ch =='-')
{
ch = FileContence[top++];
while (ch == '0')
{
ch = FileContence[top++];
}
if (ch>'0' && ch<='9')
{
int xh=ch-'0';
while (xh>0)
{
a=a/10;
xh--;
}
}
}
else
{
ch = FileContence[top++];
while (ch == '0')
{
ch = FileContence[top++];
}
if (ch>'0' && ch<='9')
{
int xh=ch-'0';
while (xh>0)
{
a=a*10;
xh--;
}
}
ch=FileContence[top++];
}
}
}
tt[i++]=-a;
}
else if (ch!='-' && ch>='0' && ch<='9')
{
if (ch>='0' && ch<='9')
{
a=ch-'0';
ch=FileContence[top++];
while (ch>='0' && ch<='9')
{
a=a*10+ch-'0';
ch=FileContence[top++];
}
if (ch=='.')
{
int k=1;
ch=FileContence[top++];
while (ch>='0' && ch<='9')
{
a=a+(ch-'0')/(10.0*k);
k=k*10;
ch=FileContence[top++];
}
}
if (ch=='e' || ch=='E')
{
ch = FileContence[top++];
if (ch =='-')
{
ch = FileContence[top++];
while (ch == '0')
{
ch = FileContence[top++];
}
if (ch>'0' && ch<='9')
{
int xh=ch-'0';
while (xh>0)
{
a=a/10;
xh--;
}
}
}
else
{
ch = FileContence[top++];
while (ch == '0')
{
ch = FileContence[top++];
}
if (ch>'0' && ch<='9')
{
int xh=ch-'0';
while (xh>0)
{
a=a*10;
xh--;
}
}
ch=FileContence[top++];
}
}
}
tt[i++]=a;
}
else
{
ch=FileContence[top++];
}
}
int k=0;
for (int m=0;m<=(int(i/3)+1)-1;m++)
{
k++;
zuobiao[m][0]=tt[k++];
zuobiao[m][1]=tt[k++];
if (k>=i)
break;
}
return ;
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -