Draft:Non dominated sorting: Difference between revisions

Revision as of 18:45, 20 February 2025

Latest revision as of 21:03, 25 August 2025

(One intermediate revision by one other user not shown)

Line 16:

In this context, an element dominates another element if it is better than the other element in at least one objective and no worse in any other objectives<ref name="NSGA" />. For example, if we have two elements A and B, and A has a better value than B in at least one objective, and no worse value in any other objectives, then A dominates B. On the other hand, if B has a better value than A in at least one objective, and no worse value in any other objectives, then B dominates A. If neither A dominates B nor B dominates A, then A and B are said to be non-dominated or incomparable with respect to each other.

Non-dominated sorting is a technique used to sortsorts elements into different non-dominated fronts. Each front represents a subset of elements that are not dominated by any other elements in the same front. Elements in a given front are dominated by elements in the fronts that come before it, and dominate elements in the front that comes after it.<ref name="ENS"/> The first non-dominated front contains the best elements - those that are not dominated by any other elements. In fact the first front corresponds exactly to the [[maxima of a point set|maximal elements of the set]]. The second front contains elements that are dominated only by elements in the first front (an element in the second front is not necessarily dominated by all the elements in the first front, but by at least one of them). The subsequent fronts contain elements that are progressively less optimal with respect to the objective functions.<ref name="ENS"/>

The first non-dominated front contains the best elements - those that are not dominated by any other elements. In fact the first front corresponds exactly to the [[maxima of a point set|maximal elements of the set]]. The second front contains elements that are dominated only by elements in the first front (an element in the second front is not necessarily dominated by all the elements in the first front, but by at least one of them). The subsequent fronts contain elements that are progressively less optimal with respect to the objective functions.<ref name="ENS"/>

Non-dominated sorting is used in several [[multi-objective optimization]] algorithms.<ref name="NSGA"/><ref name="FNS"/><ref name="ENS"/>

== Usage ==

Line 30 ⟶ 26:

== Algorithms and complexity ==

Various algorithms have been devised to perform non-dominated sorting. The first algorithm for non-dominated sorting was introduced in 1995 N. Srinivas and K. Deb in a paper presenting the NSGA optimization algorithm.<ref name="NSGA">{{Cite journal |last1=Srinivas |first1=N. |last2=Deb |first2=Kalyanmoy |date=1994-09-01 |title=Muiltiobjective Optimization Using Nondominated Sorting in Genetic Algorithms |url=https://direct.mit.edu/evco/article/2/3/221-248/1396 |journal=Evolutionary Computation |language=en |volume=2 |issue=3 |pages=221–248 |doi=10.1162/evco.1994.2.3.221 |s2cid=13997318 |issn=1063-6560}}</ref>. It has a complexity of {{math|''O''(''MN'' ³)}} where {{mvar|M}} is the number of objectives and {{mvar|N}} is the size size of the set of elements. More recent algorithms have been developed with improved time complexity such as '''Fast Non-Dominated Sorting (FNS)''' ({{math|''O''(''MN'' ²)}})<ref name="FNS">{{Cite journal |last1=Deb |first1=K. |last2=Pratap |first2=A. |last3=Agarwal |first3=S. |last4=Meyarivan |first4=T. |date=2002-04-01 |title=A fast and elitist multiobjective genetic algorithm: NSGA-II |url=https://ieeexplore.ieee.org/document/996017 |journal=IEEE Transactions on Evolutionary Computation |volume=6 |issue=2 |pages=182–197 |doi=10.1109/4235.996017 |bibcode=2002ITEC....6..182D }}</ref>, '''Jensen’s algorithm''' ({{math|''O''(''N'' log^''M''−1 ''N'')}}) <ref name="Jensen">{{Cite journal |last=Jensen |first=M.T. |date=2003-10-01 |title=Reducing the Run-Time Complexity of Multiobjective EAs: The NSGA-II and Other Algorithms |url=https://ieeexplore.ieee.org/document/1237166 |journal=IEEE Transactions on Evolutionary Computation |language=en |volume=7 |issue=5 |pages=503–515 |doi=10.1109/TEVC.2003.817234 |issn=1089-778X}}</ref>, or the '''Efficient Non-Dominated Sorting (ENS)''' (from {{math|''O''(''MN'' log ''N'')}} to {{math|''O''(''MN'' ²)}}) <ref name="ENS">{{Cite journal |last1=Xingyi Zhang |last2=Ye Tian |last3=Ran Cheng |last4=Yaochu Jin |date=2015-04-01 |title=An Efficient Approach to Nondominated Sorting for Evolutionary Multiobjective Optimization |url=https://ieeexplore.ieee.org/document/6766752 |journal=IEEE Transactions on Evolutionary Computation |volume=19 |issue=2 |pages=201–213 |doi=10.1109/TEVC.2014.2308305 |s2cid=19088623 |issn=1089-778X}}</ref>

The non-dominated sorting algorithm used in <ref name="NSGA"/> can be described simply as follows (see <ref name="ENS"/><ref name="FNS"/>):