population.cpp

用遗传算法求物流配送中心解选址问题．有运行结果

// Population.cpp: implementation of the CPopulation class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Population.h"

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

CPopulation::CPopulation(): MaxGeneration(100),Pc(0.8),Pm(0.05)
{
	
	int i,j;
	ifstream in1("dij.txt"),in2("Fi.txt"),in3("Qi.txt");
	srand(time(0));

	
	for(i=0;i<M;i++)
		for(j=i;j<M;j++)
		{
			in1>>m_d[i][j];
			m_d[j][i]=m_d[i][j];
		}

	for(i=0;i<M;i++)
	{
		in2>>m_F[i];
		in3>>m_Q[i];
	}

	for(i=0;i<PopSize;i++)
	{
		m_individual[i].InitializePop();
		m_individual[i].CaculateObjectValue(m_d,m_F,m_Q);
	}
	
	m_currentPopSize=PopSize;
	m_currentGen=0;
}

void CPopulation::Crossover()
{
	int i,j,k;
	int index[PopSize];
	int point,t;
	int point1,point2;
	double p;
	vector<int> temp1,temp2,temp3,temp4;
	for(i=0; i<PopSize; i++)
		index[i]=i;
	for(i=0; i<PopSize; i++)
	{
		point=rand()%(PopSize-i);
		t=index[i];
		index[i]=index[i+point];
		index[i+point]=t;
	}
	for(i=0; i<PopSize-1; i+=2)
	{
		p=rand()%1000/1000.0;
		if(p<Pc)
		{
			point1=rand()%M;
			point2=rand()%M;
			if(point1>point2)
			{
				t=point1;
				point1=point2;
				point2=t;
			}
			temp1.clear();
			temp2.clear();
			temp3.clear();
			temp4.clear();
			for(j=point2+1;j<M;j++)
			{
				temp3.push_back(m_individual[index[i]].m_gene[j]);
				temp4.push_back(m_individual[index[i+1]].m_gene[j]);
			}
			
			for(j=0;j<=point2;j++)
			{
				temp3.push_back(m_individual[index[i]].m_gene[j]);
				temp4.push_back(m_individual[index[i+1]].m_gene[j]);
			}
			for(j=point1;j<=point2;j++)
			{
				temp1.push_back(m_individual[index[i]].m_gene[j]);
				temp2.push_back(m_individual[index[i+1]].m_gene[j]);
			}
			for(j=0;j<temp1.size();j++)
				for(k=0;k<temp4.size();k++)
					if(temp1[j]==temp4[k])
						temp4.erase(temp4.begin()+k);
			for(j=0;j<temp2.size();j++)
				for(k=0;k<temp3.size();k++)
					if(temp2[j]==temp3[k])
						temp3.erase(temp3.begin()+k);
			for(k=point2+1;k<M;k++)
			{
				m_individual[index[i]].m_gene[k]=temp4[k-point2-1];
				m_individual[index[i+1]].m_gene[k]=temp3[k-point2-1];
			}
			for(k=0;k<point1;k++)
			{
				m_individual[index[i]].m_gene[k]=temp4[M-point2-1+k];
				m_individual[index[i+1]].m_gene[k]=temp3[M-point2-1+k];
			}
			m_individual[index[i]].CaculateObjectValue(m_d,m_F,m_Q);
			m_individual[index[i+1]].CaculateObjectValue(m_d,m_F,m_Q);
		}
	}
}

void CPopulation::Mutation()
{
	int i,point1,point2,t;
	double p;
	CChromosome chrom;
	for(i=0;i<PopSize;i++)
	{
		p=rand()%1000/1000.0;
		if(p<Pm)
		{
			point1=rand()%M;
			point2=rand()%M;
			t=m_individual[i].m_gene[point1];
			m_individual[i].m_gene[point1]=m_individual[i].m_gene[point2];
			m_individual[i].m_gene[point2]=t;
			m_individual[i].CaculateObjectValue(m_d,m_F,m_Q);

		}
	}
}

void CPopulation::Wheel_SelectIndividual()//轮盘赌选择
{
	double sum,temp;
	int index,i;
	CChromosome chrom[PopSize];
	double individual[PopSize];
	sum=0;
	for(i=0; i<PopSize; i++)
		sum+=m_individual[i].m_fitness;
	individual[0]=m_individual[0].m_fitness/sum;
	for(i=1; i<PopSize; i++)
		individual[i]=individual[i-1]+(m_individual[i].m_fitness/sum);
	for(i=0; i<PopSize; i++)
	{
		temp=rand()%1000/1000.0;
		index=0;
		while(temp>individual[index])
		{
			index++;
		}
		chrom[i]=m_individual[index];
	}
	for(i=0; i<PopSize; i++)
		m_individual[i]=chrom[i];
}

void CPopulation::FindBestAndWorstIndividual()
{
	int i,best=0,worst=0;
	for(i=0;i<PopSize;i++)
	{
		if(m_individual[best]>m_individual[i])
			best=i;
		if(m_individual[worst]<m_individual[i])
			worst=i;
	}
	m_bestIndex=best;
	m_worstIndex=worst;	
}

void CPopulation::Sort_SelectIndividual()
{
	int i,j,k;
	CChromosome t;
	for(i=m_currentPopSize-1;i>=0;i--)
	{
		k=0;
		for(j=0;j<=i;j++)
		{
			if(m_individual[j]>m_individual[k])
				k=j;
		}
		if(k!=i)
		{
			t=m_individual[i];
			m_individual[i]=m_individual[k];
			m_individual[k]=t;
		}
	}
	if(m_currentBestIndividual<m_individual[PopSize-1])
		m_individual[PopSize-1]=m_currentBestIndividual;
	if(m_individual[0]<m_currentBestIndividual)
		m_currentBestIndividual=m_individual[0];
	m_currentPopSize=PopSize;
}

void CPopulation::Run()
{
	int i,j;
	m_currentGen=0;
	
	FindBestAndWorstIndividual();
	m_currentBestIndividual=m_individual[m_bestIndex];
	cout<<"GEN="<<m_currentGen<<":";	
	cout<<m_currentBestIndividual.m_objectValue<<endl;
	for(i=1;i<MaxGeneration;i++)
	{
		m_currentGen=i;
		Crossover();
		Mutation();
		Wheel_SelectIndividual();
		FindBestAndWorstIndividual();
		if(m_currentBestIndividual<m_individual[m_worstIndex])
			m_individual[m_worstIndex]=m_currentBestIndividual;
		if(m_currentBestIndividual>m_individual[m_bestIndex])
			m_currentBestIndividual=m_individual[m_bestIndex];
		
		cout<<"GEN="<<m_currentGen<<":";
		cout<<m_currentBestIndividual.m_objectValue<<',';
		for(j=0;j<m_currentBestIndividual.m_gene.size();j++)
			cout<<m_currentBestIndividual.m_gene[j]<<',';
		cout<<endl;
	}
}

CPopulation::~CPopulation()
{

}