title: A New Algorithm Using the Non-Dominated Tree to Improve Non-Dominated Sorting.
abstract: Non-dominated sorting is a technique often used in evolutionary algorithms to determine the quality of solutions in a population. The most common algorithm is the Fast Non-dominated Sort (FNS). This algorithm, however, has the drawback that its performance deteriorates when the population size grows. The same drawback applies also to other non-dominating sorting algorithms such as the Efficient Non-dominated Sort with Binary Strategy (ENS-BS). An algorithm suggested to overcome this drawback is the Divide-and-Conquer Non-dominated Sort (DCNS) which works well on a limited number of objectives but deteriorates when the number of objectives grows. This article presents a new, more efficient algorithm called the Efficient Non-dominated Sort with Non-Dominated Tree (ENS-NDT). ENS-NDT is an extension of the ENS-BS algorithm and uses a novel Non-Dominated Tree (NDTree) to speed up the non-dominated sorting. ENS-NDT is able to handle large population sizes and a large number of objectives more efficiently than existing algorithms for non-dominated sorting. In the article, it is shown that with ENS-NDT the runtime of multi-objective optimization algorithms such as the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) can be substantially reduced.
authors.affiliation: School of Engineering, University of Skövde, Skövde, 54134, Sweden patrik.gustavsson@his.se.
authors.forename: Patrik
authors.initials: P
authors.lastname: Gustavsson
authors.affiliation: School of Engineering, University of Skövde, Skövde, 54134, Sweden anna.syberfeldt@his.se.
authors.forename: Anna
authors.initials: A
authors.lastname: Syberfeldt
mesh_terms: D000465:Algorithms; D005075:Biological Evolution; D003627:Data Interpretation, Statistical; D003663:Decision Trees; D008954:Models, Biological
keywords: Evolutionary computation; Pareto optimality; k-d tree; multi-objective evolutionary algorithms; non-dominated sorting; runtime complexity.