gaclass.cpp

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

//************************************************************************************//
//
//                       GAClass.cpp
//						 
//                      
//                      
//***********************************************************************************//



#include "stdafx.h"
#include "myGAClass.h"
#include "math.h"
#include <time.h>
//#ifdef _DEBUG

//#undef THIS_FILE

//static char BASED_CODE THIS_FILE[] = __FILE__;

//#endif

#include "GAOptionDlg.h"

#pragma warning (disable:4995)

#pragma  warning(default:4995)

#include "GARunDlg.h"

int mrab1(int a,int b)
{
	//srand((unsigned)time( NULL ));
	
	//int k=b-a+1;

	//int p;
	//p=a+(int)(((double)rand()*k)/RAND_MAX);


	int r;
	r=rand()*2+1;//random seed

	
	int k,l,m,i,p;
	k=b-a+1; l=2;
	while (l<k) l=l+l;
	m=4*l; k=r; i=1;
	while (i<=1)
	{ k=k+k+k+k+k;
	k=k%m; l=k/4+a;
	if (l<=b) { p=l; i=i+1;}
	}

	//TRACE("%d\n",p);

	return(p);
}


//群体
IMPLEMENT_DYNCREATE(GAPopulation,CObject)
GAPopulation::GAPopulation(CRuntimeClass* pClass){
	m_bIsBroken=FALSE;
	m_dBestResult=0.0;
	m_nBestIndex=-1;
	m_nMaxGen=MAX_GENERATION;
	m_nSize=DEFAULT_SIZE;
	m_pDoubleValSet=NULL;
	m_pIntValSet=NULL;
	m_pIndivArray=NULL;

	m_nIndivLen=DEFAULT_INDIV_LEN;//缺省的个体编码长度
	m_nCodeType=TYPE_BIT;

	m_dSelP=SELECT_P;
	m_dCrossP=CROSS_P;
	m_dMuteP=MUTE_P;

	m_nValScope=2;

	m_pClass=pClass;//added at 2002.7.3

	m_dInflat=1.0;//added at 2002.7.12

	m_pTemplateIndiv=NULL;
	m_nProcState=FALSE;
}

GAPopulation::GAPopulation(CRuntimeClass* pClass,int nSize,int nMaxGen,int nIndivLen,int nCodeType){
	m_bIsBroken=FALSE;
	m_dBestResult=0.0;
	m_nBestIndex=-1;
	m_nMaxGen=nMaxGen;
	m_nSize=nSize;
	m_pDoubleValSet=NULL;
	m_pIntValSet=NULL;
	m_pIndivArray=NULL;
	
	m_nIndivLen=nIndivLen;//缺省的个体编码长度
	m_nCodeType=nCodeType;

	m_dSelP=SELECT_P;
	m_dCrossP=CROSS_P;
	m_dMuteP=MUTE_P;

	m_nValScope=2;

	m_pClass=pClass;//added at 2002.7.3
	m_dInflat=1.0;//added at 2002.7.20

	m_pTemplateIndiv=NULL;
	m_nProcState=eProcStart;
}

GAPopulation::GAPopulation(GAPopulation& pop){
	m_dBestResult=pop.m_dBestResult;
	m_dCrossP=pop.m_dCrossP;
	m_dMuteP=pop.m_dMuteP;
	m_dSelP=pop.m_dSelP;
	m_nBestIndex=pop.m_nBestIndex;
	m_nCodeType=pop.m_nCodeType;
	m_nIndivLen=pop.m_nIndivLen;
	m_nMaxGen=pop.m_nMaxGen;
	m_nSize=pop.m_nSize;
	m_nValScope=pop.m_nValScope;

	m_bIsBroken=pop.m_bIsBroken;

	m_pClass=pop.m_pClass;//added at 2002.7.3
	m_dInflat=pop.m_dInflat;//added at 2002.7.20


	int i;
	if(m_pIndivArray==NULL){
		InitialPop();
	}
	for(i=0;i<m_nSize;i++){
		m_pIndivArray[i]->Duplicate(pop.m_pIndivArray[i]);
	}

	m_pTemplateIndiv->Duplicate(pop.m_pTemplateIndiv);

	m_nProcState=pop.m_nProcState;
}

GAPopulation GAPopulation::operator =(GAPopulation& pop){
	Duplicate(&pop,this);
	return *this;
}


void GAPopulation::InitialPop()
{
	CGAOptionDlg dlgGASetup;
	if(dlgGASetup.DoModal()==IDOK){
		m_nSize=dlgGASetup.m_nPopSize;
		m_nMaxGen=dlgGASetup.m_nMaxGen;
		m_dCrossP=dlgGASetup.m_nCrossP/100.0;
		m_dSelP=dlgGASetup.m_nSelP/100.0;
		m_dMuteP=dlgGASetup.m_nMuteP/100.0;
		m_nSelectMethod=dlgGASetup.m_nSelMethod;
	}
	srand((unsigned)time( NULL ));
	int i=0;
	if(m_pIndivArray==NULL){
		m_pIndivArray=new GAIndividual* [m_nSize];
		for( i=0;i<m_nSize;i++){
			m_pIndivArray[i]=(GAIndividual*)m_pClass->CreateObject();
		}
	}
	for( i=0;i<m_nSize;i++){
		m_pIndivArray[i]->Create(this,m_nIndivLen);
		//TRACE("%s\n",m_pIndivArray[i]->GetIndivString());
		//m_pIndivArray[i]->Evaluate();//added at 2002.9.25
	}
}

GAIndividual* GAPopulation::CreateTemplateIndiv(void){
	m_pTemplateIndiv=(GAIndividual*)m_pClass->CreateObject();
	m_pTemplateIndiv->Create(this,m_nIndivLen);
	int i=0;
	int n=0;
	for( i=0;i<m_nIndivLen;i++){
		n=div(i,2).rem;
		m_pTemplateIndiv->GetNode(i)->SetValue(n);
	}
	return  m_pTemplateIndiv;
}

void GAPopulation::Evaluate(BOOL bRecaculateAll){
	if(bRecaculateAll){
		for(int i=0;i<m_nSize;i++){
			m_pIndivArray[i]->Evaluate();//added at 2002.9.25
		}
	}
	else{
		BOOL bSame=FALSE;
		CGARunDlg* pDlg=(CGARunDlg*)GetResultWindow();
		pDlg->m_ctrPrgPopDecode.SetPos(0);

		for(int i=0;i<m_nSize;i++){
			bSame=FALSE;
			for(int j=i-1;j>=0&&bSame==FALSE;j--){
				GAIndividual* pTemp=m_pIndivArray[j];
				if(pTemp->Compare(m_pIndivArray[i])){
					m_pIndivArray[i]->SetObjVal(pTemp->GetObjVal());
					bSame=TRUE;
				}
			}
			if(bSame==FALSE/*&&!m_pIndivArray[i]->IsObjValCaculated()*/){
				m_pIndivArray[i]->Evaluate();
			}
			pDlg->m_ctrPrgPopDecode.StepIt();////added at 2002.9.30
		}
 	}
}

void GAPopulation::WaitingForThreadEnd()
{
	DWORD wExitCode=0;//to be changed
	GetExitCodeThread(m_hEvolveThread,&wExitCode);
	while(wExitCode==STILL_ACTIVE){
		GetExitCodeThread(m_hEvolveThread,&wExitCode);
	}
}

void GAPopulation::Invert(){
	//逆转步骤：将个体的随机位之间的代码进行逆转
	GAIndividual* pIndiv=NULL;
	for(int i=0;i<m_nSize;i+=2){
		pIndiv=GetIndividual(i);
		pIndiv->Invert();
	}
}

BOOL GAPopulation::IsMuteUpdateNeeded(){

	return IsInvertNeeded();
}
void GAPopulation::MuteUpdate(){
	//步骤：首先从最优解复制出整个或者部分群体
	GAIndividual* pBest=GetBestIndiv();
	int j=0;
	int nLen=pBest->GetLength();
	for(int i=0;i<m_nSize;i++){
		if(j>=nLen)break;
		GAIndividual* pUpdated=GetIndividual(i);
		if(pUpdated!=pBest&&j<nLen){
			for(int k=j;k<nLen;k++){
				GANode* pNode=pUpdated->GetNode(k);
				if(pNode->GetIntValue()==1){
					pNode->SetValue(0);
					j=k+1;
					break;
				}
			}
		}
	}
	//对群体中的个体中为1的代码逐位变异为0
}

void GAPopulation::Evolve(){
//进化步骤：先随机选择个体进行交叉，对群体进行变异，对群体选择个体进入下一代

	TRACE("****************************初始解****************************************\n");
	Evaluate();
	Sort();
	CGARunDlg* pDlg=new CGARunDlg(NULL,this);
	pDlg->Create(IDD_GARUN_DIALOG,NULL);
	pDlg->ShowWindow(SW_SHOW);
	pDlg->CenterWindow(NULL);

	m_pResultWnd=pDlg;
	

	CWinThread* pThread=
		AfxBeginThread(EvovleThreadProc,(LPVOID)this,THREAD_PRIORITY_NORMAL);
	m_hEvolveThread=pThread->m_hThread;

}

