Package org.moeaframework.core

Class NondominatedSorting

java.lang.Object
org.moeaframework.core.NondominatedSorting
Direct Known Subclasses:
FastNondominatedSorting
public class NondominatedSorting extends Object
Non-dominated sorting algorithm for dominance depth ranking. Assigns the rank and crowdingDistance attributes to solutions. Solutions of rank 0 belong to the Pareto non-dominated front.

Despite its name, this naive non-dominated sort implementation tends to be faster than the "fast non-dominated sort" implementation from [1]. This is primarily due to the fact that for the average case, the "fast" version always requires O(MN^2) comparisons while this naive implementations requires only (K-1)/2 * M * (N-1)*N/2, assuming there are K equally sized fronts.

References:

  1. Deb et al (2002). "A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II." IEEE Transactions on Evolutionary Computation. 6(2):182-197.

  • Field Details

    • RANK_ATTRIBUTE

      public static final String RANK_ATTRIBUTE
      Attribute key for the rank of a solution.
      See Also:

    • CROWDING_ATTRIBUTE

      public static final String CROWDING_ATTRIBUTE
      Attribute key for the crowding distance of a solution.
      See Also:

    • comparator

      protected final DominanceComparator comparator
      The dominance comparator.

  • Constructor Details

    • NondominatedSorting

      public NondominatedSorting()
      Constructs a fast non-dominated sorting operator using Pareto dominance.

    • NondominatedSorting

      public NondominatedSorting(DominanceComparator comparator)
      Constructs a non-dominated sorting operator using the specified dominance comparator.
      Parameters:
      comparator - the dominance comparator

  • Method Details

    • getComparator

      public DominanceComparator getComparator()
      Returns the dominance comparator used by this non-dominated sorting routine.
      Returns:
      the dominance comparator used by this non-dominated sorting routine

    • evaluate

      public void evaluate(Population population)
      Performs non-dominated sorting on the specified population, assigning the rank and crowdingDistance attributes to solutions.
      Parameters:
      population - the population whose solutions are to be evaluated

    • updateCrowdingDistance

      public void updateCrowdingDistance(Population front)
      Computes and assigns the crowdingDistance attribute to solutions. The specified population should consist of solutions within the same front/rank.
      Parameters:
      front - the population whose solutions are to be evaluated

    • getRank

      public static final int getRank(Solution solution)
      Returns the rank of the specified solution.
      Parameters:
      solution - the solution
      Returns:
      the rank of the specified solution

    • setRank

      public static final void setRank(Solution solution, int rank)
      SEts the rank of the specified solution.
      Parameters:
      solution - the solution
      rank - the rank of the specified solution

    • getCrowding

      public static final double getCrowding(Solution solution)
      Returns the crowding distance of the specified solution.
      Parameters:
      solution - the solution
      Returns:
      the crowding distance of the specified solution

    • setCrowding

      public static final void setCrowding(Solution solution, double crowding)
      Sets the crowding distance of the specified solution.
      Parameters:
      solution - the solution
      crowding - the crowding distance of the specified solution