tspsga.cpp

这是一个用遗传算法来求解旅行商问题（TSP问题：Travelling Salesman Problem）的源代码

#include "StdAfx.h"
#include ".\TSPSGA.h"
POINT CtyPt[20] = 
{
	{5.294, 1.558},
	{4.286, 3.622},
	{4.719, 2.774},
	{4.185, 2.230},
	{0.915, 3.821},
	{4.771, 6.041},
	{1.524, 2.871},
	{3.447, 2.111},
	{3.718, 3.665},
	{2.649, 2.556},
	{4.399, 1.194},
	{4.660, 2.949},
	{1.232, 6.440},
	{5.036, 0.244},
	{2.710, 3.140},
	{1.072, 3.454},
	{5.855, 6.203},
	{0.194, 1.862},
	{1.762, 2.693},
	{2.682, 6.097},
};

//全局函数产生[0，1]之间的随机数
double Crand(long seed)
{
	const long int MBIG=0x0fffffff;
	const long int MSEED=0x03c04ffd;
	const int MZ=0;
	const double FAC=1.0/MBIG;
	static int inext,inextp,iff=0;
	static long ma[56],mj,mk;
	int i,j,k;
	if(seed<0 || iff==0)
	{
		iff=1;
		mj=MSEED-(seed<0? -seed:seed);
		mj%=MBIG;
		ma[55]=mj;
		for(mk=1,i=1;i<=54;i++)
		{
			j=(21*i)%55;
			ma[j]=mk;
			mk=mj-mk;
			if(mk<MZ) mk+=MBIG;
			mj=ma[j];
		}
		
		for(k=1;k<=4;k++)
		{
			for(i=1;i<=55;i++)
			{
				ma[i]-=ma[1+(i+30)%55];
				if(ma[i]<MZ) ma[i]+=MBIG;
			}

			inext=0;
			inextp=31;
			seed=1;
		}
	}

	if(++inext==56)
	{
		inext=1;
	}

	if(++inextp==56) 
	{
		inextp=1;
	}

	mj=ma[inext]-ma[inextp];
	if(mj<MZ) 
	{
		mj+=MBIG;
	}

	ma[inext]=mj;

	return mj*FAC;
}

CTSPSGA::CTSPSGA(void)
{
	m_PopSize = 300;
	m_CtyCnt = 20;
	m_ChromLen = 20;
	m_Maxgen = 1000;
	m_Tour = 50;
	m_Pcross = 0.55;
	m_Pmutation = 0.15;

	m_pCtyPt = new POINT[m_CtyCnt];
	memcpy(m_pCtyPt, CtyPt, sizeof(POINT)*m_CtyCnt);
 
	memset(&m_BestFit, 0, sizeof(BESTEVER));
	m_BestFit.pChrom = new char[m_ChromLen+1];
	
	memset(m_BestFit.pChrom, 0, m_ChromLen+1);

	m_POldPop = new INDIVIDUAL[m_PopSize];
	m_PNewPop = new INDIVIDUAL[m_PopSize];

	for (int i=0; i<m_PopSize; i++)
	{
		m_POldPop[i].pChrom = new char[m_ChromLen+1];
		m_PNewPop[i].pChrom = new char[m_ChromLen+1];
		
		memset(m_POldPop[i].pChrom, 0, m_ChromLen+1);
		memset(m_PNewPop[i].pChrom, 0, m_ChromLen+1);
	}

}


CTSPSGA::~CTSPSGA(void)
{
	
	delete []m_pCtyPt;
	m_pCtyPt = NULL;

	delete [](m_BestFit.pChrom);
	m_BestFit.pChrom = NULL;

	for (int i=0; i<m_PopSize; i++)
	{
		delete [](m_POldPop[i].pChrom);
		delete [](m_PNewPop[i].pChrom);
	}

	delete []m_POldPop;
	m_POldPop = NULL;

	delete []m_PNewPop;
	m_PNewPop = NULL;
}


void CTSPSGA::InitPop(void)
{
	srand( (unsigned)time( NULL ) );
	int k = 0;
	char c[2] = "";
	bool  *pFlag = new bool[m_CtyCnt];

	for (int i=0; i<m_PopSize; i++)
	{
		memset(pFlag, 0, sizeof(bool)*m_CtyCnt);
		for (int j=0; j<m_ChromLen; j++)
		{
			do
			{
				k = rand()%m_CtyCnt;
			}while(pFlag[k]);

			memset(c, 0, sizeof(c));
			c[0] = k + 'A';
			pFlag[k] = 1;
			strcat(m_POldPop[i].pChrom, c);
		}

		m_POldPop[i].parent[0] = 0;
		m_POldPop[i].parent[1] = 1;
		m_POldPop[i].xsite = 0;

		//计算初始适应度
		ComputeFitness(m_POldPop+i);
	}

	delete []pFlag;
	pFlag = NULL;
}


double CTSPSGA::ComputeFitness(PINDIVIDUAL pIndividual)
{	
	
	pIndividual->fitness = GetAllDistance(pIndividual->pChrom);


	if (pIndividual->fitness < 51.50)
	{
		pIndividual->fitness = 51.50 - pIndividual->fitness;
	}
	else
	{
		pIndividual->fitness = 0.0;
	}
	
	return pIndividual->fitness;
}

double CTSPSGA::GetAllDistance(char *Line)
{	
	double Value = 0.0;
	double Re = 0.0;
	int k1 =0;
	int k2 = 0;

	for(int i=0; i<m_CtyCnt; i++)
	{
		k1 = Line[i] - 'A';
		k2 = Line[(i+1) % m_CtyCnt] - 'A';
		Value = GetDistance(m_pCtyPt[k1], m_pCtyPt[k2]);

		Re += Value;
	}

	return Re;
}


double CTSPSGA::GetDistance(POINT pt1, POINT pt2)
{	
	return sqrt((double)( (pt2.x - pt1.x)*(pt2.x - pt1.x) + (pt2.y - pt1.y)*(pt2.y - pt1.y))); 
}


int CTSPSGA::WheelSelect(void)
{	
	double pick = Crand((unsigned)time( NULL ));
	double sum = 0.0;
	int i = 0;

	if (m_SumFitness != 0)
	{
		for (i=0; (sum < pick) && (i < m_PopSize); i++)
		{
			sum +=  m_POldPop[i].fitness / m_SumFitness;
		}
	}
	else
	{
		i  = 1 + rand() % m_PopSize; 
	}

	return (i - 1);
}

int CTSPSGA::TourSelect(void)
{	
	int Best;
	double BestFit;
	int j;

	Best = rand()%m_PopSize;
	BestFit = m_POldPop[Best].fitness;

	for (int i=1; i<m_Tour; i++)
	{
		j = rand()%m_PopSize;
		
		if (BestFit > m_POldPop[j].fitness)
		{
			BestFit = m_POldPop[j].fitness;
			Best = j;
		}
	}
	
	return Best;
}

int CTSPSGA::CrossOver(const char *Parent1, const char *Parent2, char *Child1, char *Child2)
{	
	int  Len = strlen(Parent1);
	int  Pos1 = 1 + rand() % (m_ChromLen - 2);
	int  Pos2 = 0;
	do
	{
		Pos2 = 1 + rand() % (m_ChromLen - 2);
	}while (abs(Pos1 - Pos2) == 0);

	double pick = Crand((unsigned)time( NULL ));

	if (pick > m_Pcross)
	{
		memcpy(Child1, Parent1, Len);
		memcpy(Child2, Parent2, Len);
		return 0;
	}
	

	if (Pos1 > Pos2)
	{
		int tem = Pos1;
		Pos1 = Pos2;
		Pos2 = tem;
	}

	//中间部分保存不变
	memcpy(Child1+Pos1, Parent1+Pos1, Pos2 - Pos1);
	memcpy(Child2+Pos1, Parent2+Pos1, Pos2 - Pos1);

	Produce(Parent2, Child1, Pos1, Pos2);
	Produce(Parent1, Child2, Pos1, Pos2);

	return Pos1*1000+Pos2;
}


