cgaqueen.cpp

用遗传算法解决八皇后问题！ 有比较详细的注释！ 还有有关遗传算法理论的描述。

#include "CgaQueen.h"

CgaQueen::CgaQueens(double CrossRate,double MutationRate,int ChromoLength,int PopSize)
{
	m_dCrossRate = CrossRate;

	m_dMutationRate = MutationRate;

	m_iChromoLength = ChromoLength;

	m_iPopSize = PopSize;

	m_dTotalFitnessScore = 0.0;

	m_dBestFitnessScore = 1.0;

	m_iGeneration = 0;

	m_iGeneLength = 0;

	m_iGroup = 0;

	m_bBusy = true;

	m_bSolved = false;

	CreateStartPopulation();
}

void CgaQueen::CreateStartPopulation()
{
	srand(rand());
	CGenome *temp;
	for(int i = 0; i < m_iPopSize; i++)
		//temp.CGnome(Queen);
	{
		temp = new CGenome;
		temp->CGenom(m_iChromoLength);
		m_vecGenomes.push_back(*temp);
	}

}

void CgaQueen::ShowChromo()
{
	for(m_vecGenomes_it = m_vecGenomes.begin();
		m_vecGenomes_it != m_vecGenomes.end();
		m_vecGenomes_it++)
	{
		m_vecGenomes_it->ShowBits();
	}
}

bool CgaQueen::UpdateFitnessScores()
{
	int i = 0;
	int wrong = 0;
	m_dTotalFitnessScore = 0;
	for( i = 0; i < m_iPopSize; i++)
	{
		//*
		m_vecGenomes[i].UpdateFitnessScore();
		if(m_vecGenomes[i].dFitness == m_dBestFitnessScore)
		{
			m_CSolve = m_vecGenomes[i];
			return true;
		}
		//*/
		m_dTotalFitnessScore+=m_vecGenomes[i].dFitness;
	}
	return false;

}

int CgaQueen::RouletteWheelSelection()
{
	int num = 0;
	//srand(rand());
	double fSlice = (double)(rand()%(int)(m_dTotalFitnessScore*1000))/1000;
	double cfTotal = 0;
	for(int i = 0; i < m_iPopSize; i++)
	{
		cfTotal +=  m_vecGenomes[i].dFitness;
		if(cfTotal > fSlice)
		{
			num = i;
			break;
		}

	}
	return num;
}
void CgaQueen::CrossOverPMX(vector<int>&mum,vector<int>&dad,vector<int>&baby1,vector<int>&baby2)
{

		//不进行杂交的情况
	if((double)(rand()%1000)/1000 < m_dCrossRate || mum == dad)
	{ 
		baby1 = dad;
		baby2 = mum;
		return;
	}
	//杂交
	//srand(rand());
	int pos1 = rand()%m_iChromoLength;
	int pos2 = rand()%m_iChromoLength;
	do
	{
		pos2 = rand()%m_iChromoLength;
	}while(pos2 > pos1);
	//沿着染色体的长度随机选择一个点断开染色体
	//srand(rand());
	int end = rand()%(m_iChromoLength-pos1);
	//int end = rand()%m_iChromoLength;
	baby1 = dad;
	baby2 = mum;
	int i = 0,j = 0;
	for(i = pos1,j = pos2; i <= pos1 + end && i < m_iChromoLength; i++,j++)
	{
		int gene1 = dad[i];
		int gene2 = mum[j];
		if(gene1 != gene2)
		{
			int *posGene1 = find(baby1.begin(),baby1.end(),gene1);
			int *posGene2 = find(baby1.begin(),baby1.end(),gene2);	
			swap(*posGene1,*posGene2);
			posGene1 = find(baby2.begin(),baby2.end(),gene1);
			posGene2 = find(baby2.begin(),baby2.end(),gene2);
			swap(*posGene1,*posGene2);
		}
	}
	/*
	cout<<"pos1 = "<<pos1<<endl;
	cout<<"end  = "<<end<<endl;
	cout<<"pos2 = "<<pos2<<endl;
	cout<<"dad   = ";
	for(i = 0; i < m_iChromoLength; i++)
	{
		cout<<dad[i]+1<<' ';
	}
	cout<<endl;
	cout<<"mum   = ";
	for(i = 0; i < m_iChromoLength; i++)
	{
		cout<<mum[i]+1<<' ';
	}
	cout<<endl;
	cout<<"baby1 = ";
	for(i = 0; i < m_iChromoLength; i++)
	{
		cout<<baby1[i]+1<<' ';
	}
	cout<<endl;
	cout<<"baby2 = ";
	for(i = 0; i < m_iChromoLength; i++)
	{
		cout<<baby2[i]+1<<' ';
	}
	cout<<endl;
	//*/
}

