research-article

Public Access

Best Order Sort: A New Algorithm to Non-dominated Sorting for Evolutionary Multi-objective Optimization

Authors:

Proteek Chandan Roy,

Md. Monirul Islam,

Kalyanmoy DebAuthors Info & Claims

GECCO '16 Companion: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion

Pages 1113 - 1120

https://doi.org/10.1145/2908961.2931684

Published: 20 July 2016 Publication History

GECCO '16 Companion: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion

Best Order Sort: A New Algorithm to Non-dominated Sorting for Evolutionary Multi-objective Optimization

Pages 1113 - 1120

Abstract
References

Abstract

Finding the non-dominated sorting of a given set vectors has applications in Pareto based evolutionary multi-objective optimization (EMO), finding convex hull, linear optimization, nearest neighbor, skyline queries in database and many others. Among these, EMOs use this method for survival selection. The worst case complexity of this problem is found to be O(Nlog^M-1N) when the number of objectives M is constant and the size of solutions N is varying. But this bound becomes too large when M depends on N. In this paper we are proposing a new algorithm with worst case complexity O(MNlogN+MN²), however, with reduced running time in many objective cases. This algorithm can make use of the faster implementation of sorting algorithms. It removes unnecessary comparisons among the solutions which improves the running time. The proposed algorithm is compared with four other competing algorithms on three different datasets. Experimental results show that our approach, namely, best order sort (BOS) is computationally more efficient than all other compared algorithms with respect to running time.

References

[1]

S. Adra and P. Fleming. Diversity management in evolutionary many-objective optimization. Evolutionary Computation, IEEE Transactions on, 15(2):183--195, April 2011.

Digital Library

[2]

J. L. Bentley. Multidimensional divide-and-conquer. Commun. ACM, 23(4):214--229, Apr. 1980.

Digital Library

[3]

J. L. Bentley, H. T. Kung, M. Schkolnick, and C. D. Thompson. On the average number of maxima in a set of vectors and applications. J. ACM, 25(4):536--543, Oct. 1978.

Digital Library

[4]

M. Buzdalov and A. Shalyto. A provably asymptotically fast version of the generalized Jensen algorithm for non-dominated sorting. In T. Bartz-Beielstein, J. Branke, B. Filipic, and J. Smith, editors, Parallel Problem Solving from Nature - PPSN XIII, volume 8672 of Lecture Notes in Computer Science, pages 528--537. Springer International Publishing, 2014.

[5]

C. A. Coello Coello and M. Lechuga. MOPSO: a proposal for multiple objective particle swarm optimization. In Evolutionary Computation, 2002. CEC '02. Proceedings of the 2002 Congress on, volume 2, pages 1051--1056, 2002.

Digital Library

[6]

K. Deb and H. Jain. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints. Evolutionary Computation, IEEE Transactions on, 18(4):577--601, Aug 2014.

[7]

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-II. Evolutionary Computation, IEEE Transactions on, 6(2):182--197, Apr 2002.

Digital Library

[8]

K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable multi-objective optimization test problems. In Evolutionary Computation, 2002. CEC '02. Proceedings of the 2002 Congress on, volume 1, pages 825--830, May 2002.

[9]

K. Deb and S. Tiwari. Omni-optimizer: A procedure for single and multi-objective optimization. In Proceedings of the Third International Conference on Evolutionary Multi-Criterion Optimization, EMO'05, pages 47--61, Berlin, Heidelberg, 2005. Springer-Verlag.

Digital Library

[10]

H. Fang, Q. Wang, Y.-C. Tu, and M. F. Horstemeyer. An efficient non-dominated sorting method for evolutionary algorithms. Evol. Comput., 16(3):355--384, Sept. 2008.

Digital Library

[11]

F.-A. Fortin, S. Grenier, and M. Parizeau. Generalizing the improved run-time complexity algorithm for non-dominated sorting. In Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, GECCO '13, pages 615--622, New York, NY, USA, 2013. ACM.

Digital Library

[12]

P. Godfrey, R. Shipley, and J. Gryz. Maximal vector computation in large data sets. In Proceedings of the 31st International Conference on Very Large Data Bases, VLDB '05, pages 229--240. VLDB Endowment, 2005.

Digital Library

[13]

S. Gupta and G. Tan. A scalable parallel implementation of evolutionary algorithms for multi-objective optimization on gpus. In Evolutionary Computation (CEC), 2015 IEEE Congress on, pages 1567--1574, May 2015.

[14]

J. Horn, N. Nafpliotis, and D. Goldberg. A niched Pareto genetic algorithm for multiobjective optimization. In Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on, pages 82--87 vol.1, Jun 1994.

[15]

S. Huband, P. Hingston, L. Barone, and L. While. A review of multiobjective test problems and a scalable test problem toolkit. Evolutionary Computation, IEEE Transactions on, 10(5):477--506, Oct 2006.

Digital Library

[16]

M. Jensen. Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms. Evolutionary Computation, IEEE Transactions on, 7(5):503--515, Oct 2003.

Digital Library

[17]

J. Knowles and D. Corne. The Pareto archived evolution strategy: a new baseline algorithm for Pareto multiobjective optimisation. In Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, volume 1, page 105 Vol. 1, 1999.

[18]

H. T. Kung, F. Luccio, and F. P. Preparata. On finding the maxima of a set of vectors. J. ACM, 22(4):469--476, Oct. 1975.

Digital Library

[19]

K. McClymont and E. Keedwell. Deductive sort and climbing sort: New methods for non-dominated sorting. Evol. Comput., 20(1):1--26, Mar. 2012.

Digital Library

[20]

L. Monier. Combinatorial solutions of multidimensional divide-and-conquer recurrences. J. Algorithms, 1(1):60--74, 1980.

[21]

T. Murata and H. Ishibuchi. MOGA: multi-objective genetic algorithms. In Evolutionary Computation, 1995., IEEE International Conference on, volume 1, pages 289--294, Nov 1995.

[22]

P. Roy, M. Islam, K. Murase, and X. Yao. Evolutionary path control strategy for solving many-objective optimization problem. Cybernetics, IEEE Transactions on, 45(4):702--715, April 2015.

[23]

N. Srinivas and K. Deb. Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evol. Comput., 2(3):221--248, Sept. 1994.

Digital Library

[24]

S. Tang, Z. Cai, and J. Zheng. A fast method of constructing the non-dominated set: Arena's principle. In Proceedings of the 2008 Fourth International Conference on Natural Computation - Volume 01, ICNC '08, pages 391--395, Washington, DC, USA, 2008. IEEE Computer Society.

Digital Library

[25]

H. Wang and X. Yao. Corner sort for pareto-based many-objective optimization. Cybernetics, IEEE Transactions on, 44(1):92--102, Jan 2014.

[26]

M. A. Yukish. Algorithms to Identify Pareto Points in Multi-dimensional Data Sets. PhD thesis, Pennsylvania State University, 2004. AAI3148694.

Digital Library

[27]

X. Zhang, Y. Tian, R. Cheng, and Y. Jin. An efficient approach to nondominated sorting for evolutionary multiobjective optimization. Evolutionary Computation, IEEE Transactions on, 19(2):201--213, April 2015.

[28]

E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization. In K. Giannakoglou et al., editors, Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems (EUROGEN 2001), pages 95--100. International Center for Numerical Methods in Engineering (CIMNE), 2002.

Cited By

Li YLiu BDuan TWang ZLi HCui J(2025)A Novel Key Point Based MLCS Algorithm for Big Sequences MiningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.348523437:1(15-28)Online publication date: Jan-2025
https://doi.org/10.1109/TKDE.2024.3485234
Mishra SPrakash VCoello Coello C(2025)Analysis of Merge Non-dominated Sorting AlgorithmEvolutionary Multi-Criterion Optimization10.1007/978-981-96-3538-2_4(46-57)Online publication date: 28-Feb-2025
https://doi.org/10.1007/978-981-96-3538-2_4
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
Show More Cited By

Index Terms

