individual.cpp

遗传算法实现旅行商问题：经典遗传算法解决旅行商问题

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

#include "Individual.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
Individual::Individual()
{
	
}

Individual::Individual(VectorInt vi)
:CitySeq(vi),adap(-1)
{
	
}

Individual::Individual(const Individual& other):CitySeq(other.CitySeq),adap(-1)
{
	
}

Individual::~Individual()
{
	CitySeq.~vector();
}
//ofstream test("test.txt");
Individual& Individual::cross(Individual& other)//PMX交叉算子
{
	Individual *pInd=new Individual(*this);
	int rand1=ranRange(0,CITYCOUNT-1);
	int rand2=(rand1+1)%CITYCOUNT;
	int max=rand1<rand2?rand2:rand2+CITYCOUNT;
	MapInt convertTable;

//	test<<endl;
//	test<<rand1<<"---->"<<rand2<<endl;

	for (int i=rand1;i<=max;i++)
	{
		int ir=i%CITYCOUNT;
		pInd->CitySeq.at(ir)=other.CitySeq.at(ir);
		convertTable[other.CitySeq.at(ir)]=CitySeq.at(ir);
	}

//	this->printIndividual(test);
//	other.printIndividual(test);
//	pInd->printIndividual(test);
//	test<<endl;

	for (miter mi=convertTable.begin();mi!=convertTable.end();mi++)
	{
		int key=(*mi).first;
		int firstkey=key;
		int value;
		miter mit;
		while ((mit=convertTable.find(key))!=convertTable.end())
		{
			key=(*mit).first;
			value=(*mit).second;
			if (key==value || firstkey==value)
			{
				key=value;
				break;
			}
			key=value;
		}
		convertTable[firstkey]=key;
	}

	int size=CitySeq.size();
	for (i=0;i<size;i++)
	{
		if (rand1<rand2 && (i>=rand1 && i<=rand2))
			continue;
		if(rand1>rand2 && (i>=rand1 || i<=rand2))
			continue;
		else
		{
			int elem=pInd->CitySeq.at(i);
			miter mit;
			if ((mit=convertTable.find(elem))!=convertTable.end())
			{
				pInd->CitySeq.at(i)=(*mit).second;
			}
		}
	}	

//	pInd->printIndividual(test);

	return *pInd;
}

Individual& Individual::variate()////逆置
{
	int rand1=ranRange(0,CITYCOUNT-1);
	int rand2;
	do 
	{
		rand2=ranRange(0,CITYCOUNT-1);
	} while (rand1==rand2);
	int sum=rand1<rand2?(rand1+rand2):(rand1+rand2+CITYCOUNT);
	int mid=sum/2;
	int temp;
	Individual *pInd=new Individual(*this);
	VectorInt& vi=pInd->CitySeq;
	for (int i=rand1;i<=mid;i++)
	{
		int low=i%CITYCOUNT;;
		int high=(sum-i)%CITYCOUNT;
		temp=vi.at(low);
		vi.at(low)=vi.at(high);
		vi.at(high)=temp;
	}

	return *pInd;
}

int Individual::CalValue()
{
	int size=CitySeq.size();
	int sum=0;
	int city1,city2;
	for (int i=0;i<size;i++)
	{
		if(i!=size-1)
		{
			city1=CitySeq.at(i);
			city2=CitySeq.at(i+1);
			sum+=layout.getDistance(city1,city2);
		}
		else
		{
			city1=CitySeq.at(i);
			city2=CitySeq.at(0);
			sum+=layout.getDistance(city1,city2);
		}
	}
//	cout<<sum<<endl;
	return sum;
}

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

bool Individual::operator<(Individual& other)
{
	int v1=this->CalValue();
	int v2=other.CalValue();
	return v1<v2;
}

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

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



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