tspgt.cpp

用于求解TSP问题的matlab源代码

// TSPGT.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdlib.h"
#include "time.h"


#define CITIES 144
#define CELLNUM 100
#define FILENAME "144.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:
	int Fitness;
    bool InverPos(int CityPos1,int CityPos2);
    int GetCityPos(int City);
    void Print();
    int Evaluate();
    bool ValidCell();
    CCell & operator=(CCell & m_1);
    CCell();
    int City[CITIES];
};

//CCell Best;
//void InitCell(int index);
int CityMatrix[CITIES][CITIES];
CCell CellSet[CELLNUM];
CCell TempCell;
void InitCityMatrix();
//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();
    InitCityMatrix();  
    Best.Evaluate ();
    for (int kk=0;kk<CELLNUM;kk++)
        CellSet[kk].Evaluate();
    //    InitCellSet();
    int i=0;
    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:%d\n",Best.Fitness);
            }
 
  
    } 
	for(i=0;i<CITIES;i++)
	{
        fprintf(fp,"%d ",Best.City[i]);
	}
	fprintf(fp,"%d",Best.Fitness);
	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()
{
    FILE *fp;
    fp= fopen(FILENAME,"rt");
    if (fp==NULL)
    {
        printf("FILE OPEN ERROR\n");
        return ;
    }
    for(int i=0;i<CITIES;i++)
        for(int j=0;j<CITIES;j++)
        {
            fscanf(fp,"%d",&(CityMatrix[i][j]));
        }
        fclose(fp);
}

/*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;
}

int CCell::Evaluate()
{
    EvalNum++;
    int 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;
}