Population.cpp

Go to the documentation of this file.

#include <Population.h>

Population::Population(string name,
                       int initialPopulationSize, 
                       int maximumPopulationSize,
                       Random * random          ,   
                       MultiobjectiveProblem * problem) {   
  name_                  = name                  ;
  problem_               = problem               ;
  populationSize_        = initialPopulationSize ;
  maximumPopulationSize_ = maximumPopulationSize ;
  random_                = random                ;
  
  population_   = new Individual * [maximumPopulationSize_] ;

  if (!population_) {
    cerr << "Population::Population " << name_ 
         << "-> error when asking for memory " 
         << endl ;
    exit(-1) ;
  } // if
  
  int i ;
  for (i = 0; i < populationSize_; i++) 
    population_[i] = new Individual(problem_, random) ;
} // Population::Population

Population::~Population(void) {
  for (int i = 0; i < populationSize_ ; i++)
    delete population_[i] ;
  delete [] population_   ;
} // Population::~Population

int Population::getPopulationSize() const {
  return populationSize_;
} // getPopulationSize
  
 
int Population::getMaximumPopulationSize() const {
  return maximumPopulationSize_ ;
} // getMaximumPopulationSize
  
Individual * Population::getIth(int index) const {
  if ((index < populationSize_) && (index >= 0))
    return population_[index];
  else {
    cerr << "Population(" << name_ << ")::getIth - Index out of range "
         << "when getting a copy of " << "an individual" ;
    cerr << endl ;
    exit(-1) ;
  } // else
} // Population::getIth


Individual * Population::getRandom() const {
  int index ;

  index = random_->rnd(0, populationSize_-1) ;
  if ((index < populationSize_) && (index >= 0))
    return population_[index];
  else {
    cerr << "Population(" << name_ << ")::getRandom - Index out of range "
         << "when getting a copy of " << "an individual" ;
    cerr << endl ;
    exit(-1) ;
  } // else
} // Population::getIth

Individual * Population::extractIth(int index) {
  Individual * result ;
  
  result = population_[index] ;
  if ((index < populationSize_) && (index >= 0)) {
    if (population_[index]->numberOfPopulations_ > 1)
      population_[index]->numberOfPopulations_ -- ;
    int i ;
    for (i = index; i < (populationSize_ - 1); i++)
      population_[i] = population_[i + 1] ;
    populationSize_ -- ;
  } // if
  else {
    cerr << "Population(" << name_ << ")::extractIth - Index " 
         << index << " out of range " ;
    cerr << endl ;
    exit(-1) ;
  } // else
  
  return result ;
} // Population::extractIth

void Population::setIth(int index, Individual * individual) {
  if ((index < populationSize_) && (index >= 0))
    population_[index] = individual ;
  else {
    cerr << "Population(" << name_ << ")::setIth - Index out of range "
         << "when inserting an " << "individual" ;
    cerr << endl ;
    exit(-1) ;
  } // else  
} // setIth

void Population::setFitness(int index, double * fitness) {
  population_[index]->setFitness(fitness);
} // setFitness


void Population::addIndividual(Individual * individual) {
  if (populationSize_ < maximumPopulationSize_) {
    population_[populationSize_] = individual ;
    populationSize_ += 1 ;
  } // if
  else {
    cerr << "Population(" << name_ << ")::addIndividual->The population "
         << "size has reached its "<< "maximum size (" 
         << maximumPopulationSize_ << ")" << endl ;
    exit(-1) ;
  } // else
} // Population::addIndividual

  
void Population::deleteIth(int index) {
//cout << "Delete element " << index 
//     << " of " << populationSize_ 
//     << " populations: " << population_[index]->numberOfPopulations_ 
//     << endl ;
  if ((index < populationSize_) && (index >= 0)) {
    if (population_[index]->numberOfPopulations_ > 1) 
      population_[index]->numberOfPopulations_ -- ;
    else {    
      delete population_[index] ;
    } // else
    int i ;
    for (i = index; i < (populationSize_ - 1); i++)
      population_[i] = population_[i + 1] ;
    populationSize_ -- ;
  } // if
  else {
    cerr << "Population(" << name_ << ")::deleteIth - Index " 
         << index << " out of range " ;
    cerr << endl ;
    exit(-1) ;
  } // else
} // Population::deleteIth

void Population::removeAllIndividuals() {
  //int i ;
  //int j = populationSize_ ;
  //cout << "Elements to delete: " << j << endl ;
  //for (i = 0; i < j; i++)
  //  deleteIth(0) ;
  while (populationSize_ > 0) {
    //cout << *(getIth(populationSize_-1)) << endl ;
    deleteIth(populationSize_ - 1) ;
  } // while
} // Population::removeAllIndividuals

void Population::reset() {
  populationSize_ = 0 ;
} // Population::reset


void Population::swap(int index1, int index2) {
  Individual * tmp ;
  tmp                 = population_[index1] ;
  population_[index1] = population_[index2] ;
  population_[index2] = tmp                 ;
} // Population::reset


void Population::printFitness(char * fileName) {
  ofstream outputFile ;
  int      i          ;
  int      j          ;

  outputFile.open(fileName) ;
  outputFile.precision(35) ;
  
  for (j = 0 ; j < getPopulationSize(); j++) {
    for (i = 0; i < problem_->numberOfFunctions_ ; i++)
      outputFile << getIth(j)->getFitness()[i] 
                 << "\t" ;
    //outputFile << getIth(j)->distance_ ;                 
    outputFile << endl ;
  } // for

  outputFile.close() ;      
} // Population::printFitness

void Population::printGenotype(char * fileName) {
  ofstream outputFile ;
  int      i          ;
  int      j          ;

  outputFile.open(fileName, ios::out) ;
  outputFile.precision(35) ;
  
  for (j = 0 ; j < getPopulationSize(); j++) {
    for (i = 0; i < problem_->numberOfVariables_ ; i++) {
      getIth(j)->chromosome_->gene_[i]->writeGenotype(outputFile) ;
      outputFile << "\t" ;
    } // for
    outputFile << endl ;
  } // for 
  
  outputFile.close() ;      
} // Population::printGenotype

Individual * Population::strengthAndCrowdingTournamentSelection() {
  int random ;
  
  Individual * individual1 ;
  Individual * individual2 ;
  
  random = random_->rnd(0,populationSize_- 1) ; 
  individual1 = this->getIth(random) ;
  random = random_->rnd(0,populationSize_- 1) ; 
  individual2 = this->getIth(random) ;

  if (individual1->strengthRawFitness_ < individual2->strengthRawFitness_)
    return individual1 ;
  else if (individual1->strengthRawFitness_ > individual2->strengthRawFitness_)
    return individual2 ;
  else {
    if (individual1->distance_ > individual2->distance_)
      return individual1 ;
    else
      return individual2 ;
  } // else
} // Population::strengthAndCrowdingTournamentSelection()


void Population::sortByFitness(int functionIdentifier) {
  Individual * swap ;

  if ((functionIdentifier >= problem_->numberOfFunctions_) ||
      (functionIdentifier < 0)) {
    cerr << "Population::sortByFitness->the function identifier " 
         << functionIdentifier << " is invalid. Must be between 1 and "
         << problem_->numberOfFunctions_ << endl ;
    exit(-1) ;
  } // if
   
  // bubble sort loop
  for (int i = (populationSize_-1); i > 0 ;i--)
    for (int j = 0; j < i; j++) {
      if (population_[j]->fitness_[functionIdentifier] >
          population_[j + 1]->fitness_[functionIdentifier]){
        swap             = population_[j]   ;
        population_[j]   = population_[j+1] ;
        population_[j+1] = swap             ;
      } // if
    } // for
} // Population::sortByObjective

