ga.cpp

用开发语言vc++编程实现用遗传算法求解函数f=x*sin（10*x）+1.0的最大值。

// 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




//////////////////////////////////////////////////////////////////////
// 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())//indicating whether a variable has been initialized
		lsRptData.RemoveAll();//Removes all the elements from this array. If the array is already empty, the function still works. 
}

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);//可以取得0～1之间的浮点数
	if(tmp<=probability)
		return 1;
	return 0;
}

//[-1,2]范围内
//解出适应性函数的函数值
//vx是形参t1是实参
float GA::ObjFunc(float vx)
{
	double y;
	if ((vx*sin(10*vx)+1.0+0.726262)>0)
	{
		y=vx*sin(10*vx)+1.0+0.2;
	} 
	else
	{
		y=0.00;
	}
	return (float)y;
}

//确定目标函数的取值范围为[-1,2]；
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=-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;//The Random method returns an integer
		pOldPop[i].chrom[j]='\0';
		pOldPop[i].x=(float)DeCode(pOldPop[i].chrom);//取值为[-1,2]；
		pOldPop[i].fitness=ObjFunc(pOldPop[i].x);//将适应性函数求解得出的数组的值，赋给	pOldPop[i].fitness
		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("________________________________________________________________________________"));
}

////////////////////////////////////////////////////////////////////
//选择方式用到的是适度函数比例法，又称轮转法；                    //       
//这里用到的是最简单方法在[0,1]区间内的均匀分布的随机变量的实验   //
//量进行选择，即将[0,1]区间按群体中N个数字串的选择率分为N个小区   //
//间，若随机变量值落入哪个小区间，则相应的个体被选中              //
///////////////////////////////////////////////////////////////////

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

////////////////////////////////////////////////////////////////////
//位变异是以一个很小的概率从群体中随机选取若干个体，对于选中的个  //
//体又随机的选取染色体的某一位或多位进行数码的翻转，对于二进制的  //
//数字串就是某一个位置上的值1变为0或者0变为1。                    //
///////////////////////////////////////////////////////////////////

int GA::Mutation(unsigned chromval)
{
	int mutate;
	mutate=Flip(fPm);//判断是否小于变异率；
	if(mutate)
	{
		nMutation++;
		if(chromval)
			chromval=0;
		else
			chromval=1;
	}
	return chromval;
}


////////////////////////////////////////////////////////////////////
//一点交叉的方法是先根据个体数字串长度L，随机产生一个交叉的位置，//
//即[1,L-1]区间上的一个整数，然后在这个位置上，将双亲的基因码链  //
//截断，最后互换尾部                                             //
//////////////////////////////////////////////////////////////////

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);//确定函数的取值范围为[-1,2]；
		pNewPop[i].fitness=ObjFunc(pNewPop[i].x);//解出适应性函数的函数值
		pNewPop[i].parent1=mate1;//确定双亲1
		pNewPop[i].parent2=mate2;//确定双亲2
		pNewPop[i].xsite=nXcross;//确定交叉的位置
		pNewPop[i+1].x=(float)DeCode(pNewPop[i+1].chrom);//确定函数的取值范围为[-1,2]；
		pNewPop[i+1].fitness=ObjFunc(pNewPop[i+1].x);//解出下一代的适应性函数的函数值
		pNewPop[i+1].parent1=mate1;//确定下一代的双亲1
		pNewPop[i+1].parent2=mate2;//确定下一代的双亲2
		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=0;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=00;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;
}