operators_nsga2.cpp

多目标优化进化算法目前公认效果收敛性最好的算法NSGA2c++源码,具有一般性

///////////////////////////////////////////////////////////////////
/*****************************************************************
Copyright: Artificial Life and Adaptive Robotics Laboratory - ALAR
School of ITEE, UNSW@ADFA, Australia, 2005
*******************************************************************/
///////////////////////////////////////////////////////////////////


#include "operators_NSGA2.h"
#include <assert.h>


operators_NSGA2::~operators_NSGA2()
{
	if (max_values) {delete [] max_values; max_values=NULL;}
	if (min_values) {delete [] min_values; min_values=NULL;}
}

// create population q from population p by crowded tournament selection
void operators_NSGA2::selection(population &q,population &p)   // same size
{
	
	int size=p.pop_size;  // population size , the same for both a and p
	
	
	individual mate1,mate2;
	
	int index1,index2,rank1,rank2;
	int c=0;
	
	
	crowding_sort(p, FALSE);
	
	while(c<size)
	{
		
		index1=(int)(rnd.nextDouble()*(size)); 
		if (index1>=size) index1=size-1;
		
		index2=(int)(rnd.nextDouble()*(size));
		if (index2>=size) index2=size-1;
		
		mate1=p.individuals[index1];
		mate2=p.individuals[index2];
		
		rank1=mate1.rank;// p.rank[index1];
		rank2=mate2.rank;// p.rank[index2];
		
		//crowded tournament selection
		if (rank1<rank2) 
			q.individuals[c]=mate1; 
		if (rank1>rank2)
			q.individuals[c]=mate2;
		if (rank1==rank2)
		{
			if (mate1.DglobalFitness>mate2.DglobalFitness)
				q.individuals[c]=mate1;
			else
				q.individuals[c]=mate2;
		}
		c += 1;
	}
}

void operators_NSGA2::crossover(population &pop)
{
	individual mate1,mate2;
	int size=pop.pop_size/2;
	int CH_LEN=pop.individuals[0].chromosome_len;
	
	
	
	int csite=0,i,index, counter=0;
	
	int nc=0;	
	
	
	
	unsigned int *cc1=new unsigned int[CH_LEN]; 
	unsigned int *cc2=new unsigned int[CH_LEN];
	//unsigned int *cm1=new unsigned int[CH_LEN];
	//unsigned int *cm2=new unsigned int[CH_LEN];
	individual temp;//=NULL;
	index=0;
	temp=pop.individuals[0];
	while (counter<size)
	{
		// selcect parents
		
		mate1=pop.individuals[index] ;
		index++;
		
		mate2=pop.individuals[index];
		index++;
		//copyarray(cm1,mate1.Bgenes,CH_LEN);
		//copyarray(cm2,mate2.Bgenes,CH_LEN);
		
		
		//crossover
		double r=rnd.nextDouble();
		if (r<=pc) // do crossover
		{
			nc++;
			csite=(int)(rnd.nextDouble()*(CH_LEN));
			if (csite>=CH_LEN) csite=CH_LEN-1;
			for (i=0;i<csite;i++)
			{
				//cc1[i]=cm1[i];
				//cc2[i]=cm2[i];
				cc1[i]=mate1.Bgenes[i];
				cc2[i]=mate2.Bgenes[i];
			}
			for (i=csite;i<CH_LEN;i++)
			{
				//cc1[i]=cm2[i];
				//cc2[i]=cm1[i];
				cc1[i]=mate2.Bgenes[i];
				cc2[i]=mate1.Bgenes[i];
			}
		}
		else  //  copying
		{
			for (i=0;i<CH_LEN;i++)
			{
				//cc1[i]=cm1[i];
				//cc2[i]=cm2[i];
				cc1[i]=mate1.Bgenes[i];
				cc2[i]=mate2.Bgenes[i];
			}
		}
		
		
		temp.set_chromosome(cc1);
		set_objectivevalue(temp,temp.Dgenes); 
		pop.individuals[counter]=temp; 
		
		
		temp.set_chromosome(cc2); 
		set_objectivevalue(temp,temp.Dgenes);
		pop.individuals[counter+1]=temp;
		counter += 2;
    }
	
	if (cc1) {delete [] cc1;cc1=NULL;}
	if (cc2) {delete [] cc2;cc2=NULL;}
	//if (cm1) {delete [] cm1;cm1=NULL;}
	//if (cm2) {delete [] cm2;cm2=NULL;}
}

