genalg.cpp

来自「用C++开发的一个人工神经网络小游戏」· C++ 代码 · 共 575 行

// GenAlg.cpp: implementation of the CGenAlg class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "EludeObstacle.h"
#include "GenAlg.h"

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

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


bool operator<(SGenome& lhs, SGenome& rhs)
{
	return (lhs.dFitness < rhs.dFitness);
}

extern int globe_dMaxPerturbation;
extern int globe_iNumElite;
extern double globe_dBigMutationRate;
extern double globe_dBigPerturbation;
extern double globe_dMutationActionRate;
extern int globe_numGen;
extern int globe_initTimeRange;
extern double globe_dMutationInsert;
extern int globe_dMutationInsertTimeRange;

/*
double abs(double num)
{
	if(num>0)return num;
	else return -num;
}
*/

//returns a random integer between x and y
inline int	  RandInt(int x,int y) {return rand()%(y-x+1)+x;}

//returns a random float between zero and 1
inline double RandFloat()		   {return (rand())/(RAND_MAX+1.0);}

//returns a random float in the range -1 < n < 1
inline double RandomClamped()	   {return RandFloat() - RandFloat();}


//类的构造函数
CGenAlg::CGenAlg()				 
{
}


void CGenAlg::init(int popsize, double MutRate, double CrossRate, int GenLenght)
{	
	m_iPopSize = popsize;
	m_dMutationRate = MutRate;
	m_dCrossoverRate = CrossRate;
	m_iChromoLength = GenLenght;
	m_dTotalFitness = 0;
	m_cGeneration = 0;
	m_iFittestGenome = 0;
	m_dBestFitness = 0;
	m_dWorstFitness = 99999999;
	m_dAverageFitness = 0;
	//记住加上这命令
	m_vecPop.clear();
	for (int i=0; i<m_iPopSize; i++)
	{		
		m_vecPop.push_back(SGenome());//结构体的构造函数本身就已经把适应性评分初始化为0,大家可以回顾一下前面
		
		//把所有的权值初始化为-1~1的随机数
		for (int j=0; j<m_iChromoLength; j++)
		{
			m_vecPop[i].action.push_back(rand()%5);
			m_vecPop[i].time.push_back(rand()%globe_initTimeRange + 3);
		}
	}
}



//基因突变函数
void CGenAlg::MutateTime(vector<double> &chromo)
{
	//遵循预定的突变概率,对基因进行突变
	for (int i=0; i<globe_numGen; ++i)
	{
		//如果发生突变的话
		if (RandFloat() < m_dMutationRate)
		{
			//使该权值增加或者减少一个很小的数值
			chromo[i] += (RandomClamped() * globe_dMaxPerturbation);
			if(chromo[i] < 0){chromo[i] = 0;}
		}
	}
}

void CGenAlg::MutateAction(vector<int> &chromo)
{
	//遵循预定的突变概率,对基因进行突变
	for (int i=0; i<globe_numGen; ++i)
	{
		//如果发生突变的话
		if (RandFloat() < globe_dMutationActionRate)
		{
			chromo[i] = rand()%5;
		}
	}
}

/*
void Mutate(const vector<double> &originalAction , const vector<double> &originalTime,vector<double> &action , vector<double> &time)
{
	int sequence = rand()%globe_numGen;
	int control = 0;
	for(int i = 0;i < globe_numGen-1;i++)
	{
		if(i < sequence)
		{
			action[i] = originalAction[i];
			time[i] = originalTime[i];
		}
		else if(i > sequence)
		{
			action[i+1] = originalAction[i];
			time[i+1] = originalTime[i];
		}
		else
		{
			action[i] = rand()%5;
			time[i] = rand()%10;
		}
	}
}

  */

/*
void CGenAlg::MutateAction(vector<double> &chromo)
{
	//遵循预定的突变概率,对基因进行突变
	for (int i=0; i<chromo.size(); ++i)
	{
		//如果发生突变的话
			i = rand()%chromo.size();
			if(rand()%5 != 0)
			{
				if(chromo[i] == 1)
				{
					chromo[i] = 2;
				}
				else if(chromo[i] == 2)
				{
					chromo[i] = 1;
				}
				else if(chromo[i] == 3)
				{
					chromo[i] = 4;
				}
				else if(chromo[i] == 4)
				{
					chromo[i] = 3;
				}
			}
			else
			{
				chromo[i] = 0;
			}

	
	}
}
*/

//转盘函数
SGenome CGenAlg::GetChromoRoulette()
{
	//产生一个0到人口总适应性评分的随机数.
	double Slice = (double)((RandFloat()) * m_dTotalFitness);

	//这个将承载转盘所指向的那个基因.
	SGenome TheChosenOne;
	
	//记录转过的基因的适应性评分的总和
	double FitnessSoFar = 0;

	for (int i=0; i<m_iPopSize; ++i)
	{
		FitnessSoFar += m_vecPop[i].dFitness;
		
		//如果累计分数大于随机数,就选择此时的基因.
		if (FitnessSoFar >= Slice)
		{
			TheChosenOne = m_vecPop[i];
			break;
		}
	}
	
	return TheChosenOne;
}

/*
SGenome CGenAlg::GetChromoRoulette()
{
	//产生一个0到人口总适应性评分的随机数.
	int i = (int)((RandFloat() * 0.5 + 0.5) * m_iPopSize);

	//这个将承载转盘所指向的那个基因.
	SGenome TheChosenOne = m_vecPop[i];
	
	

	return TheChosenOne;
}
*/

void CGenAlg::Crossover(const vector<double> &mum,
                        const vector<double> &dad,
                        vector<double>       &baby1,
                        vector<double>       &baby2,

						const vector<double> &mum2,
                        const vector<double> &dad2,
                        vector<double>       &baby12,
                        vector<double>       &baby22)
{
	//当交叉没有发生或者父母基因组是同一条的时候,只要以父方的基因作为后代就行了
	if ( (RandFloat() > m_dCrossoverRate) || (mum == dad)) 
	{
		baby1 = mum;
		baby2 = dad;
		baby12 = mum2;
		baby22 = dad2;

		return;
	}
	
	//确定交叉的长度
	int cp = RandInt(0, m_iChromoLength - 1);

	//产生子代
	for (int i=0; i<cp; ++i)
	{
		baby1.push_back(mum[i]);
		baby2.push_back(dad[i]);
		baby12.push_back(mum2[i]);
		baby22.push_back(dad2[i]);
	}

	for (i=cp; i<mum.size(); ++i)
	{
		baby1.push_back(dad[i]);
		baby2.push_back(mum[i]);
		baby12.push_back(dad2[i]);
		baby22.push_back(mum2[i]);
	}
	
	return;
}



void CGenAlg::CrossoverAtSplits(const vector<int> &originalAction , 
								const vector<double> &originalTime,
								vector<int> &action , 
								vector<double> &time)
{
	for(int i = 0;i < globe_numGen;i++)
	{
		if (RandFloat() < globe_dMutationInsert)
		{
			if(action.size() >= globe_numGen){return;}
			action.push_back(rand()%5);
			time.push_back(rand()%globe_dMutationInsertTimeRange+5);
		}
		if(action.size() >= globe_numGen){return;}

		int a = originalAction[i];
		if(a != 0 && a != 1 && a != 2 && a != 3 && a != 4){AfxMessageBox("originalAction[i]!!!");}

		action.push_back(originalAction[i]);
		time.push_back(originalTime[i]);
	}

	/*
	//当交叉没有发生或者父母基因组是同一条的时候,只要以父方的基因作为后代就行了
	if ( (RandFloat() > m_dCrossoverRate) || (mum == dad) || (m_vecSplitPoints.size() == 1)) 
	{
		baby1 = mum;
		baby2 = dad;
		
		return;
	}
	
	//确定交叉时切断的两个点
	int tempNum = m_vecSplitPoints.size();
	int cp1 = m_vecSplitPoints[RandInt(0, m_vecSplitPoints.size()-2)];
	int cp2 = m_vecSplitPoints[RandInt(cp1, m_vecSplitPoints.size()-1)];
	
	
	//产生新的一代
	for (int i=0; i<mum.size(); ++i)
	{
		if ( (i<cp1) || (i>=cp2) )
		{
			//keep the same genes if outside of crossover points
			baby1.push_back(mum[i]);
			baby2.push_back(dad[i]);
		}
		
		else
		{
			//switch over the belly block
			baby1.push_back(dad[i]);
			baby2.push_back(mum[i]);
		}
		
	}
	
	return;
	*/
}


