gaclass.cpp

这是一份整理好的遗传算法的类

		m_pNodeArray[i]=pDup->m_pNodeArray[i];
	}
	m_pParent=pDup->m_pParent;	
	return this;
}
GAIndividual::~GAIndividual(){
	delete []m_pNodeArray;
}

GAIndividual* GAIndividual::Create(GAPopulation* pPop,int nLength){
	ASSERT(nLength>0);
	ASSERT(pPop!=NULL);
	m_pParent=pPop;
	SetLength(nLength);
	m_pNodeArray=new GANode[nLength];
	GANode* pNode=NULL;
	for(int i=0;i<nLength;i++){
		pNode=new GANode;
		pNode=pNode->Create(m_pParent,m_pParent->GetCodeType());
		m_pNodeArray[i].CopyNode(pNode);
		delete pNode;
	}
	return this;
}

BOOL GAIndividual::Compare(GAIndividual* pCompare){
	for(int i=0;i<m_nLength;i++){
		if(GetNode(i)->Compare(pCompare->GetNode(i))==FALSE)
			return FALSE;
	}
	return TRUE;
}

BOOL GAIndividual::CrossOver(GAIndividual* pCross){
	int nBit1=GetRandomBit();
	//int nBit2=GetRandomBit();
//	srand((unsigned)time(NULL));
//	double dCrossP=fabs(sin((double)rand()));//这不是均匀分布的随机数
	/*if(nBit1>nBit2){
		int temp=nBit1;
		nBit1=nBit2;
		nBit2=temp;
	}*/
	double dCrossP=mrab1(0,1000)/1000.0;
	if(dCrossP<=m_pParent->GetCrossP()){
		GANode tempNode;
		//for(int i=nBit1;i<=nBit2;i++){
		for(int i=nBit1;i<m_nLength;i++){
			tempNode=*(pCross->GetNode(i));
			pCross->m_pNodeArray[i]=*(GetNode(i));
			m_pNodeArray[i]=tempNode;
		}
		m_bIsObjValCaculated=false;//added at 2002.9.15
		return TRUE;
	}
	return FALSE;
}


void GAIndividual::Mute(){
//变异算法：对个体而言，产生在长度范围内的随机变异位、同时产生变异概率，
//如果变异概率大于既定的变异概率，则进行该随机位的变异操作，否则，不变异
	//int nBit=GetRandomBit();
	for(int nBit=0;nBit<m_nLength;nBit++){
	GANode* pNode=GetNode(nBit);
		//if(pNode!=NULL){
		pNode->Mute();
		m_bIsObjValCaculated=FALSE;
		//}
	}
}
double GAIndividual::Evaluate(){
//	if(m_bIsObjValCaculated)return m_dObjVal;
	double dVal=0.0;
	for(int i=0;i<m_nLength;i++){
		GANode* pNode=GetNode(i);
		if(pNode->GetValueType()==TYPE_BIT)
			dVal+=(double)pNode->GetIntValue();
		else
			dVal+=pNode->GetDoubleValue();
	}
	m_dObjVal=dVal;
	m_bIsObjValCaculated=TRUE;
	return dVal;
}

double GAIndividual::GetFitness(){
	//暂时以目标函数值直接作为适应度的大小
	double dVal=Evaluate();
/*
	if(dVal!=0){
		m_dFitness=1.0/dVal;
	}
	else{
		m_dFitness=0.0;
	}
*/
	m_dFitness=dVal;
	return m_dFitness;
}

//not duplicate the parent's info
void GAIndividual::Duplicate(GAIndividual* pDup){
	for(int i=0;i<m_nLength;i++){
		m_pNodeArray[i]=pDup->m_pNodeArray[i];
	}
	m_dObjVal=pDup->m_dObjVal;
}

// 设置个体的目标函数值（此值可能来自其他已进行评价过的相同个体）
void GAIndividual::SetObjVal(double dVal)
{
	m_dObjVal=dVal;
	m_bIsObjValCaculated=TRUE;
}


void GAIndividual::UpdateFromTemplate(GAIndividual* pTemp){
	for(int i=0;i<m_nLength;i++){
		if(pTemp->GetNode(i)->GetIntValue()==0)m_pNodeArray[i].SetValue(0);
	}
}
///////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//GANode 类 实现
IMPLEMENT_DYNCREATE(GANode,CObject)


