K_Distance.cpp

Go to the documentation of this file.

#include <K_Distance.h>

K_Distance::K_Distance(Population * population) {
  population_         = population                                ;
  numberOfFunctions_  = population_->problem_->numberOfFunctions_ ;
  calculatedDistance_ = 0                                         ;
  distance_ = new double*[population_->maximumPopulationSize_] ;
  for (int i = 0; i < population_->maximumPopulationSize_; i++)
    distance_[i] = new double[population_->maximumPopulationSize_] ;
  
  kDistance_ = new double*[population_->maximumPopulationSize_] ;
  for (int i = 0; i < population_->maximumPopulationSize_; i++)
    kDistance_[i] = new double[population_->maximumPopulationSize_-1] ;
} // K_Distance::K_Distance

K_Distance::~K_Distance() {
  for (int i = 0; i < population_->maximumPopulationSize_; i++)
    delete distance_[i] ;
  delete [] distance_ ;
} // K_Distance::~K_Distance

void K_Distance::calculateDistanceMatrix() {
  for (int i = 0; i < (population_->getPopulationSize()); i++) {
    double minimumDistance   = MAX_REAL; 
    population_->getIth(i)->location_ = i ; // The position of the individual
                                            // in the distance matrix
    for (int j = 0; j < (population_->getPopulationSize()) ; j++) {
      if (i < j) {
        distance_[i][j] = getDistance(population_->getIth(i), 
                                      population_->getIth(j)) ;
      } // if
      else if (i == j)
        distance_[i][j] = 0 ;
      else // (i > j)
        distance_[i][j] = distance_[j][i] ;
#ifdef __PRINT__
//cout <<"INDIVIDUAL " << i << "\t" << *(population_->getIth(i)) << endl ;
//cout <<"INDIVIDUAL " << j << "\t" << *(population_->getIth(j)) << endl ;
cout << "DISTANCE("<<i<<","<<j<<")= " << distance_[i][j] << endl ;
#endif        

      if ((i != j) && (distance_[i][j] < minimumDistance)) {
        kDistance_[i][0] = distance_[i][j] ; 
        minimumDistance = distance_[i][j]  ;
      } // if
    } // for
  } // for
  calculatedDistance_ = 1 ;
#ifdef __PRINT__
cout << "________ DISTANCES ______ PopSize: " << population_->getPopulationSize() << endl ;
for (int i = 0; i < population_->getPopulationSize(); i++) {
   for (int j = 0; j < population_->getPopulationSize(); j++) {
     cout << distance_[i][j]<< "\t" ;
  }
  cout << endl ;
}
cout << "______KDistances 0____________ " << endl ;
for (int i = 0; i < population_->getPopulationSize(); i++) 
  cout << kDistance_[i][0] << endl ;
#endif  
} // K_Distance::calculateDistanceMatrix

/*
 * @brief Calculates the distances to the kth neighbour
 *
 * Calculates the distances among the individuals. It is assumed that
 * the distance to the 1st neighbour has been already calculated
 */
void K_Distance::calculateKDistance(int k) {
#ifdef __PRINT__     
  cout << "CALCULATEKDISTANCE: K = " << k << endl ;
#endif  
  for (; calculatedDistance_ < k ; calculatedDistance_ ++) {
    // We must find the next minimun distance, excluding the so far 
    // encountered distances. We must consider that there may be
    // several individuals at the same distance
    int    lastMinimumDistanceCounter ;
    double lastMinimumDistance        ;
    double nextMinimumDistance        ;
    for (int i = 0; i < population_->getPopulationSize(); i++) {
      nextMinimumDistance = MAX_REAL ;
      lastMinimumDistanceCounter = 1 ;
      lastMinimumDistance    = kDistance_[i][0] ;
      for (int j = 1 ; j < calculatedDistance_; j++) {
        if (kDistance_[i][j] == lastMinimumDistance)
          lastMinimumDistanceCounter ++ ;
        else {
          lastMinimumDistanceCounter = 1            ;
          lastMinimumDistance    = kDistance_[i][j] ;
        } // else
      } // for
      for (int j = 0 ; j < population_->getPopulationSize(); j++) {
        if (i != j) {
          if (distance_[i][j] < lastMinimumDistance) 
            ; 
          else if (distance_[i][j] == lastMinimumDistance) {
            if (lastMinimumDistanceCounter == 0)
              nextMinimumDistance = lastMinimumDistance ;
            else
              lastMinimumDistanceCounter-- ;
          } // else if
          else { //distance_[i][j] > lastMinimumDistance
            if (distance_[i][j] < nextMinimumDistance)
              nextMinimumDistance = distance_[i][j] ;
          } // else 
        } // if
      } // for
      kDistance_[i][calculatedDistance_] = nextMinimumDistance ;
    } // for
  } // for
#ifdef __PRINT__
  for (int i = 0 ; i < population_->getPopulationSize() ; i++) {
    for (int j = 0; j < calculatedDistance_; j++) 
//      cout << "kDistance_[" << j<< "]["<<i"]: " << "\t" ;
      cout << kDistance_[i][j] << "\t" ;
    cout << endl ;
  } // for
#endif  
} // K_Distance::calculateKDistance

