MOEA Framework 2.12
API Specification

org.moeaframework.algorithm
Class ReferencePointNondominatedSortingPopulation

java.lang.Object
  extended by org.moeaframework.core.Population
      extended by org.moeaframework.core.NondominatedSortingPopulation
          extended by org.moeaframework.algorithm.ReferencePointNondominatedSortingPopulation
All Implemented Interfaces:
Iterable<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 Summary
ReferencePointNondominatedSortingPopulation(int numberOfObjectives, int divisions)
          Constructs an empty population that maintains the rank attribute for its solutions.
ReferencePointNondominatedSortingPopulation(int numberOfObjectives, int divisions, DominanceComparator comparator)
          Constructs an empty population that maintains the rank attribute for its solutions.
ReferencePointNondominatedSortingPopulation(int numberOfObjectives, int divisions, DominanceComparator comparator, Iterable<? extends Solution> iterable)
          Constructs a new population with the specified solutions that maintains the rank attribute for its solutions.
ReferencePointNondominatedSortingPopulation(int numberOfObjectives, int divisionsOuter, int divisionsInner)
          Constructs an empty population that maintains the rank attribute for its solutions.
ReferencePointNondominatedSortingPopulation(int numberOfObjectives, int divisionsOuter, int divisionsInner, DominanceComparator comparator)
          Constructs an empty population that maintains the rank attribute for its solutions.
ReferencePointNondominatedSortingPopulation(int numberOfObjectives, int divisionsOuter, int divisionsInner, DominanceComparator comparator, Iterable<? extends Solution> iterable)
          Constructs a new population with the specified solutions that maintains the rank attribute for its solutions.
ReferencePointNondominatedSortingPopulation(int numberOfObjectives, int divisionsOuter, int divisionsInner, Iterable<? extends Solution> iterable)
          Constructs a new population with the specified solutions that maintains the rank attribute for its solutions.
ReferencePointNondominatedSortingPopulation(int numberOfObjectives, int divisions, Iterable<? extends Solution> iterable)
          Constructs a new population with the specified solutions that maintains the rank attribute for its solutions.
 
Method Summary
protected static double achievementScalarizingFunction(Solution solution, double[] weights)
          The Chebyshev achievement scalarizing function.
protected  List<List<Solution>> associateToReferencePoint(Population population)
          Associates each solution to the nearest reference point, returning a list-of-lists.
protected  double[] calculateIntercepts()
          Calculates the intercepts between the hyperplane formed by the extreme points and each axis.
protected  Solution findExtremePoint(int objective)
          Returns the extreme point in the given objective.
protected  Solution findSolutionWithMinimumDistance(List<Solution> solutions, double[] weight)
          Returns the solution with the minimum perpendicular distance to the given reference point.
protected  void normalizeByIntercepts(double[] intercepts)
          Normalizes the solutions in this population by the given intercepts (or scaling factors).
protected static double pointLineDistance(double[] line, double[] point)
          Returns the minimum perpendicular distance between a point and a line.
protected  void translateByIdealPoint()
          Offsets the solutions in this population by the ideal point.
 void truncate(int size)
          Truncates the population to the specified size using the reference-point based nondominated sorting method.
 void truncate(int size, Comparator<? super Solution> comparator)
          Truncates the population to the specified size using the reference-point based nondominated sorting method.
protected  void updateIdealPoint()
          Updates the ideal point given the solutions currently in this population.
 
Methods inherited from class org.moeaframework.core.NondominatedSortingPopulation
add, clear, get, iterator, prune, remove, remove, replace, sort, update
 
Methods inherited from class org.moeaframework.core.Population
addAll, addAll, contains, containsAll, containsAll, indexOf, isEmpty, removeAll, removeAll, size
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

ReferencePointNondominatedSortingPopulation

public ReferencePointNondominatedSortingPopulation(int numberOfObjectives,
                                                   int 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,
                                                   int 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,
                                                   int 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,
                                                   int 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

ReferencePointNondominatedSortingPopulation

public ReferencePointNondominatedSortingPopulation(int numberOfObjectives,
                                                   int divisionsOuter,
                                                   int divisionsInner)
Constructs an empty population that maintains the rank attribute for its solutions.

Parameters:
numberOfObjectives - the number of objectives
divisionsOuter - the number of outer divisions
divisionsInner - the number of inner divisions

ReferencePointNondominatedSortingPopulation

public ReferencePointNondominatedSortingPopulation(int numberOfObjectives,
                                                   int divisionsOuter,
                                                   int divisionsInner,
                                                   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
divisionsOuter - the number of outer divisions
divisionsInner - the number of inner divisions
comparator - the dominance comparator
iterable - the solutions used to initialize this population

ReferencePointNondominatedSortingPopulation

public ReferencePointNondominatedSortingPopulation(int numberOfObjectives,
                                                   int divisionsOuter,
                                                   int divisionsInner,
                                                   DominanceComparator comparator)
Constructs an empty population that maintains the rank attribute for its solutions.

Parameters:
numberOfObjectives - the number of objectives
divisionsOuter - the number of outer divisions
divisionsInner - the number of inner divisions
comparator - the dominance comparator

ReferencePointNondominatedSortingPopulation

public ReferencePointNondominatedSortingPopulation(int numberOfObjectives,
                                                   int divisionsOuter,
                                                   int divisionsInner,
                                                   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
divisionsOuter - the number of outer divisions
divisionsInner - the number of inner divisions
iterable - the solutions used to initialize this population
Method Detail

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 .


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

MOEA Framework 2.12
API Specification

Copyright 2009-2016 MOEA Framework. All rights reserved.
Licensed under the GNU Lesser General Public License.
Return to the MOEA Framework homepage. Visit us on Github!