//个体中的基因位
GANode::GANode(){
	m_dGroup=0.0;
	m_nBit=1;
	m_nValueType=TYPE_BIT;
	m_pParent=NULL;
	m_dMinVal=0;
	m_dMaxVal=1;
	m_dValEps=CODE_VALUE_EPS;
}
GANode::GANode(GANode& node){
	m_dGroup=node.m_dGroup;
	m_nBit=node.m_nBit;
	m_nValueType=node.m_nValueType;
	m_pParent=node.m_pParent;
	m_dMinVal=node.m_dMinVal;
	m_dMaxVal=node.m_dMaxVal;
	m_dValEps=node.m_dValEps;
}
GANode GANode::operator =(GANode& node){
	m_dGroup=node.m_dGroup;
	m_nBit=node.m_nBit;
	m_nValueType=node.m_nValueType;
	m_pParent=node.m_pParent;
	m_dMinVal=node.m_dMinVal;
	m_dMaxVal=node.m_dMaxVal;
	m_dValEps=node.m_dValEps;

	return *this;
}

GANode::~GANode(){

}

GANode* GANode::Create(GAPopulation* pPop,int nType,double dMin,double dMax,double dEps){
	m_pParent=pPop;
	m_nValueType=nType;
	if(nType==TYPE_BIT){
//		srand((unsigned)time(NULL));
//		int nBit=rand();
		int nBit=mrab1(0,1000);
		m_nBit=nBit<500?0:1;//此处强制随机产生0的概率增大，使得初始个体更靠近最优解
		//m_nBit=1;//for test only
	}
	else{//暂无实现
		m_dMinVal=dMin;
		m_dMaxVal=dMax;
		m_dValEps=dEps;
		m_dGroup=m_dMinVal+mrab1(0,(m_dMaxVal-m_dMinVal)/m_dValEps)*m_dValEps;
	}
	return this;
}

BOOL GANode::Mute()
{
	
//	srand( (unsigned)time( NULL ) );
//	double dMuteP=fabs(sin((double)rand()));
	double dMuteP=mrab1(0,1000)/1000.0;
	if(dMuteP<=m_pParent->GetMuteP()){
		if(m_nValueType==TYPE_BIT){
			m_nBit=1-m_nBit;
		}
		else{
			m_dGroup=m_dMinVal+mrab1(0,(m_dMaxVal-m_dMinVal)/m_dValEps)*m_dValEps;
		}
		return TRUE;
	}
	return FALSE;
}

int GAIndividual::GetRandomBit()
{
	int nBit=mrab1(0,m_nLength-1);
	return nBit;
}

BOOL GANode::Compare(GANode *pNode)
{
	//if(m_nValueType!=pNode->m_nValueType)return FALSE;
	if(m_nValueType==TYPE_BIT){
		if(m_nBit!=pNode->m_nBit)return FALSE;
	}
	else{
		if(m_dGroup!=pNode->m_dGroup)return FALSE;
	}
	return TRUE;
}



BOOL GAIndividual::IsObjValCaculated()
{
	return m_bIsObjValCaculated;
}



