ga.cpp

VC编写的基本遗传算法,建立遗传算子类

// GA.cpp: implementation of the GA class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "SGA.h"
#include "GA.h"

#include <iostream.h>
#include <math.h>

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

//						Code by .御米.
//						[e-mail]
//						http://blog.donews.com/6lines


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

GA::GA()
{
	nPopSize=DEFPOPSIZ;
	nChromLen=DEFCHRLEN;
	nMaxGen=DEFMAXGEN;
	fPc=DEFPC;
	fPm=DEFPM;
	nGen=0;
	nCross=0;
	nMutation=0;
	coef=pow(2.00,nChromLen)-1.0;
	srand((unsigned)time(NULL));

	if(!(MaxFitStat=new float[nMaxGen+1]))
	{
		MessageBox("Allocate Memory Failed !");
		exit(-1);
	}
	if(!(AvgFitStat=new float[nMaxGen+1]))
	{
		MessageBox("Allocate Memory Failed !");
		exit(-1);
	}
	if(!(pOldPop=new POP[nPopSize]))
	{
		MessageBox("Allocate Memory Failed !");
		exit(-1);
	}
	if(!(pNewPop=new POP[nPopSize]))
	{
		MessageBox("Allocate Memory Failed !");
		exit(-1);
	}

}

GA::~GA()
{
	if(MaxFitStat)
		delete [] MaxFitStat;
	if(AvgFitStat)
		delete [] AvgFitStat;
	if(pOldPop)
		delete [] pOldPop;
	if(pNewPop)
		delete [] pNewPop;
	if(!lsRptData.IsEmpty())
		lsRptData.RemoveAll();
}

void GA::InitData(unsigned ppsz,unsigned chrlen,unsigned maxgen,float pc,float pm)
{
	if(pOldPop)
		delete [] pOldPop;
	if(pNewPop)
		delete [] pNewPop;
	if(!lsRptData.IsEmpty())
		lsRptData.RemoveAll();
	if(MaxFitStat)
	{
		delete [] MaxFitStat;
		if(!(MaxFitStat=new float[maxgen+1]))
		{
			MessageBox("Allocate Memory Failed !");
			exit(-1);
		}
	}
	if(AvgFitStat)
	{
		delete [] AvgFitStat;
		if(!(AvgFitStat=new float[maxgen+1]))
		{
			MessageBox("Allocate Memory Failed !");
			exit(-1);
		}
	}
	nPopSize=ppsz;
	nChromLen=chrlen;
	nMaxGen=maxgen;
	fPc=pc;
	fPm=pm;
	nGen=0;
	nCross=0;
	nMutation=0;
	coef=pow(2.00,nChromLen)-1.0;
	srand((unsigned)time(NULL));

	if(!(pOldPop=new POP[nPopSize]))
	{
		MessageBox("Allocate Memory Failed !");
		exit(-1);
	}
	if(!(pNewPop=new POP[nPopSize]))
	{
		MessageBox("Allocate Memory Failed !");
		exit(-1);
	}
}

int GA::Flip(float probability)
{
	double tmp;
	tmp=(double)(rand()/(double)RAND_MAX);
	if(tmp<=probability)
		return 1;
	return 0;
}

float GA::ObjFunc(float vx)
{
	double y;
	//y=3.1415926*vx;
	//y=sin(2.0*y);
	//return (float)(y*y);
	y=vx*sin(10*3.1415926*vx)+2.0;
	return (float)y;
}

float GA::DeCode(unsigned * pChrom)
{
	double t1,t2;
	t1=0.0;
	t2=1.0;
	for(int i=nChromLen-1;i>=0;i--)
	{
		if(pChrom[i])
			t1+=t2;
		t2*=2.0;
	}
	//t1/=coef;
	t1=-1.0+t1*3.0/coef;
	return (float)t1;
}

void GA::StatPop(POP * pop)
{
	fSumFit=pop[0].fitness;
	fMinFit=pop[0].fitness;
	fMaxFit=pop[0].fitness;
	nMaxPop=0;
	nMinPop=0;
	for(unsigned i=1;i<nPopSize;i++)
	{
		fSumFit+=pop[i].fitness;
		if(pop[i].fitness>fMaxFit)
		{
			fMaxFit=pop[i].fitness;
			nMaxPop=i;
		}
		if(pop[i].fitness<fMinFit)
		{
			fMinFit=pop[i].fitness;
			nMinPop=i;
		}
	}
	fAvgFit=fSumFit/(float)nPopSize;
}

