Package org.moeaframework.algorithm

Class ReferencePointNondominatedSortingPopulation

java.lang.Object
org.moeaframework.core.Population
org.moeaframework.core.NondominatedSortingPopulation
org.moeaframework.algorithm.ReferencePointNondominatedSortingPopulation
All Implemented Interfaces:
Iterable<Solution>, Stateful, Displayable, Formattable<Solution>
public class ReferencePointNondominatedSortingPopulation extends NondominatedSortingPopulation
Implementation of the reference-point-based nondominated sorting method for NSGA-III. NSGA-III includes an additional parameter, the number of divisions, that controls the spacing of reference points. For large objective counts, an alternate two-layered approach was also proposed allowing the user to specify the divisions on the outer and inner layer. When using the two-layered approach, the number of outer divisions should less than the number of objectives, otherwise it will generate reference points overlapping with the inner layer. If there are M objectives and p divisions, then binomialCoefficient(M+p-1, p) reference points are generated.

Unfortunately, since no official implementation has been released by the original authors, we have made our best effort to implement the algorithm as described in the journal article. We would like to thank Tsung-Che Chiang for developing the first publicly available implementation of NSGA-III in C++.

References:

  1. Deb, K. and Jain, H. "An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints." IEEE Transactions on Evolutionary Computation, 18(4):577-601, 2014.
  2. Deb, K. and Jain, H. "Handling Many-Objective Problems Using an Improved NSGA-II Procedure. WCCI 2012 IEEE World Contress on Computational Intelligence, Brisbane, Australia, June 10-15, 2012.
  3. C++ Implementation by Tsung-Che Chiang

  • Constructor Details

    • ReferencePointNondominatedSortingPopulation

      public ReferencePointNondominatedSortingPopulation(int numberOfObjectives, NormalBoundaryDivisions divisions)
      Constructs an empty population that maintains the rank attribute for its solutions.
      Parameters:
      numberOfObjectives - the number of objectives
      divisions - the number of divisions

    • ReferencePointNondominatedSortingPopulation

      public ReferencePointNondominatedSortingPopulation(int numberOfObjectives, NormalBoundaryDivisions divisions, DominanceComparator comparator, Iterable<? extends Solution> iterable)
      Constructs a new population with the specified solutions that maintains the rank attribute for its solutions.
      Parameters:
      numberOfObjectives - the number of objectives
      divisions - the number of divisions
      comparator - the dominance comparator
      iterable - the solutions used to initialize this population

    • ReferencePointNondominatedSortingPopulation

      public ReferencePointNondominatedSortingPopulation(int numberOfObjectives, NormalBoundaryDivisions divisions, DominanceComparator comparator)
      Constructs an empty population that maintains the rank attribute for its solutions.
      Parameters:
      numberOfObjectives - the number of objectives
      divisions - the number of divisions
      comparator - the dominance comparator

    • ReferencePointNondominatedSortingPopulation

      public ReferencePointNondominatedSortingPopulation(int numberOfObjectives, NormalBoundaryDivisions divisions, Iterable<? extends Solution> iterable)
      Constructs a new population with the specified solutions that maintains the rank attribute for its solutions.
      Parameters:
      numberOfObjectives - the number of objectives
      divisions - the number of divisions
      iterable - the solutions used to initialize this population

  • Method Details

    • getDivisions

      public NormalBoundaryDivisions getDivisions()
      Returns the number of divisions used to create the reference points.
      Returns:
      the divisions object

    • updateIdealPoint

      protected void updateIdealPoint()
      Updates the ideal point given the solutions currently in this population.

    • translateByIdealPoint

      protected void translateByIdealPoint()
      Offsets the solutions in this population by the ideal point. This method does not modify the objective values, it creates a new attribute with the name "Normalized Objectives".

    • normalizeByIntercepts

      protected void normalizeByIntercepts(double[] intercepts)
      Normalizes the solutions in this population by the given intercepts (or scaling factors). This method does not modify the objective values, it modifies the "Normalized Objectives" attribute.
      Parameters:
      intercepts - the intercepts used for scaling

    • achievementScalarizingFunction

      protected static double achievementScalarizingFunction(Solution solution, double[] weights)
      The Chebyshev achievement scalarizing function.
      Parameters:
      solution - the normalized solution
      weights - the reference point (weight vector)
      Returns:
      the value of the scalarizing function

    • findExtremePoint

      protected Solution findExtremePoint(int objective)
      Returns the extreme point in the given objective. The extreme point is the point that minimizes the achievement scalarizing function using a reference point near the given objective. The NSGA-III paper (1) does not provide any details on the scalarizing function, but an earlier paper by the authors (2) where some precursor experiments are performed does define a possible function, replicated below.
      Parameters:
      objective - the objective index
      Returns:
      the extreme point in the given objective

    • calculateIntercepts

      protected double[] calculateIntercepts()
      Calculates the intercepts between the hyperplane formed by the extreme points and each axis. The original paper (1) is unclear how to handle degenerate cases, which occurs more frequently at larger dimensions. In this implementation, we simply use the nadir point for scaling.
      Returns:
      an array of the intercept points for each objective

    • pointLineDistance

      protected static double pointLineDistance(double[] line, double[] point)
      Returns the minimum perpendicular distance between a point and a line.
      Parameters:
      line - the line originating from the origin
      point - the point
      Returns:
      the minimum distance

    • associateToReferencePoint

      protected List<List<Solution>> associateToReferencePoint(Population population)
      Associates each solution to the nearest reference point, returning a list-of-lists. The outer list maps to each reference point using their index. The inner list is an unordered collection of the solutions associated with the reference point.
      Parameters:
      population - the population of solutions
      Returns:
      the association of solutions to reference points

    • findSolutionWithMinimumDistance

      protected Solution findSolutionWithMinimumDistance(List<Solution> solutions, double[] weight)
      Returns the solution with the minimum perpendicular distance to the given reference point.
      Parameters:
      solutions - the list of solutions being considered
      weight - the reference point
      Returns:
      the solution nearest to the reference point

    • truncate

      public void truncate(int size, Comparator<? super Solution> comparator)
      Truncates the population to the specified size using the reference-point based nondominated sorting method.
      Overrides:
      truncate in class NondominatedSortingPopulation
      Parameters:
      size - the target population size after truncation
      comparator - the comparator to be used for truncation

    • truncate

      public void truncate(int size)
      Truncates the population to the specified size using the reference-point based nondominated sorting method.
      Overrides:
      truncate in class NondominatedSortingPopulation
      Parameters:
      size - the target population size after truncation

    • saveState

      public void saveState(ObjectOutputStream stream) throws IOException
      Description copied from interface: Stateful
      Writes the state of this object to the stream. The order that objects are written to the stream is important. We recommend first calling super.saveState(stream) followed by writing each field.
      Specified by:
      saveState in interface Stateful
      Overrides:
      saveState in class NondominatedSortingPopulation
      Parameters:
      stream - the stream
      Throws:
      IOException - if an I/O error occurred

    • loadState

      public void loadState(ObjectInputStream stream) throws IOException, ClassNotFoundException
      Description copied from interface: Stateful
      Loads the state of this object from the stream. The order for reading objects from the stream must match the order they are written to the stream in Stateful.saveState(ObjectOutputStream).
      Specified by:
      loadState in interface Stateful
      Overrides:
      loadState in class NondominatedSortingPopulation
      Parameters:
      stream - the stream
      Throws:
      IOException - if an I/O error occurred
      ClassNotFoundException - if the stream referenced a class that is not defined