int CTSPSGA::Produce(const char *Parent, char *Child, int Pos1, int Pos2)
{
	char *pCh = new char[m_ChromLen];
	memset(pCh, 0, m_ChromLen);


	//从Parent中第二个交叉点开始生成排列顺序,当到达表尾时,
	//返回表头继续
	memcpy(pCh, Parent+Pos2, m_ChromLen - Pos2);
	memcpy(pCh + m_ChromLen - Pos2, Parent, Pos2);
	
	//从Parent中去除 Child 中已有的排列
	for (int i=0; i<m_ChromLen; i++)
	{
		for(int j=0; j<Pos2 - Pos1; j++)
		{
			if (pCh[i] == Child[Pos1+j])
			{
				pCh[i] = '0';
			}
		}
	}

	//将pCh中的排列顺序,复制到在Child中从第二个交叉点起开始,
	//到达表尾时,再从表头开始
	int k = Pos2;
	for (int i=0; i<m_ChromLen; i++)
	{
		if (pCh[i] != '0')
		{
			Child[k] = pCh[i];
			k = (k + 1) % m_ChromLen;
		}
	}

	delete []pCh;
	pCh = NULL;

	return 0;
}


void CTSPSGA::Generation(void)
{

	int  mate1;
	int  mate2;
	int  jCross;
	int  j = 0;

	PreSelect();

	do
	{
		mate1 = WheelSelect(); 
		mate2 = WheelSelect();

		//mate1 = TourSelect();
		//mate2 = TourSelect();

		jCross = CrossOver(m_POldPop[mate1].pChrom, 
						   m_POldPop[mate2].pChrom,
						   m_PNewPop[j].pChrom, 
 						   m_PNewPop[j+1].pChrom);
	

		ComputeFitness(m_PNewPop+j);
		m_PNewPop[j].parent[0] = mate1 + 1;
		m_PNewPop[j].parent[1] = mate2 + 1;
		m_PNewPop[j].xsite = jCross;

		ComputeFitness(m_PNewPop+j+1);
		m_PNewPop[j+1].parent[0] = mate1 + 1;
		m_PNewPop[j+1].parent[1] = mate2 + 1;
		m_PNewPop[j+1].xsite = jCross;

		j = j + 2;

	}while (j < (m_PopSize - 1));
}


void CTSPSGA::PreSelect(void)
{
	m_SumFitness = 0.0;

	for (int i=0; i<m_PopSize; i++)
	{
		m_SumFitness += m_POldPop[i].fitness;	
	}
}


void CTSPSGA::Statistics(PINDIVIDUAL pIndividual)
{
	m_SumFitness = 0.0;
	m_MinFitness = pIndividual[0].fitness;
	m_MaxFitness = pIndividual[0].fitness;

	for (int i=0; i<m_PopSize; i++)
	{
		m_SumFitness += pIndividual[i].fitness;
		
		if (m_MinFitness > pIndividual[i].fitness)
		{
			m_MinFitness = pIndividual[i].fitness;
		}

		if (m_MaxFitness < pIndividual[i].fitness)
		{
			m_MaxFitness = pIndividual[i].fitness;
		}

		if (pIndividual[i].fitness > m_BestFit.fitness)
		{
			m_BestFit.fitness = pIndividual[i].fitness;
			m_BestFit.generation = m_Gen;
			strcpy(m_BestFit.pChrom, pIndividual[i].pChrom);
		}
	}

	m_AvgFitness = m_SumFitness / (double) m_PopSize;
}

