nsgapopulation.cpp

遗传算法程序最新版

/***************************************************************
/* Single & Multi-Objective Real-Coded Genetic Algorithms Code */
/* Author: Kumara Sastry                                       */
/* Illinois Genetic Algorithms Laboratory (IlliGAL)            */
/* Deparment of General Engineering                            */
/* University of Illinois at Urbana-Champaign                  */
/* 104 S. Mathews Ave, Urbana, IL 61801                        */
/***************************************************************/

#include "population.hpp"

NsgaPopulation::NsgaPopulation(void) 
{
  int ii, combinedPopSize = 2*(globalSetup->populationSize);
  numFronts = 0;
  numFrontChange = 0;
  combinedGuys = new NsgaIndividual*[combinedPopSize];
  numIndsFront = new int[combinedPopSize];
  paretoFront = new int*[combinedPopSize];
  for(ii = 0; ii < combinedPopSize; ii++) {
    combinedGuys[ii] = new NsgaIndividual;
    paretoFront[ii] = new int[combinedPopSize];
  }
  bestobj = new double[globalSetup->finalNoOfObjectives];
  worstobj = new double[globalSetup->finalNoOfObjectives];
  avgobj = new double[globalSetup->finalNoOfObjectives];
  maxfit = new double[globalSetup->finalNoOfObjectives];
  minfit = new double[globalSetup->finalNoOfObjectives];
  avgfit = new double[globalSetup->finalNoOfObjectives];  
  varfit = new double[globalSetup->finalNoOfObjectives];  
  computeObjStatistics(GUYS);
  mapObjectiveToFitness(GUYS);
  computeFitnessStatistics(GUYS);
}

NsgaPopulation::~NsgaPopulation(void) 
{
  int ii, combinedPopSize = 2*(globalSetup->populationSize);
  for(ii = 0; ii < combinedPopSize; ii++) {
    delete combinedGuys[ii];
    delete paretoFront[ii];
  }
  delete []combinedGuys;
  delete []numIndsFront;
  delete []paretoFront;
  delete []bestobj;
  delete []worstobj;
  delete []avgobj;
  delete []minfit;
  delete []maxfit;
  delete []avgfit;
  delete []varfit;
}


/***
Peforms a nondominated sort of individuals to create a set of pareto fronts.
Details: 
  *  The flag whichGuys refer to either the current population (for the initial generation) or the combined population.
  *  domCount[i]: (domination count) Number of the individuals that dominate individual i
  *  numIndDom[i]: Number of individuals that individual i dominates
  *  indDomByMe[i]: Array of indices of individuals that individual i dominates
  *  paretoFront[i]: Array of indices of individuals that are members of pareto front i.
  *  numIndsFront[i]: Number of individuals in the ith front.
  *  For every unique pair of individuals (i,j)
     --Check if i dominates j, If yes then add j to indDomByMe[i], increment numIndDom[i] by 1 and increment domCount[j] by 1.
     --On the other hand if j dominates i, then add i to indDomByMe[j], increment numIndDom[j] by 1 and increment domCount[i] by 1.
  * For every individual i
     --If domCount[i] equals 0, then add individual i to paretoFront[0], increment numIndsFront[0], and set the rank of individual i to 0
  * Set frontID = 0. While number of individuals in the pareto Front is greater than zero, do
     --For every individual i in the pareto front frontID 
         *  For every individual j that individual i dominates
	    --Decrement the domination count of j by i
            --If the domination count of j is equal to zero, then add j to the paretoFron[frontID+1], increment numIndsFront[frontID+1], and set the rank of individual j to frontID+1.
     --Increment the frontID by one
 * Set total number of pareto fronts to frontID.
*/
void NsgaPopulation::doNonDominatedSort(int whichGuys)
{
  int ii, jj, popSize, fid, idomj, nif;
  int *domCount, **indDomByMe, *numIndDom;
  int oldNoOfFronts;
  NsgaIndividual **theGuys;

  oldNoOfFronts = numFronts;

  if(whichGuys == GUYS) {
    popSize = globalSetup->populationSize;
    theGuys = (NsgaIndividual**)guys;
  }
  else if(whichGuys == COMBINEDGUYS) {
    popSize = 2*(globalSetup->populationSize);
    theGuys = combinedGuys;
  }
  domCount = new int[popSize];
  numIndDom = new int[popSize];
  indDomByMe = new int*[popSize];
  for(ii = 0; ii < popSize; ii++) { 
    indDomByMe[ii] = new int[popSize];
    domCount[ii] = numIndDom[ii] = 0;
  }
  for(ii = 0; ii < popSize-1; ii++) {
    for(jj = ii+1; jj < popSize; jj++) {
      idomj = dominates(theGuys[ii],theGuys[jj]);//根据适应度进行优劣判断
      if(idomj == IDOMJ) {
	indDomByMe[ii][numIndDom[ii]] = jj;
	numIndDom[ii] += 1;
	domCount[jj] += 1;
      }                                          //将种群中每个个体的优劣进行相互比较，indDomByMe[i][]数组表示被i                                              //
      else if(idomj == JDOMI) {                  //个体支配的个体标号，numIndDom[i]是被i支配的个体总数，domCount[i]
	indDomByMe[jj][numIndDom[jj]] = ii;          //是支配i的个体数目
	numIndDom[jj] += 1;
	domCount[ii] += 1;
      }
    }
  }
  nif = 0;

  for(ii = 0; ii < popSize; ii++) {
    if(domCount[ii] == 0) {
      paretoFront[0][nif++] = ii;                //将pareto最优个体的标号存入paretoFront[0][],将其Rank置0
      theGuys[ii]->setRank(0);
    }
  }
  numIndsFront[0] = nif;             //numIndsFront[i]为第i层的个体总数

  fid = 0;
  while(numIndsFront[fid] != 0) {
    nif = 0;
    for(ii = 0; ii < numIndsFront[fid]; ii++) {
      for(jj = 0; jj < numIndDom[paretoFront[fid][ii]]; jj++) {
	domCount[indDomByMe[paretoFront[fid][ii]][jj]] -= 1;             //将非支配个体层数减一，若为0依次放入次层，置Rank值
	if(domCount[indDomByMe[paretoFront[fid][ii]][jj]] == 0) {        //即为非劣分层算法->NSGA-2
	  paretoFront[fid+1][nif++] = indDomByMe[paretoFront[fid][ii]][jj];
	  theGuys[indDomByMe[paretoFront[fid][ii]][jj]]->setRank(fid+1);
	}
      }
    }
    fid += 1;
    numIndsFront[fid] = nif;
  }
  numFronts = fid;
  numFrontChange = abs(oldNoOfFronts - numFronts);
  if(whichGuys == GUYS) 
    for(ii = 0; ii < popSize; ii++) guys[ii] = theGuys[ii];
  else if(whichGuys == COMBINEDGUYS)
    for(ii = 0; ii < popSize; ii++) combinedGuys[ii] = theGuys[ii];
  
  for(ii = 0; ii < popSize; ii++) 
    delete indDomByMe[ii];
  delete []domCount;
  delete []numIndDom;
  delete []indDomByMe;
}

/***
Computes the crowding distance of each individual.
Details:
  * The flag whichGuys refer to either the current population (for the initial generation) or the combined population.
  * For every front i
    -- For every objective j
       * Sort the individuals in front i in ascending order of objective j
       * Set the crowding distance of the first and the last individual to infinity
       * For every individual k in the front i except the first and the last individuals
         --Normalize the fitness j by dividing the fitness j of individual k-1  and individual k+1 by maximum jth fitness.
	 --Add absolute value of (Normalized jth fitness of individual k+1 - Normalized jth fitness of individual k-1) to the crowding distance of kth individual.
*/
void NsgaPopulation::computeCrowdingDistance(int whichGuys)
{
  int ii, jj, kk, firstInd, lastInd;
  int indId1, indId2, indId, popSize;
  int *sortListByObj;
  double normFit1, normFit2, *crowdDist;
  NsgaIndividual **theGuys;
  
  if(whichGuys == GUYS) {
    popSize = globalSetup->populationSize;
    theGuys = (NsgaIndividual**)guys;
  }
  else if(whichGuys == COMBINEDGUYS) {
    popSize = 2*(globalSetup->populationSize);
    theGuys = combinedGuys;
  }

  crowdDist = new double[popSize];
  for(ii = 0; ii < popSize; ii++) crowdDist[ii] = 0.0;

  for(ii = 0; ii < numFronts; ii++) {
    sortListByObj = new int[numIndsFront[ii]];
    for(jj = 0; jj < globalSetup->finalNoOfObjectives; jj++) {
      for(kk = 0; kk < numIndsFront[ii]; kk++)
	sortListByObj[kk] = paretoFront[ii][kk];
      quickSort(theGuys, sortListByObj, 0, numIndsFront[ii],jj);       //对每层的个体进行排序
      firstInd = sortListByObj[0];
      lastInd = sortListByObj[numIndsFront[ii]-1];
      crowdDist[firstInd] = crowdDist[lastInd] = INFTY;
      for(kk = 1; kk < numIndsFront[ii]-1; kk++) {
	indId = sortListByObj[kk];
	indId1 = sortListByObj[kk+1];
	indId2 = sortListByObj[kk-1];
	normFit1 = theGuys[indId1]->getFitness(jj)/(1.0+maxfit[jj]);         
	normFit2 = theGuys[indId2]->getFitness(jj)/(1.0+maxfit[jj]);
	crowdDist[indId] += fabs(normFit1 - normFit2);                //确定个体的拥挤度