//起到初始化的作用
void CGenAlg::Reset()
{

	m_dTotalFitness		= 0;
	m_dBestFitness		= 0;
	m_dWorstFitness		= 9999999;
	m_dAverageFitness	= 0;

}




void CGenAlg::CalculateBestWorstAvTot()
{
	m_cGeneration++;

	m_dTotalFitness = 0;
	
	double HighestSoFar = 0;
	double LowestSoFar  = 9999999;
	
	for (int i=0; i<m_iPopSize; ++i)
	{
		//update fittest if necessary
		if (m_vecPop[i].dFitness > HighestSoFar)
		{
			HighestSoFar	 = m_vecPop[i].dFitness;
			
			m_iFittestGenome = i;

			m_dBestFitness	 = HighestSoFar;
		}
		
		//update worst if necessary
		if (m_vecPop[i].dFitness < LowestSoFar)
		{
			LowestSoFar = m_vecPop[i].dFitness;
			
			m_dWorstFitness = LowestSoFar;
		}
		
		m_dTotalFitness	+= m_vecPop[i].dFitness;
				
	}//next chromo
	
	m_dAverageFitness = m_dTotalFitness / m_iPopSize;
}



void CGenAlg::GrabNBest(int	NBest, vector<SGenome>	&Pop)
{
	//add the required amount of copies of the n most fittest 
	//to the supplied vector
	int i = 0;
	while(i++ != NBest)
	{
			Pop.push_back(m_vecPop[(m_iPopSize) - i]);
	}
}



//以等级为基础的缩放比例函数
void CGenAlg::FitnessScaleRank()
{
	const int FitnessMultiplier = 1;

	//assign fitness according to the genome's position on
	//this new fitness 'ladder'
	for (int i=0; i<m_iPopSize; i++)
	{
		m_vecPop[i].dFitness = i * FitnessMultiplier;
	}

	//recalculate values used in selection
	CalculateBestWorstAvTot();
}




