Draft:Non dominated sorting: Difference between revisions

Revision as of 11:52, 11 July 2023

Latest revision as of 21:03, 25 August 2025

(18 intermediate revisions by 7 users not shown)

Line 1:

{{AfCAFC submission|td||ts=20230711114637v|u=BooBoo314159|ns=118|demodecliner=Xkalponik|declinets=20240417205836|reason2=essay|ts=20240129175012}} <!-- Important, doDo not remove this line before article has been created.! -->

{{AFC submission|d|nn|u=BooBoo314159|ns=118|decliner=Vanderwaalforces|declinets=20231102133913|small=yes|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)}}

----

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

{{Short description|Non-dominated sorting}}

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.

{{Draft topics|computing}}

{{AfC topic|stem}}

{{Underlinked|date=November 2023}}

Non-dominated sorting is a technique used to sort 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.

The first nonNon-dominated frontsorting contains(also theknown best elementsas non-dominated thoseranking) thatis area nottechnique dominatedthat byinvolves anycategorizing othera elements.set The second front containsof elements thatbased areon dominatedtheir onlydominance byrelationship elementswith ineach theother. firstThe frontpurpose (anof elementnon-dominated in the second frontsorting is notto necessarilyrank dominatedthe byelements allfrom the elementsbest into the firstworst front,element butaccording byto attheir leastdominance one of them)relationship. The subsequentdominance frontsrelationship containbetween elements thatis aredetermined progressivelyby lesscomparing optimaltheir withscores respecton toa thefixed 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<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.

In fact the first front corresponds exactly to the [[maxima of a point set|maximal elements of the set]].

Non-dominated sorting sorts 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"/>

Non-dominated sorting is often used in [[multi-objective optimization]] algorithms.

== Usage ==

Non-dominated sorting, is a concept and algorithm widely employed in various domains to solve [[multi-objective optimization]] problems. The primary objective of non-dominated sorting is to classify a set of solutions into distinct fronts based on their dominance relationship, enabling the identification of the most desirable solutions.<ref name="FNS" /><ref name="ENS" />

NonIn particular, non-dominated sorting playsis aused crucialin rolesome inmultiobjective versions of [[evolutionary algorithms|Evolutionary algorithm]] and [[genetic algorithms|Genetic algorithm]] <ref name="FNS" /><ref name="NSGA" /><ref name="ENS" />. These algorithms simulate an evolutionary process, iteratively generating and improving a population of candidate solutions. Non-dominated sorting allows the algorithms to identify and maintain a diverse set of non-dominated solutions.

