gaclass.cpp

利用基本遗传算法（SGA）来对函数 进行求优

#include "StdAfx.h"
#include "GAClass.h"
#include <math.h>

//public:

CGenAlg::CGenAlg(pop pp,IniData ini,ReportFormat RF,CEdit &m_edit)
{
	//
	this->pp=pp;

	/*this->ini.crossrate=ini.crossrate;
	this->ini.lchrom=ini.lchrom;
	this->ini.maxgen=ini.maxgen;
	this->ini.mutationrate=ini.mutationrate;
	this->ini.parameters=ini.parameters;
	this->ini.popsize=ini.popsize;*/
	this->ini=ini;
	
	this->RF=RF;
	this->m_edit=&m_edit;


}

CGenAlg::~CGenAlg()
{
	//
	//delete pp.newpop;
	//delete pp.oldpop;
	//delete GR;
	//delete SelectedPop;
}

void CGenAlg::Initialize()
{
	//
	SingleInformation *newpop = new SingleInformation[ini.popsize];
	SingleInformation *oldpop = new SingleInformation[ini.popsize];
	GR=new GengerationResult[ini.maxgen];
	SelectedPop = new int[ini.popsize];
	int i;
	
	for (i=0;i<ini.popsize;i++)
	{
		newpop[i].x=new double[ini.parameters];
		oldpop[i].x=new double[ini.parameters];
	}

	ReSetSelectedPop();
		
	srand((unsigned)time(NULL));
	for ( i=0;i<ini.popsize;i++)
	{
		//
		newpop[i].ID=i;
		newpop[i].parent1=0;
		newpop[i].parent2=0;
		
		for (int j=0;j<ini.lchrom*ini.parameters;j++)
		{
			
			newpop[i].Gray[j]=rand()%2+48;
		}
		newpop[i].Gray[ini.lchrom*ini.parameters]='\0';
		/*GrayToBin(newpop[i].Gray,newpop[i].Bin,ini);
		BinToReal(newpop[i],ini);
		newpop[i].funvalue=FunValue(newpop[i].x,ini);
		newpop[i].fitness=newpop[i].funvalue;*/
		/*Statistics(0);*/
	}
	
	pp.newpop=newpop;
	pp.oldpop=oldpop;
	//this->GR=GR;

	for(i=0;i<ini.popsize;i++)
	{
		GrayToBin(pp.newpop[i].Gray,pp.newpop[i].Bin,ini);
		BinToReal(pp.newpop[i],ini);
		pp.newpop[i].funvalue=FunValue(pp.newpop[i].x,ini);
		pp.newpop[i].fitness=pp.newpop[i].funvalue;
	}
}

