abyss.java

这是多目标进化算法包

/**
 * AbYSS.java
 *
 * @author Juan J. Durillo
 * @version 1.0
 */
package jmetal.metaheuristics.abyss;

import jmetal.base.*;
import jmetal.base.archive.CrowdingArchive;
import jmetal.base.Algorithm;
import jmetal.base.operator.comparator.CrowdingDistanceComparator;
import java.util.*;
import jmetal.util.*;
import jmetal.base.operator.localSearch.LocalSearch;

/**
 * This class implements the AbYSS algorithm. This algorithm is an adaptation
 * of the single-objective scatter search template defined by F. Glover in:
 * F. Glover. "A template for scatter search and path relinking", Lecture Notes 
 * in Computer Science, Springer Verlag, 1997.
 */
public class AbYSS extends Algorithm {
   
  /**
   * Stores the problem to solve
   */
  private Problem problem_;        
  
  /**
   * Stores the number of subranges in which each variable is divided. Used in
   * the diversification method. By default it takes the value 4 (see the method
   * <code>initParams</code>).
   */
  int numberOfSubranges_ ;
  
  /**
   * These variables are used in the diversification method.
   */
  int []  sumOfFrequencyValues_        ; 
  int []  sumOfReverseFrequencyValues_ ;
  int [][] frequency_                  ; 
  int [][] reverseFrequency_           ; 
  
  /**
   * Stores the initial solution set
   */
  private SolutionSet solutionSet_;
  
  /**
   * Stores the external solution archive
   */
  private CrowdingArchive archive_ ;
  
  /**
   * Stores the reference set one
   */
  private SolutionSet refSet1_ ;
  
  /**
   * Stores the reference set two
   */
  private SolutionSet refSet2_ ;
  
  /**
   * Stores the solutions provided by the subset generation method of the
   * scatter search template
   */
  private SolutionSet subSet_ ;    
  
  /**
   * Maximum number of solution allowed for the initial solution set
   */
  private int solutionSetSize_;
  
  /**
   * Maximum size of the external archive
   */
  private int archiveSize_;
  
  /** 
   * Maximum size of the reference set one
   */
  private int refSet1Size_;
  
  /**
   * Maximum size of the reference set two
   */
  private int refSet2Size_;  
  
  /**
   * Maximum number of getEvaluations to carry out
   */
  private int maxEvaluations;  
  
  /**
   * Stores the current number of performed getEvaluations
   */
  private int evaluations_ ;
  
  /**
   * Stores the comparators for dominance and equality, respectively
   */
  private Comparator dominance_ ;
  private Comparator equal_     ;
  private Comparator fitness_   ;
  private Comparator crowdingDistance_;
  
  /**
   * Stores the crossover operator
   */
  private Operator crossoverOperator_;
  
  /**
   * Stores the improvement operator
   */
  private LocalSearch improvementOperator_;
  
  /**
   * Stores a <code>Distance</code> object
   */
  private Distance distance_;
    
  /**
   * Constructor.
   * @param problem Problem to solve
   */
  public AbYSS(Problem problem){
    //Initialize the fields 
    problem_ = problem ;                  
       
    solutionSet_ = null ;
    archive_     = null ;
    refSet1_     = null ;
    refSet2_     = null ;
    subSet_      = null ;    
  } // AbYSS
    
  /**
   * Reads the parameter from the parameter list using the
   * <code>getInputParameter</code> method.
   */
  public void initParam(){
    //Read the parameters
    solutionSetSize_= ((Integer)getInputParameter("populationSize")).intValue();
    refSet1Size_    = ((Integer)getInputParameter("refSet1Size")).intValue();
    refSet2Size_    = ((Integer)getInputParameter("refSet2Size")).intValue();
    archiveSize_    = ((Integer)getInputParameter("archiveSize")).intValue();
    maxEvaluations  = ((Integer)getInputParameter("maxEvaluations")).intValue();
        
    //Initialize the variables
    solutionSet_ = new SolutionSet(solutionSetSize_);     
    archive_     = new CrowdingArchive(archiveSize_,problem_.getNumberOfObjectives());        
    refSet1_     = new SolutionSet(refSet1Size_);        
    refSet2_     = new SolutionSet(refSet2Size_);        
    subSet_      = new SolutionSet(solutionSetSize_*1000);
    evaluations_       = 0 ;
    
    numberOfSubranges_ = 4 ; 

    dominance_ = new jmetal.base.operator.comparator.DominanceComparator();
    equal_     = new jmetal.base.operator.comparator.EqualSolutions();     
    fitness_   = new jmetal.base.operator.comparator.FitnessComparator();
    crowdingDistance_ = new jmetal.base.operator.comparator.CrowdingDistanceComparator();
    distance_  = new Distance();
    sumOfFrequencyValues_        = new int[problem_.getNumberOfVariables()] ;
    sumOfReverseFrequencyValues_ = new int[problem_.getNumberOfVariables()] ;
    frequency_        = new int[numberOfSubranges_][problem_.getNumberOfVariables()] ;
    reverseFrequency_ = new int[numberOfSubranges_][problem_.getNumberOfVariables()] ;    
    
    //Read the operators of crossover and improvement
    crossoverOperator_   =  operators_.get("crossover");
    improvementOperator_ = (LocalSearch) operators_.get("improvement");
    improvementOperator_.setParameter("archive",archive_);        
  } // initParam
            