void CTSPSGA::Report(void)
{

	double OldValue = 0.0;
	double NewValue = 0.0;
	
	/*
	for (int i=0; i<m_PopSize; i++)
	{
		OldValue = GetAllDistance(m_POldPop[i].pChrom);
		NewValue = GetAllDistance(m_PNewPop[i].pChrom);

		fprintf(m_File, "\n第%d个个体\n", i+1);
		fprintf(m_File, "原始  编码：%s \n", m_POldPop[i].pChrom);
		fprintf(m_File, "新一代编码：%s \n", m_PNewPop[i].pChrom);

		fprintf(m_File, "原始  适应度：%f 旅程长度为:%f\n", m_POldPop[i].fitness, OldValue);
		fprintf(m_File, "新一代适应度：%f 旅程长度为:%f\n", m_PNewPop[i].fitness, NewValue);

		fprintf(m_File, "新一代父体1：%d  父体2：%d   交叉点：%d\n", 
				m_PNewPop[i].parent[0],
				m_PNewPop[i].parent[1],
				m_PNewPop[i].xsite);
			
	}
*/
	//OldValue = GetAllDistance("ACLBIQFTMEPRGSOJHDKN");
	OldValue = GetAllDistance(m_BestFit.pChrom);
	fprintf(m_File, "第%d代统计:\n", m_Gen);
	fprintf(m_File, "最小适应度：%f   最大适应度：%f   平均适应度：%f\n",
         m_MinFitness, m_MaxFitness ,m_AvgFitness);
	fprintf(m_File, "\n迄今发现最佳个体所在代数： %d   最佳适应度： %f   编码：%s  旅程长度为:%f\n",
		m_BestFit.generation,  m_BestFit.fitness, m_BestFit.pChrom, OldValue);

	printf("第%d代统计:\n", m_Gen);
	printf("最小适应度：%f   最大适应度：%f   平均适应度：%f\n",
         m_MinFitness, m_MaxFitness ,m_AvgFitness);
	printf("\n迄今发现最佳个体所在代数： %d   最佳适应度： %f   编码：%s  旅程长度为:%f\n",
		m_BestFit.generation,  m_BestFit.fitness, m_BestFit.pChrom, OldValue);
}

extern int Run;
extern int OpCnt;

void CTSPSGA::StartRun(void)
{
	PINDIVIDUAL p = NULL;
	
	m_File = fopen("tt.txt", "a+");

	InitPop();

	for (m_Gen=0; m_Gen<m_Maxgen; m_Gen++)
	{
		Generation();
		Statistics(m_PNewPop);
		//Report();
			
		p = m_PNewPop;
		m_PNewPop = m_POldPop;
		m_POldPop = p;
	}

	double OldValue = GetAllDistance(m_BestFit.pChrom);
	
	if (OldValue < 24.53)
	{
		OpCnt ++;	
	}

	fprintf(m_File, "\n运行第%d次\n", Run+1);
	fprintf(m_File, "\n迄今发现最佳个体所在代数： %d   最佳适应度： %f   编码：%s  旅程长度为:%f\n",
		m_BestFit.generation,  m_BestFit.fitness, m_BestFit.pChrom, OldValue);
	fprintf(m_File, "已有最优个数:%d\n", OpCnt);


	printf("\n运行第%d次\n", Run+1);
	printf("\n迄今发现最佳个体所在代数： %d   最佳适应度： %f   编码：%s  旅程长度为:%f\n",
		m_BestFit.generation,  m_BestFit.fitness, m_BestFit.pChrom, OldValue);
	printf("已有最优个数:%d\n", OpCnt);

	fclose(m_File);
}

int CTSPSGA::SetPopSize(int Size)
{
	int Re = m_PopSize;
	m_PopSize = Size;
	return Re;
}

int CTSPSGA::GetPopSize(void)
{
	return m_PopSize;
}

int CTSPSGA::SetChromLen(int ChromLen)
{
	int Re = m_ChromLen;
	m_ChromLen = ChromLen;
	return Re;
}

int CTSPSGA::GetChromLen(void)
{
	return m_ChromLen;
}

int CTSPSGA::SetMaxgen(int Maxgen)
{
	int Re = m_Maxgen;
	m_Maxgen = Maxgen;
	return Re;
}

int CTSPSGA::GetMaxgen(void)
{
	return m_Maxgen;
}

double CTSPSGA::SetPcross(double Pcross)
{
	double Re = m_Pcross;
	m_Pcross = Pcross;
	return Re;
}

double CTSPSGA::GetPcross(void)
{
	return m_Pcross;
}

double CTSPSGA::SetPmutation(int Pmutation)
{
	double Re = m_Pmutation;
	m_Pmutation = Pmutation;
	return Re;
}

double CTSPSGA::GetPmutation(void)
{
	return m_Pmutation;
}

int CTSPSGA::PrintPops(void)
{	
	for (int i=0; i<m_PopSize; i++)
	{
		printf("%d | fitness: %f\n", i, m_POldPop[i].fitness);
	}
	return 0;
}