void operators_NSGA2::mutation(population &pop)
{
	if ((pm<=0)||(pm>1)) return;
	
	int size=pop.pop_size/2;
	int CH_LEN=pop.individuals[0].chromosome_len;
	
	//population newpop;
	int i,counter=0;
	double r;
	int nc=0;	
	unsigned int *cm1=new unsigned int[CH_LEN];
	
	//newpop.set_pop_size(size); 
	
	//rnd.setSeed(n_SEED); 
	
	individual mate1;
	individual temp;//=NULL;
	temp=pop.individuals[0];
	while (counter<size)
	{
		mate1=pop.individuals[counter];
		copyarray(cm1,mate1.Bgenes,CH_LEN);
		
		for (i=0;i<CH_LEN;i++)
		{
			r=rnd.nextDouble();
			if (r<=pm)
			{
				cm1[i]=(cm1[i]==0)?1:0;
			}
		}
		
		temp.set_chromosome(cm1);
		set_objectivevalue(temp,temp.Dgenes); 
		
		pop.individuals[counter]=temp; 
		
		counter += 1;
	}
	if (cm1) {delete [] cm1;cm1=NULL;}
}

void operators_NSGA2::crowding_sort(population &F, int sort)
{
	
	int i,j,k,size = F.pop_size;
	
	double t1,t2;
	individual Itemp;
	for (i=0;i<size;i++)    // to store array index
	{
		
		F.individuals[i].DglobalFitness=0;
	}
	
	int NObjs=F.individuals[0].InumberofObjs;
	
	if (size<=2) return;   // 2 individuals: select which one?
	
	for (k=0;k<NObjs;k++)   // sort the set in the order of ith objective
	{
		
		for(i=0;i<size-1;i++)
		{
			for (j=i+1;j<size;j++)	
			{
				t1 = F.individuals[i].DfitnessN[k];
				t2 = F.individuals[j].DfitnessN[k];
				if (t1>t2)
				{
					Itemp            = F.individuals[i];
					F.individuals[i] = F.individuals[j];
					F.individuals[j] = Itemp; 
				}
			}
		}
		
		F.individuals[0].DglobalFitness=D_MAX;
		F.individuals[size-1].DglobalFitness=D_MAX;
		
		for(i=1;i<size-1;i++)
		{
			double temp=F.individuals[i].DglobalFitness;
			if (temp<D_MAX)
			{
				temp+=fabs(F.individuals[i+1].DfitnessN[k]-F.individuals[i-1].DfitnessN[k])/(max_values[k]-min_values[k]);	
				F.individuals[i].DglobalFitness=temp; 
			}
		}
		if ((k==0)&&((objID==7)||(objID==8))&& (!sort)) 
		{
			F.individuals[0].DglobalFitness=2*F.individuals[1].DglobalFitness;
		}
	}
	
	////////sorting crowding values: descending order ///////////////////////////////////
	if (sort){		
		for(i=0;i<size-1;i++)
		{
			for (j=i+1;j<size;j++)	
			{
				t1=F.individuals[i].DglobalFitness;
				t2=F.individuals[j].DglobalFitness;
				if (t1<t2)
				{
					Itemp=F.individuals[i];
					F.individuals[i]=F.individuals[j];
					F.individuals[j]=Itemp; 
				}
			}
		}
	}
}

void operators_NSGA2::set_objectivevalue_maxmin(population &p, int size)
{
	int i,j;
	int p_size=p.pop_size; 
	for (i=0;i<size;i++)
	{
		
		min_values[i]=p.individuals[0].DfitnessN[i];
		max_values[i]=p.individuals[0].DfitnessN[i];
		for (j=1;j<p_size;j++)
		{	
			if (p.individuals[j].DfitnessN[i]<min_values[i])
				min_values[i]=p.individuals[j].DfitnessN[i];
			
			if (p.individuals[j].DfitnessN[i]>max_values[i])
				max_values[i]=p.individuals[j].DfitnessN[i];
		}	
	}
	
}

void operators_NSGA2::copyarray(unsigned int *&d, unsigned int *s,int size)
{
	for (int i=0;i<size;i++)
		d[i]=s[i];
}

void operators_NSGA2::initialize_population(const int n_Genes,int n_Objs,int *GSize,double *Ub,double *Lb,population &pop)
{
	int i,j;
	double *real_params;
	
	real_params=new double[n_Genes];
	
	individual *id_temp=NULL;
	
	for(i=0;i<pop.pop_size;i++)
	{
		
		for(j=0;j<n_Genes;j++)     // initialize real values for x1,x2,..xn
			real_params[j]=Lb[j] + rnd.nextDouble()*(Ub[j]-Lb[j]);
		
		if (id_temp) {delete id_temp;id_temp=NULL;}
		id_temp=new individual(n_Genes,n_Objs,GSize,Ub,Lb,real_params,TRUE); 
		
		
		
		set_objectivevalue(*id_temp,real_params);
		
		
		pop.individuals[i]=*id_temp; 
	}
	
	add_secondobjective(pop,pop.pop_size);
	
	if (real_params) {delete [] real_params; real_params=NULL;}
	if (id_temp) {delete id_temp;id_temp=NULL;}
	
}

void operators_NSGA2::set_objectivevalue(individual &id, double *real_params)
{
	
	int j,n_Objs=id.InumberofObjs;