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 Summary

Fields

Modifier and Type	Field	Description
protected final DominanceComparator	comparator	The dominance comparator.

Constructor Summary

Constructors

Constructor	Description
NondominatedSorting()	Constructs a fast non-dominated sorting operator using Pareto dominance.
NondominatedSorting(DominanceComparator comparator)	Constructs a non-dominated sorting operator using the specified dominance comparator.

Method Summary

Modifier and Type	Method	Description
void	evaluate(Population population)	Performs non-dominated sorting on the specified population, assigning the rank and crowdingDistance attributes to solutions.
DominanceComparator	getComparator()	Returns the dominance comparator used by this non-dominated sorting routine.
void	updateCrowdingDistance(Population front)	Computes and assigns the crowdingDistance attribute to solutions.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

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