tspgt.cpp

本程序是求解TSP问题（读距离矩阵版本）.

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

int CityMatrix[CITIES][CITIES];
CCell CellSet[CELLNUM];
CCell TempCell;
void InitCityMatrix();

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 <100000)
    {
            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 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);
}


#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));
}


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 (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;
}