//个体
//选择方法：由于选择方法太多，而最基本的概率选择法由于每个个体的概率在个体数
//较多的情形下影响效率，故本程序倾向于排序选择
//本函数为随机联赛选择：
GAPopulation* GAPopulation::Select(){
	//此处增加对群体中个体进行估计
	//BOOL bSame=FALSE;
	////added at 2002.9.30
	//CGARunDlg* pDlg=(CGARunDlg*)GetResultWindow();
	//pDlg->m_ctrPrgPopDecode.SetPos(0);

	//for(int i=0;i<m_nSize;i++){
	//	bSame=FALSE;
	//	for(int j=i-1;j>=0&&bSame==FALSE;j--){
	//		GAIndividual* pTemp=m_pIndivArray[j];
	//		if(pTemp->Compare(m_pIndivArray[i])){
	//			m_pIndivArray[i]->SetObjVal(pTemp->GetObjVal());
	//			bSame=TRUE;
	//		}
	//	}
	//	if(bSame==FALSE/*&&!m_pIndivArray[i]->IsObjValCaculated()*/){
	//		m_pIndivArray[i]->Evaluate();
	//	}
	//	pDlg->m_ctrPrgPopDecode.StepIt();////added at 2002.9.30
	//}
	int nSel1,nSel2;
	GAIndividual* pSel1,*pSel2;
	
	pSel1=pSel2=NULL;
	GAPopulation* pNewPop=new GAPopulation(m_pClass);//changed at 7.3,2002
	Duplicate(this,pNewPop);//复制前一代数据到新的一代
	for(int i=0;i<m_nSize;i++){
		nSel1=GetRandomIndiv();
		nSel2=GetRandomIndiv();
		pSel1=GetIndividual(nSel1);
		pSel2=GetIndividual(nSel2);
		pNewPop->m_pIndivArray[i]->Duplicate(GetBetterIndiv(pSel1,pSel2));
		//pNewPop->m_pIndivArray[i]->Duplicate(GetIndividual(i));
	}

	//the following save the best individual to the next pop to ensure the global optimal solution
	GAIndividual* pBest=GetBestIndiv();
	pNewPop->m_pIndivArray[0]->Duplicate(pBest);
	return pNewPop;
}

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

BOOL GAPopulation::IsTemplateUpdateNeeded(){
	return FALSE;
}

void GAPopulation::TemplateUpdate(){
	if(m_pTemplateIndiv==NULL)m_pTemplateIndiv=CreateTemplateIndiv();
	int i=0;
	for(i=0;i<m_nSize;i++){
		m_pIndivArray[i]->UpdateFromTemplate(m_pTemplateIndiv);
	}
}

double GAPopulation::GetBestResult(){
	m_dBestResult=0;
	for(int i=0;i<m_nSize;i++){
		if(GetIndividual(i)->Evaluate()>m_dBestResult)
			m_dBestResult=GetIndividual(i)->Evaluate();
	}
	return m_dBestResult;
}//得到最优结果

GAPopulation::~GAPopulation(){
	//WaitingForThreadEnd();//added at 2002.8.22 to avoid the lost control of the evovle thread
	
	delete []m_pDoubleValSet;
	delete []m_pIntValSet;

	if(m_pIndivArray!=NULL){
		for(int i=0;i<m_nSize;i++){
			GAIndividual* pIndv=m_pIndivArray[i];
			delete pIndv;
		}
		delete []m_pIndivArray;
		m_pIndivArray=NULL;
	}
}


int GAPopulation::GetRandomIndiv()
{
	int nIndex=mrab1(0,m_nSize-1);
	return nIndex;
}

//复制群体，用于生成下一代群体等
void GAPopulation::Duplicate(GAPopulation* pResource,GAPopulation* pDestation)
{
//	pDestation=new GAPopulation;
	pDestation->m_dBestResult=pResource->m_dBestResult;
	pDestation->m_dCrossP=pResource->m_dCrossP;
	pDestation->m_dMuteP=pResource->m_dMuteP;
	pDestation->m_dSelP=pResource->m_dSelP;
	pDestation->m_nBestIndex=pResource->m_nBestIndex;
	pDestation->m_nCodeType=pResource->m_nCodeType;
	pDestation->m_nIndivLen=pResource->m_nIndivLen;
	pDestation->m_nMaxGen=pResource->m_nMaxGen;
	pDestation->m_nSize=pResource->m_nSize;
	pDestation->m_nValScope=pResource->m_nValScope;

	pDestation->m_bIsBroken=pResource->m_bIsBroken;

	pDestation->m_pClass=pResource->m_pClass;//added at 2002.7.3
	pDestation->m_dInflat=pResource->m_dInflat;//added at 2002.7.20

	pDestation->m_pResultWnd=pResource->m_pResultWnd;//added at 2002.10.1
	pDestation->m_nSelectMethod=pResource->m_nSelectMethod;//added at 2002.10.1


	int i;
	if(pDestation->m_pIndivArray==NULL){
		pDestation->m_pIndivArray=new GAIndividual* [m_nSize];
		for( i=0;i<m_nSize;i++){
			pDestation->m_pIndivArray[i]=(GAIndividual*)m_pClass->CreateObject();
		}
		for( i=0;i<m_nSize;i++){
			pDestation->m_pIndivArray[i]->Create(pResource->m_pIndivArray[i]);
		}
	}
	else{
		for(i=0;i<m_nSize;i++){
			pDestation->m_pIndivArray[i]->Duplicate(pResource->m_pIndivArray[i]);
		}
	}
	pDestation->m_nProcState=pResource->m_nProcState;
/*
	if(pDestation->m_pDoubleValSet==NULL)
	pDestation->m_pDoubleValSet=new double[m_nSize];
	for(int i=0;i<m_nValScope;i++){
		pDestation->m_pDoubleValSet[i]=pResource->m_pDoubleValSet[i];
	}
*/

/*
	if(pDestation->m_pIntValSet==NULL)
		pDestation->m_pIntValSet=new int[m_nSize];
	for(i=0;i<m_nValScope;i++){
		pDestation->m_pIntValSet[i]=pResource->m_pIntValSet[i];
	}
*/
}

