genetic.cpp

遗传算法的核心实现类 C++语言编写

				//str.Format("%d",Pos);
				//if(i==1&&Pos==0)
					//AfxMessageBox(str);
				m_pNichePop[i*m_nLength+m]=m_pNichePop[Pos*m_nLength+m];
			}
		}
		else
		{
			for(int m=0;m<m_nLength;m++)
				m_pNichePop[i*m_nLength+m]=m_pPop[(Pos-m_nNicheGA)*m_nLength+m];
		}

		/////////////////
		if(Pos>=2*m_nNicheGA)
		{
			PopFitness[Pos]=old;
			for(int m=0;m<m_nLength;m++)
			{
				m_pPop[(Pos-m_nNicheGA)*m_nLength+m]=pOldNiche[m];
			}
		}
		delete pOldNiche;
		//找到一个小生境核i后--更新适应度--把核内的适应度降下来
		for(int j=0;j<m_nPopSize+m_nNicheGA;j++)
		{
			
			//判断个体位于哪个小生境
			if(j<m_nNicheGA)
			{
				if(HaimingDistance(i,m_pNichePop,j,m_pNichePop)<=m_dNichDistanceBoundary)
				{
					//惩罚j以后的小生境
					if(j>i)
					{
						m_pNicheFitness[j]=m_dPenality;
						PopFitness[j]=m_dPenality;
					}
				}
			}
			//降低种群相似群体的适应度
			else
			{
				if(HaimingDistance(i,m_pNichePop,j-m_nNicheGA,m_pPop)<=m_dNichDistanceBoundary)
				{
					if(PopFitness[j]<=m_pNicheFitness[i])
					{
						PopFitness[j]=m_dPenality;
						
					}
				}
				
			}
			
		}
	
		//清除已选出的最值，以免影响以后的寻优
		//PopFitness[Pos]=0;
		PopFitness[i]=0;
	}



	//将小生境核复制到种群中产生新的种群
	for(i=0;i<m_nNicheGA;i++)
	{
		for(int m=0;m<m_nLength;m++)
			m_pPop[i*m_nLength+m]=m_pNichePop[i*m_nLength+m];
		//m_pPopValue[i]=m_pNicheFitness[i];
	}

	for(i=0;i<m_nPopSize;i++)
	{
		DecodeChromosome(i*m_nLength+m_pPop,X);
		m_pPopValue[i]=Function(X);
	}
	//对m_nNicheGA以后的个体直接惩罚
	for(i=0;i<m_nNicheGA;i++)
	{
		for(int j=m_nNicheGA;j<m_nPopSize;j++)
		{	
			if(HaimingDistance(i,m_pNichePop,j,m_pPop)<=m_dNichDistanceBoundary)
			{
				m_pPopValue[j]=m_dPenality;
			}
		}
	}
	//计算平均适应度

	double sum=0;
	m_struct.Index[0]=m_struct.Index[1]=0;
	m_struct.dMin=m_struct.dMax=m_pPopValue[0];

	for(i=0;i<m_nPopSize;i++)
	{
		//指针后移i*m_nLength个长度
		sum+=m_pPopValue[i];
		if(m_pPopValue[i]>m_struct.dMax)
		{
			m_struct.dMax=m_pPopValue[i];
			m_struct.Index[1]=i;
		}
		if(m_pPopValue[i]<m_struct.dMin)
		{
			m_struct.dMin=m_pPopValue[i];
			m_struct.Index[0]=i;
		}

	}
	////////////////////////////////////////////////
	//计算适应度
	for( i=0;i<m_nPopSize;i++)
		m_pPopFitness[i]=m_pPopValue[i]/sum;
	/////////////////////////////////////////////
	m_struct.dAverage=sum/m_nPopSize;


	
	delete[] PopFitness;
	delete []X;
}


//////////////////////////////////////////////////////////////////////////////////////
//功能：选择算子。按轮盘赌注，从种群中选择优良品种改良后代，好的种子可能会被多次选中
//返回：函数运行过程中需要动态分配内存，分配成功返回true,否则false;
/////////////////////////////////////////////////////////////////////////////////////
BOOL CGenetic::SelectionOperator()
{
	char *pPop=new char[m_nLength*m_nPopSize];//存储新种群
	double *sumfit=new double[m_nPopSize+1];//存储积累轮盘数据，以备产生随机数看落在哪个区间。一定要加一

	if (pPop == NULL)
	{
		AfxMessageBox("内存分配失败");
		return FALSE;
	}// 内存分配失败
	if (IsBadReadPtr(pPop, sizeof(char) *m_nLength*m_nPopSize))
	{
		AfxMessageBox("IsBadReadPtr failed");
		return FALSE;
	}// 内存分配失败
	memset(pPop, 0, sizeof(char) *m_nLength*m_nPopSize);// 将各元素值置0
	
	if (sumfit == NULL)
	{
		AfxMessageBox("内存分配失败");
		return FALSE;
	}// 内存分配失败
	if (IsBadReadPtr(sumfit, sizeof(double) *(m_nPopSize+1)))
	{
		AfxMessageBox("IsBadReadPtr failed");
		return FALSE;
	}// 内存分配失败
	memset(sumfit, 0, sizeof(double) *(m_nPopSize+1));// 将各元素值置0


	sumfit[0]=0;
	sumfit[m_nPopSize]=1;//积累之和当然是1

	double sum=0;
	//sum为适应度之和
	for(int i=1;i<m_nPopSize;i++)
	{	
		sum+=m_pPopFitness[i-1];
		sumfit[i]=sum;
	}

    srand((unsigned)time(NULL));
	double datarand;//产生随机数
	//轮盘选择--复制个体
	for(i=0;i<m_nPopSize;i++)
	{
		datarand=(double)rand()/RAND_MAX;
		for(int j=0;j<m_nPopSize;j++)
		{
			if((datarand>sumfit[j])&&(datarand<=sumfit[j+1]))
				memcpy(pPop+i*m_nLength,m_pPop+j*m_nLength,sizeof(char)*m_nLength);
		
		}
	}
	memset(m_pPop,0,sizeof(char)*m_nLength*m_nPopSize);
	memcpy(m_pPop,pPop,sizeof(char)*m_nLength*m_nPopSize);
   
	delete[] sumfit;
	delete[] pPop;
	return TRUE;
}
		

///////////////////////////////////////////////////////////////////////////
//功能：交叉算子。让种群相互结婚，本算法采用“近亲”结婚，（0，1）（2，3），，结婚，
//       书上写的是随机结婚，但种群排列本无顺序，“近亲”结婚也代表随机的意思，目的是为了计算方便
//返回：函数运行过程中需要动态分配内存，分配成功返回true,否则false;实际上可以改成void型
//      因为分配的内存大小只有m-nlength个字节
//////////////////////////////////////////////////////////////////////////////////////////////////
BOOL CGenetic::CrossoverOperator()
{
	srand((unsigned)time(NULL));
	char *Flag=new char[m_nLength];

	if (Flag == NULL)
		return FALSE;					// 内存分配失败
	if (IsBadReadPtr(Flag, sizeof(char) *m_nLength))
		return FALSE;
	memset(Flag, 0, sizeof(char) *m_nLength);// 将各元素值置0

	int randPos;
	double isCross;
	for(int i=0;i<m_nPopSize;i+=2)
	{
		randPos=int((double)m_nLength*rand()/RAND_MAX);
		isCross=(double)rand()/RAND_MAX;
	    if(isCross<m_dPc)
		{	
			for(int j=0;j<=randPos;j++)
			{
				Flag[j]=m_pPop[i*m_nLength+j];
				m_pPop[i*m_nLength+j]=m_pPop[(i+1)*m_nLength+j];
				m_pPop[(i+1)*m_nLength+j]=Flag[j];

			}
		}
	}
	delete[] Flag;
	return TRUE;	
}