Best Order Sort: A New Algorithm to Non-dominated Sorting for Evolutionary Multi-objective Optimization
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
2. Theory of computation

Recommendations

Deductive sort and climbing sort: New methods for non-dominated sorting

In recent years an increasing number of real-world many-dimensional optimisation problems have been identified across the spectrum of research fields. Many popular evolutionary algorithms use non-dominance as a measure for selecting solutions for future ...
Using Dominated Solutions at Edges to the Diversity and the Uniformity of Non-dominated Solution Distributions in NSGA-II
Abstract
This paper proposes a method for improving the diversity of the Pareto front and the uniformity of non-dominated solution distributions in a fast elitist non-dominated sorting genetic algorithm (NSGA-II), which is an evolutionary multi-objective ...
A comprehensive survey on NSGA-II for multi-objective optimization and applications
Abstract
In the last two decades, the fast and elitist non-dominated sorting genetic algorithm (NSGA-II) has attracted extensive research interests, and it is still one of the hottest research methods to deal with multi-objective optimization problems. ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '16 Companion: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion

July 2016

1510 pages

ISBN:9781450343237

DOI:10.1145/2908961

Editor:
Tobias Friedrich
Hasso Plattner Institute
,
General Chair:
Frank Neumann
University of Adelaide
,
Program Chair:
Andrew M. Sutton
Hasso Plattner Institute

Copyright © 2016 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 ACM 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: 20 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

GECCO '16

Sponsor:

SIGEVO

GECCO '16: Genetic and Evolutionary Computation Conference

July 20 - 24, 2016

Colorado, Denver, USA

Acceptance Rates

GECCO '16 Companion Paper Acceptance Rate 137 of 381 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
944
Total Downloads

Downloads (Last 12 months)150
Downloads (Last 6 weeks)18

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li YLiu BDuan TWang ZLi HCui J(2025)A Novel Key Point Based MLCS Algorithm for Big Sequences MiningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.348523437:1(15-28)Online publication date: Jan-2025
https://doi.org/10.1109/TKDE.2024.3485234
Mishra SPrakash VCoello Coello C(2025)Analysis of Merge Non-dominated Sorting AlgorithmEvolutionary Multi-Criterion Optimization10.1007/978-981-96-3538-2_4(46-57)Online publication date: 28-Feb-2025
https://doi.org/10.1007/978-981-96-3538-2_4
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
Mukherjee AMandal SDutta P(2024)Generating Multi-objective Fronts from Streamed Data Using Nested ListPattern Recognition10.1007/978-3-031-78189-6_9(128-143)Online publication date: 11-Dec-2024
https://doi.org/10.1007/978-3-031-78189-6_9
Prakash VMishra S(2023)Revisiting Basic Concepts of Dominance Relationship in Non-Dominated Sorting2023 International Conference on Emerging Techniques in Computational Intelligence (ICETCI)10.1109/ICETCI58599.2023.10331200(215-220)Online publication date: 21-Sep-2023
https://doi.org/10.1109/ICETCI58599.2023.10331200
Chaabani AKaraja MSaid L(2023)An Efficient Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization2023 9th International Conference on Control, Decision and Information Technologies (CoDIT)10.1109/CoDIT58514.2023.10284357(1565-1570)Online publication date: 3-Jul-2023
https://doi.org/10.1109/CoDIT58514.2023.10284357
Bharti VSinghal ASaxena ABiswas BShukla KWagner M(2022)Parallelization of corner sort with CUDA for many-objective optimizationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528877(484-492)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528877
Irawan DNaujoks BBäck TEmmerich M(2022)Dominance-based variable analysis for large-scale multi-objective problemsNatural Computing10.1007/s11047-022-09910-522:2(243-257)Online publication date: 25-Aug-2022
https://doi.org/10.1007/s11047-022-09910-5
Naser Abdali THassan RMohd Aman ANguyen QAl-Khaleefa A(2021)Hyper-Angle Exploitative Searching for Enabling Multi-Objective Optimization of Fog ComputingSensors10.3390/s2102055821:2(558)Online publication date: 14-Jan-2021
https://doi.org/10.3390/s21020558
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten