| Submission declined on 17 April 2024 by Xkalponik (talk). This submission is not adequately supported by reliable sources. Reliable sources are required so that information can be verified. If you need help with referencing, please see Referencing for beginners and Citing sources. This submission reads more like an essay than an encyclopedia article. Submissions should summarise information in secondary, reliable sources and not contain opinions or original research. Please write about the topic from a neutral point of view in an encyclopedic manner.
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
|  |
| Submission declined on 2 November 2023 by Vanderwaalforces (talk). This draft's references do not show that the subject qualifies for a Wikipedia article. In summary, the draft needs multiple published sources that are: Declined by Vanderwaalforces 12 months ago.
| |
Comment: This looks like a nice topic but please see WP:OR. Vanderwaalforces (talk) 13:39, 2 November 2023 (UTC)
 | This article needs more links to other articles to help integrate it into the encyclopedia. (November 2023) |
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.[1]
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[1]. 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 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.[2]
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 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.[2]
Non-dominated sorting is used in several multi-objective optimization algorithms.[1][3][2]
Usage
editNon-dominated sorting, is a concept and algorithm 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.[3][2]
In particular, non-dominated sorting is used in some multiobjective versions of Evolutionary algorithm and Genetic algorithm [3][1][2]. 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 set of non-dominated solutions.
Algorithms and complexity
editVarious 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.[1]. It has a complexity of O(MN 3) where M is the number of objectives and 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) (O(MN 2))[3], Jensen’s algorithm (O(N log M−1 N)) [4], or the Efficient Non-Dominated Sorting (ENS) (from O(MN log N) to O(MN 2)) [2]
The non-dominated sorting algorithm used in [1] can be described simply as follows (see [2][3]):
- Start with a set of elements called S.
- Iteratively, find the elements in 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 S.
- If 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
editLet's say we have the following set of elements with two objective functions, x and y:
x, y A: (5, 4) B: (3, 5) C: (2, 3) D: (4, 5) E: (7, 5) F: (4, 3)
We will now apply the algorithm presented in the previous section 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 x dimension (A's x value of 5 is greater than B's x value of 3)
- B dominates A in the y dimension (B's y value of 5 is greater than A's y value of 4)
Thus we can see the A and B do not dominated each other.
We repeat this process for all pairs of elements in the set. Then, we can use this information to sort the elements into different non-dominated fronts. The first front contains the elements that are not dominated by any other elements - in this case, just element E. The second front contains the elements that are dominated only by elements in the first front - in this case, elements A and D. The third front contains the elements that are dominated only by elements in the first and second fronts - in this case, elements B and F. The fourth and final front contains the element that is dominated by all other elements - in this case, element C.
So the non-dominated fronts for this set are:
Front 1: E Front 2: A, D Front 3: B, F Front 4: C
References
edit- ^ a b c d e f Srinivas, N.; Deb, Kalyanmoy (1994-09-01). "Muiltiobjective Optimization Using Nondominated Sorting in Genetic Algorithms". Evolutionary Computation. 2 (3): 221–248. doi:10.1162/evco.1994.2.3.221. ISSN 1063-6560. S2CID 13997318.
- ^ a b c d e f g Xingyi Zhang; Ye Tian; Ran Cheng; Yaochu Jin (2015-04-01). "An Efficient Approach to Nondominated Sorting for Evolutionary Multiobjective Optimization". IEEE Transactions on Evolutionary Computation. 19 (2): 201–213. doi:10.1109/TEVC.2014.2308305. ISSN 1089-778X. S2CID 19088623.
- ^ a b c d e Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. (2002-04-01). "A fast and elitist multiobjective genetic algorithm: NSGA-II". IEEE Transactions on Evolutionary Computation. 6 (2): 182–197. doi:10.1109/4235.996017.
- ^ Jensen, M.T. (2003-10-01). "Reducing the Run-Time Complexity of Multiobjective EAs: The NSGA-II and Other Algorithms". IEEE Transactions on Evolutionary Computation. 7 (5): 503–515. doi:10.1109/TEVC.2003.817234. ISSN 1089-778X.
External links
editHere are links to some implementation of non-dominated sorting