/////////////////////////////////////////////////////////////////////////
//功能：变异算子，每个位按初始设置的变异概率变异
////////////////////////////////////////////////////////////////////////////////
BOOL CGenetic::MutationOperator()
{
	double mutation;
	for(int i=0;i<m_nLength*m_nPopSize;i++)
	{
		mutation=(double)rand()/RAND_MAX;
		if(mutation<m_dPm)
		{
			if(m_pPop[i]=='0')
				m_pPop[i]='1';
			else
				m_pPop[i]='0';
		}
	}
	return TRUE;
}


///////////////////////////////////////////////////////////////////////////////////////
//功能：进化函数。
//返回值：返回最优目标函数值
//参数：
//
double CGenetic::Evolution(int nMaxStep,double Max[],double Min[],double Average[],double X[])
{
	GenerateInitialPopulation();
	for(int i=0;i<nMaxStep;i++)
	{
		ComputeValueAndFitness();
		SelectionOperator();
		CrossoverOperator();
		MutationOperator();
		Max[i]=m_struct.dMax;
		Min[i]=m_struct.dMin;
		Average[i]=m_struct.dAverage;
	}
	ComputeValueAndFitness();
	DecodeChromosome(m_pPop+m_struct.Index[1],X);

	return m_struct.dMax;
}

/////////////////////////////////////////////////////////////////
//产生下一代个体
////////////////////////////////////////////////////////////////
void CGenetic::GenerateNextPopulation()
{
	ComputeValueAndFitness();
	SelectionOperator();
	CrossoverOperator();
	MutationOperator();
}

//////////////////////////////////////////////////////////////////////////
//功能：设置变量的上下界约束
//返回值：无
//参数：
// Value[]------变量的上下界约束
////////////////////////////////////////////////////////////////////////////
void CGenetic::SetConstraint(double Value[])//Vlaue的值是2倍参数个数
{
	for(int i=0;i<m_nParameterCount;i++)
	{
		ASSERT(Value[i+m_nParameterCount]>=Value[i]);
	}
	
	memset(m_pConstraint, 0, sizeof(double) * 2*m_nParameterCount);
	memcpy(m_pConstraint, Value, sizeof(double) * 2*m_nParameterCount);
	
}


//////////////////////////////////////////////////////////////////////////////////////
//设置交叉概率，默认为0.6，构造函数里面已经指定为默认值，如需要自己设置，需要在建立对象后调用此函数
/////////////////////////////////////////////////////////////////////////////////////////////
void CGenetic::SetCrossoverPro(double dPc/*=0.6*/)
{
	m_dPc=dPc;
}


////////////////////////////////////////////////////////////////////////////////////////////////
//设置变异概率，默认为0.001，构造函数里面已经指定为默认值，如需要自己设置，需要在建立对象后调用此函数
///////////////////////////////////////////////////////////////////////////////////////////
void CGenetic::SetMutationPro(double dPm/*=0.001*/)
{
	m_dPm=dPm;
}


////////////////////////////////////////////////////////////////////////////////////
//获得编码精度
///////////////////////////////////////////////////////////////////////////////
double CGenetic::GetCodePrecision() const
{
	return m_dCodePrecision;
}


/////////////////////////////////////////////////////////////////////////////////////////
//获得交叉概率
/////////////////////////////////////////////////////////////////////////////////////////
double CGenetic::GetCrossoverPro() const
{
	return m_dPc;
}


//////////////////////////////////////////////////////////////////////////////////////////
//获得变异概率
/////////////////////////////////////////////////////////////////////////////////////////
double CGenetic::GetMutationPro() const
{
	return m_dPm;
}


//////////////////////////////////////////////////////////////////////////
//获得染色体长度
/////////////////////////////////////////////////////////////////////////
int CGenetic::GetChromosomeLength() const
{
	return m_nLength;
}

//////////////////////////////////////////////////////////////////////
//获得变量约束
double* CGenetic::GetConstraint() const
{
	return m_pConstraint;
}
//////////////////////////////////////////////////////////////////////////////
//获得种群规模
//////////////////////////////////////////////////////////////////////////////
int CGenetic::GetPopSize() const
{
	return m_nPopSize;
}


//////////////////////////////////////////////////////////////////
//获得每个变量的染色体长度
/////////////////////////////////////////////////////////////////
int* CGenetic::GetGetEachLength()const
{
	return m_pEachLength;
}