void GA::InitPop()
{
	for(unsigned i=0;i<nPopSize;i++)
	{
		for(unsigned j=0;j<nChromLen;j++)
			pOldPop[i].chrom[j]=rand()%2;
		pOldPop[i].chrom[j]='\0';
		pOldPop[i].x=(float)DeCode(pOldPop[i].chrom);
		pOldPop[i].fitness=ObjFunc(pOldPop[i].x);
		pOldPop[i].parent1=0;
		pOldPop[i].parent2=0;
		pOldPop[i].xsite=0;
	}
	StatPop(pOldPop);
}

void GA::InitReport()
{
	char tmp[100];

	lsRptData.AddHead(CString("                                            Simple Genetic Algorithm - SGA"));
	lsRptData.AddTail(CString("________________________________________________________________________________"));
	lsRptData.AddTail(CString("        SGA Parameters:"));
	sprintf(tmp,"Population Size(nPopSize) = %u",nPopSize);
	lsRptData.AddTail(CString(tmp));
	sprintf(tmp,"Chromosome Length(nChromLen) = %u",nChromLen);
	lsRptData.AddTail(CString(tmp));
	sprintf(tmp,"Maximum of Generation(nMaxGen) = %u",nMaxGen);
	lsRptData.AddTail(CString(tmp));
	sprintf(tmp,"Crossover Probability(fPc) = %f",fPc);
	lsRptData.AddTail(CString(tmp));
	sprintf(tmp,"Mutation Probability(fPm) = %f",fPm);
	lsRptData.AddTail(CString(tmp));
	lsRptData.AddTail(CString("________________________________________________________________________________"));
	sprintf(tmp,"Initial Population Max Fitness = %f",fMaxFit);
	lsRptData.AddTail(CString(tmp));
	sprintf(tmp,"Initial Population Average Fitness = %f",fAvgFit);
	lsRptData.AddTail(CString(tmp));	
	sprintf(tmp,"Initial Population Min Fitness = %f",fMinFit);
	lsRptData.AddTail(CString(tmp));
	sprintf(tmp,"Initial Population Sum Fitness = %f",fSumFit);
	lsRptData.AddTail(CString(tmp));
	lsRptData.AddTail(CString("________________________________________________________________________________"));
}

unsigned GA::Select()
{
	double tmprnd,tmpsum;
	unsigned i;
	tmpsum=0.0;
	i=0;
	tmprnd=(double)(rand()/(double)RAND_MAX)*fSumFit;
	do
	{
		tmpsum+=pOldPop[i].fitness;
		i++;
	}while((tmpsum<tmprnd)&&(i<nPopSize));
	if(i==nPopSize)
		return (rand()%nPopSize);
	return i-1;
}

int GA::Mutation(unsigned chromval)
{
	int mutate;
	mutate=Flip(fPm);
	if(mutate)
	{
		nMutation++;
		if(chromval)
			chromval=0;
		else
			chromval=1;
	}
	return chromval;
}

int GA::CrossOver(unsigned * parent1,unsigned * parent2,int popidx)
{
	unsigned i;
	if(Flip(fPc))
	{
		nXcross=rand()%nChromLen;
		nCross++;
	}
	else 
		nXcross=nChromLen;
	if(nXcross!=nChromLen)
	{
		for(i=0;i<nXcross;i++)
		{
			pNewPop[popidx].chrom[i]=Mutation(parent1[i]);
			pNewPop[popidx+1].chrom[i]=Mutation(parent2[i]);
		}
		for(i=nXcross;i<nChromLen;i++)
		{
			pNewPop[popidx].chrom[i]=Mutation(parent2[i]);
			pNewPop[popidx+1].chrom[i]=Mutation(parent1[i]);
		}
	}
	else
		for(i=0;i<nChromLen;i++)
		{
			pNewPop[popidx].chrom[i]=Mutation(parent1[i]);
			pNewPop[popidx+1].chrom[i]=Mutation(parent2[i]);
		}
	return 1;
}

