research-article

If unsure, shuffle: deductive sort is Θ(MN³), but O(MN²) in expectation over input permutations

Authors:

Maxim BuzdalovAuthors Info & Claims

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

Pages 516 - 523

https://doi.org/10.1145/3377930.3390246

Published: 26 June 2020 Publication History

Abstract

Despite significant advantages in theory of evolutionary computation, many papers related to evolutionary algorithms still lack proper analysis and limit themselves by rather vague reflections on why making a certain design choice improves the performance. While this seems to be unavoidable when talking about the behavior of an evolutionary algorithm on a practical optimization problem, doing the same for computational complexities of parts of evolutionary algorithms is harmful and should be avoided.

Non-dominated sorting is one of such parts, commonly used in various evolutionary multiobjective algorithms. The complexity of the problem as such is not well-understood, and many algorithms were proposed for solving it in recent years. Unfortunately, the analysis of some of them is imperfect. In this paper, we prove that, contrary to what is claimed by its authors, the algorithm known as Deductive Sort has the worst-case time complexity of Θ(MN³), where M is the number of objectives and N is the population size. However, if one shuffles the input, the worst-case expected running time drops down to O(MN²).

References

[1]

Stephan Borzsony, Donald Kossmann, and Konrad Stocker. 2001. The Skyline Operator. In Proceedings of 17th International Conference on Data Engineering (ICDE'2001). IEEE, 421--430.

[2]

Maxim Buzdalov. 2018. Generalized offline orthant search: One code for many problems in multiobjective optimization. In Proceedings of Genetic and Evolutionary Computation Conference. 593--600.

Digital Library

[3]

Maxim Buzdalov. 2019. Make Evolutionary Multiobjective Algorithms Scale Better with Advanced Data Structures: Van Emde Boas Tree for Non-Dominated Sorting. In International Conference on Evolutionary Multi-Criterion Optimization (EMO'2019). Springer. Lecture Notes in Computer Science Vol. 11411, East Lansing, MI, USA, 66--77. ISBN: 978-3-030-12597-4.

[4]

Maxim Buzdalov and Anatoly Shalyto. 2014. A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-Dominated Sorting. In International Conference on Parallel Problem Solving from Nature - PPSN XIII. Springer. Lecture Notes in Computer Science Vol. 8672, Ljubljana, Slovenia, 528--537.

[5]

Kalyanmoy Deb, Rayan Hussein, Proteek Roy, and Gregorio Toscano. 2017. Classifying Metamodeling Methods for Evolutionary Multi-Objective Optimization: First Results. In International Conference on Evolutionary Multi-Criterion Optimization (EMO'2017). Springer. Lecture Notes in Computer Science Vol. 10173, Münster, Germany, 160--175. ISBN: 978-3-319-54156-3.

[6]

Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. 2002. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (April 2002), 182--197.

Digital Library

[7]

Félix-Antoine Fortin, Simon Greiner, and Marc Parizeau. 2013. Generalizing the Improved Run-Time Complexity Algorithm for Non-Dominated Sorting. In 2013 Genetic and Evolutionary Computation Conference (GECCO'2013). ACM Press, New York, USA, 615--622. ISBN: 978-1-4503-1963-8.

[8]

Patrik Gustavsson and Anna Syberfeldt. 2018. A New Algorithm Using the Non-Dominated Tree to Improve Non-Dominated Sorting. Evolutionary Computation 26, 1 (September 2018), 89--116.

Digital Library

[9]

Julia Handl and Joshua Knowles. 2005. Exploiting the Trade-Off-The Benefits of Multiple Objectives in Data Clustering. In International Conference on Evolutionary Multi-Criterion Optimization (EMO'2005). Springer. Lecture Notes in Computer Science Vol. 3410, Guanajuato, México, 547--560.

[10]

Mikkel T. Jensen. 2003. Reducing the Run-Time Complexity of Multiobjective EAs: The NSGA-II and Other Algorithms. IEEE Transactions on Evolutionary Computation 7, 5 (October 2003), 503--515.

Digital Library

[11]

Kevin Leyton-Brown and Yoav Shoham. 2008. Essentials of Game Theory: A Concise Multidisciplinary Introduction. Synthesis Lectures on Artificial Intelligence and Machine Learning 2, 1 (2008), 1--88.

[12]

Ruey-Der Lou and Majid Sarrafzadeh. 1993. An Optimal Algorithm for the Maximum Three-Chain Problem. SIAM J. Comput. 22, 5 (1993), 976--993.

Digital Library

[13]

Margarita Markina and Maxim Buzdalov. 2017. Hybridizing Non-Dominated Sorting Algorithms: Divide-and-Conquer Meets Best Order Sort. In 2017 Genetic and Evolutionary Computation Conference (GECCO'2017). ACM, 153--154.

Digital Library

[14]

Kent McClymont and Ed Keedwell. 2012. Deductive Sort and Climbing Sort: New Methods for Non-Dominated Sorting. Evolutionary Computation 20, 1 (Spring 2012), 1--26.

Digital Library

[15]

Sumit Mishra, Maxim Buzdalov, and Rakesh Senwar. 2020. Time Complexity Analysis of the Dominance Degree Approach for Non-Dominated Sorting. In Proceedings of Genetic and Evolutionary Computation Conference Companion. Accepted for publication.

Digital Library

[16]

Sumit Mishra, Samrat Mondal, Sriparna Saha, and Carlos A. Coello Coello. 2018. GBOS: Generalized Best Order Sort Algorithm for Non-Dominated Sorting. Swarm and Evolutionary Computation 43 (December 2018), 244--264.

[17]

Sumit Mishra, Sriparna Saha, and Samrat Mondal. 2018. MBOS: Modified Best Order Sort Algorithm for Performing Non-dominated Sorting. In 2018 IEEE Congress on Evolutionary Computation (CEC'2018). IEEE Press, Rio de Janeiro, Brazil, 725--732. ISBN: 978-1-5090-6017-7.

[18]

Javier Moreno, Daniel Rodriguez, Antonio J Nebro, and Jose A Lozano. 2020. Merge Nondominated Sorting Algorithm for Many-Objective Optimization. IEEE Transactions on Cybernetics (2020). Accepted for publication.

[19]

Yakov Nekrich. 2011. A Fast Algorithm for Three-Dimensional Layers of Maxima Problem. In Workshop on Algorithms and Data Structures. Springer, 607--618.

[20]

Proteek Roy, Rayan Hussein, and Kalyanmoy Deb. 2017. Metamodeling for Multimodal Selection Functions in Evolutionary Multi-Objective Optimization. In 2017 Genetic and Evolutionary Computation Conference (GECCO'2017). ACM Press, Berlin, Germany, 625--632. ISBN: 978-1-4503-4920-8.

[21]

Proteek Chandan Roy and Kalyanmoy Deb. 2016. High Dimensional Model Representation for Solving Expensive Multi-Objective Optimization Problems. In 2016 IEEE Congress on Evolutionary Computation (CEC'2016). IEEE Press, Vancouver, Canada, 2490--2497. ISBN: 978-1-5090-0623-6.

[22]

Proteek Chandan Roy, Kalyanmoy Deb, and Md Monirul Islam. 2018. An Efficient Nondominated Sorting Algorithm for Large Number of Fronts. IEEE Transactions on Cybernetics 99 (2018), 1--11.

[23]

Proteek Chandan Roy, Md. Monirul Islam, and Kalyanmoy Deb. 2016. Best Order Sort: A New Algorithm to Non-Dominated Sorting for Evolutionary Multi-Objective Optimization. In 2016 Genetic and Evolutionary Computation Conference (GECCO'2016). ACM Press, Denver, Colorado, USA, 1113--1120. ISBN: 978-1-4503-4323-7.

Digital Library

[24]

N. Srinivas and Kalyanmoy Deb. 1994. Multiobjective Optimization Using Non-dominated Sorting in Genetic Algorithms. Evolutionary Computation 2, 3 (Fall 1994), 221--248.

Digital Library

[25]

Junchen Wang, Changhe Li, Yiya Diao, Sanyou Zeng, and Hui Wang. 2018. An Efficient Nondominated Sorting Algorithm. In 2018 Genetic and Evolutionary Computation Conference (GECCO'2018). ACM, 203--204.

[26]

Xingyi Zhang, Ye Tian, Ran Cheng, and Jin Yaochu. 2015. An Efficient Approach to Nondominated Sorting for Evolutionary Multiobjective Optimization. IEEE Transactions on Evolutionary Computation 19, 2 (April 2015), 201--213.

[27]

Yuren Zhou, Zefeng Chen, and Jun Zhang. 2017. Ranking Vectors by Means of the Dominance Degree Matrix. IEEE Transactions on Evolutionary Computation 21, 1 (2017), 34--51.

Digital Library

Cited By

Prakash VMishra S(2024)Hierarchical non-dominated sort: analysis and improvementGenetic Programming and Evolvable Machines10.1007/s10710-024-09487-125:1Online publication date: 16-Apr-2024
https://doi.org/10.1007/s10710-024-09487-1
Kong LPan JSnášel V(2024)A Review of Non-dominating Sorting AlgorithmsBusiness Intelligence and Information Technology10.1007/978-981-97-3980-6_15(173-183)Online publication date: 30-Aug-2024
https://doi.org/10.1007/978-981-97-3980-6_15
Prakash VMishra SCoello Coello C(2023)On the Computational Complexity of Efficient Non-dominated Sort Using Binary SearchEvolutionary Multi-Criterion Optimization10.1007/978-3-031-27250-9_30(419-432)Online publication date: 9-Mar-2023
https://doi.org/10.1007/978-3-031-27250-9_30
Show More Cited By

Index Terms

If unsure, shuffle: deductive sort is Θ(MN³), but O(MN²) in expectation over input permutations
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching

Recommendations

Counterexample to the best-case running time of efficient non-dominated sorting algorithm
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Non-dominated sorting is one of the important steps in Pareto dominance-based multiobjective evolutionary algorithms. In this paper, we show that the number of comparisons in the best case of an approach, Efficient Non-dominated Sort (ENS) from the paper ...
Labeling-oriented non-dominated sorting is Θ(MN³)
GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Non-dominated sorting is a common routine used in many evolutionary multiobjective algorithms to rank solutions based on the Pareto-dominance relation. Unlike many other problems appearing in evolutionary computation, this problem has a simple formal ...
On the Computational Complexity of Efficient Non-dominated Sort Using Binary Search
Evolutionary Multi-Criterion Optimization
Abstract
Over the years, several approaches have been proposed to solve the problem of non-dominated sorting, which is one of the crucial steps in Pareto dominance-based multi-objective evolutionary algorithms (MOEAs). However, some of these approaches, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

June 2020

1349 pages

ISBN:9781450371285

DOI:10.1145/3377930

General Chair:
Carlos Artemio Coello Coello
CINVESTAV-IPN

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Russian Science Foundation

Conference

GECCO '20

Sponsor:

SIGEVO

GECCO '20: Genetic and Evolutionary Computation Conference

July 8 - 12, 2020

Cancún, Mexico

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
87
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Prakash VMishra S(2024)Hierarchical non-dominated sort: analysis and improvementGenetic Programming and Evolvable Machines10.1007/s10710-024-09487-125:1Online publication date: 16-Apr-2024
https://doi.org/10.1007/s10710-024-09487-1
Kong LPan JSnášel V(2024)A Review of Non-dominating Sorting AlgorithmsBusiness Intelligence and Information Technology10.1007/978-981-97-3980-6_15(173-183)Online publication date: 30-Aug-2024
https://doi.org/10.1007/978-981-97-3980-6_15
Prakash VMishra SCoello Coello C(2023)On the Computational Complexity of Efficient Non-dominated Sort Using Binary SearchEvolutionary Multi-Criterion Optimization10.1007/978-3-031-27250-9_30(419-432)Online publication date: 9-Mar-2023
https://doi.org/10.1007/978-3-031-27250-9_30
Mishra SPrakash VBuzdalov MKrawiec K(2021)Labeling-oriented non-dominated sorting is Θ(MN3)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3459425(189-190)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3459425
Mishra SPrakash VKrawiec K(2021)Time complexity analysis of the deductive sort in the best caseProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3459416(337-338)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3459416
Mishra SBuzdalov M(2020)Filter Sort Is $$\varOmega (N^3)$$ in the Worst CaseParallel Problem Solving from Nature – PPSN XVI10.1007/978-3-030-58115-2_47(675-685)Online publication date: 2-Sep-2020
https://doi.org/10.1007/978-3-030-58115-2_47

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents