Draft:Non dominated sorting: Difference between revisions

Revision as of 17:16, 5 March 2025

Latest revision as of 21:03, 25 August 2025

Line 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"/>):