genetic.cpp

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

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

#include "stdafx.h"
#include "Genetic.h"
#include<afxwin.h>

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




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




/////////////////////////////////////////////////////////////////////////
//默认构造函数，数据都是默认指定，基本上用不着
/////////////////////////////////////////////////////////////////////////
CGenetic::CGenetic()
{
	
	m_nParameterCount=1;//只有一个变量
	m_nPopSize=400;
	m_dPc=0.6;
	m_dPm=0.001;
	m_dCodePrecision=0.01;
	m_pConstraint=NULL;
	m_pPop=NULL;
	m_pEachLength=NULL;	
	m_pPopValue=NULL;
	m_pPopFitness=NULL;
    m_pConstraint = new double[2];
	m_pConstraint[0]=-2;
	m_pConstraint[1]=2;

	m_dPenality=0.0000000000000000000000001;
	m_dNichDistanceBoundary=0.5;
	m_pNichePop=NULL;
	m_pNicheFitness=NULL;

	m_struct.dAverage=m_struct.dMax=m_struct.dMin=0;
	m_struct.Index[0]=m_struct.Index[1]=0;
	int nInitial=Init(m_nParameterCount,m_nPopSize,m_dCodePrecision);
	ASSERT(nInitial);
	
	
}



//////////////////////////////////////////////////////////////////////////////////////////
//构造函数，指定参数配置
//返回值：无
//参数：
//1 nParameterCount---变量个数，
//2 nPopSize----------种群规模，默认为400
//3 dCodePrecision----编码精度，即变量搜索的精度，默认为0.01
//4 Constraint[]------变量约束的上下界值，前nParameterCount个为下界取值，后nParameterCount个为上界取值
//                    如果变量是单边约束，建议通过tag（）函数转为比区间，避免内存消耗过多
////////////////////////////////////////////////////////////////////////////////////////////
void CGenetic::CGeneticInit(int nParameterCount,double Constraint[],int nPopSize/*=400*/,double dCodePrecision/*=0.01*/)
{
	m_nParameterCount=nParameterCount;
	m_nPopSize=nPopSize;
	m_dPc=0.6;
	m_dPm=0.001;
	m_dCodePrecision=dCodePrecision;
	m_pConstraint=NULL;
	m_pPop=NULL;
	m_pEachLength=NULL;	
	m_pPopValue=NULL;
	m_pPopFitness=NULL;

	m_struct.dAverage=m_struct.dMax=m_struct.dMin=0;
	m_struct.Index[0]=m_struct.Index[1]=0;

	m_pConstraint = new double[2*m_nParameterCount];
	ASSERT (m_pConstraint );
					// 内存分配失败
	
	memset(m_pConstraint, 0, sizeof(double)*2*m_nParameterCount);// 将各元素值置0
	SetConstraint(Constraint);

	int nInitial=Init(m_nParameterCount,m_nPopSize,m_dCodePrecision);
	ASSERT(nInitial);

    

}



////////////////////////////////////////////////////////////////////////////
//功能：析够函数，释放所有堆分配内存
////////////////////////////////////////////////////////////////////////////
CGenetic::~CGenetic()
{
	if (m_pConstraint)
	{
		delete[] m_pConstraint;
		m_pConstraint = NULL;
	}
	if(m_pPop)
	{
		delete[] m_pPop;
		m_pPop=NULL;
	}
	if(m_pEachLength)
	{
		delete[] m_pEachLength;
		m_pEachLength=NULL;
	}
	if(m_pPopValue)
	{
		delete[] m_pPopValue;
		m_pPopValue=NULL;
	}

	if(m_pPopFitness)
	{
		delete[] m_pPopFitness;
		m_pPopFitness=NULL;
	}
	
	if(m_pNichePop)
	{
		delete[] m_pNichePop;
		m_pNichePop=NULL;
	}
	
}


///////////////////////////////////////////////////////////////////////////
//功能：初始化函数，分配内存，确定染色体长度，保存在m_nLengthz中，这个长度是由 
//      nParameterCount，pConstraint[]和dCodePrecision共同决定的
//返回值：内存分配成功返回TRUE,否则返回FALSE
//参数：
//1 nParameterCount--------变量个数
//2 nPopSize---------------种群规模
//3 dCodePrecision---------编码精度
/////////////////////////////////////////////////////////////////////////////
BOOL CGenetic::Init(int nParameterCount,int nPopSize,double dCodePrecision)
{
	m_dCodePrecision=dCodePrecision;
	m_nParameterCount=nParameterCount;
	m_nPopSize=nPopSize;
	ASSERT(nParameterCount>0);


	if(m_pPop)
	{
		delete[] m_pPop;
		m_pPop=NULL;
	}
	if(m_pEachLength)
	{
		delete[] m_pEachLength;
		m_pEachLength=NULL;
	}

	if(m_pPopValue)
	{
		delete[] m_pPopValue;
		m_pPopValue=NULL;
	}

	if(m_pPopFitness)
	{
		delete[] m_pPopFitness;
		m_pPopFitness=NULL;
	}

    
	// 分配内存
	

	m_pEachLength=new int[m_nParameterCount];
	if(!m_pEachLength)
		return FALSE;
	if (IsBadReadPtr(m_pEachLength, sizeof(int) *m_nParameterCount))
		return FALSE;
	memset(m_pEachLength, 0, sizeof(int)*m_nParameterCount);// 将各元素值置0
	///非常重要
/////////////////////////////////////////////////////////////////////////////////////////
	m_nLength=GetChromLength();//同时获得各个变量的编码长度，存储在m_pEachLength成员变量中
    ///////////////////////////////////////////////////////////////////////////////////

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

	m_pPopValue=new double[m_nPopSize];
	if (m_pPopValue == NULL)
		return FALSE;					// 内存分配失败
	if (IsBadReadPtr(m_pPopValue, sizeof(double) *m_nPopSize))
		return FALSE;
	memset(m_pPopValue, 0, sizeof(double) *m_nPopSize);// 将各元素值置0

	m_pPopFitness=new double[m_nPopSize];
	if (m_pPopFitness == NULL)
		return FALSE;					// 内存分配失败
	if (IsBadReadPtr(m_pPopFitness, sizeof(double) *m_nPopSize))
		return FALSE;
	memset(m_pPopFitness, 0, sizeof(double) *m_nPopSize);// 将各元素值置0
	return TRUE;
}


////////////////////////////////////////////////////////////////////////////////
//功能：给定变量值返回目标函数的值
//参数：
// 1  X[]----------变量的值，共有m_nParmeterCount个变量
//////////////////////////////////////////////////////////////////////////////////
double CGenetic::Function(double X[])
{
	return 100*(X[0]*X[0]-X[1])*(X[0]*X[0]-X[1])+(1-X[0])*(1-X[0]);
	//double value=(-((4-2.1*X[0]*X[0]+X[0]*X[0]*X[0]*X[0]/3.0)*X[0]*X[0]+X[0]*X[1]+(-4+4*X[1]*X[1])*X[1]*X[1]));
//
//	if(value<0)
//		value=0;
//	return value;
}

///////////////////////////////////////////////////////////////////////////////////
//获得变量个数
//////////////////////////////////////////////
int CGenetic::GetParameterCount() const
{
	return m_nParameterCount;
}


///////////////////////////////////////////////////////////////////////////
//功能：获得染色体长度确定染色体长度，保存在m_nLengthz中，这个长度是由 
//      nParameterCount，pConstraint[]和dCodePrecision共同决定的
//返回值：返回染色体长度，即二进制编码长度
//////////////////////////////////////////////////////////////////////////////
int CGenetic::GetChromLength()
{
	double step;
	int totalLength=0;
	for(int i=0;i<m_nParameterCount;i++)
	{	
		 step=(m_pConstraint[i+m_nParameterCount]-m_pConstraint[i])/m_dCodePrecision;
		 m_pEachLength[i]=(int)(log10(step)/log10(2));
		 totalLength+=m_pEachLength[i];
	}
	return totalLength;
	
}



/////////////////////////////////////////////////////////////////////////////////////
//功能：随机产生初始种群，结果为庞大的二进制串，保存在m_pPop[]中
//返回值：无
//参数：无
/////////////////////////////////////////////////////////////////////////////////////
void CGenetic::GenerateInitialPopulation()
{
	srand((unsigned)time(NULL));
	//随机编码
	for(int i=0;i<m_nPopSize*m_nLength;i++)
    if(((double)rand())/RAND_MAX<0.5)
		m_pPop[i]='0';
	else
		m_pPop[i]='1';

}



///////////////////////////////////////////////////////////////////////////////
//功能：解码函数。指定长度为m_nLength长的一个二进制串，解码后的值存储在X[]中
//返回值：无
//参数：
//1  pointer--指向一个染色体的指针
//2  X[]-------存储解码后的变量值
//////////////////////////////////////////////////////////////////////////////////
void CGenetic::DecodeChromosome(char* pointer,double X[])
{
	int* Flag=new int[m_nLength];
	
	
	char* Gray=new char[m_nLength];
	for(int i=0;i<m_nLength;i++)
	{
		Gray[i]=pointer[i];	
	}

	for(i=1;i<m_pEachLength[0];i++)
	{
		if((Gray[i-1]!=pointer[i]))
			Gray[i]='1';
		else
			Gray[i]='0';
	}

	for(i=m_pEachLength[0]+1;i<m_nLength;i++)
	{
		if((Gray[i-1]!=pointer[i]))
			Gray[i]='1';
		else
			Gray[i]='0';
	}
	

	/*
	实用Gray编码须先将Gray编码转化为二进制编码
	pointer[i]
	*/
	for(i=0;i<m_nLength;i++)
	{
		if(pointer[i]=='0')
			Flag[i]=0;
		else
			Flag[i]=1;
	}

	

	int length=0;
	for(i=0;i<m_nParameterCount;i++)
	{
		int sum=0;
		//解码（二进制）到每个变量（十进制）
		for(int j=0;j<m_pEachLength[i];j++)
		{
			sum+=Flag[j+length]*_bry(m_pEachLength[i]-1-j);

		}

		X[i]=m_pConstraint[i]+sum*(m_pConstraint[i+m_nParameterCount]-m_pConstraint[i])/(_bry(m_pEachLength[i])-1);
        length+=m_pEachLength[i];
	}
	delete[] Flag;
	delete[] Gray;
}


