Package org.moeaframework.core.population

Class FastNondominatedSorting

java.lang.Object
org.moeaframework.core.population.NondominatedSorting
org.moeaframework.core.population.FastNondominatedSorting
public class FastNondominatedSorting extends NondominatedSorting
Fast 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. Requires at worst O(MN^2) operations instead of O(MN^3) required by a naive implementation of NondominatedSorting, but tends to run slower than the naive implementation except on edge cases (e.g., for N solutions there are N fronts).

[1] does not discuss how to handle duplicate solutions. A straightforward interpretation is that duplicate solutions should have the worst crowding distance (and hence are truncated/pruned from the population first). Therefore, duplicate solutions are assigned a crowding distance of 0.

References:

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

  • Constructor Details

    • FastNondominatedSorting

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

    • FastNondominatedSorting

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

  • Method Details

    • evaluate

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