void GAPopulation::Destroy()
{
	delete this;
}

GAIndividual* GAPopulation::GetBetterIndiv(GAIndividual *p1, GAIndividual *p2)
{
	double f1=p1->GetFitness();
	double f2=p2->GetFitness();

	double dP=mrab1(0,1000)/1000.0;

	GAIndividual* pIndv=NULL;
	if(f1<f2){
		pIndv=p1;
		p1=p2;
		p2=pIndv;
	}

	if(dP<=m_dSelP)
		return p1;
	else
		return p2;
	////return f1>=f2?p1:p2;
	//return p1;
	
}



double GAPopulation::GetMinValue()
{
	//double dMinY=GetIndividual(0)->Evaluate();
	double dMinY=GetIndividual(0)->GetObjVal();
	for(int i=0;i<m_nSize;i++){
		if(GetIndividual(i)->GetObjVal()<dMinY)
			//dMinY=GetIndividual(i)->Evaluate();
			dMinY=GetIndividual(i)->GetObjVal();
	}
	return dMinY;
}

double GAPopulation::GetMaxValue()
{
	//double dMaxY=GetIndividual(0)->Evaluate();
	double dMaxY=GetIndividual(0)->GetObjVal();
	for(int i=0;i<m_nSize;i++){
		if(GetIndividual(i)->GetObjVal()>dMaxY)
			//dMaxY=GetIndividual(i)->Evaluate();
			dMaxY=GetIndividual(i)->GetObjVal();
	}
	return dMaxY;
	
}


/////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//GAIndividual 类 实现
IMPLEMENT_DYNCREATE(GAIndividual,CObject)


GAIndividual::GAIndividual(){
	m_dFitness=0.0;
	m_dObjVal=0.0;
	m_nLength=1;
	m_pNodeArray=NULL;
	m_pParent=NULL;
	m_bIsObjValCaculated=FALSE;

}

GAIndividual::GAIndividual(GAIndividual& div){
	m_dFitness=div.m_dFitness;
	m_dObjVal=div.m_dObjVal;
	m_nLength=div.m_nLength;
	m_bIsObjValCaculated=div.m_bIsObjValCaculated;
	
	m_pNodeArray=new GANode[m_nLength];
	for(int i=0;i<m_nLength;i++){
	m_pNodeArray[i]=div.m_pNodeArray[i];
	}
	m_pParent=div.m_pParent;
}

GAIndividual GAIndividual::operator =(GAIndividual& div){
	m_dFitness=div.m_dFitness;
	m_dObjVal=div.m_dObjVal;
	m_nLength=div.m_nLength;
	m_bIsObjValCaculated=div.m_bIsObjValCaculated;
	if(m_pNodeArray!=NULL){
		delete []m_pNodeArray;	
		m_pNodeArray=NULL;
	}
	m_pNodeArray=new GANode[m_nLength];

	for(int i=0;i<m_nLength;i++){
		m_pNodeArray[i]=div.m_pNodeArray[i];
	}
	m_pParent=div.m_pParent;	
	return *this;
}

GAIndividual* GAIndividual::Create(GAIndividual* pDup){
	m_dFitness=pDup->m_dFitness;
	m_dObjVal=pDup->m_dObjVal;
	m_nLength=pDup->m_nLength;
	m_bIsObjValCaculated=pDup->m_bIsObjValCaculated;
	if(m_pNodeArray!=NULL){
		delete []m_pNodeArray;	
		m_pNodeArray=NULL;
	}
	m_pNodeArray=new GANode[m_nLength];

	for(int i=0;i<m_nLength;i++){