wgenalg.cpp

用C++开发的一个人工神经网络小游戏

// WGenAlg.cpp: implementation of the CWGenAlg class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "EludeObstacle.h"
#include "WGenAlg.h"

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

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

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


extern double g_WdMaxPerturbation;
extern int g_WiNumElite;
extern double g_WdBigMutationRate;
extern double g_WdBigPerturbation;

extern int g_WindowsHeight;
extern int g_WindowsWidth;
extern int ifShowDiagram;

/*
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();}


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


void CWGenAlg::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(SWGenome());//结构体的构造函数本身就已经把适应性评分初始化为0,大家可以回顾一下前面
		
		//把所有的权值初始化为-1~1的随机数
		for (int j=0; j<m_iChromoLength; j++)
		{
			m_vecPop[i].vecWeights.push_back(rand()%5);
		}
	}
}


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

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

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

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

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

	for (int i=0; i<m_iPopSize; ++i)
	{
		FitnessSoFar += m_vecPop[i].dFitness;
		
		//防止负数太多
		TheChosenOne = m_vecPop[0];

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


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

		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]);
	}

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



void CWGenAlg::CrossoverAtSplits(const vector<double> &mum,
                                const vector<double> &dad,
                                vector<double>       &baby1,
                                vector<double>       &baby2)
{
	//当交叉没有发生或者父母基因组是同一条的时候,只要以父方的基因作为后代就行了
	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 CWGenAlg::Reset()
{

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

}




void CWGenAlg::CalculateBestWorstAvTot()
{
	

	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;

	m_cGeneration++;
	m_arAverageFitness[m_cGeneration-1] = m_dAverageFitness;
	m_arBestFitness[m_cGeneration-1] = m_dBestFitness;

	
}



void CWGenAlg::GrabNBest2(int	NBest, vector<SWGenome>	&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(SWGenome(m_vecPop[(m_iPopSize) - i].vecWeights,0));
	}
	//m_vecPop[(m_iPopSize) - i].action = 2;
}



//以等级为基础的缩放比例函数
void CWGenAlg::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 CWGenAlg::Epoch(vector<SWGenome> &vecNewPop)
{
	//用类的成员变量来储存父代的基因组(在此之前m_vecPop储存的是不带估值的所有基因组)
	m_vecPop = vecNewPop;

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

	int t = m_vecPop.size();
	double x[6];
	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());

	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;



	//cout<<"  "<<m_vecPop[m_vecPop.size()-1].vecWeights[0]<<"  "<<m_vecPop[m_vecPop.size()-1].vecWeights[1]<<endl;
	
	//计算最好,最坏,平均,和总的适应性评分
	CalculateBestWorstAvTot();

	vecNewPop.clear();

	

	//这里实现杰出人物算法(如果他们不是偶数的话会发生冲突)
	//优先把优良品种放进容器里面
	/*
	if (!(globe_iNumCopiesElite * globe_iNumElite % 2))
	{
		GrabNBest(globe_iNumElite, globe_iNumCopiesElite, vecNewPop);
	}
	*/
	
	GrabNBest2(g_WiNumElite, vecNewPop); 
	
	//产生新一代的所有基因组
	while (vecNewPop.size() < m_iPopSize)
	{
		//转盘随机抽出两个基因
		SWGenome mum = GetChromoRoulette();
		SWGenome dad = GetChromoRoulette();
		
		//创建两个子代基因组
		vector<double>		baby1, baby2;
		
		//交叉父方的基因和母方的基因
		//CrossoverAtSplits(mum.vecWeights, dad.vecWeights, baby1, baby2);
		baby1 = mum.vecWeights;
		baby2 = dad.vecWeights;

		double x0 = mum.vecWeights[0];
		double x1 = mum.vecWeights[1];
		double x2 = mum.vecWeights[2];

		x0 = baby1[0];
		x1 = baby1[1];
		x2 = baby1[2];

		//使子代基因发生基因突变
		Mutate(baby1);
		Mutate(baby2);
		
		x0 = baby1[0];
		x1 = baby1[1];
		x2 = baby1[2];

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


}



void CWGenAlg::outputTheData(CDC* pDC)
{
	//显示统计图表
	if(ifShowDiagram == 0)
	{
		CPen pen,pen2,*p_pen;
		pen.CreatePen(PS_SOLID,2,RGB(125,233,255));
		p_pen = pDC->SelectObject(&pen);
		
		int x1 = g_WindowsWidth / 8;
		int y1 = g_WindowsHeight / 2 - g_WindowsHeight / 16;
		
		int x2 = g_WindowsWidth / 8; 
		int y2 = g_WindowsHeight - g_WindowsHeight / 16;
		
		pDC->MoveTo(x1,y1);
		pDC->LineTo(x1,y1 - g_WindowsHeight * 3 / 8);
		pDC->MoveTo(x1,y1);
		pDC->LineTo(x1 + g_WindowsWidth * 3 / 4,y1);
		
		pDC->MoveTo(x2,y2);
		pDC->LineTo(x2,y2 - g_WindowsHeight * 3 / 8);
		pDC->MoveTo(x2,y2);
		pDC->LineTo(x2 + g_WindowsWidth * 3 / 4,y2);
		
		
		double max1 = m_arBestFitness[0];
		double max2 = m_arAverageFitness[0];
		for(int i = 0; i < m_cGeneration;i++)
		{
			if(max1 < m_arBestFitness[i])
				max1 = m_arBestFitness[i];
			if(max2 < m_arAverageFitness[i])
				max2 = m_arAverageFitness[i];
		}
		
		int interval;
		if(m_cGeneration == 1)
		{
			interval = 0;
		}
		else
		{
			interval = g_WindowsWidth * 3 / 4 / (m_cGeneration-1);
		}
		
		pen2.CreatePen(PS_SOLID,1,RGB(142,196,255));
		p_pen = pDC->SelectObject(&pen2);
		
		pDC->MoveTo(x1,y1 - m_arBestFitness[0] / max1 * g_WindowsHeight * 3 / 8);
		for(i = 0;i < m_cGeneration;i++)
		{
			int x = x1 + i * interval;
			int y = y1 - m_arBestFitness[i] / max1 * g_WindowsHeight * 3 / 8;
			pDC->LineTo(x, y);
			pDC->LineTo(x, y1);
			pDC->MoveTo(x, y);
		}
		
		//int interval2 = g_WindowsWidth * 3 / 4 / (m_cGeneration-1);
		pDC->MoveTo(x2,y2 - m_arAverageFitness[0] / max2 * g_WindowsHeight * 3 / 8);
		for(i = 0;i < m_cGeneration;i++)
		{
			int x = x2 + i * interval;
			int y = y2 - m_arAverageFitness[i] / max2 * g_WindowsHeight * 3 / 8;
			pDC->LineTo(x, y);
			pDC->LineTo(x, y2);
			pDC->MoveTo(x, y);
		}
	}

	

	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();
}