population.cpp

一个简单遗传算法

// population.cpp: implementation of the Cpopulation class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "HeredityDemo.h"
#include "population.h"
#include "individual.h"
#include <stdlib.h>
#include <time.h>
#include <fstream.h>

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

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

Cpopulation::Cpopulation()
{

}

Cpopulation::Cpopulation(int MaxOrMin,int ObjectNum, int DimensionNum, int PopulationSize, int ChromosomeLength, double CrossoverRare, double MutationRate )
{
	m_MaxOrMin=MaxOrMin;//表示是极大问题还是极小问题
	m_PopulationSize=PopulationSize;//表示种群的大小
	m_pIndividualNum = new Cindividual[m_PopulationSize];//种群中的每一个个体
	m_pIndividualNum1 = new Cindividual[m_PopulationSize];//这些个体是一些中间转换个体，主要是为了运算
	m_pSelectResult = new int[m_PopulationSize];//在进行选择操作后，把选择后的结果存放到该处	
	m_ObjectNum=ObjectNum;//表示是多少目标的问题，如是1个目标还是2个目标还是多个目标
    m_DimensionNum=DimensionNum;//表示问题的维数，是1维的还是2维的还是多维的，实际上就是X的个数
	m_CrossoverRate=CrossoverRare;//杂交的概率
	m_MutationRate=MutationRate;//变异的概率
	m_ChromosomeLength=ChromosomeLength;//染色体的长度，在这里是指每一条颜色体的长度
	m_pBestIndividualChromosome= new int[m_DimensionNum*m_ChromosomeLength];//将得到的最好的个体的染色体放到该处
	m_pWorstIndividualChromosome= new int[m_DimensionNum*m_ChromosomeLength];
	m_pBestIndividualValue= new double[m_ObjectNum];
	m_pWorstIndividualValue= new double[m_ObjectNum];
	GenerateInitialPopulation();//对生成的个体的初始化
}
Cpopulation::~Cpopulation()// 析构函数释放在构造函数中动态申请的堆空间
{
	delete [] m_pIndividualNum;
	delete [] m_pIndividualNum1;
	delete [] m_pSelectResult;
	delete [] m_pBestIndividualChromosome;
	delete [] m_pBestIndividualValue;
	delete [] m_pWorstIndividualChromosome;
	delete [] m_pWorstIndividualValue;
}
void Cpopulation::GenerateInitialPopulation()//该函数功能是对生成的个体的初始化
{
	srand((unsigned)time(NULL));// 对时间量初始化，避免伪随机
	for(int i=0;i<m_PopulationSize;i++)
	{

		 m_pIndividualNum[i].InitializtionIndividual(m_ObjectNum,m_DimensionNum,m_ChromosomeLength,m_MaxOrMin);//调用个体的初始化函数，对个体初始化
         m_pIndividualNum1[i].InitializtionIndividual1(m_ObjectNum,m_DimensionNum,m_ChromosomeLength,m_MaxOrMin);	  
	}
}
double   Cpopulation::GetPerGenerationBestValue()//得到每一代的最好目标值，下标和染色体编码
{
	double *ObjectValue1= new double[m_ObjectNum];
	double *ObjectValue2= new double[m_ObjectNum];
	double temp1,temp2;
	if(0==m_MaxOrMin)
	{
		int MaxIndex=0;
        for(int i=0;i<m_PopulationSize-1;i++)
		{       
			for(int j=0;j<m_ObjectNum;j++)
			{   
				(m_pIndividualNum+MaxIndex)->GetObjectValue(ObjectValue1);
				temp1=*(ObjectValue1+j);
				(m_pIndividualNum+i+1)->GetObjectValue(ObjectValue2);
				temp2=*(ObjectValue2+j);
                if(temp1<temp2)
					MaxIndex=i+1;
			}			
		}
		m_BestIndividualIndex=MaxIndex;
        (m_pIndividualNum+MaxIndex)->GetObjectValue(ObjectValue1);
		(m_pIndividualNum+MaxIndex)->GetChromosomeValue(m_pBestIndividualChromosome);
		for(int k=0;k<m_ObjectNum;k++)
		{   
			*(m_pBestIndividualValue+k)=*(ObjectValue1+k);
		}		
	}
	else
	{
		int MinIndex=0;
        for(int i=0;i<m_PopulationSize-1;i++)
		{       
			for(int j=0;j<m_ObjectNum;j++)
			{   
				(m_pIndividualNum+MinIndex)->GetObjectValue(ObjectValue1);
				temp1=*(ObjectValue1+j);
				(m_pIndividualNum+i+1)->GetObjectValue(ObjectValue2);
				temp2=*(ObjectValue2+j);
                if(temp1>temp2)
					MinIndex=i+1;
			}			
		}
		m_BestIndividualIndex=MinIndex;
        (m_pIndividualNum+MinIndex)->GetObjectValue(ObjectValue1);
		(m_pIndividualNum+MinIndex)->GetChromosomeValue(m_pBestIndividualChromosome);
		for(int k=0;k<m_ObjectNum;k++)
		{   
			*(m_pBestIndividualValue+k)=*(ObjectValue1+k);
		}
	}
	delete [] ObjectValue1;
	delete [] ObjectValue2; 
	return *(m_pBestIndividualValue+0);

}
double   Cpopulation::GetPerGenerationAvgValue()//得到每一代目标值的平均值
{
	double *ObjectValue1= new double[m_ObjectNum];
	double sum=0.0;
	for(int i=0;i<m_PopulationSize;i++)
	{
		(m_pIndividualNum+i)->GetObjectValue(ObjectValue1);
		for(int j=0;j<m_ObjectNum;j++)
		{
			sum+=*(ObjectValue1+j);
		}
	}
	sum=sum/m_PopulationSize;
	m_PerGenerationAvgValue=sum;
	
	delete [] ObjectValue1;
	return m_PerGenerationAvgValue;
}
double    Cpopulation::GetPerGenerationWorseValue()//功能是得到每一代中最差的个体，得到最差个体的目标值，下标和染色体编码
{
	double *ObjectValue1= new double[m_ObjectNum];
	double *ObjectValue2= new double[m_ObjectNum];
	double temp1,temp2;
	int MaxIndex=0;
	if(0==m_MaxOrMin)
	{
		
        for(int i=0;i<m_PopulationSize-1;i++)
		{       
			for(int j=0;j<m_ObjectNum;j++)
			{   
				(m_pIndividualNum+MaxIndex)->GetObjectValue(ObjectValue1);
				temp1=*(ObjectValue1+j);
				(m_pIndividualNum+i+1)->GetObjectValue(ObjectValue2);
				temp2=*(ObjectValue2+j);
                if(temp1>temp2)
					MaxIndex=i+1;
			}
			m_WorseIndividualIndex=MaxIndex;
			(m_pIndividualNum+MaxIndex)->GetObjectValue(ObjectValue1);
		    (m_pIndividualNum+MaxIndex)->GetChromosomeValue(m_pWorstIndividualChromosome);
		    for(int k=0;k<m_ObjectNum;k++)
			{   
			*(m_pWorstIndividualValue+k)=*(ObjectValue1+k);
			}			
		}
	}

	delete [] ObjectValue1;
	delete [] ObjectValue2; 
	return *(m_pWorstIndividualValue+0);
}
void    Cpopulation::ComputerSelectionRate()//通过适应值计算每一个个体的选择概率和累加概率
{
	    double sum=0.0;
		double sum1=0.0;
		double *FitnessValue = new double[m_ObjectNum];
	    for(int i=0;i<m_PopulationSize;i++)
		{
			(m_pIndividualNum+i)->GetFitnessValue(FitnessValue);
				sum+=*(FitnessValue);
		}
		for(int j=0;j<m_PopulationSize;j++)
		{
			(m_pIndividualNum+j)->GetFitnessValue(FitnessValue);
			sum1+=*(FitnessValue)/sum;
			(m_pIndividualNum+j)->SetSelectionRate(*(FitnessValue)/sum);
			(m_pIndividualNum+j)->SetAddSelectionRate(sum1);

		}
		delete [] FitnessValue;
}
void   Cpopulation::OutputPerGenerationInformation(int GenerationNum)//功能是输出每一代的最好目标值和平均值及编码
{
	   cout<<"The "<<GenerationNum<<" Best value"<<" ";
	   cout.precision(8);
	   cout<<*(m_pBestIndividualValue+0)<<" ";
	   cout<<"AvgValue "<<m_PerGenerationAvgValue<<" ";
	   cout<<"Code=";
	   for(int i=0;i<m_DimensionNum*m_ChromosomeLength;i++)
	   {
		   cout<<*(m_pBestIndividualChromosome+i)<<" ";
	   }
	   cout<<endl;
}
void Cpopulation::OutputPerIndividualInformation()//功能输出每个个体的详细信息，包括目标数值，适应数值，参数数值，编码等，方便跟踪检查
{   
	for(int i=0;i<m_PopulationSize;i++)
	{
		cout<<"geti"<<i<<" ";
		
		(m_pIndividualNum+i)->OutputDetailInformation();		
	}
}
void Cpopulation::SelectionOperator()//功能进行选择操作，用的是轮盘的方法
{
	 double RandDate;
	 for(int i=0;i<m_PopulationSize;i++)
	 {
         RandDate= (rand()%1000)/1000.0;//***************
		 if(RandDate<=m_pIndividualNum->GetAddSelectionRate())
		 {
		 		 *(m_pSelectResult+i)=0; 
		 }
		 else
		 {
			 for(int j=0;j<m_PopulationSize-1;j++)
			 {
			 
			 if(RandDate>(m_pIndividualNum+j)->GetAddSelectionRate() && RandDate<=(m_pIndividualNum+j+1)->GetAddSelectionRate())
			 {
				 *(m_pSelectResult+i)=j+1; 
				 break;
			 }
			 }

		 }		 
	 }	 
}
void Cpopulation::OutputSelectedResult()//功能是输出经选择操作后的结果，方便跟踪检查
{
	for(int j=0;j<m_PopulationSize;j++)
	{
		cout<<*(m_pSelectResult+j)<<" ";
	}
}
void Cpopulation::crossoverOperator(double CrossoverRate)
{
	int temp0=m_ChromosomeLength*m_DimensionNum;
    int *ChromosomeValue1 = new int[temp0];
	int *ChromosomeValue2 = new int[temp0];
	double temp1;
    int    temp2;
	for(int i=0;i<m_PopulationSize;i+=2)
	{
		temp1=(rand()%1000)/1000.0;
		if(temp1<CrossoverRate)
		{
              temp2=rand()%(m_ChromosomeLength*m_DimensionNum);
			  (m_pIndividualNum+m_pSelectResult[i])->GetChromosomeValue(ChromosomeValue1);
			  (m_pIndividualNum+m_pSelectResult[i+1])->GetChromosomeValue(ChromosomeValue2);
			  int ChromosomeValue3;
			  for(int j=temp2;j<m_ChromosomeLength*m_DimensionNum;j++,temp2++)
			  { 
				  ChromosomeValue3=*(ChromosomeValue1+temp2);
				  *(ChromosomeValue1+temp2)=*(ChromosomeValue2+temp2);
				  *(ChromosomeValue2+temp2)=ChromosomeValue3;

			  }
			  (m_pIndividualNum1+i)->SetChromosome(ChromosomeValue1);	
			  (m_pIndividualNum1+i+1)->SetChromosome(ChromosomeValue2);
		}
		else
		{
			(m_pIndividualNum+m_pSelectResult[i])->GetChromosomeValue(ChromosomeValue1);
			(m_pIndividualNum+m_pSelectResult[i+1])->GetChromosomeValue(ChromosomeValue2);
			(m_pIndividualNum1+i)->SetChromosome(ChromosomeValue1);
			(m_pIndividualNum1+i+1)->SetChromosome(ChromosomeValue2);

		}		
	}
	delete [] ChromosomeValue1;
	delete [] ChromosomeValue2;
}
void Cpopulation::MutationOperator(double MutationRate)
{
	double temp;
	for(int i=0;i<m_PopulationSize;i++)
	{
		int *ChromosomeValue = new int[m_ChromosomeLength*m_DimensionNum];
		(m_pIndividualNum1+i)->GetChromosomeValue(ChromosomeValue);
		for(int k=0;k<m_ChromosomeLength*m_DimensionNum;k++)
		{
			temp= (rand()%1000)/1000.0;

	    	if(temp<MutationRate)

			{
	        	if(*(ChromosomeValue+k)==0)
				{
		    	*(ChromosomeValue+k)=1;
				}
	        	else
				{
		    	*(ChromosomeValue+k)=0;
				}			
			}
		}
		(m_pIndividualNum1+i)->SetChromosome(ChromosomeValue);
		delete [] ChromosomeValue;		
	}	
	for(int j=0;j<m_PopulationSize;j++)
	{
		int *ChromosomeValue = new int[m_ChromosomeLength*m_DimensionNum];
		(m_pIndividualNum1+j)->GetChromosomeValue(ChromosomeValue);
		(m_pIndividualNum+j)->SetChromosome(ChromosomeValue);
		(m_pIndividualNum+j)->DecodeChromosome();
		(m_pIndividualNum+j)->CalculateFitnessValue(m_MaxOrMin);
		(m_pIndividualNum+j)->CalculateObjectValue();
		ComputerSelectionRate();
    	delete [] ChromosomeValue;
	}
}
void Cpopulation::PopulationEvolution(int GenerationNum)
{
	srand((unsigned)time(NULL));
	int    *ChromosomeValue = new int[m_ChromosomeLength*m_DimensionNum];
	double BestValue;
	ofstream file1("file1.txt");
	for(int i=1;i<=GenerationNum;i++)
	{   
		  GetPerGenerationBestValue();
	      GetPerGenerationAvgValue();
          GetPerGenerationWorseValue();
		  OutputPerGenerationInformation(i);
		  BestValue=*(m_pBestIndividualValue+0);		  
		  for(int k=0;k<m_ChromosomeLength*m_DimensionNum;k++)
		  {
			  *(ChromosomeValue+k)=*(m_pBestIndividualChromosome+k);
		  }
		  file1<<i<<" ";
		  file1<<*(m_pBestIndividualValue+0)<<" ";
		  file1<<m_PerGenerationAvgValue<<endl;
		  ComputerSelectionRate();
		  SelectionOperator();
          crossoverOperator(m_CrossoverRate);
		  MutationOperator(m_MutationRate);
          GetPerGenerationBestValue();
          GetPerGenerationAvgValue();
          GetPerGenerationWorseValue();
	     if(*(m_pBestIndividualValue+0)<BestValue)
		  {
			 (m_pIndividualNum+m_BestIndividualIndex)->SetChromosome(ChromosomeValue);
			 (m_pIndividualNum+m_BestIndividualIndex)->DecodeChromosome();
		     (m_pIndividualNum+m_BestIndividualIndex)->CalculateFitnessValue(m_MaxOrMin);
		     (m_pIndividualNum+m_BestIndividualIndex)->CalculateObjectValue();
			 (m_pIndividualNum+m_WorseIndividualIndex)->SetChromosome(m_pBestIndividualChromosome);
			 (m_pIndividualNum+m_WorseIndividualIndex)->DecodeChromosome();
		     (m_pIndividualNum+m_WorseIndividualIndex)->CalculateFitnessValue(m_MaxOrMin);
		     (m_pIndividualNum+m_WorseIndividualIndex)->CalculateObjectValue();

		  }
		 else
		 {
			 (m_pIndividualNum+m_WorseIndividualIndex)->SetChromosome(ChromosomeValue);
			 (m_pIndividualNum+m_WorseIndividualIndex)->DecodeChromosome();
		     (m_pIndividualNum+m_WorseIndividualIndex)->CalculateFitnessValue(m_MaxOrMin);
		     (m_pIndividualNum+m_WorseIndividualIndex)->CalculateObjectValue();
		 }		  
	}
}
int  Cpopulation::GetPopulationSize()
{
     return m_PopulationSize;
}
int  Cpopulation::GetObjectNum()
{
	 return m_ObjectNum;
}
int  Cpopulation::GetDimensionNum()
{
	 return m_DimensionNum;
}
double  Cpopulation::GetCrossoverRate()
{
	 return m_CrossoverRate;
}
double  Cpopulation::GetMutationRate()
{
	 return m_MutationRate;
}
int  Cpopulation::GetChromosomeLength()
{
	 return m_ChromosomeLength;
}