void Population::sortByStrengthRawFitnessAndCrowding() {
  Individual * swap ;
  // bubble sort loop
  for (int i = (populationSize_-1); i > 0 ;i--)
    for (int j = 0; j < i; j++) {
      if ((population_[j]->strengthRawFitness_ > 
           population_[j+1]->strengthRawFitness_) ||
          ((population_[j]->strengthRawFitness_ == 
            population_[j+1]->strengthRawFitness_) && 
           (population_[j]->distance_ < 
            population_[j+1]->distance_))){
        swap             = population_[j]   ;
        population_[j]   = population_[j+1] ;
        population_[j+1] = swap             ;
      } // if
    } // sort
} // Population::sortByStrengthFitnessAndCrowding


void Population::sortByStrengthFitness() {
  Individual * swap ;
  // bubble sort loop
  for (int i = (populationSize_-1); i > 0 ;i--)
    for (int j = 0; j < i; j++) {
      if (population_[j]->strengthFitness_ > 
          population_[j+1]->strengthFitness_){
        swap             = population_[j]   ;
        population_[j]   = population_[j+1] ;
        population_[j+1] = swap             ;
      } // if
    } // for
} // Population::sortByStrengthFitness

void Population::sortByRankAndCrowding() {
  Individual * swap ;
  // bubble sort loop
  for (int i = (populationSize_-1); i > 0 ;i--)
    for (int j = 0; j < i; j++) {
      if ((population_[j]->rank_ > population_[j+1]->rank_) ||
          ((population_[j]->rank_ == population_[j+1]->rank_) && 
           (population_[j]->distance_ < 
            population_[j+1]->distance_))){
        swap             = population_[j]   ;
        population_[j]   = population_[j+1] ;
        population_[j+1] = swap             ;
      } // if
    } // sort
} // Population::sortByRankAndCrowding

void Population::crowdingDistanceAssignment() {
  int    lastIndividual ;
  double distance       ;
   
  if (this->getPopulationSize() > 0) {  
    lastIndividual = this->getPopulationSize() - 1 ;
    for (int i = 0; i < this->getPopulationSize(); i++)
      this->getIth(i)->distance_ = 0 ;
    
    for (int i = 0 ; i < problem_->numberOfFunctions_; i++) {     
      this->sortByFitness(i) ;    
      double difference = this->getIth(lastIndividual)->fitness_[i] -
                          this->getIth(0)->fitness_[i] ;
      if (difference < 0.0) {
        cerr << "Population(" << name_ << ")::crowdingDistanceAssignment "
             << "- Distance < 0" ;
        cerr << endl ;
        exit(-1) ;
      } // if

      for (int j = 0; j < lastIndividual ; j++) {
        distance = this->getIth(j)->distance_ ;
        if ((j == 0) || (j == (lastIndividual-1))) 
          distance = MAX_REAL ; 
          //distance = 100 * this->getIth(lastIndividual)->fitness_[i] ;
        else
          distance += fabs(this->getIth(j+1)->fitness_[i] -
                           this->getIth(j-1)->fitness_[i]) / difference ;
        this->getIth(j)->distance_ = distance ;
      } // for
    } // for
  } // if
} // Population::crowdingDistanceAssignment