UINT /*GAPopulation::*/EvovleThreadProc(LPVOID pParam)
{
	GAPopulation* pPop=(GAPopulation*)pParam;
	int nGeneration=1;
	
	CTime tBegin=CTime::GetCurrentTime();
	
	ofstream ofile;
	ofile.open("minValue.txt",ios_base::out,ios_base::_Openprot);
	GAIndividual* pBest,*pTemp,*pNewBest,*pNewBest2;
	pTemp=NULL;	pBest=NULL;pNewBest=NULL;pNewBest2=NULL;

	pPop->Sort();//首先进行一次排序
	while(!pPop->IsBroken()&&nGeneration<=pPop->GetMaxGeneration()){
		///////////save the best individual firstly
		//TRACE("*******************************第 %d 代***************************\n\n",nGeneration);
		{//to avoid the first generation because it is not evaluated before selection
			pBest=pPop->GetIndividual(pPop->GetBestIndivIndex());
			pTemp=pPop->CreateNewIndiv();
			pTemp->Duplicate(pBest);
			double dVal=pTemp->GetObjVal();
			CString str=pTemp->GetIndivString();
			//ofile<<str<<"  ****minValue:   "<<dVal<<endl;
			ofile<<dVal<<endl;
		}

		////////////////////////invertd
		//if(pPop->IsInvertNeeded()){
		//	TRACE("begin Inverting*************************************************");
		//	pPop->Invert();
		//}
		///////////////////
		//if(pPop->IsMuteUpdateNeeded()){
		//	pPop->MuteUpdate();
		//}

		///////////////////////mute updated,2002.10.21
		/*div_t dResult;
		dResult=div(nGeneration,50);
		if(dResult.rem==0){
			ofile<<"*************************begin mute update***********************"<<endl;
			//pPop->MuteUpdate();
			pPop->TemplateUpdate();
		}*/
		/////////////////////////

		/////////////////////////////////////////////
		GAPopulation* pNewPop=NULL;
		if(pPop->GetSelMethod()==GAPopulation::SEL_DRANK){
			pNewPop=new GAPopulation(pPop->GetRuntimeClass());
			pPop->Duplicate(pPop,pNewPop);
		}
		int i;
		for(i=0;i<pPop->GetPopSize()/2;i++){
			int n1=pPop->GetRandomIndiv();
			int n2=pPop->GetRandomIndiv();
			GAIndividual* pSel1,*pSel2;
			pSel1=(pPop->GetIndividual(n1));
			pSel2=(pPop->GetIndividual(n2));
			pSel1->CrossOver(pSel2);
		}
		
		for(i=0;i<pPop->GetPopSize();i++){
			GAIndividual* pSel=pPop->GetIndividual(i);
			pSel->Mute();
		}
		pPop->Evaluate(FALSE);

		if(pPop->GetSelMethod()==GAPopulation::SEL_DRANK){
			pPop->Sort();//for 双重排序选择
			pPop->Select2(pNewPop,pPop);//选择并将pPop指向选择后的群体
			delete pNewPop;
		}
		else{
			//for 概率选择方法
			pNewPop=pPop->Select();//pNewPop的内存分配在成员函数select()中完成；
			pPop->Duplicate(pNewPop,pPop);
			//pPop->Sort();
			delete pNewPop;
			/////////
		}

		////////replace the last indiv in the new pop with the saved best indiv
		int nBestIndex=pPop->GetBestIndivIndex();
		pNewBest=pPop->GetIndividual(nBestIndex);
		if(!pTemp->Compare(pNewBest)&&pNewBest->GetFitness()<pTemp->GetFitness()){
			pPop->ReplaceIndiv(nBestIndex,pTemp);
		}
		else{
			delete pTemp;
		}
		//////////////////////////////////////////////////////////////////


		CWnd* pWnd=pPop->GetResultWindow();
		if(pWnd!=NULL)
			pWnd->SendMessage(WM_UPDATE_RESULT,(WPARAM)pPop,NULL);
			//pPop->SetInflatValue(pPop->GetInflatValue()*1.1);
			nGeneration++;
	}	
	

	CTime tEnd=CTime::GetCurrentTime();
	CTimeSpan tSpan=(tEnd-tBegin);
	CString strTime;
	strTime = tSpan.Format( "Take hours: %H, mins: %M, secs: %S\n" );
	strTime+="end the computation!";
	AfxMessageBox(strTime);
	pPop->ShowBestResult(ofile);
	pPop->SetProcState(GAPopulation::eProcEnd);
	//pPop->WriteBestResultToFile(ofile);
	ofile.close();
	
	CGARunDlg* pDlg=(CGARunDlg*)(pPop->GetResultWindow ());
	if(pDlg!=NULL){
		pDlg->GetDlgItem(IDCANCEL)->EnableWindow(TRUE);
	}
	delete pPop;//销毁工作
	
	

	return 0;
}

//排序
void GAPopulation::Sort(){
	int i=0;
	int k=0;
	GAIndividual* pTemp=NULL;
	GAIndividual* p1,*p2;
	for(i=0;i<m_nSize-1;i++){
		p1=GetIndividual(i);
		k=i;
		for(int j=i+1;j<m_nSize;j++){
			p2=GetIndividual(j);
			//if(p1->GetFitness()<p2->GetFitness()){
			if(p1->GetObjVal()>p2->GetObjVal()){
				k=j;
				p1=GetIndividual(k);
			}
		}
		pTemp=m_pIndivArray[i];
		m_pIndivArray[i]=m_pIndivArray[k];
		m_pIndivArray[k]=pTemp;
	}
}

GAPopulation* GAPopulation::Select2(GAPopulation* p1,GAPopulation* p2){
	GAPopulation* pBetter=NULL;//the better;
	GAPopulation* pWorse=NULL;//the worse;
	GAIndividual* pIndiv1=NULL;
	GAIndividual* pIndiv2=NULL;
	pIndiv1=p1->GetIndividual(p1->GetPopSize()/2);
	pIndiv2=p2->GetIndividual(p2->GetPopSize()/2);
	if(pIndiv1->GetFitness()>=pIndiv2->GetFitness()){
		pBetter=p1;pWorse=p2;
	}
	else{
		pBetter=p2;pWorse=p1;
	}
	
	int i,j;
	i=j=0;
	int nSize=pBetter->GetPopSize();
	for(i=0;i+j<=pBetter->GetPopSize()/2;i++){
		pIndiv2=pWorse->GetIndividual(i);
		pIndiv1=pBetter->GetIndividual(nSize/2+j);
		if(pIndiv2->GetFitness()>=pIndiv1->GetFitness()){
			(pBetter->GetIndividual(nSize-i-1))->Duplicate(pIndiv2);
		}
		else{
			j++;
		}
	}
	if(p2!=pBetter){
		GAPopulation* pTemp=NULL;
		pTemp=p2;
		p2=pBetter;
		p1=pTemp;
	}
	p2->Sort();
	return p2;
}


