Draft:Non dominated sorting: Difference between revisions

Revision as of 04:06, 2 November 2023

Revision as of 13:39, 2 November 2023

Line 1:

{{AFC submission|d|nn|u=BooBoo314159|ns=118|decliner=Vanderwaalforces|declinets=20231102133913|ts=20230714053833}} <!-- Do not remove this line! -->

{{AFC comment|1=This looks like a nice topic but please see [[WP:OR]]. [[User:Vanderwaalforces|Vanderwaalforces]] ([[User talk:Vanderwaalforces|talk]]) 13:39, 2 November 2023 (UTC)}}

----

{{Short description|Non-dominated sorting}}

{{Underlinked|date=November 2023}}

{{Draft topics|computing}}

{{AfC topic|stem}}

{{AfC submission|||ts=20230714053833|u=BooBoo314159|ns=118}}

{{AfC submission|t||ts=20230711114637|u=BooBoo314159|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->

Non-dominated sorting (also known as non-dominated ranking) is a technique that involves categorizing a set of elements based on their dominance relationship with each other. The purpose of non-dominated sorting is to rank the elements from the best to the worst element according to their dominance relationship. The dominance relationship between elements is determined by comparing their scores on a fixed number of objective functions .<ref name="NSGA" />.

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

Line 54 ⟶ 57:

== 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}}</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: