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.

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, instead it sets the NormalizedObjectives attribute.

    • 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, instead it sets the NormalizedObjectives 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

    • 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.

      As a side-effect, this method also sets the Niche and NicheDistance attributes.

      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

    • updateNiches

      public void updateNiches()
      Updates the Niche and NicheDistance attributes on all solutions in this population. Normally, this is handled by the truncate(int, Comparator) method, but this can be called when the calculation is needed explicitly, such as after initialization.

    • copy

      public ReferencePointNondominatedSortingPopulation copy()
      Description copied from class: Population
      Returns a copy of this population. This can be thought of as a "deep copy", which creates a copy of both the population itself and copies of the individual solutions in the population. Consequently, the returned copy is completely independent, such that any modifications to the contents or order will not impact the original.

      Since creating such a "deep copy" can be expensive, prefer using the constructor Population(Iterable) or Population.addAll(Iterable) whenever possible. These alternatives are useful when filtering or reordering the solutions, but the solutions themselves are left unchanged.

      Overrides:
      copy in class NondominatedSortingPopulation
      Returns:
      the copy of this population

    • 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