////////////////////////////////////////////////////////////////////////////////////
//功能：静态函数，求2的n次方
//返回：2的n次方
//参数：
////////////////////////////////////////////////////////////////////////////////////
long CGenetic::_bry(int n)
{
	if(n==0)
		return 1;
	else
	{
	int k=0,value=1;

	while(k<n)
	{
		value*=2;
		k++;
	}
	return value;
	}
}

////////////////////////////////////////////////////////////////////////
//拷贝构造函数
/////////////////////////////////////////////////////////////////////////
CGenetic& CGenetic::operator=(const CGenetic& other)
{
	if (&other != this)
	{
		m_nParameterCount=other.m_nParameterCount;
    	m_nPopSize=other.m_nPopSize;
    	m_dPc=other.m_dPc;
    	m_dPm=other.m_dPm;
    	m_dCodePrecision=other.m_dCodePrecision;

		if(m_pConstraint)
		{
			delete[] m_pConstraint;
			m_pConstraint=NULL;
		}
		m_pConstraint=new double[m_nParameterCount];
		memset(m_pConstraint,0,sizeof(double)*m_nParameterCount);
		memcpy(m_pConstraint,other.GetConstraint(),sizeof(double)*m_nParameterCount);
		//////////////////////////
		BOOL bSuccess = Init(other.GetParameterCount(),other.m_nPopSize,other.m_dCodePrecision);
		ASSERT(bSuccess);

		// copy the pointer
	
	}

	// finally return a reference to ourselves
	return *this ;
}


//////////////////////////////////////////////////////////////////////////
//功能：种群评价函数。计算种群的函数值和适应度
//dMin,dMax返回该种群中的最大最小适应度的个体
//	m_struct，和	m_pPopValue[]将被更新
//////////////////////////////////////////////////////////////////////////
void CGenetic::ComputeValueAndFitness()
{
	double *X=new double[m_nParameterCount];
	double sum=0;
	m_struct.Index[0]=m_struct.Index[1]=0;
	DecodeChromosome(m_pPop,X);
	m_struct.dMin=m_struct.dMax=Function(X);

	for(int i=0;i<m_nPopSize;i++)
	{
		//指针后移i*m_nLength个长度
		DecodeChromosome(i*m_nLength+m_pPop,X);
		m_pPopValue[i]=Function(X);
		
		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 []X;
}

void CGenetic::ComputeNicheValueAndFitness()
{
	double *X=new double[m_nParameterCount];
	
    //计算每个种群个体的适应度适应度
	for(int i=0;i<m_nPopSize;i++)
	{
		//指针后移i*m_nLength个长度
		DecodeChromosome(i*m_nLength+m_pPop,X);
		m_pPopValue[i]=Function(X);
	}
	////////////////////////////////////////////////

	//更新小生境核
	//寻找前m_nNicheGA个适应度最大值放到小生境核中
	double *PopFitness=new double [m_nNicheGA+m_nPopSize];
	//前m_nNicheGA个为小生境核的适应值
	for(i=0;i<m_nNicheGA;i++)
		PopFitness[i]=m_pNicheFitness[i];
	//后m_nPopSize个为种群的适应值
	for(i=0;i<m_nPopSize;i++)
		PopFitness[i+m_nNicheGA]=m_pPopValue[i];
	


	for(i=0;i<m_nNicheGA;i++)
	{
		double value=PopFitness[i];
		int Pos=i;
		int k=0;
		do
		{
			if(value<PopFitness[k])
			{
				Pos=k;
				value=PopFitness[k];
			}
			k++;
		}while(k<=m_nNicheGA+m_nPopSize);
		
		//获得小生境核适应度
		//小生境发生变化--保存小生境值以共下一个小生境选择
		
		
		char* pOldNiche=new char [m_nLength];
		double old;
		if(Pos>=2*m_nNicheGA)
		{
			old=m_pNicheFitness[i];
			for(int m=0;m<m_nLength;m++)
			{
				pOldNiche[m]=m_pNichePop[i*m_nLength+m];
			}
		}
		
		m_pNicheFitness[i]=PopFitness[Pos];
		
		
		

		//复制编码
		if(Pos<m_nNicheGA)
		{
			for(int m=0;m<m_nLength;m++)
			{
				//CString str;