count.cpp

用遗传算法实现巡回旅行商（邮差问题）的程序。可自由设置城市位置及数目

// count.cpp: implementation of the count class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "travelSP.h"
#include "count.h"
#include "item.h"
#include "stdlib.h"
#include "stdio.h"
#include "math.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

count::count()
{

}

count::~count()
{

}
///////////////////////////////////////////init//////
void count::init()
{
	int i,j;
	FILE *fp;
	CString str1,str2;

	city=(CityMsg *)calloc(sizeof(struct CityMsg),maxindiv);
	newcity=(CityMsg *)calloc(sizeof(struct CityMsg),maxindiv);

	str1.Format("城市数：%3d     个 体 数： %d\n",citysum,maxindiv);
	str2+=str1;
	str1.Format("总代数：%3d     crossrate: %.4lf\n",maxgen,crossrate);
	str2+=str1;
	str2+="\n初始基因系列:\n\n";

	for(i=0;i<maxindiv;i++)
	{
		city[i].citynum=(int *)calloc(sizeof(int),citysum);
		newcity[i].citynum=(int *)calloc(sizeof(int),citysum);

		for(j=0;j<citysum;j++)
			city[i].citynum[j]=setcitynum(i,j);
			
	}

	setfitness(city);
	
	for(i=0;i<maxindiv;i++)
	{
		for(j=0;j<citysum;j++)
		{
			str1.Format("%d ",city[i].citynum[j]);
			str2+=str1;
		}

		str1.Format("   fit: %.4lf\n",city[i].fitness);
		str2+=str1;
	}

	fp=fopen("calcdata.txt","w");
	fprintf(fp,"%s",str2);
	fclose(fp);
//	AfxMessageBox(str2);

	}
/////////////////////////init///////////////////////
int count::setcitynum(int ii,int n)
{ 
	item item1;
	int i,j,*mask,value,p,num=0;
	if(n==0)
	{
		value=(int)(item1.random()*citysum);
		if(value==citysum)value=citysum-1;
	}
	else
	{
		mask=(int *)calloc(sizeof(int),citysum-n);

		for(i=0;i<citysum;i++)
		{	
			p=0;
			for(j=0;j<n;j++)
				if(city[ii].citynum[j]==i)
					p=1;
			
			if(p!=1)
			{
				mask[num]=i;
				num++;
			}
		}
		i=(int)(item1.random()*(citysum-n));
		if(i==citysum-n)i=citysum-n-1;
		value=mask[i];
		free(mask);
	}
	
	return value;
}
///////////////////////////////////////////////////set fitness.

void count::countaroundlength(struct CityMsg *pcity)
{
	int i,j,x0,y0,x,y,headx,heady;
	double length;

	if(citysum==0)
	{
		for(i=0;i<maxindiv;i++)
			pcity[i].fitness=0;
		return;
	}

	for(i=0;i<maxindiv;i++)
	{
		headx=x0=citysite[pcity[i].citynum[0]].x;
		heady=y0=citysite[pcity[i].citynum[0]].y;
		length=0;
		for(j=1;j<citysum;j++)
		{
			x=citysite[pcity[i].citynum[j]].x;
			y=citysite[pcity[i].citynum[j]].y;
			length+=sqrt((double)((x-x0)*(x-x0)+(y-y0)*(y-y0)));
			x0=x; y0=y;
		}
		length+=sqrt((double)((x0-headx)*(x0-headx)+(y0-heady)*(y0-heady)));
		pcity[i].fitness=length;			
	}

}

void count::setfitness_t(struct CityMsg *pcity)//only use in init function: 适应度参数
{
	int i;
	double maxlength=0;
	countaroundlength(pcity);
	for(i=0;i<maxindiv;i++)
		if(pcity[i].fitness>maxlength)
			maxlength=pcity[i].fitness;
	fit_t=maxlength*1.01;
	
}

void count::setfitness(struct CityMsg *pcity)//set the fitness of all individual in a generation.
{
	int i;
	setfitness_t(pcity);
	for(i=0;i<maxindiv;i++)
		pcity[i].fitness=fit_t-pcity[i].fitness;

}