void CgaQueen::CrossOver(vector<int>&mum,vector<int>&dad,vector<int>&baby1,vector<int>&baby2)
{
	//不进行杂交的情况
	if((double)(rand()%1000)/1000 < m_dCrossRate || mum == dad)
	{
		baby1 = dad;
		baby2 = mum;
		return;
	}
	//杂交
	srand(rand());
	int pos = rand()%m_iChromoLength;
	//沿着染色体的长度随机选择一个点断开染色体
	for(int i = 0; i < pos; i++)
	{
		baby1.push_back(dad[i]);
		baby2.push_back(mum[i]);
	}
	for(i = pos; i < m_iChromoLength; i++)
	{
		baby1.push_back(mum[i]);
		baby2.push_back(dad[i]);
	}
}

void CgaQueen::Mutate(vector<int>&baby)
{
	//根据变异率确定是否变异
	//srand(rand());
	if((double)(rand()%1000)/1000 > m_dMutationRate)
	{
		return;
	}
	/*插入变异
	int pos = rand()%m_iChromoLength;
	int gene = baby[pos];
	baby.erase(baby.begin()+pos);
	int insert_pos = rand()%m_iChromoLength;
	baby.insert(baby.begin()+pos,gene);
	//*/


	//*交换变异
	//选择第一个基因
	int pos1 = rand()%m_iChromoLength;
	//选择第二个基因
	int pos2 = rand()%m_iChromoLength;
	while(pos1 == pos2)
	{
		////srand(rand());
		pos2 = rand()%m_iChromoLength;
	}
	//交换位置
	swap(baby[pos1],baby[pos2]);
	//*/
	/*
	cout<<"变异成功！"<<endl;
	for(int i = 0; i < m_iChromoLength; i++)
	{
		cout<<baby[i]+1<<' ';
	}
	cout<<endl;
	//*/
}

void CgaQueen::Epoach()
{
	//找到可行解了

	if(UpdateFitnessScores() == true)
	{
		m_bSolved = true;
		m_bBusy = false;
		return;
	}
	for(int i = 1; i < m_iPopSize; i++) //收敛到同一个解退出
	{
		if(m_vecGenomes[i].vecBits != m_vecGenomes[0].vecBits)
		{
			break;
		}
	}
	if(i == m_iPopSize)
	{
		m_bSolved = false;
		m_bBusy = false;
		return;
	}
	//创建一个新群体
	int Babies = 0;
	//存储婴儿
	vector<CGenome> vecBabyGenomes;
	//赌轮选择
	while(Babies < m_iPopSize)
	{
		CGenome mum = m_vecGenomes[RouletteWheelSelection()];
		CGenome dad = m_vecGenomes[RouletteWheelSelection()];
	
		CGenome baby1,baby2;
		baby1.CGenom(m_iChromoLength);
		baby2.CGenom(m_iChromoLength);
		//杂交
		//CrossOver(mum.vecBits,dad.vecBits,baby1.vecBits,baby2.vecBits);
		CrossOverPMX(mum.vecBits,dad.vecBits,baby1.vecBits,baby2.vecBits);
		//变异
		Mutate(baby1.vecBits);
		Mutate(baby2.vecBits);
		Babies += 2;
		vecBabyGenomes.push_back(baby1);
		vecBabyGenomes.push_back(baby2);
		/*
		cout<<"mum   = ";
		mum.ShowBits();
		cout<<"dad   = ";
		dad.ShowBits();
		cout<<"baby1 = ";
		baby1.ShowBits();
		cout<<"baby2 = ";
		baby2.ShowBits();
		//*/
	}
	m_vecGenomes = vecBabyGenomes;
	m_iGeneration++;
}