population.cpp

遗传算法程序最新版

void Population::computeFitnessStatistics(void)
{
  int ii, bestIndvID, worstIndvID;
  double oneOverPopulationSize;
  double oldMaxFit, oldAvgFit, oldFitVar;

  // have to compute maxobj, minobj, maxfit, minfit, avgfit, bestInd,
  // fitnessVariance, objectiveVariance
  oneOverPopulationSize = 1.0/(1.0*(globalSetup->populationSize));

  oldMaxFit = *maxfit;
  oldFitVar = *varfit;
  oldAvgFit = *avgfit;

  *varfit = oneOverPopulationSize*(newGuys[0]->getFitness())*(newGuys[0]->getFitness());
  *avgfit = oneOverPopulationSize*(newGuys[0]->getFitness());
  bestIndvID = worstIndvID = 0;

  for(ii = 1; ii < globalSetup->populationSize; ii++) {
    *avgfit += oneOverPopulationSize*(newGuys[ii]->getFitness());
    *varfit += oneOverPopulationSize*(newGuys[ii]->getFitness())*(newGuys[ii]->getFitness());
    if(selection->betterIndividual(newGuys[ii], newGuys[bestIndvID])) bestIndvID = ii;
    if(selection->betterIndividual(newGuys[worstIndvID], newGuys[ii])) worstIndvID = ii;
  }
  *varfit -= (*avgfit)*(*avgfit);
  *maxfit = newGuys[bestIndvID]->getFitness();
  *minfit = newGuys[worstIndvID]->getFitness();
  
  *(bestInd) = *(newGuys[bestIndvID]);
  *bestFitChange = fabs(oldMaxFit - *maxfit);
  *avgFitChange = fabs(oldAvgFit - *avgfit);
  *fitVarChange = fabs(oldFitVar - *varfit);
}

/*============================================================
** Function Name: Population::loadPopulationFromFile(void)
** Function Task: this method calls Individual::evaluateFitness().
** unless the Niching type is Detereministic Crowding because
** the fitness evaluation be required soon after offsprings are
** generated during crossover.
** Output:None
** Functions called: Individual::evaluateFitness();
**========================================================*/
void Population::loadPopulationFromFile(void)
{
  int ii, numGlobalEvals = 0, jj;
  int numSolutions, numToLoad;
  double *variableValues;
  double *objValues, *constViolValues;
  double dummy;
  double penaltyValue;

  variableValues = new double[globalSetup->noOfDecisionVariables];
  objValues = new double[globalSetup->finalNoOfObjectives];
  constViolValues = new double[globalSetup->finalNoOfConstraints];

  std::ifstream infile(globalSetup->populationFileName);
  infile >> numSolutions;
  if(numSolutions > globalSetup->populationSize) 
    numToLoad = globalSetup->populationSize;
  else
    numToLoad = numSolutions;
  printf("Loading initial population of size %d\n", numSolutions);
  for(ii = 0; ii < numToLoad; ii++) {
    for(jj = 0; jj < globalSetup->noOfDecisionVariables; jj++) {
      infile >> variableValues[jj];
      //      printf("%14.10f ", variableValues[jj]);
    }
    for(jj = 0; jj < globalSetup->finalNoOfObjectives; jj++) {
      infile >> objValues[jj];
    }
    if(globalSetup->finalNoOfConstraints) {
      for(jj = 0; jj < globalSetup->finalNoOfConstraints; jj++) {
	infile >> constViolValues[jj];
      }
      infile >> penaltyValue;
    }
    //    printf("%f %f\n", objValues[0], objValues[1]);
    guys[ii]->loadIndividual(variableValues,objValues,constViolValues,penaltyValue);
    newGuys[ii]->loadIndividual(variableValues,objValues,constViolValues,penaltyValue);
  }
  if(globalSetup->evaluateAgain) {
    for(ii = 0; ii < globalSetup->populationSize; ii++) {
      guys[ii]->evaluateFitness();
      if(globalSetup->gaType == NSGA) {
	for(jj = 0; jj < globalSetup->finalNoOfObjectives; jj++) {
          ((NsgaIndividual *)(newGuys[ii]))->setObjective(jj, ((NsgaIndividual *)(guys[ii]))->getObjective(jj));
	}
	for(jj = 0; jj < globalSetup->finalNoOfConstraints; jj++) {
          ((NsgaIndividual *)(newGuys[ii]))->setViolation(jj, ((NsgaIndividual *)(guys[ii]))->getViolation(jj));
	}
      }
      else {
	newGuys[ii]->setObjective(guys[ii]->getObjective());
	for(jj = 0; jj < globalSetup->finalNoOfConstraints; jj++) {
          newGuys[ii]->setViolation(jj, guys[ii]->getViolation(jj));
	}
      }
      newGuys[ii]->setPenalty(guys[ii]->getPenalty());
      newGuys[ii]->setNoOfViolations(guys[ii]->getNoOfViolations());
    }
  }
  else if(numSolutions < globalSetup->populationSize) {
    for(ii = numSolutions; ii < globalSetup->populationSize; ii++) {
      guys[ii]->evaluateFitness();
      if(globalSetup->gaType == NSGA) {
	for(jj = 0; jj < globalSetup->finalNoOfObjectives; jj++) {
          ((NsgaIndividual *)(newGuys[ii]))->setObjective(jj, ((NsgaIndividual *)(guys[ii]))->getObjective(jj));
	}
	for(jj = 0; jj < globalSetup->finalNoOfConstraints; jj++) {
	  ((NsgaIndividual *)(newGuys[ii]))->setViolation(jj, ((NsgaIndividual *)(guys[ii]))->getViolation(jj));
	}
      }
      else {
        newGuys[ii]->setObjective(guys[ii]->getObjective());
	for(jj = 0; jj < globalSetup->finalNoOfConstraints; jj++) {
          newGuys[ii]->setViolation(jj, guys[ii]->getViolation(jj));
	}
      }
      newGuys[ii]->setPenalty(guys[ii]->getPenalty());
      newGuys[ii]->setNoOfViolations(guys[ii]->getNoOfViolations());
    }
  }
  delete []variableValues;
  delete []objValues;
  delete []constViolValues;
  infile.close();
}


/*============================================================
** Function Name: Population::doEvaluate(void)
** Function Task: this method calls Individual::evaluateFitness().
** unless the Niching type is Detereministic Crowding because
** the fitness evaluation be required soon after offsprings are
** generated during crossover.
** Output:None
** Functions called: Individual::evaluateFitness();
**========================================================*///未找到
int Population::doEvaluate(void)
{
  int ii, numGlobalEvals = 0;

  if(globalSetup->nichingType != DeterministicCrowding)
    for(ii = 0; ii < globalSetup->populationSize; ii++)
      newGuys[ii]->evaluateFitness();
  numGlobalEvals = globalSetup->populationSize;
  return numGlobalEvals;
}

/*============================================================
** Function Name: Population::doLocalSearch(void)
** Function Task: This method calls local searcher for each of
** the individuals in the population with probability
** localSearchProbability.
** A Lamarckian (backsubstituting point obtained from local search)
** or Baldwinian (taking only the fitness value of the point from
** local searcher and not its structure) strategy is used based on
** the lamarckianProbability.
** Output:None
** Functions called: LocalSearch::localSearch()
**========================================================*///未看
int Population::doLocalSearch(void)
{
  int ii, jj, numLocalEvals = 0, numEvals;
  Individual *localGuy;

  localGuy = new Individual;

  if((globalSetup->gaType == SGA) &&
     (globalSetup->localSearchMethod != NoLocalSearch)) {

    for(ii = 0; ii < globalSetup->populationSize; ii++) {
      if(myRandom.flip(globalSetup->localSearchProbability)) {
	numEvals = localSearch->localSearcher(newGuys[ii],localGuy,freezeMask);
	numLocalEvals += numEvals;
	if(myRandom.flip(globalSetup->lamarckianProbability))
	  *newGuys[ii] = *localGuy;
	else {
	  for(jj = 0; jj < globalSetup->noOfDecisionVariables; jj++)
	    localGuy->setValue(jj,(*newGuys[ii])[jj]);
	  *newGuys[ii] = *localGuy;
	}
      }
    }
  }
  delete localGuy;
  return numLocalEvals;
}

/***
Replace the old population with the new population. Incorporates elitism using the parameter globalSetup::replaceProportion. If the value of replaceProportion is less than 1.0 then the bottom (100*replaceProportion)% individuals from the current population are replaced by the top (100*replaceProportion)% individuals from the new population.
*/
void Population::replacePopulation(void)
{
  int ii, startIndex, *randomArray1, *randomArray2;

  if(fabs(globalSetup->replaceProportion - 1.0) <= ZERO) {
    Individual **temp = newGuys;
    newGuys = guys;
    guys = temp;
  }
  else {
    Individual **eliteGuys;
    randomArray1 = new int[globalSetup->populationSize];
    randomArray2 = new int[globalSetup->populationSize];

    for(ii = 0; ii < globalSetup->populationSize; ii++) {
      randomArray1[ii] = ii;
      randomArray2[ii] = ii;
    }
    rankingQuickSort(randomArray1, 0, globalSetup->populationSize);

    Individual **temp = newGuys;
    newGuys = guys;
    guys = temp;

    rankingQuickSort(randomArray2, 0, globalSetup->populationSize);

    eliteGuys = new Individual*[globalSetup->populationSize];

    startIndex = (int)((1.0-globalSetup->replaceProportion)*(globalSetup->populationSize));

    for(ii = 0; ii < startIndex; ii++)
      eliteGuys[ii] = new Individual(newGuys[randomArray2[globalSetup->populationSize-1-ii]]);
    for(ii = startIndex; ii < globalSetup->populationSize; ii++)
      eliteGuys[ii] = new Individual(guys[randomArray1[globalSetup->populationSize - 1 - ii + startIndex]]);

    for(ii = 0; ii < globalSetup->populationSize; ii++) {
      *(newGuys[ii]) = *(eliteGuys[ii]);
      delete eliteGuys[ii];
    }
    delete []eliteGuys;
  }
}

///Perfrom selection
void Population::doSelect(void) { selection->select(mpool); }

///Perform crossover
void Population::doCrossover(void)
{
  int ii;
  for(ii = 0; ii < globalSetup->populationSize; ii += 2)
    if(myRandom.flip(globalSetup->xOverProbability))
      crossover->crossover(newGuys[ii], newGuys[ii+1]);
}

///Perform mutation
void Population::doMutate(void)
{
  int ii;
  for(ii = 0; ii < globalSetup->populationSize; ii++)
    newGuys[ii]->mutate(freezeMask);
}

/***
Map objective to fitness depending on minimization or maximzation and the constraint handling method.
If the problem is a maximization and the constraint handling method is either a tournament method or if there are no constraints, then the fitness is set equal to the objective value. If the constraint handling method is penalty then the fitness is equal to the objective value minus the penalty due to constraint violation. On the other hand, if the problem is a minimization one and the constraint handling method is either a tournament method or if there are no constraints, then set the fitness equal to the negative of the objective value. If the constraint handling method is the penalty method then the fitness is equal to the negative of the objective value minus the penalty due to constraint violation.
*/
void Population::mapObjectiveToFitness(void)
{
  int ii;
  if(*(globalSetup->typeOfOptimizations) == Maximization) {
    switch(globalSetup->constraintMethod) {
    case NoConstraints: case Tournament:
      for(ii = 0; ii < globalSetup->populationSize; ii++)
	newGuys[ii]->setFitness(newGuys[ii]->getObjective());
      break;
    case Penalty:
      for(ii = 0; ii < globalSetup->populationSize; ii++)
	newGuys[ii]->setFitness(newGuys[ii]->getObjective() - newGuys[ii]->getPenalty());
      break;
    default: exit(0);
    }
  }
  else {
    switch(globalSetup->constraintMethod) {
    case NoConstraints: case Tournament:
      for (ii=0;ii<globalSetup->populationSize; ii++)
	newGuys[ii]->setFitness(-newGuys[ii]->getObjective());
      break;
    case Penalty:
      for(ii = 0; ii < globalSetup->populationSize; ii++)
	newGuys[ii]->setFitness(-newGuys[ii]->getObjective() - newGuys[ii]->getPenalty());
      break;
    default: exit(0);
    }
  }
}

/***
 Procedures for scaling fitness used with proportionate selection schemes and with fitness sharing. Two scaling methods (1) Sigma scaling (truncation), and (2) ranking are provided.
Ranking Method: Sort the individuals according to their fitness and constraint violation and assign a linear ranking as the new fitness. Here the best individual has a fitness of N and the worst individual has a fitness value of 1.
Reference:  Baker, J.E. (1985). "Adaptive Selection Methods for Genetic Algorithms", In Grefenstte, J. (Ed.), Proceedings of the International Conference on Genetic Algorithms and Their Applications (pp. 101-111). Hillsdale, NJ:Lawrence Erlbaum Associates (TCGA No. 00460).
Sigma Scaling (Truncation): Scale the fitness using as
fscaled = 1 + (f - favg)/(sigmaParameter*fstd),
where f is the fitness of the individual, favg is the average fitness, and fstd is the standard deviation of fitness and sigmaParameter is usually taken as 2.0.
If the fscaled is less than 0.0 then it is arbitrarily set a low value of 0.1.
Reference: Forrest, S. (1985). "Documentation for PRISONERS DILEMMA and NORMS programs that use the genetic algorithm. Unpublished manuscript, University of Michigan, Ann Arbor. (TCGA No. 00614).
If none of the scaling method is used and the minimum fitness is negative then an absolute value of the minimum fitness is added to the fitness of each individual.
*///缩放适应度
void Population::scaleFitness(void)
{
  double sigmaParam;
  int *randomArray, ii;
  double fitStdDev, scaledFitness, sigTerm;

  randomArray = new int[globalSetup->populationSize];
  switch(globalSetup->scalingMethod) {
  case Ranking:
    for(ii = 0; ii < globalSetup->populationSize; ii++)
      randomArray[ii] = ii;
    rankingQuickSort(randomArray, 0, globalSetup->populationSize);
    scaledFitness = 1.0*(globalSetup->populationSize);
    newGuys[randomArray[globalSetup->populationSize - 1]]->setFitness(scaledFitness);

    for(ii = globalSetup->populationSize-2; ii >= 0; ii--) {
      if(selection->betterIndividual(newGuys[randomArray[ii+1]],newGuys[randomArray[ii]]))
	scaledFitness = newGuys[randomArray[ii+1]]->getFitness() - 1.0;
      newGuys[randomArray[ii]]->setFitness(scaledFitness);
    }
    break;
  case SigmaScaling:
    sigmaParam = ((double *)globalSetup->scalingParameters)[0];
    fitStdDev = sqrt(*varfit);
    for(ii = 0; ii < globalSetup->populationSize; ii++) {
      if(fitStdDev >= 0.0001) {
	sigTerm = sigmaParam * fitStdDev;
	scaledFitness = (newGuys[ii]->getFitness() -
			 *avgfit + sigTerm)/sigTerm;
      }
      else
	scaledFitness = (newGuys[ii]->getFitness() + *avgfit)/(2.0*(*avgfit));
      if(scaledFitness < 0.0) scaledFitness = 0.1;
      newGuys[ii]->setFitness(scaledFitness);
    }
    break;
  default:
    if(*minfit < 0.0) {
      for(ii = 0; ii < globalSetup->populationSize; ii++) {
	scaledFitness = newGuys[ii]->getFitness() - *minfit;
	newGuys[ii]->setFitness(scaledFitness);
      }
    }
  }
  delete []randomArray;
}

/// Quick sort procedure used for ranking selection　未看透
void Population::rankingQuickSort(int *output, int left, int right)
{
  int ii, xx;
  Individual *target;

  if(right > left) {
    target = newGuys[output[right-1]];
    ii = left-1;
    xx = right-1;
    for(;;) {
      while(!(selection->betterIndividual(newGuys[output[++ii]],target)))
	if(ii >= right-1) break;
      if(ii >= xx) break;
      while(selection->betterIndividual(newGuys[output[--xx]],target))
	if(xx <= 0) break;
      if(ii >= xx) break;
      swap(output[ii],output[xx]);
    }
    swap(output[ii],output[right-1]);
    rankingQuickSort(output, left, ii);
    rankingQuickSort(output, ii+1, right);
  }
}

/// swap procedure used by quick sort
void Population::swap(int& ii, int& jj)
{
  int temp;
  temp = jj; jj = ii; ii = temp;
}