void Population::maxiMinDistanceAssignment() {
  double distance             ;
  int   lastIndividual ;
  
  Population * tempPopulation = new Population("tmp", 
                                               0, 
                                               this->populationSize_, 
                                               this->random_, 
                                               this->problem_) ;
     
  if (this->getPopulationSize() > 0) {  
    lastIndividual = this->getPopulationSize() - 1 ;
    for (int i = 0; i < this->getPopulationSize(); i++)
      this->getIth(i)->distance_ = 0 ;
    
    // STEP 1. Get the extreme solutions
    for (int i = 0 ; i < problem_->numberOfFunctions_; i++) {     
      this->sortByFitness(i) ;    
      this->getIth(0)->distance_ = MAX_REAL ;
      tempPopulation->addIndividual(this->extractIth(0)) ;
    } // for 
    
    double maxDistance           ;
    int    individualMaxDistance ;
    while (this->getPopulationSize() > 0) {
      // STEP 2. Obtain the distances to tempPopulation
      maxDistance           = 0.0 ;
      individualMaxDistance = 0 ; 
      for (int i = 0; i < getPopulationSize(); i++) {
        this->getIth(i)->distance_ = MAX_REAL ;
        tempPopulation->minimumDistanceToPopulation(this->getIth(i)) ;
        if (this->getIth(i)->distance_ > maxDistance) {
          maxDistance = this->getIth(i)->distance_ ;
          individualMaxDistance = i ;
        } // if
      } // for
      // STEP 3. The individual with maximum distance is selected
      tempPopulation->addIndividual(this->extractIth(individualMaxDistance)) ;
    } // while
    // STEP 4. Restoring original population
    while (tempPopulation->populationSize_ > 0)
      this->addIndividual(tempPopulation->extractIth(0)) ;
  } // if
  delete tempPopulation ;
} // Population::crowdingDistanceAssignment


void Population::minimumDistanceToPopulation(Individual * individual) {
  // Intially, the distance of an individual is MAX_REAL. Otherwise, it is 
  // assumed that we are measuring the distance to more than one population 
  double minimumDistance = individual->distance_ ;

  for (int i = 0; i < this->getPopulationSize(); i++) {
    double tmp = 0.0 ;

    for (int j = 0; j < problem_->numberOfVariables_; j++)
      tmp += pow(individual->chromosome_->gene_[j]->getRealAllele() - 
                 this->getIth(i)->chromosome_->gene_[j]->getRealAllele(),
                 2) ;      
 
/* 
    for (int j = 0; j < individual->chromosome_->numberOfGenes_ ; j++)
      tmp += pow(individual->fitness_[j] - 
                 population->getIth(i)->fitness_[j],
                 2) ;      
*/
    if (minimumDistance > tmp)
      minimumDistance = tmp ;  
  } // for
  
  individual->distance_ = minimumDistance ;
} // Population::distanceToPopulation

void Population::strengthAssignment() {
  if (this->getPopulationSize() > 0) {
    // STEP 1. Initialize strength and raw fitness values
    for (int i = 0; i < this->getPopulationSize(); i++) {
      this->getIth(i)->strength_   = 0 ;
    } // for
  
    // STEP 2. Obtain the strength values of the individuals in the archive and
    //         in the population
    for (int i = 0; i < (this->getPopulationSize() - 1); i++) {
      int result ;
      for (int j = i + 1; j < (this->getPopulationSize()) ; j++) {
        //result = this->getIth(i)->numberOfViolatedConstraintsTest(this->getIth(j)) ;
        result = this->getIth(i)->overallConstraintViolationTest(this->getIth(j)) ;
        if (result == 0)
          result = this->getIth(i)->dominanceTest(this->getIth(j)) ;
        if (result == 1) {
          //cout << i << " dominates " << j << endl ;
          this->getIth(i)->strength_ ++ ;          
        }                               
        else if (result == -1) {
          //cout << j << " dominates " << i << endl ;
          this->getIth(j)->strength_ ++ ;
        }
      } // for
    } // for
  } // if
} // Population::strengthAssignment

void Population::strengthRawFitnessAssignment() {
  if (this->getPopulationSize() > 0) {
    // STEP 1. Initialize strength and raw fitness values
    for (int i = 0; i < this->getPopulationSize(); i++) {
      getIth(i)->strengthRawFitness_   = 0 ;
    } // for
  
    // STEP 2. Obtain the strength values of the individuals in the archive and
    //         in the population
    for (int i = 0; i < (getPopulationSize() - 1); i++) {
      int result ;
      for (int j = i + 1; j < getPopulationSize() ; j++) {
        //result = this->getIth(i)->numberOfViolatedConstraintsTest(this->getIth(j)) ;
        result = this->getIth(i)->overallConstraintViolationTest(this->getIth(j)) ;
        if (result == 0)
          result = getIth(i)->dominanceTest(getIth(j)) ;
        if (result == -1)
          getIth(i)->strengthRawFitness_ += getIth(j)->strength_ ;   
        else if (result == 1)                                        
          getIth(j)->strengthRawFitness_ += getIth(i)->strength_ ; 
      } // for  
    } // for 
  } // if
} // Population::strengthRawFitnessAssignment