////////////////////////////star run  function  ////////////////////////////
void count::producegen()//produce a new generation.
{
	int sdi1,sdi2;
	int i=0,j;
	item itemt;
	while(i<maxindiv)
	{
		sdi1=selectindiv();sdi2=selectindiv();
		if(itemt.flip(crossrate)==1)
			crossover(sdi1,sdi2,i,i+1);
		else
			for(j=0;j<citysum;j++)
			{
				newcity[i].citynum[j]=city[sdi1].citynum[j];
				newcity[i+1].citynum[j]=city[sdi2].citynum[j];
			}
		
		i+=2;
	}
	variation();
	setfitness(newcity);
	
}


int count::selectindiv()//select a individual from the parent generation.
{
	double totalfitness,mask,mask2;
	int i;
	item itemt;
	totalfitness=0;
	mask=0;
	for(i=0;i<maxindiv;i++)
		totalfitness+=city[i].fitness;
	i=0; mask2=itemt.random();
	if(totalfitness!=0)
		do{
			mask+=city[i].fitness/totalfitness;
			i++;
		}while(mask<mask2&&i<maxindiv);
	else
	{
		i=(int)(itemt.random()*maxindiv);
		if(i==maxindiv)i=maxindiv-1;
		i++;
	}
	return i-1;
}

void count::crossover(int sdi1,int sdi2,int nd1,int nd2)
{
	int jcross1,jcross2, i,j;
	int k,p;
	item itemt;
	jcross1=(int)(itemt.random()* citysum);
	jcross2=(int)(itemt.random()* citysum);
	if(jcross1==citysum)jcross1=citysum-1;
	if(jcross2==citysum)jcross2=citysum-1;
	if(jcross1>jcross2)
	{
		i=jcross1;
		jcross1=jcross2;
		jcross2=i;
	}

	for(i=jcross1;i<=jcross2;i++)
	{
		newcity[nd1].citynum[i]=city[sdi1].citynum[i];
		newcity[nd2].citynum[i]=city[sdi2].citynum[i];
	}
//////
	i=jcross2+1;
	if(i>=citysum)i=0;
	j=i;  
	while(i!=jcross1)
	{
		p=0;
		for(k=jcross1;k<=jcross2;k++)
			if(newcity[nd1].citynum[k]==city[sdi2].citynum[j])
				p=1;
		
		if(p!=1)
		{
			newcity[nd1].citynum[i]=city[sdi2].citynum[j];
			i++;j++;
			if(i>=citysum)i=0;
			if(j>=citysum)j=0;
		}
		else
		{
			j++;
			if(j>=citysum)j=0;
		}
	}

///////
	i=jcross2+1;
	if(i>=citysum)i=0;
	j=i;  
	while(i!=jcross1)
	{
		p=0;
		for(k=jcross1;k<=jcross2;k++)
			if(newcity[nd2].citynum[k]==city[sdi1].citynum[j])
				p=1;
		
		if(p!=1)
		{
			newcity[nd2].citynum[i]=city[sdi1].citynum[j];
			i++;j++;
			if(i>=citysum)i=0;
			if(j>=citysum)j=0;
		}
		else
		{
			j++;
			if(j>=citysum)j=0;
		}
	}
/////////

}

void count::variation()
{
	item itemt;
	int n,m,i,j,variation_num,tmpcitynum;
	float variation_rate=0.033f;//变异率
	variation_num=(int)(variation_rate*maxindiv);
	for(m=0;m<variation_num;m++)
	{
		n=(int)(itemt.random()*maxindiv);
		if(n==maxindiv)n--;
		i=(int)(itemt.random()*citysum);
		j=(int)(itemt.random()*citysum);
		if(i==citysum)i--;
		if(j==citysum)j--;
		if(i==j&&i==0)j++;
		else if(i==j)i--;

		tmpcitynum=newcity[n].citynum[i];
		while(i!=j)
		{
			if(i+1<citysum)
			{
				newcity[n].citynum[i]=newcity[n].citynum[i+1];
				i++;
			}
			else 
			{
				newcity[n].citynum[i]=newcity[n].citynum[0];
				i=0;
			}
		}
		newcity[n].citynum[j]=tmpcitynum;
	}
}