== 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">{{citeCite journal |last1=Srinivas |first1=N. |last2=Deb |first2=Kalyanmoy |date=1994-09-01 |title=MultiobjectiveMuiltiobjective optimizationOptimization usingUsing non-Nondominated dominated sortingSorting in geneticGenetic algorithmsAlgorithms |url=https://direct.mit.edu/evco/article/2/3/221-248/1396 |journal=Evolutionary Computation |datelanguage=1994en |volume=2 |issue=3 |pages=221–248 |urldoi=https:10.1162//ieeexploreevco.ieee1994.org/document/67917272.3.221 |s2cid=13997318 |issn=1063-6560}}</ref>. It hadhas a complexity of {{math|''O''(''MN'' ³)}} where {{mvar|M}} is the number of objectives and {{mvar|N}} is the populationsize 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">{{citeCite journal |last1=Deb |first1=KalyanmoyK. |last2=Pratap |first2=AmritA. |last3=Agarwal |first3=SameerS. |last4=Meyarivan |first4=TAMTT. |date=2002-04-01 |title=A fast and elitist multi-objectivemultiobjective genetic algorithm: NSGA-II |journal=IEEE transactionsTransactions on evolutionaryEvolutionary computation |date=2002Computation |volume=6 |issue=2 |pages=182-197182–197 |urldoi=https://ieeexplore10.ieee.org/abstract/document1109/4235.996017 |bibcode=2002ITEC....6..182D }}</ref>, '''Jensen’s algorithm''' ({{math|''O''(''N'' log^''M''−1 ''N'')}}) <ref name="Jensen">{{citeCite journal |last1last=Jensen |first1first=Mikkel M.T. |date=2003-10-01 |title=Reducing the runRun-timeTime complexityComplexity of multiobjectiveMultiobjective EAs: The NSGA-II and otherOther algorithmsAlgorithms |journal=IEEE Transactions on Evolutionary Computation |datelanguage=2003en |volume=7 |issue=5 |pages=503-515503–515 |urldoi=https:10.1109//ieeexploreTEVC.ieee2003.org/abstract/document/1237166817234 |issn=1089-778X}}</ref>, or the '''Efficient Non-Dominated Sorting (ENS)''' (from {{math|''O''(''MN'' log ''N'')}} to {{math|''O''(''MN'' ²)}}) <ref name="ENS">{{citeCite journal |last1=Xingyi Zhang |first1=Xingyi |last2=Ye Tian |first2last3=YeRan |last3=Cheng |first3last4=RanYaochu |last4=Jin |first4date=Yaochu2015-04-01 |title=An efficientEfficient approachApproach to nondominatedNondominated sortingSorting for evolutionaryEvolutionary multiobjectiveMultiobjective optimizationOptimization |journal=IEEE Transactions on Evolutionary Computation |date=2014 |volume=19 |issue=2 |urlpages=https:/201–213 |doi=10.1109/ieeexploreTEVC.ieee2014.org/abstract/document/67667522308305 |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"/>):

# Start with a set of elements called {{mvar|S}}.

# Iteratively, find the elements in {{mvar|S}} that are not dominated by any other elements. These elements are considered to be in a new "front" (in the first iteration, it's the first front).

# Remove these elements from {{mvar|S}}.

# If {{mvar|S}} is empty, the algorithm ends. Otherwise, go back to step 2.

In summary, the algorithm identifies non-dominated elements and assigns them to fronts, removing them from consideration until all elements have been processed.

== A simple example ==

Line 24 ⟶ 47:

E: (7, 5)

F: (4, 3)

[[File:Illustration pareto sorting.svg|thumb|upright=2| The 6 points are sorted into 4 non-dominated fronts.]]

We will now apply the algorithm presented in the previous section [[Draft:Non dominated sorting#Algorithms and complexity|Algorithms and complexity]].

To perform non-dominated sorting on this set, we can first compare each element to every other element as explained earlier. For example, we can compare element A to element B as follows:

* A dominates B in the {{mvar|x}} dimension (A's {{mvar|x}} value of 5 is greater than B's {{mvar|x}} value of 3)

Line 40 ⟶ 65:

Front 3: B, F

Front 4: C

== Usage ==

Non-dominated sorting, is a concept and algorithm widely employed in various domains to solve [[multi-objective optimization]] problems. The primary objective of non-dominated sorting is to classify a set of solutions into distinct fronts based on their dominance relationship, enabling the identification of the most desirable solutions.

Non-dominated sorting plays a crucial role in evolutionary algorithms and genetic algorithms <ref name="FNS" /><ref name="NSGA" />. These algorithms simulate an evolutionary process, iteratively generating and improving a population of candidate solutions. Non-dominated sorting allows the algorithms to identify and maintain a diverse set of non-dominated solutions.

== 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 |title=Multiobjective optimization using non- dominated sorting in genetic algorithms |journal=Evolutionary Computation |date=1994 |volume=2 |issue=3 |pages=221–248 |url=https://ieeexplore.ieee.org/document/6791727}}</ref>. It had a complexity of {{math|''O''(''MN'' ³)}} where {{mvar|M}} is the number of objectives and {{mvar|N}} is the population size. 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=Kalyanmoy |last2=Pratap |first2=Amrit |last3=Agarwal |first3=Sameer |last4=Meyarivan |first4=TAMT |title=A fast and elitist multi-objective genetic algorithm: NSGA-II |journal=IEEE transactions on evolutionary computation |date=2002 |volume=6 |issue=2 |pages=182-197 |url=https://ieeexplore.ieee.org/abstract/document/996017}}</ref>, '''Jensen’s algorithm''' ({{math|''O''(''N'' log^''M''−1 ''N'')}}) <ref name="Jensen">{{cite journal |last1=Jensen |first1=Mikkel T |title=Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms |journal=IEEE Transactions on Evolutionary Computation |date=2003 |volume=7 |issue=5 |pages=503-515 |url=https://ieeexplore.ieee.org/abstract/document/1237166}}</ref>, or the '''Efficient Non-Dominated Sorting (ENS)''' (from {{math|''O''(''MN'' log ''N'')}} to {{math|''O''(''MN'' ²)}}) <ref name="ENS">{{cite journal |last1=Zhang |first1=Xingyi |last2=Tian |first2=Ye |last3=Cheng |first3=Ran |last4=Jin |first4=Yaochu |title=An efficient approach to nondominated sorting for evolutionary multiobjective optimization |journal=IEEE Transactions on Evolutionary Computation |date=2014 |volume=19 |issue=2 |url=https://ieeexplore.ieee.org/abstract/document/6766752}}</ref>.

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

# Start with a set of elements called {{mvar|S}}.

# Iteratively, find the elements in {{mvar|S}} that are not dominated by any other elements. These elements are considered to be in a new "front" (in the first iteration, it's the first front).

# Remove these elements from {{mvar|S}}.

# If {{mvar|S}} is empty, the algorithm ends. Otherwise, go back to step 2.

In summary, the algorithm identifies non-dominated elements and assigns them to fronts, removing them from consideration until all elements have been processed.

== References ==

Line 65 ⟶ 71:

== External links ==

Here are links to some implementation of non-domminateddominated sorting

* https://github.com/mbuzdalov/non-dominated-sorting

* https://github.com/anyoptimization/pymoo/tree/main/pymoo/util/nds