Individual *
Population::crowdedComparison(Individual * individual1, 
                                           Individual * individual2) {
  if (individual1->rank_ < individual2->rank_)
    return individual1 ;
  else if (individual1->rank_ > individual2->rank_)
    return individual2 ;
  else {
    if (individual1->distance_ > individual2->distance_)
      return individual1 ;
    else
      return individual2 ;
  } // else
} // Population::crowdedComparison

int 
Population::removeDominatedIndividuals() {
  Ranking    * ranking         ;
  Population * dummyPopulation ;
  int counter ;

  ranking = new Ranking(this) ;
  dummyPopulation = new Population("dummy", 
                                   0, 
                                   maximumPopulationSize_, 
                                   random_, 
                                   problem_) ;
  if ((ranking == NULL) || (dummyPopulation == NULL)) {
    cerr << "Population::removeDominatedIndividuals-> error creating objects" 
         << endl ;
    exit(-1) ;
  } // if

  ranking->rankPopulation(populationSize_) ;
  ranking->copyFrontToPopulation(0, 
                ranking->nonDominatedFront_[0]->getPopulationSize(),
                dummyPopulation) ;

  counter = this->getPopulationSize() - dummyPopulation->getPopulationSize() ;
  this->removeAllIndividuals() ;
  while (dummyPopulation->getPopulationSize() > 0) {
    int last = dummyPopulation->getPopulationSize() - 1 ;
    this->addIndividual(dummyPopulation->extractIth(last)) ;
  } // while

  delete ranking ;
  delete dummyPopulation ;

  return counter ;
} // Population::removeDominatedIndividuals


Individual * 
Population::rankingAndCrowdingTournamentSelection() {
  int random ;
  
  Individual * individual1 ;
  Individual * individual2 ;
  
  random = random_->rnd(0,populationSize_- 1) ; 
  individual1 = this->getIth(random) ;
  random = random_->rnd(0,populationSize_- 1) ; 
  individual2 = this->getIth(random) ;

  return crowdedComparison(individual1, individual2) ;
} // Population::rankingTournamentSelection()

Individual * Population::tournamentSelection() {
  int random ;
  int result ; 
  Individual * individual1 ;
  Individual * individual2 ;
  
  random = random_->rnd(0,populationSize_- 1) ; 
  individual1 = this->getIth(random) ;
  random = random_->rnd(0,populationSize_- 1) ; 
  individual2 = this->getIth(random) ;

  result = individual1->numberOfViolatedConstraintsTest(individual2) ;
  if (result == 0)
    result = individual1->dominanceTest(individual2) ;
  if (result == -1) // Individual1 is dominated
    return individual2 ;
  else if (result == 1) // Individual 2 is dominated
    return individual1 ; 
  else { // Both are non-dominated
    if (random_->rndreal(0.0, 1.0) < 0.5)
      return individual1 ;
    else
      return individual2 ;
  } // else
} // Population::tournamentSelection()

bool Population::thereIsAnEqualFitnessIndividual(Individual * individual,
                                                 int        * position) {
  bool found ;
  int  index ;
  found = false ;
  index = 0 ;

  while ((!found) && (index < populationSize_)) {
    if (individual->identicalFitness(population_[index]))
      found = true ;    
    index ++ ;
  } // while

  if (position != NULL) 
    *position = index - 1 ;
    
  if (found)
    return true ;
  else
    return false ;
} // Population::thereIsAnEqualFitnessIndividual

bool Population::individualIsInPopulation(Individual * individual, 
                                          int *        position) {
  bool found ;
  int  index ;

  found = false ;
  index = 0 ;
  while ((!found) && (index < populationSize_)) {
    if (*individual == *(population_[index]))
      found = true ;
    index ++ ;
  } // while

  if (position != NULL) 
    *position = index - 1 ;

  if (found)
    return true ;
  else
    return false ;
} // Population::individualIsInPopulation

int Population::testIfIndividualDominates(Individual * individual) {
  int counter ;
  int result  ;
  
  counter = 0 ;
  result  = 0 ;
  
  while ((counter < this->getPopulationSize()) && 
         (result != -1)) {
      result = individual->dominanceTest(this->getIth(counter)) ;
    
    counter ++ ;
  } // while
  
  return result ;
} // Population::testIfIndividualDominatesPopulation

 void Population::clustering(int clusters, Population ** centroids) {
   *centroids = new Population("Centroids",0, populationSize_, random_, problem_) ;
   if (*centroids == NULL) {
     cerr << "Population(" << name_ << ")::clustering-> error creating "
          << "the centroids population" 
          << endl ;
     exit(-1) ;
   } // if  
   if (clusters > 0) {
     if (populationSize_ <= clusters) {
       for (int i = 0 ; i < populationSize_; i++)
         (*centroids)->addIndividual(new Individual(getIth(i))) ; 
     } // if
     else {
       // Step 1. At the beginning there are as many centroids as individuals
       int numberOfCentroids = populationSize_ ;
       // Step 2. Initialize the centroids population 
       for (int i = 0; i < populationSize_; i++) 
         (*centroids)->addIndividual(new Individual(getIth(i))) ;
       // Step 3. Iterate until the required number of centroids  
       while (numberOfCentroids > clusters) {
//cout << "Number of centroids: " << numberOfCentroids << endl ;       
         double minimumDistance = MAX_REAL ;
         int x, y = -1 ; // Identifiers of the individuals at minimum distance
         // Step 3.1. Obtain the distance between pairs of individuals
         for (int i = 0; i < (numberOfCentroids - 1); i++) {
           for (int j = i + 1; j < (numberOfCentroids - 1) ; j++) {
             double distance = 0.0 ;
             for (int k = 0; k < problem_->numberOfVariables_; k++)
               distance += pow(((RealGene *)((*centroids)->getIth(i)->chromosome_->gene_[k]))->allele_ - 
                               ((RealGene *)((*centroids)->getIth(j)->chromosome_->gene_[k]))->allele_,
                           2) ; 
             if (distance < minimumDistance) {
               minimumDistance = distance ;
               x = i ;
               y = j ;
             } // if  
           } // for  
         } // for  
         // Step 3.2. Merge the individuals with minimal distance. 
         //           The individual x is the resulting centroid
         for (int i = 0; i < problem_->numberOfVariables_; i++) {
           double tmp1 ;
           double tmp2 ;
           tmp1 = ((RealGene *)((*centroids)->getIth(x)->chromosome_->gene_[i]))->allele_ ;
           tmp2 = ((RealGene *)((*centroids)->getIth(y)->chromosome_->gene_[i]))->allele_ ;
           tmp1 = (tmp1 + tmp2) / 2.0 ;
           ((RealGene *)((*centroids)->getIth(x)->chromosome_->gene_[i]))->allele_ = tmp1 ;
         } // for
         // Step 3.3 The individual y is removed
         (*centroids)->deleteIth(y) ;
//cout << "Centroids population: " << (*centroids)->getPopulationSize() << endl ;       
         // Step 3.4. Decrement the centroids counter
         numberOfCentroids -- ;
       } // while  
     } // else     
   } // if
 } // Population::clustering 

---

Our Software

 Mallba

 ssGA

 JGDS

 xxGA

 JCell

 MHTB

 DEME

JMetal

More...

Go Back