//void CGenAlg::DataReport(CEdit &edit,pop pp,IniData Ini,ReportFormat RF)
void CGenAlg::DataReport(CEdit &edit,int GenID)
{
	//
	//注意：此处必须为引用，因为在c++里面，一旦形如CEdit edit这样定义之后，表示又定义了一个新的CEdit对象，而不是指针，必须要用引用
	//
	CString str;
	edit.GetWindowText(str);
	char inttochar[50];
	int len;
	int j;
	for (int i=0;i<ini.popsize;i++)
	{
		if (RF.ReportID)
		{
			//输出ID号
			sprintf(inttochar,"%d",pp.newpop[i].ID);
			len = strlen(inttochar);
			str = str+inttochar;
			for(int j=0;j<RF.ID_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.Reportparent1)
		{
			//输出父母一
			sprintf(inttochar,"%d",pp.newpop[i].parent1);
			len = strlen(inttochar);
			str = str+inttochar;
			for(int j=0;j<RF.parent1_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.Reportparent2)
		{
			//输出父母一
			sprintf(inttochar,"%d",pp.newpop[i].parent2);
			len = strlen(inttochar);
			str = str+inttochar;
			for(int j=0;j<RF.parent2_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.ReportGray)
		{
			//输出格雷码
			len = strlen(pp.newpop[i].Gray);
			str = str+pp.newpop[i].Gray;
			for(int j=0;j<RF.Gray_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.ReportBin)
		{
			//输出二进制码
			len = strlen(pp.newpop[i].Bin);
			str = str+pp.newpop[i].Bin;
			for(int j=0;j<RF.Bin_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.Reportx)
		{
			//输出X值
			sprintf(inttochar,"%.4f",pp.newpop[i].x[0]);
			len = strlen(inttochar);
			str = str+inttochar;
			for(int j=0;j<RF.x_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.Reportfunvalue)
		{
			//输出函数值
			sprintf(inttochar,"%.4f",pp.newpop[i].funvalue);
			len = strlen(inttochar);
			str = str+inttochar;
			for(int j=0;j<RF.funvalue_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.Reportfitness)
		{
			//输出适应度值
			sprintf(inttochar,"%.4f",pp.newpop[i].fitness);
			len = strlen(inttochar);
			str = str+inttochar;
			for(int j=0;j<RF.fitness_l-len;j++) str = str+" ";
			str = str+"|";
		}
		str = str+"\r\n";
		str = str+"------------------------------------------------------\r\n";

	}
	sprintf(inttochar,"%d",GR[GenID].maxID);
	str=str+"maxID="+inttochar;
	str=str+"\r\n";
	edit.SetWindowText(str);
}

void CGenAlg::DataReport(CEdit *pedit,int GenID)
{
	//
	CString str;
	pedit->GetWindowText(str);
	char inttochar[50];
	int len;
	int j;
	for (int i=0;i<ini.popsize;i++)
	{
		if (RF.ReportID)
		{
			//输出ID号
			sprintf(inttochar,"%d",pp.newpop[i].ID);
			len = strlen(inttochar);
			str = str+inttochar;
			for(int j=0;j<RF.ID_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.Reportparent1)
		{
			//输出父母一
			sprintf(inttochar,"%d",pp.newpop[i].parent1);
			len = strlen(inttochar);
			str = str+inttochar;
			for(int j=0;j<RF.parent1_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.Reportparent2)
		{
			//输出父母一
			sprintf(inttochar,"%d",pp.newpop[i].parent2);
			len = strlen(inttochar);
			str = str+inttochar;
			for(int j=0;j<RF.parent2_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.ReportGray)
		{
			//输出格雷码
			len = strlen(pp.newpop[i].Gray);
			str = str+pp.newpop[i].Gray;
			for(int j=0;j<RF.Gray_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.ReportBin)
		{
			//输出二进制码
			len = strlen(pp.newpop[i].Bin);
			str = str+pp.newpop[i].Bin;
			for(int j=0;j<RF.Bin_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.Reportx)
		{
			//输出X值
			sprintf(inttochar,"%.4f",pp.newpop[i].x[0]);
			len = strlen(inttochar);
			str = str+inttochar;
			for(int j=0;j<RF.x_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.Reportfunvalue)
		{
			//输出函数值
			sprintf(inttochar,"%.4f",pp.newpop[i].funvalue);
			len = strlen(inttochar);
			str = str+inttochar;
			for(int j=0;j<RF.funvalue_l-len;j++) str = str+" ";
			str = str+"|";
		}
		if (RF.Reportfitness)
		{
			//输出适应度值
			sprintf(inttochar,"%.4f",pp.newpop[i].fitness);
			len = strlen(inttochar);
			str = str+inttochar;
			for(int j=0;j<RF.fitness_l-len;j++) str = str+" ";
			str = str+"|";
		}
		str = str+"\r\n";
		str = str+"------------------------------------------------------\r\n";

	}
	sprintf(inttochar,"%d",GR[GenID].maxID);
	str=str+"maxID="+inttochar;
	str=str+"\r\n";
	pedit->SetWindowText(str);
}

//void CGenAlg::Statistics(SingleInformation *newpop,IniData Ini,GengerationResult *GR,int ID)
void CGenAlg::Statistics(int GenID)
{
	//
	int i;
	float sum=pp.newpop[0].fitness;
	GR[GenID].ID=GenID;
	GR[GenID].max=pp.newpop[0].fitness;
	GR[GenID].maxID =0;
	GR[GenID].min=pp.newpop[0].fitness;
	GR[GenID].minID =0;
	for (i=1;i<ini.popsize;i++)
	{
		if (GR[GenID].max<pp.newpop[i].fitness)
		{
			GR[GenID].max=pp.newpop[i].fitness;
			GR[GenID].maxID=i;
		}
		if (GR[GenID].min>pp.newpop[i].fitness)
		{
			GR[GenID].min=pp.newpop[i].fitness;
			GR[GenID].minID=i;
		}
		sum = sum+pp.newpop[i].fitness;
	}
	GR[GenID].sumfitness=sum;
	CurrentSumFitness=sum;
	GR[GenID].avg=sum/ini.popsize;
	CurrentAvgFitness=GR[GenID].avg;
}

void CGenAlg::Generation()
{
	//
	
	int GenID;
	int i;
	int select1,select2;
	char aaa[10];
	srand((unsigned)time(NULL));
	for(GenID=0;GenID<ini.maxgen;GenID++)
	{
		//
		/*for(i=0;i<ini.popsize;i++)
		{
			GrayToBin(pp.newpop[i].Gray,pp.newpop[i].Bin,ini);
			BinToReal(pp.newpop[i],ini);
			pp.newpop[i].funvalue=FunValue(pp.newpop[i].x,ini);
			pp.newpop[i].fitness=pp.newpop[i].funvalue;
		}*/

		Statistics(GenID);
		DataReport(m_edit,GenID);

		pp.temp=pp.oldpop;
		pp.oldpop=pp.newpop;//将新群体变成旧群体
		pp.newpop=pp.temp;

		//srand((unsigned)time(NULL));
		/*for(i=0;i<ini.popsize;i=i+2)
		{
			//
			select1=Select();
			select2=Select();
			//sprintf(aaa,"%d",select1);
			//m_edit->MessageBox(aaa);
			CrossOver(select1,select2,i,i+1,pp,ini);
		}*/
		ReSetSelectedPop();
		CountGenRate();
		Select();
		CrossOver();

		//计算新生成的群体，用旧群体的最优值代替新群体的最差值
		for(i=0;i<ini.popsize;i++)
		{
			GrayToBin(pp.newpop[i].Gray,pp.newpop[i].Bin,ini);
			BinToReal(pp.newpop[i],ini);
			pp.newpop[i].funvalue=FunValue(pp.newpop[i].x,ini);
			pp.newpop[i].fitness=pp.newpop[i].funvalue;
		}
		Statistics(GenID+1);
		Replace(GR[GenID+1].minID,GR[GenID].maxID);
		//select
		//crossover
		//mutation
	}

}

//private:

void CGenAlg::BinToReal(SingleInformation si,IniData ini)
{
	//
	int i,j,k;
	for (i=0;i<ini.parameters;i++)
	{
		si.x[i]=0;
		for (j=0;j<ini.lchrom;j++)
		{
			si.x[i]=si.x[i]*2+si.Bin[i*ini.lchrom+j]-48;
		}
	}
}

/*
int CGenAlg::Select()
{
	//轮赌盘算法
	int i;
	float pick;
	float sum;
	char aaa[10];

	pick = AverageRandom(0,1);
    sum = 0;
    if(CurrentSumFitness != 0)
    {
        for(i = 0; (sum < pick) && (i < ini.popsize); i++)
            sum += pp.oldpop[i].fitness/CurrentSumFitness;
    }
    else
        i = rand()%ini.popsize;
	return i-1;
}
*/
void CGenAlg::Select()
{
	//select
	float sum=0;
	float ptr=AverageRandom(0,1);
	int k;
	for(k=0;k<ini.popsize;k++)
	{
		sum=sum+pp.oldpop[k].genrate;
		while (sum>ptr)
		{
			StoreSelected(k);
			ptr=ptr+1;
		}
	}
}

void CGenAlg::GrayToBin(char *Gray,char *Bin,IniData ini)
{
	//
	int i,j,k;
	for (i=0;i<ini.parameters;i++)
	{
		k=i*ini.lchrom;
		Bin[k]=Gray[k];
		for (j=1;j<ini.lchrom;j++)
		{
			if(Bin[k+j-1]==Gray[k+j])
				Bin[k+j]='0';
			else Bin[k+j]='1';
		}
	}
	Bin[ini.lchrom*ini.parameters]='\0';
}

void CGenAlg::BinToGray(char *Bin,char *Gray,int strlength)
{
	//
}


void CGenAlg::CrossOver2(int parent1,int parent2,int child1,int child2,IniData ini)
{
	//
	char *p1,*p2;
	char *c1,*c2;
	p1=pp.oldpop[parent1].Gray;
	p2=pp.oldpop[parent2].Gray;
	c1=pp.newpop[child1].Gray;
	c2=pp.newpop[child2].Gray;
	//srand((unsigned)time(NULL));
	//int random_pos=rand()%ini.lchrom;
	int random_pos=AverageRandom(0,ini.lchrom);
	int i,j;
	for(i=0;i<ini.parameters;i++)
	{
		for(j=0;j<random_pos;j++)
		{
			//不交叉
			c1[i*ini.lchrom+j]=Mutation(ini.mutationrate,p1[i*ini.lchrom+j]);
			c2[i*ini.lchrom+j]=Mutation(ini.mutationrate,p2[i*ini.lchrom+j]);
		}
		for(j=random_pos;j<ini.lchrom;j++)
		{
			//交叉
			c1[i*ini.lchrom+j]=Mutation(ini.mutationrate,p2[i*ini.lchrom+j]);
			c2[i*ini.lchrom+j]=Mutation(ini.mutationrate,p1[i*ini.lchrom+j]);
		}
	}
	c1[ini.lchrom*ini.parameters]='\0';
	c2[ini.lchrom*ini.parameters]='\0';

	pp.newpop[child1].ID=child1;
	pp.newpop[child2].ID=child2;

	pp.newpop[child1].parent1=parent1;
	pp.newpop[child1].parent2=parent2;
	pp.newpop[child2].parent1=parent1;
	pp.newpop[child2].parent2=parent2;
}

void CGenAlg::CrossOver()
{
	//
	int i;
	for (i=0;i<ini.popsize;i=i+2)
	{
		CrossOver2(SelectedPop[i],SelectedPop[i+1],i,i+1,ini);
	}
}

char CGenAlg::Mutation(float mutationrate,char scr_str)
{
	//
	if(flip(mutationrate))
	{
		if(scr_str=='0')
			scr_str='1';
		else scr_str='0';
	}
	
	return scr_str;
}

bool CGenAlg::flip(float probability)
{
	//
	float ppp;
	//srand((unsigned)time(NULL));
	//ppp=rand()%1000;
	//ppp=(float)ppp/1000.0;
	ppp=AverageRandom(0,1);
	if(ppp<=probability)   return true;
	return false;
}

/*函数功能，产生一个在min~max范围内精度为4位小数的平均分布的随机数*/
float CGenAlg::AverageRandom(double min,double max)
{
	
	int minInteger = (int)(min*10000);
	int maxInteger = (int)(max*10000);
	int randInteger = rand()*rand();
	int diffInteger = maxInteger - minInteger;
	int resultInteger = randInteger % diffInteger + minInteger;
	return resultInteger/10000.0;
}

void CGenAlg::CountGenTime()
{
	//
	int popID;
	float temp;
	for (popID=0;popID<ini.popsize;popID++)
	{
		//将fitness四舍五入
		temp=pp.newpop[popID].fitness/CurrentAvgFitness;
		pp.newpop[popID].gentimes=temp/1;
		temp=temp-pp.newpop[popID].gentimes;
		if (temp>=0.5) pp.newpop[popID].gentimes++;
	}
}

void CGenAlg::CountGenRate()
{
	//
	int popID;
	for (popID=0;popID<ini.popsize;popID++)
	{
		pp.oldpop[popID].genrate=pp.oldpop[popID].fitness/CurrentAvgFitness;
	}
}

void CGenAlg::ReSetSelectedPop()
{
	for(int popID=0;popID<ini.popsize;popID++)
	{
		SelectedPop[popID]=-1;
	}
}

void CGenAlg::StoreSelected(int SelectedID)
{
	//
	int position;
	position=AverageRandom(0,ini.popsize);
	int up,down;
	up = position;
	down=position;
	while(true)
	{
		//
		if(SelectedPop[up]==-1)
		{
			SelectedPop[up]=SelectedID;
			break;
		}
		else if (SelectedPop[down]==-1)
		{
			SelectedPop[down]=SelectedID;
			break;
		}
		else 
		{
			if(up>0)up--;
			if(down<ini.popsize)down++;
		}
	}
}

void CGenAlg::Replace(int min,int max)
{
	//
	int i;
	int len=ini.lchrom*ini.parameters;
	for (i=0;i<len;i++)
	{
		pp.newpop[min].Gray[i]=pp.oldpop[max].Gray[i];
		pp.newpop[min].Bin[i]=pp.oldpop[max].Bin[i];
	}
	pp.newpop[min].Gray[len]='\0';
	pp.newpop[min].Bin[len]='\0';
	pp.newpop[min].fitness=pp.oldpop[max].fitness;
	pp.newpop[min].funvalue=pp.oldpop[max].funvalue;
	pp.newpop[min].x=pp.oldpop[max].x;
	
}

//protected:

/*double CGenAlg::FunValue(double *x,IniData ini)
{
	//
	if (x[0]==0) return 0;
	int maxnum=pow(2,ini.lchrom);
	double z=x[0]/maxnum;
	double y;
	y=10+(sin(1/z)/(pow((z-0.16),2)+0.1));
	return y;
}*/

double CGenAlg::FunValue(double *x,IniData ini)
{
	float y,t,troot;
	double x1,x2;
	int maxnum=pow(2,ini.lchrom);
	x1=x[0]/maxnum*200-100;
	x2=x[1]/maxnum*200-100;
	t=x1*x1+x2*x2;
	troot=pow(t,0.5);
	y=0.5-(pow(sin(troot),2)-0.5)/pow((1+0.001*t),2);
	return y;
}