///////////////////////////////////////////////////////////////////
//获得种群数据二进制串的指针
///////////////////////////////////////////////////////////////////
char* CGenetic::GetPop() const
{
	return m_pPop;
}

//////////////////////////////////////////////////////////////////
//获得种群函数值的指针
///////////////////////////////////////////////////////////////
double* CGenetic::GetPopValue() const
{
	return m_pPopValue;
}


//////////////////////////////////////////////
//获得种群适应度的值的指针
double* CGenetic::GetPopFitness() const
{
	return m_pPopFitness;
}

///////////////////////////////////////////////////////
//获得目前种群中具有最大函数值
/////////////////////////////////////////////////////
double CGenetic::GetMaxValue() const
{
	return m_struct.dMax;
}

////////////////////////////////////////
//获得目前种群中具有最小函数值
///////////////////////////////////////
double CGenetic::GetMinValue() const
{
	return m_struct.dMin;
}

///////////////////////////////////
//获得目前种群中平均函数值
//////////////////////////////////
double CGenetic::GetAverageValue() const
{
	return m_struct.dAverage;
}


////////////////////////////////////////////////////
//获得该代中具有最大适应度个体的解码变量值
////////////////////////////////////////////////////
double CGenetic::GetSolution(double X[]) 
{
	DecodeChromosome(m_pPop+m_struct.Index[1],X);
	return m_struct.dMax;
}
/*****************************
计算小生境核参数
在GenerateInitialPopulation()和ComputeValueAndFitness()后调用此函数
******************************/
void CGenetic::InitComputeNichePop(int nNicheGA,double dNichDistanceBoundary)
{
	ASSERT(nNicheGA<=m_nPopSize);
	m_nNicheGA=nNicheGA;
	m_dNichDistanceBoundary=dNichDistanceBoundary;
	//对原种群的适应度m_pPopFitness进行排序,以初始化小生境核
	if(m_pNichePop)
	{
		delete[] m_pNichePop;
		m_pNichePop=NULL;
	}
	m_pNichePop=new char [m_nLength*m_nNicheGA];

	if(m_pNicheFitness)
	{
		delete[] m_pNicheFitness;
		m_pNicheFitness=NULL;
	}
	m_pNicheFitness=new double [m_nNicheGA];
	
    //寻找前m_nNicheGA个适应度最大值放到小生境核中
	double *PopFitness=new double [m_nPopSize];
	for(int i=0;i<m_nPopSize;i++)
		PopFitness[i]=m_pPopFitness[i];
	for(i=0;i<m_nNicheGA;i++)
	{
		double value=PopFitness[0];
		int Pos=0;
		int k=0;
		do
		{
			if(value<PopFitness[k])
			{
				Pos=k;
				value=PopFitness[k];
			}
			k++;
		}while(k<=m_nPopSize);
		//获得小生境核适应度
		m_pNicheFitness[i]=PopFitness[Pos];
		//复制编码将种群第Pos个编码复制到第i个核
		for(int m=0;m<m_nLength;m++)
				m_pNichePop[i*m_nLength+m]=m_pPop[Pos*m_nLength+m];
		//清除已选出的最值，以免影响以后的寻优
		PopFitness[Pos]=0;
	}

	delete[] PopFitness;
}

double CGenetic::HaimingDistance(int i,char *pNichePop,int j,char *pPop)
{
	double Distance=0;
	//先解码
	double* X=new double [m_nParameterCount];
	
	DecodeChromosome(j*m_nLength+pPop,X);
	
	double* Y=new double [m_nParameterCount];
	DecodeChromosome(i*m_nLength+pNichePop,Y);

	for(int k=0;k<m_nParameterCount;k++)
		Distance+=(X[k]-Y[k])*(X[k]-Y[k]);
    Distance=sqrt(Distance);
	/*
	CString str;
	str.Format("(%d,%d)=%f",i,j,Distance);
	AfxMessageBox(str);
	*/

	delete[] X;
	delete[] Y;
	
	return Distance;

}