// replace the ith indiv with the new indiv --pNew
void GAPopulation::ReplaceIndiv(int nIndex, GAIndividual* pNew)
{
	ASSERT(nIndex>=0&&nIndex<m_nSize);
	ASSERT(pNew!=NULL);
	GAIndividual* pOld=m_pIndivArray[nIndex];
	m_pIndivArray[nIndex]=pNew;
	pNew->SetParent(this);
	ASSERT(pOld!=NULL);
	delete pOld;
}

// Create the new Individual
GAIndividual* GAPopulation::CreateNewIndiv(void)
{
	GAIndividual* pNew=NULL;
	pNew=(GAIndividual*)m_pClass->CreateObject();
	pNew->Create(this,m_nIndivLen);
	return pNew;
}


CString GAIndividual::GetIndivString(void)
{
	CString str;
	CString strTemp;
	strTemp="";
	str="";
	GANode* pNode=NULL;
	for(int i=0;i<m_nLength;i++){
			pNode=GetNode(i);
			if(pNode->GetValueType()==TYPE_BIT){
				strTemp.Format("%d  ",GetNode(i)->GetIntValue());
			}
			else{
				strTemp.Format("%.2f  ",pNode->GetDoubleValue());
			}
			str+=strTemp;
	}
	return str;
}


///the following function is deserted
void GAPopulation::ReplaceIndiv(GAIndividual* pOld, GAIndividual* pNew)
{
	/*ASSERT(pOld!=NULL);
	ASSERT(pNew!=NULL);
	m_pIndivArray[nIndex]=pNew;
	delete pOld;*/
	
}

int GAPopulation::GetBestIndivIndex(void)
{
	double dValue;
	GAIndividual* pIndiv=NULL;
	dValue=m_pIndivArray[0]->GetFitness();
	pIndiv=m_pIndivArray[0];
	int nIndex=0;
	for(int i=0;i<m_nSize;i++){
		double dFit=m_pIndivArray[i]->GetFitness();
		if(dValue<dFit){
			dValue=dFit;
			pIndiv=m_pIndivArray[i];
			nIndex=i;
		}
	}
  return nIndex;
}

void GAIndividual::SetParent(GAPopulation* pPop)
{
	m_pParent=pPop;
}

// 显示计算结果
void GAPopulation::ShowBestResult(ofstream& pf)
{
	GAIndividual* pIndv=GetBestIndiv ();
	pIndv->ShowBestResult();
}

void GAIndividual::Invert(){
	
	int nBit1=GetRandomBit();
	int nBit2=GetRandomBit();
	//	srand((unsigned)time(NULL));
	//	double dCrossP=fabs(sin((double)rand()));//这不是均匀分布的随机数
	if(nBit1>nBit2){
		int temp=nBit1;
		nBit1=nBit2;
		nBit2=temp;
	}
	GANode* pNode;
	for(int i=nBit1;i<=nBit2;i++){
		pNode=GetNode(i);
		pNode->SetValue(1-pNode->GetIntValue());//实现逆转
	}
	m_bIsObjValCaculated=false;//added at 2002.9.15
}

#define INVERT_EPS 0.05
BOOL GAPopulation::IsInvertNeeded(){
	BOOL bInvert=FALSE;
	double dMinVal=GetBestIndiv()->GetObjVal();
	double dMeanVal=GetMeanResult();
	double dEps=fabs((dMeanVal-dMinVal)/dMinVal);
	if(dEps<=INVERT_EPS){
		bInvert=TRUE;
	}
	return bInvert;
}

double GAPopulation::GetWorstResult(){
	double dMinValue,dMaxFit;
	dMinValue=m_pIndivArray[0]->GetObjVal();
	dMaxFit=m_pIndivArray[0]->GetFitness();
	GAIndividual* pIndiv=m_pIndivArray[0];
	for(int i=0;i<m_nSize;i++){
		double dValue=m_pIndivArray[i]->GetObjVal();
		double dFit=m_pIndivArray[i]->GetFitness();
		if(dFit>pIndiv->GetFitness()){
			dMinValue=dValue;
			pIndiv=m_pIndivArray[i];
		}
	}
	return dMinValue;
	
}
double GAPopulation::GetMeanResult(){
	double dMeanVal=0.0;
	for(int i=0;i<m_nSize;i++){
		double dValue=m_pIndivArray[i]->GetObjVal();
		dMeanVal+=dValue;
	}
	dMeanVal/=m_nSize;
	return dMeanVal;
	
}

void GAPopulation::ForceResultWndClose(){
	CGARunDlg* pDlg=(CGARunDlg*)GetResultWindow();
	pDlg->SendMessage(WM_CLOSE,0,0);
}