popnode.cpp

遗传算法解中国旅行商问题

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

#include "stdafx.h"
#include "China45.h"
#include "PopNode.h"

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

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

PopNode::PopNode():cost(MAXCOST),fit(0)
{
	chrom=new int[MAXCHROM];
	path=new int[MAXCHROM];
	for(int i=0;i<MAXCHROM;i++) chrom[i]=path[i]=i;
}

PopNode::~PopNode()
{
	delete chrom; delete path;
}

//交换两条基因
void PopNode::SwapNode(PopNode *pop)
{
	PopNode temp;
	temp.CopyNode(this); CopyNode(pop);
	pop->CopyNode(&temp); 
}

//交叉两条基因
void PopNode::CrossTwo(PopNode *pop, int nPos)
{
	int tmpPath[MAXCHROM];
	
	for(int i=1;i<nPos;i++) {
		int temp=chrom[i];
		chrom[i]=pop->chrom[i]; pop->chrom[i]=temp;
	}

	tmpPath[0]=0;for(i=1;i<MAXCHROM;i++) tmpPath[i]=MAXCHROM;
	
	//重新整理pop基因城市位置和路径关系
	for(i=1;i<MAXCHROM;i++)
	{
		//取得第i城市在路径中位置
		int m=pop->chrom[i]; 
		
		//临时路径置入当前城市i
		while(tmpPath[m]!=MAXCHROM) 
		{
			m=(m+1)%MAXCHROM; if(m==0) m=1;
		}
		tmpPath[m]=i;		
	}
	for(i=1;i<MAXCHROM;i++) 
	{
		pop->path[i]=tmpPath[i]; pop->chrom[tmpPath[i]]=i;
	}
	
	//重新整理this基因城市位置和路径关系
	tmpPath[0]=0;for(i=1;i<MAXCHROM;i++) tmpPath[i]=MAXCHROM;
	
	for(i=1;i<MAXCHROM;i++)
	{
		//取得第i城市在路径中位置
		int m=chrom[i]; 
		
		//临时路径置入当前城市i
		while(tmpPath[m]!=MAXCHROM) 
		{
			m=(m+1)%MAXCHROM; if(m==0) m=1;
		}
		tmpPath[m]=i;	
	}

	for(i=1;i<MAXCHROM;i++) 
	{
		path[i]=tmpPath[i]; chrom[tmpPath[i]]=i;
	}
}

//变异操作定义
void PopNode::Varite(int nPos1,int nPos2)
{
	int temp=path[chrom[nPos1]];
	path[chrom[nPos1]]=path[chrom[nPos2]];
	path[chrom[nPos2]]=temp;

	temp=chrom[nPos1];
	chrom[nPos1]=chrom[nPos2];
	chrom[nPos2]=temp;
}

//计算代价
double PopNode::CalcCost(double *distance)
{
	cost=0;
	for(int i=0;i<MAXCHROM-1;i++) 
		cost+=distance[path[i]*MAXCHROM+path[i+1]];

	cost+=distance[path[MAXCHROM-1]*MAXCHROM+path[0]];
	return cost;
}

//复制对象
void PopNode::CopyNode(PopNode *pop)
{
	for(int i=0;i<MAXCHROM;i++) 
	{
		chrom[i]=pop->chrom[i]; path[i]=pop->path[i];
	}
	cost=pop->cost; fit=pop->fit;
}