  /**
   * Returns a <code>Solution</code> using the diversification generation method
   * described in the scatter search template.
   * @throws JMException 
   */
  public Solution diversificationGeneration() throws JMException{
    Solution solution ;
    solution = new Solution(problem_) ;
    
    double value ;
    int    range ;

    for (int i = 0; i < problem_.getNumberOfVariables(); i++) {
      sumOfReverseFrequencyValues_[i] = 0 ;
      for (int j = 0; j < numberOfSubranges_; j++) {
        reverseFrequency_[j][i] = sumOfFrequencyValues_[i] - frequency_[j][i] ;
        sumOfReverseFrequencyValues_[i] += reverseFrequency_[j][i] ;
      } // for

      if (sumOfReverseFrequencyValues_[i] == 0) {
        range = PseudoRandom.randInt(0, numberOfSubranges_ - 1) ;
      } else { 
        value = PseudoRandom.randInt(0, sumOfReverseFrequencyValues_[i] - 1) ;
        range = 0 ;                
        while (value > reverseFrequency_[range][i]) {
          value -= reverseFrequency_[range][i] ;
          range++ ;
        } // while
      } // else            
            
      frequency_[range][i]     ++ ;
      sumOfFrequencyValues_[i] ++ ;

      double low = problem_.getLowerLimit(i) + range*(problem_.getUpperLimit(i) - 
                   problem_.getLowerLimit(i)) / numberOfSubranges_ ;
      double high = low + (problem_.getUpperLimit(i) - 
                   problem_.getLowerLimit(i)) / numberOfSubranges_ ;
      value = PseudoRandom.randDouble(low, high) ;
      solution.getDecisionVariables().variables_[i].setValue(value);            
    } // for       
    return solution ;
  } // diversificationGeneration
                
    
  /** 
   * Implements the referenceSetUpdate method.
   * @param build if true, indicates that the reference has to be build for the
   *        first time; if false, indicates that the reference set has to be
   *        updated with new solutions
   * @throws JMException 
   */
  public void referenceSetUpdate(boolean build) throws JMException{
    if (build) { // Build a new reference set
      // STEP 1. Select the p best individuals of P, where p is refSet1Size_. 
      //         Selection Criterium: Spea2Fitness
      Solution individual;            
      (new Spea2Fitness(solutionSet_)).fitnessAssign();
      solutionSet_.sort(fitness_);
             
      // STEP 2. Build the RefSet1 with these p individuals            
      for (int i = 0; i  < refSet1Size_; i++) {
        individual = solutionSet_.get(0);
        solutionSet_.remove(0);
        individual.unMarked();
        refSet1_.add(individual);                 
      }
                                        
      // STEP 3. Compute Euclidean distances in SolutionSet to obtain q 
      //         individuals, where q is refSet2Size_
      for (int i = 0; i < solutionSet_.size();i++){
        individual = solutionSet_.get(i);                
        individual.setDistanceToSolutionSet(distance_.distanceToSolutionSet(individual,refSet1_));                                
      }
            
      int size = refSet2Size_;
      if (solutionSet_.size() < refSet2Size_) {
        size = solutionSet_.size();
      }
                       
      // STEP 4. Build the RefSet2 with these q individuals
      for (int i = 0; i < size; i++){
        // Find the maximumMinimunDistanceToPopulation
        double maxMinimum = 0.0;
        int index = 0;
        for (int j = 0; j < solutionSet_.size(); j++) {
          if (solutionSet_.get(j).getDistanceToSolutionSet() > maxMinimum){
            maxMinimum = solutionSet_.get(j).getDistanceToSolutionSet();
            index = j;
          }
        }
        individual = solutionSet_.get(index);
        solutionSet_.remove(index);

        // Update distances to REFSET in population
        for (int j = 0; j < solutionSet_.size(); j++){
          double aux = distance_.distanceBetweenSolutions(solutionSet_.get(j),individual);
          if (aux < individual.getDistanceToSolutionSet()){
            solutionSet_.get(j).setDistanceToSolutionSet(aux);
          }
        }