int K_Distance::findMinimumDistanceIndividual() {
  int    individual          ;
  int    kDistance           ;
  double minimumDistance         ;
  double previousMinimumDistance ;
  bool   thereAreEqualDistances  ;

  individual             = -1       ;
  kDistance              = 0        ;
  minimumDistance        = MAX_REAL ;
  thereAreEqualDistances = false    ;
//cout << "kDISTANCE: " << calculatedDistance_ << endl ;
//cout << "Individuals: " << population_->getPopulationSize() << endl ;
//for (int i = 0; i < population_->getPopulationSize(); i++) 
//  cout << i << "-> " << *(population_->getIth(i)) << endl ;
//cout <<"----------------------------------" << endl ;
//for (int i = 0; i < population_->getPopulationSize(); i++) {
//  for (int j = 0; j < population_->getPopulationSize(); j++) {
//    cout << distance_[i][j]<< "\t" ;
//  }
//  cout << endl ;
//}

//for (int i = 0; i < population_->getPopulationSize(); i++)
//  cout << kDistance_[i][0] << endl ;

  // Search 1-Distances (kDistance == 0)
  for (int i = 0; 
       (i < population_->getPopulationSize()); 
       i++) {
    if (kDistance_[i][0] < minimumDistance) { 
      minimumDistance = kDistance_[i][0] ;
      individual      = i  ;
#ifdef __PRINT__
cout << "--> minimumDistance: " << minimumDistance << "\tIndividual: " << i << endl ; 
#endif
      thereAreEqualDistances = false ;    
    } // if
    else if (kDistance_[i][0] == minimumDistance)
      thereAreEqualDistances = true ;
  } // for
  
  if (thereAreEqualDistances)
  // If there are more than one individual with identical minimum 1-distance,
  // try with the next k-distance iteratively
    while (thereAreEqualDistances) {
      previousMinimumDistance = minimumDistance ;
      minimumDistance         = MAX_REAL        ;
      thereAreEqualDistances  = false           ;
      kDistance ++ ;
#ifdef __PRINT__    
cout << "--> kDistance: " << kDistance << endl ;
#endif
      if ((kDistance+1) > calculatedDistance_)
        this->calculateKDistance(kDistance+1) ;
      for (int i = 0; 
           (i < population_->getPopulationSize()) ; 
           i++) {
        if (kDistance_[i][kDistance-1] == previousMinimumDistance)
          if (kDistance_[i][kDistance] < minimumDistance) {
            minimumDistance = kDistance_[i][kDistance] ;
            individual = i ;
            thereAreEqualDistances = false ;
          } // if
          else if (kDistance_[i][kDistance] == minimumDistance)
            thereAreEqualDistances = true ;
      } // for
    } // while

  return individual ;
} // K_Distance::findMinimumDistanceIndividual


double K_Distance::getDistance(Individual * individual1, Individual * individual2) {
  double distance ;

  distance = 0 ;
  for (int i = 0; i < numberOfFunctions_; i++) {
    distance += (individual1->fitness_[i] - individual2->fitness_[i]) * 
                (individual1->fitness_[i] - individual2->fitness_[i]) ;
#ifdef __PRINT__
cout << " individual1->fitness_" << i << individual1->fitness_[i] << endl ; 
cout << " individual2->fitness_" << i << individual2->fitness_[i] << endl ; 
cout << " distance: " << distance << endl ;
#endif     

  } // for
  return sqrt(distance) ;
} // K_Distance::getDistance

int K_Distance::distanceComparison(Individual * individual1, 
                                   Individual * individual2) {
  int  result    ;
  bool finish    ;
  int  kDistance ;

  result    = 0     ;
  finish    = false ;
  kDistance = 0     ;

  int distance1 = (int)individual1->distance_ ;
  int distance2 = (int)individual2->distance_ ;

  for (kDistance = 0; 
       (kDistance < (population_->getPopulationSize()-1)) && !finish; 
       kDistance++) {
    if ((kDistance+1) > calculatedDistance_)
      this->calculateKDistance(kDistance+1) ;

    if (kDistance_[distance1][kDistance] < kDistance_[distance2][kDistance]) { 
      result = -1 ;
      finish = true ;
    } // if
    else if (kDistance_[distance1][kDistance] >
             kDistance_[distance2][kDistance]) {
      result = 1 ;
      finish = true ;
    } // else if
  } // for
#ifdef __PRINT__
cout << "Resultado comparar " << distance1 << "/" << distance2<<": " << result << endl ;
#endif
  return result ;
} // K_Distance::distanceComparison


double K_Distance::getIndividualKDistance(int  individual, int k) { 
  return kDistance_[individual][k];
} // K_Distance::getIndividualKDistance

---

Our Software

 Mallba

 ssGA

 JGDS

 xxGA

 JCell

 MHTB

 DEME

JMetal

More...

Go Back