Very Fast Non-dominated Sorting

Authors

  • Czesław Smutnicki Wroclaw University of Technology
  • Jaroslaw Rudy Wroclaw University of Technology
  • Dominik Zelazny Wroclaw University of Technology

DOI:

https://doi.org/10.7494/dmms.2014.8.1.13

Keywords:

parallel algorithms, Pareto sorting, computational complexity, GPU computing, multiple-criteria decision analysis

Abstract

New and very ecient parallel algorithm for the Fast Non-dominated Sorting of Pareto fronts is proposed. By decreasing its computational complexity, the application of the proposed method allows us to increase the speedup of the best up to now Fast and Elitist Multi-objective Genetic Algorithm (NSGA-II) more than two orders of magnitudes. Formal proofs of time complexities of basic as well as improved versions of the procedure are presented. Provided experimental results fully conrm theoretical ndings.

References

Amdahl, G.M., 1967. Validity of the single processor approach to achieving large scale computing capabilities. In Proceedings of the Spring Joint Computer Conference, AFIPS ’67 (Spring), pp. 483–485. ACM.

Bozejko, W., Pempera, J., and Smutnicki, C., 2013. Parallel tabu search algorithm for the hybrid flow shop problem. In Computers and Industrial Engineering, 65(3), pp. 466–474.

Bozejko, W., Uchronski, M., and Wodecki, M., 2014. Multi-gpu tabu search metaheuristic for the flexible job shop scheduling problem. In Advanced Methods and Applications in Computational Intelligence, volume 6 of Topics in Intelligent Engineering and Informatics, pp. 43–60.

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

Deb, K., Zope, P., and Jain, A., 2003. Distributed computing of pareto-optimal solutions with evolutionary algorithms. In Evolutionary Multi-Criterion Optimization, Vol. 2632 of Lecture Notes in Computer Science, pp. 534–549.

Durillo, J.J., Nebro, A.J., Luna, F. and Alba, E., 2008. A study of master-slave approaches to parallelize NSGA-II. In Proceedings of International Symposium on Parallel and Distributed Processing, pp. 1–8.

Jozefowiez, N., Semet, F. and Talbi, E., 2006. Enhancements of NSGA-II and its application to the vehicle routing problem with route balancing. In Artificial Evolution, Vol. 3871 of Lecture Notes in Computer Science, pp. 131–142.

Minella, G., Ruiz, R. and Ciavotta, M., 2008. A review and evaluation of multiobjective algorithms for the flowshop scheduling problem. INFORMS Journal on Computing, 20(3), pp. 451–471.

Rudy, J. and Zelazny, D., 2012. Memetic algorithm approach for multi-criteria network scheduling. In Proceedings of the International Conference On ICT Management for Global Competitiveness And Economic Growth In Emerging Economies, pp. 247–261.

Talbi, E., Mostaghim, S., Okabe, T., Ishibuchi, H., Rudolph, G., and Coello, C.A., 2008. Parallel approaches for multiobjective optimization. In Multiobjective Optimization, Vol. 5252 of Lecture Notes in Computer Science, pp. 349–372.

Yijie, S., Gongzhang, S., 2008. Improved NSGA-II multi-objective genetic algorithm based on hybridization-encouraged mechanism. Chinese Journal of Aeronautics, 21(6), pp. 540–549.

Downloads

Published

2014-11-19

How to Cite

Smutnicki, C., Rudy, J., & Zelazny, D. (2014). Very Fast Non-dominated Sorting. Decision Making in Manufacturing and Services, 8(1-2), 13–23. https://doi.org/10.7494/dmms.2014.8.1.13

Issue

Vol. 8 (2014): No. 1-2

Section

Articles

License

Remeber to prepeare, sign and scan copyright statement

Licencja Creative Commons
The content of the journal is freely available according to the Creative Commons License Attribution 4.0 International (CC BY 4.0)

Received 2014-08-23
Accepted 2014-09-09
Published 2014-11-19