genetic.cpp

一个遗传算法C++类,值得收藏！

// Genetic.cpp: implementation of the CGenetic class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"

#include "Genetic.h"
#include"math.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
/////张纯禹  2001年   [e-mail]
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CGenetic::CGenetic()
{pmutation=0.01;//变异概率
 pcross=0.9;//交叉概率
 maxgen=5000;//最大进化代数
 iVarNo=0;//染色体数目
 sumfitness=0.0;
 gen=0;
 IsSetScope=false;//还未设定个变量范围
 IsStoped=false;
 for(int i=0;i<MAXBESTNUM;i++)
   bestchrom[i].fitness=0;
 iBestNum=0;
 dblCre=0.0;
 dblDifference=0.15;
 best.fitness=0.0;
 
 initM(MATCOM_VERSION);
 }

CGenetic::~CGenetic()
{exitM();
}

int CGenetic::rselect()
{double rand1,partsum;
 int j=0;
 partsum=0;
 rand1=rand()*sumfitness;
 do{
	 partsum=partsum+newpop[j].fitness;
	 j++;
 }while((partsum<rand1)&&(j<POPSIZE));
 return (j-1);
}

void CGenetic::generation()
{int i,r1,r2;
 CHROM tempChrom;
 //进行统计，计算newpop单个染色体的适应度，选出最优染色体
 statistic(newpop);
 //从1到POPSIZE循环，根据适应度选择，进行交叉，组成oldpop
    for(i=0;i<POPSIZE;i+=2){
		r1=rselect();
		r2=rselect();
		cross(newpop[r1],newpop[r2],i);
	}

 //	oldpop,newpop进行调换
	for(i=0;i<POPSIZE;i++){
		tempChrom=newpop[i];
		newpop[i]=oldpop[i];
		oldpop[i]=tempChrom;
	}
 //从1到POPSIZE循环，对newpop进行变异
    for(i=0;i<POPSIZE;i++)
	    mutation(&newpop[i]);
}

bool CGenetic::begin()
{MSG msg;
 mData=zeros(1,bpnet->iInput);
 mResult=zeros(1,bpnet->iOutput);
for(int i=gen;i<maxgen;i++)
{if(IsStoped)
  break;
 if(bpnet->iOutput>1){
	::MessageBox(NULL,"目前只支持一个输出量!","错误",MB_OK);
	return(false);
 }
 if(gen==0)
  init();//如果刚开始运算，初始化
 generation();
 gen++;
 //防止假死机
 ::PeekMessage(&msg,NULL,0,0,PM_REMOVE);
 ::DispatchMessage(&msg);
 msg.message=-1;
 ::DispatchMessage(&msg);//这样可以消除屏闪
}

return(true);
}


void CGenetic::cross(CHROM chrom1, CHROM chrom2, int iPlace)
{double c;
 int i=0;
//以交叉概率进行交叉，并对交叉后的新染色体进行判别
//循环，直到产生合法的新染色体
 do{if(flip(pcross)){//交叉概率
	c=rand();
    for(i=0;i<iVarNo;i++){
	oldpop[iPlace].chrom[i]=c*chrom1.chrom[i]+(1-c)*chrom2.chrom[i];
	oldpop[iPlace+1].chrom[i]=(1-c)*chrom1.chrom[i]+c*chrom2.chrom[i];
	}
	}
	else//直接赋值，不再交叉
	{oldpop[iPlace]=chrom1;
	 oldpop[iPlace+1]=chrom2;
	}
}while(!identify(oldpop[iPlace])||!identify(oldpop[iPlace+1]));

}

bool CGenetic::flip(double possibility)
{double ppp;
ppp=rand();
if(ppp<=possibility)
 return (true);
else 
 return (false);
}

void CGenetic::mutation(CHROM *chrome)
{double m=10;
 int i=0;
 CHROM temp1,temp2;
 if(flip(pmutation)){ //以变异概率进行变异
	 do{ for(i=0;i<iVarNo;i++)
		   temp2.chrom[i]=chrome->chrom[i];
         for(i=0;i<iVarNo;i++)
			 temp1.chrom[i]=randxy(varminmax[i][0]-varminmax[i][1],varminmax[i][1]-varminmax[i][0])/10;
          for(i=0;i<iVarNo;i++)
			  temp2.chrom[i]+=m*temp1.chrom[i];
		  if(!identify(temp2))
			  m=(double)m/(double)(2.0);
	 }while(!identify(temp2));
 }
 else{
	 for(i=0;i<iVarNo;i++)
		   temp2.chrom[i]=chrome->chrom[i];
 }
 for(i=0;i<iVarNo;i++)
	 chrome->chrom[i]=temp2.chrom[i];
}

void CGenetic::statistic(CHROM pop[])
{int i;
 sumfitness=0;
 //循环，计算单个染色体的适应度,以及sumfitness
 for(i=0;i<POPSIZE;i++){
   pop[i].fitness=CalFitness(pop[i]);
   sumfitness+=pop[i].fitness;}
 //选出符合条件的染色体
 for(i=0;i<POPSIZE;i++){
	if(pop[i].fitness>=dblCre&&IsNew(pop[i]))
		bestchrom[iBestNum++]=pop[i];
	if(pop[i].fitness>best.fitness)
		best=pop[i];//纪录最佳染色体
}

}

void CGenetic::init()
{//对种群进行随机初始化
int i,j; 
srand( (unsigned)time( NULL ) );

if(iVarNo!=0&&IsSetScope)
{for(i=0;i<POPSIZE;i++){
	for(j=0;j<iVarNo;j++){//在最值间随机赋值
		newpop[i].chrom[j]=randxy(varminmax[j][0],varminmax[j][1]);
        oldpop[i].chrom[j]=newpop[i].chrom[j];
	}
}
}
 else
 {if(iVarNo==0)::MessageBox(NULL,"变量数不能为0!","错误...",MB_OK);	
  else if(!IsSetScope) ::MessageBox(NULL,"还未设置变量范围","错误...",MB_OK);
 }
}



double CGenetic::randxy(double x, double y)
{ return (x+(y-x)*rand());

}

void CGenetic::setscope(double scope[MAXVARNO][2], int iNo)
{int i;
for(i=0;i<iNo;i++)
{varminmax[i][0]=scope[i][0];//最小值
 varminmax[i][1]=scope[i][1];//最大值
}
IsSetScope=true; 

}

double CGenetic::CalFitness(CHROM chrome)
{ double dblResult;
 int i;
 for(i=0;i<iVarNo;i++)
	 mData.r(i+1)=chrome.chrom[i];
 mResult=bpnet->simulate(mData); 
 dblResult=mResult.r(1);
 return(dblResult); 
}



bool CGenetic::identify(CHROM chrome)
{int i=0;
 bool IsOk=true;;
 for(i=0;i<iVarNo;i++){
	 if(chrome.chrom[i]>varminmax[i][1]||chrome.chrom[i]<varminmax[i][0])
	 {IsOk=false;
	 break;}
 }
 return (IsOk);
}



double CGenetic::difference(CHROM ch1, CHROM ch2)
{double differ,temp1=0.0,temp2=0.0,temp3=0.0,dblTemp1,dblTemp2;
 int i; 
 for(i=0;i<iVarNo;i++){
	 dblTemp1=ch1.chrom[i]/(varminmax[i][1]-varminmax[i][0]);
	 dblTemp2=ch2.chrom[i]/(varminmax[i][1]-varminmax[i][0]);
	 temp1=temp1+fabs(dblTemp1-dblTemp2)*fabs(dblTemp1-dblTemp2);
     temp2+=dblTemp1*dblTemp1;
	 temp3+=dblTemp2*dblTemp2;
	}
 temp2=(temp2>temp3)?temp2:temp3;//取较大者
 differ=sqrt(temp1)/sqrt(temp2);
 return (differ);
}

bool CGenetic::IsNew(CHROM ch)
{int i;
 bool IsDifferent;
 IsDifferent=true;
 for(i=0;i<iBestNum;i++)
	 if((difference(ch,bestchrom[i])<dblDifference)&&(angle(ch,bestchrom[i])<dblAngle))
	 {IsDifferent=false;
      break;
	 }
return (IsDifferent);

}

double CGenetic::angle(CHROM ch1, CHROM ch2)
{double pi,temp1=0.0,temp2=0.0,temp3=0.0,dblCos=0.0,angle;
 int i=0;
 double dblTemp1,dblTemp2;
 for(i=0;i<iVarNo;i++)
 {dblTemp1=ch1.chrom[i]/(varminmax[i][1]-varminmax[i][0]);
  dblTemp2=ch2.chrom[i]/(varminmax[i][1]-varminmax[i][0]);
  temp1+=dblTemp1*dblTemp2;
  temp2+=dblTemp1*dblTemp1;
  temp3+=dblTemp2*dblTemp2;
 }
 temp2=sqrt(temp2);
 temp3=sqrt(temp3);
 dblCos=temp1/(temp2*temp3);
 pi=acos(-1.0);
 angle=acos(dblCos);
 angle=(angle/pi)*180.0;//转化为角度
 return (angle);

}