void GA::UpdateGen()
{
	unsigned i,mate1,mate2;
	i=0;
	do
	{
		mate1=Select();
		mate2=Select();
		CrossOver(pOldPop[mate1].chrom,pOldPop[mate2].chrom,i);
		pNewPop[i].x=(float)DeCode(pNewPop[i].chrom);
		pNewPop[i].fitness=ObjFunc(pNewPop[i].x);
		pNewPop[i].parent1=mate1;
		pNewPop[i].parent2=mate2;
		pNewPop[i].xsite=nXcross;
		pNewPop[i+1].x=(float)DeCode(pNewPop[i+1].chrom);
		pNewPop[i+1].fitness=ObjFunc(pNewPop[i+1].x);
		pNewPop[i+1].parent1=mate1;
		pNewPop[i+1].parent2=mate2;
		pNewPop[i+1].xsite=nXcross;
		i=i+2;
	}while(i<nPopSize);
}

void GA::Report(int gen)
{
	char out[200],tmp[100];

	lsRptData.AddTail(CString("        Population Report"));
	sprintf(out,"Generation: %d",gen);
	lsRptData.AddTail(CString(out));
	lsRptData.AddTail(CString("Indiv       Parents     xsite         x              Fitness          String"));
	for(unsigned i=00;i<nPopSize;i++)
	{
		sprintf(out,"%03u>:     (%03u,%03u)      %02u %14.4f %12.4f         ",
			i,pNewPop[i].parent1,pNewPop[i].parent2,
			pNewPop[i].xsite,pNewPop[i].x,pNewPop[i].fitness);
		for(unsigned j=0;j<nChromLen;j++)
			sprintf(tmp+j,"%d",pNewPop[i].chrom[j]);
		strcat(out,tmp);
		lsRptData.AddTail(CString(out));
	}
	lsRptData.AddTail(CString("________________________________________________________________________________"));
	lsRptData.AddTail(CString("        Result:"));
	sprintf(out,"Generation Calculated(nGen) = %u",nGen);
	lsRptData.AddTail(CString(out));
	sprintf(out,"Max Fitness = %f",fMaxFit);
	lsRptData.AddTail(CString(out));
	sprintf(out,"Chromosome Value with Max Fitness = (%2u, %f)",nMaxPop,pNewPop[nMaxPop].x);
	lsRptData.AddTail(CString(out));
	sprintf(out,"Average Fitness = %f",fAvgFit);
	lsRptData.AddTail(CString(out));
	sprintf(out,"Min Fitness = %f",fMinFit);
	lsRptData.AddTail(CString(out));
	sprintf(out,"Chromosome Value with Min Fitness = (%2u, %f)",nMinPop,pNewPop[nMinPop].x);
	lsRptData.AddTail(CString(out));
	sprintf(out,"Crossover Num = %u",nCross);
	lsRptData.AddTail(CString(out));
	sprintf(out,"Mutate Num = %u",nMutation);
	lsRptData.AddTail(CString(out));
	lsRptData.AddTail(CString("________________________________________________________________________________"));

	MaxFitStat[gen]=fMaxFit;
	AvgFitStat[gen]=fAvgFit;
}

void GA::RunGA()
{
	float oldmaxfit;
	int oldmaxpp;

	if(!lsRptData.IsEmpty())
		InitData();
	InitPop();
	InitReport();
	pPop=pNewPop;
	pNewPop=pOldPop;
	StatPop(pNewPop);
	Report(nGen);
	pNewPop=pPop;
	do
	{
		nGen++;
		oldmaxfit=fMaxFit;
		oldmaxpp=nMaxPop;
		UpdateGen();
		StatPop(pNewPop);
		if(fMaxFit<oldmaxfit)
		{
			for(unsigned i=0;i<nChromLen;i++)
				pNewPop[nMinPop].chrom[i]=pOldPop[oldmaxpp].chrom[i];
			pNewPop[nMinPop].x=pOldPop[oldmaxpp].x;
			pNewPop[nMinPop].fitness=pOldPop[oldmaxpp].fitness;
			StatPop(pNewPop);
		}
		Report(nGen);
		pPop=pOldPop;
		pOldPop=pNewPop;
		pNewPop=pPop;
	}while(nGen<nMaxGen);
}