individual.cpp

用遗传算法解决旅行商问题 用遗传算法解决旅行商问题

#include "Individual.h"

namespace evo{
Individual::Individual(void):cityseq(),value(-1)
{

}

Individual::~Individual(void)
{
	//cout<<"discontruct individual";
	cityseq.~vector();
}

Individual::Individual(VectorInt seq)
:cityseq(seq),value(-1)
{
	
}

Individual::Individual(const Individual &other)
:cityseq(other.cityseq),value(-1)
{
}

Individual& Individual::variate()//变异
{
	int rand1=ranRange(0,CITY_COUNT-1);
	int rand2;
	do
	{
		rand2=ranRange(0,CITY_COUNT-1);
	}while(rand2==rand1);
	//cout<<rand1<<"->"<<rand2<<endl;
	int sum=rand1>rand2?(rand1+rand2+CITY_COUNT):(rand1+rand2);
	int mid=sum/2;
	int temp;
	Individual *pInd=new Individual(*this);//产生新个体
	VectorInt& newvec=pInd->cityseq;
	for(int i=rand1;i<=mid;i++)//对选定的基因片段min->max逆置
	{
		int low=i%CITY_COUNT;
		int hig=(sum-i)%CITY_COUNT;
		temp=newvec.at(low);
		newvec.at(low)=newvec.at(hig);
		newvec.at(hig)=temp;
	}
	return *pInd;
}

Individual & Individual::cross(Individual&  other)//杂交
{
	int rand1=ranRange(0,CITY_COUNT-1);
	int rand2=(rand1+1)%CITY_COUNT;//定长的基因片
	
	int max=rand1>rand2?rand2+CITY_COUNT:rand2;
	//cout<<rand1<<"-->"<<rand2<<"  ";
	Mapii convertTable;//转换表
	Individual *pInd=new Individual(*this);//构造新个体

	for(int i=rand1;i<=max;i++)//从另一个个体拷贝从min->max的编码，并初始化转换表
	{
		int ir=i%CITY_COUNT;
		pInd->cityseq.at(ir)=other.cityseq.at(ir);
		convertTable[other.cityseq.at(ir)]=cityseq.at(ir);
	}

	for(miter mi=convertTable.begin();mi!=convertTable.end();mi++)//寻找嵌套的对应关系,并修改转换表
	{
		int key=(*mi).first;
		int firstkey=key,value;
		miter iter;
		int j=0;
		while((iter=convertTable.find(key))!=convertTable.end())
		{
			key=(*iter).first;
			value=(*iter).second;
			
			//cout<<key<<"-"<<value<<" ";
			if(value==firstkey || key==value)
			{
				key=value;
				break;
			}
			key=value;
			if((j++)==10)
				break;
		}
		convertTable[firstkey]=key;
		//cout<<"|";
	}
	//cout<<endl;
	int size=pInd->cityseq.size();
	for(int i=0;i<size;i++)//通过转换表,修改个体
	{
		if(rand1<rand2 && (i>=rand1 && i<=rand2))
			continue;
		else if(rand1>rand2 && (i>=rand1 || i<=rand2))
			continue;
		else
		{
			int elem=pInd->cityseq.at(i);
			miter iter;
			if((iter=convertTable.find(elem))!=convertTable.end())
			{
				pInd->cityseq.at(i)=(*iter).second;
			}
		}
	}
	return *pInd;
	
}


int Individual::ranRange(int arg1, int arg2)
{
	int max,min;
	if(arg1==arg2)
		return arg1;
	if(arg1>arg2)
	{
		max=arg1;
		min=arg2;
	}
	else
	{
		max=arg2;
		min=arg1;
	}
	int range=max-min;
	
	int random=rand()%(range+1);
	return random+min;

}


void Individual::printIndividual(ostream& cout)
{
	cout<<"[";
	int size=cityseq.size();
	for(int i=0;i<size-1;i++)
		cout<<cityseq[i]<<",";
	cout<<cityseq[size-1]<<"]  适应值："<<calValue()<<endl;
}

void Individual::printIndividual(ofstream& cout)
{
	cout<<"[";
	int size=cityseq.size();
	for(int i=0;i<size-1;i++)
		cout<<cityseq[i]<<",";
	cout<<cityseq[size-1]<<"]  适应值："<<calValue()<<endl;
}

int Individual::calValue()
{
	if(value==-1)
	{
		int size=cityseq.size(),sum=0;
		for(int i=0;i<size-1;i++)
		{
			int city1=cityseq.at(i);
			int city2=cityseq.at(i+1);
			sum+=evo::layout.getDistance(city1,city2);
		}
		sum+=layout.getDistance(cityseq.at(size-1),cityseq.at(0));
		value=sum;
		return value;
	}
	else
		return value;
}

bool Individual::operator==(const Individual & other) const
{
	return this->cityseq==other.cityseq;
}

bool Individual::operator<(Individual &other)
{
	int value1=calValue();
	int value2=other.calValue();
	return value1<value2;
	
}

//bool operator==(const Individual& indi1,const Individual& indi2)
//{
//	return indi1.cityseq==indi2.cityseq;
//}
//
//bool operator<(const Individual& indi1,const Individual& indi2)
//{
//	return indi1.calValue()<indi2.calValue();
//}
}