//此函数产生新的一代,见证着整个进化的全过程.
//以父代人口的基因组容器作为参数传进去,该函数将返回新一代额基因组(当然是已经过了优胜劣汰的)
void CGenAlg::Epoch(vector<SGenome> &vecNewPop)
{
	//用类的成员变量来储存父代的基因组(在此之前m_vecPop储存的是不带估值的所有基因组)
	m_vecPop = vecNewPop;
	
	

	//初始化相关变量
	Reset();
	
	//
	//FitnessScaleRank();

	double t = m_vecPop.size();
	double x[5];
	x[0] = m_vecPop[0].dFitness;
	x[1] = m_vecPop[1].dFitness;
	x[2] = m_vecPop[2].dFitness;
	x[3] = m_vecPop[3].dFitness;
	x[4] = m_vecPop[4].dFitness;
	x[5] = m_vecPop[5].dFitness;

	
	//对人口的适应性评分作排序以供以后的适应性评分缩放比例,和杰出人物算法作准备
	sort(m_vecPop.begin(), m_vecPop.end());
	
	//char buf[4];
	//sprintf(buf,"%d&%d", m_vecPop[0].dFitness,m_vecPop[m_vecPop.size()-1].dFitness);
	//AfxMessageBox(buf);


	x[0] = m_vecPop[0].dFitness;
	x[1] = m_vecPop[1].dFitness;
	x[2] = m_vecPop[2].dFitness;
	x[3] = m_vecPop[3].dFitness;
	x[4] = m_vecPop[4].dFitness;
	x[5] = m_vecPop[5].dFitness;
	
	
	x[0] = m_vecPop[m_vecPop.size() - 1 - 0].dFitness;
	x[1] = m_vecPop[m_vecPop.size() - 1 - 1].dFitness;
	x[2] = m_vecPop[m_vecPop.size() - 1 - 2].dFitness;
	x[3] = m_vecPop[m_vecPop.size() - 1 - 3].dFitness;
	x[4] = m_vecPop[m_vecPop.size() - 1 - 4].dFitness;
	x[5] = m_vecPop[m_vecPop.size() - 1 - 5].dFitness;
	/*
	if(m_vecPop[0].vecWeights.size() <= 20)
	{
		for (int control=0;control<m_vecPop[0].vecWeights.size();control++)
		{
			cout<<m_vecPop[m_vecPop.size()-1].vecWeights[control]<<" ";
		}
	}

	cout<<endl;
	*/


	//cout<<"  "<<m_vecPop[m_vecPop.size()-1].vecWeights[0]<<"  "<<m_vecPop[m_vecPop.size()-1].vecWeights[1]<<endl;
	
	//计算最好,最坏,平均,和总的适应性评分
	CalculateBestWorstAvTot();
	
	//创建一个新的容器去储存新的人口的基因组
	//vector <SGenome> vecNewPop;	
	vecNewPop.clear();

	//这里实现杰出人物算法(如果他们不是偶数的话会发生冲突)
	//优先把优良品种放进容器里面
	GrabNBest(globe_iNumElite, vecNewPop);
	
	//产生新一代的所有基因组
	while (vecNewPop.size() < m_iPopSize)
	{
		//转盘随机抽出两个基因
		SGenome mum = GetChromoRoulette();
		SGenome dad = GetChromoRoulette();
		
		//创建两个子代基因组
		vector<double> baby1_time, baby2_time;
		vector<int> baby1_action,baby2_action;

		//交叉父方的基因和母方的基因
		//CrossoverAtSplits(mum.action, dad.action, baby1, baby2);
		
		/*
		baby1_action = dad.action;
		baby2_action = mum.action;
		baby1_time = dad.time;
		baby2_time = mum.time;
		*/
		
		
		CrossoverAtSplits(dad.action,dad.time,baby1_action,baby1_time);
		CrossoverAtSplits(mum.action,mum.time,baby2_action,baby2_time);
		
		
		/*
		Crossover(dad.action,mum.action,baby1_action,baby2_action
			,dad.time,mum.time,baby1_time,baby2_time);
		*/

		//使子代基因发生基因突变
		MutateTime(baby1_time);
		MutateTime(baby2_time);

		MutateAction(baby1_action);
		MutateAction(baby2_action);

		/*
		double x0 = baby1[0];
		double x1 = baby1[1];
		double x2 = baby1[2];
		*/
		
		
			

		//把两个子代基因组放到新的基因组容器里面
		vecNewPop.push_back( SGenome(baby1_action,baby1_time,0) );
		vecNewPop.push_back( SGenome(baby2_action,baby2_time,0) );
	}//子代产生完毕
	
	//如果你设置的人口总数非单数的话,就会出现错误
	if(vecNewPop.size() != m_iPopSize)
	{
		AfxMessageBox("你的人口数目不是单数!!!");
		return;
	}

	//现在成员变量m_vecPop将储存新一代的基因组
}



void CGenAlg::outputTheData(CDC* pDC)
{
	CFont *pOldfont,*newfont=new CFont;
	TEXTMETRIC tm;
	newfont->CreateFont(15,0,0,0,FW_NORMAL,0,0,0,GB2312_CHARSET,OUT_DEFAULT_PRECIS,CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,DEFAULT_PITCH,"宋体");
	pOldfont=pDC->SelectObject(newfont);
	pDC->GetTextMetrics(&tm);
	pDC->SetTextColor(RGB(255,255,255));
	pDC->SetBkMode(TRANSPARENT);

	char buf[20];
	sprintf(buf,"基因的世代: %d", m_cGeneration);
	pDC->TextOut(20,20,buf);

	sprintf(buf,"最优基因的得分: %Lf", m_dBestFitness);
	pDC->TextOut(20,35,buf);

	sprintf(buf,"基因的平均得分: %Lf", m_dAverageFitness);
	pDC->TextOut(20,50,buf);

	pDC->SelectObject(pOldfont);
	newfont->DeleteObject();
}