Very Fast Non-Dominated Sorting
DOI:
https://doi.org/10.7494/dmms.2014.8.1.13Keywords:
parallel algorithms, Pareto sorting, computational complexity, GPU computing, multiple-criteria decision analysisAbstract
A new and very efficient 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 magnitude. Formal proofs of time complexities of basic as well as improved versions of the procedure are presented. The provided experimental results fully confirm theoretical findings.
References
Amdahl G.M. (1967). Validity of the single processor approach to achieving large-scale computing capabilities. In: Proceedings of the April 18–20, 1967, Spring Joint Computer Conference – AFIPS ’67 (Spring), Atlantic City, NJ, pp. 483–485. New York: ACM. DOI: http://doi.org/10.1145/1465482.1465560.
Bożejko W., Pempera J. & Smutnicki C. (2013). Parallel tabu search algorithm for the hybrid flow shop problem. Computers & Industrial Engineering, 65(3), pp. 466–474. DOI: http://doi.org/10.1016/j.cie.2013.04.007.
Bożejko W., Uchroński M. & Wodecki M. (2014). Multi-GPU tabu search metaheuristic for the flexible job shop scheduling problem. In: Klempous R., Nikodem J., Jacak W. & Chaczko Z. (Eds.), Advanced Methods and Applications in Computational Intelligence. Topics in Intelligent Engineering and Informatics, 6, pp. 43–60. Heidelberg: Springer. DOI: http://doi.org/10.1007/978-3-319-01436-4_3.
Deb K., Pratap A., Agarwal S. & Meyarivan T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), pp. 182–197. DOI: http://doi.org/10.1109/4235.996017.
Deb K., Zope P. & Jain A. (2003). Distributed computing of Pareto-optimal solutions with evolutionary algorithms. In: Fonseca C.M., Fleming P.J., Zitzler E., Thiele L. & Deb K. (Eds.), Evolutionary Multi-Criterion Optimization. EMO 2003. Lecture Notes in Computer Science, 2632, pp. 534–549. Berlin–Heidelberg: Springer. DOI: http://doi.org/10.1007/3-540-36970-8_38.
Durillo J.J., Nebro A.J., Luna F. & Alba E. (2008). A study of master-slave approaches to parallelize NSGA-II. In: Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing, Miami, FL, April 14–18, 2008, pp. 1–8. IEEE. DOI: http://doi.org/10.1109/IPDPS.2008.4536375.
Jozefowiez N., Semet F. & Talbi E.-G. (2006). Enhancements of NSGA II and its application to the vehicle routing problem with route balancing. In: Talbi E.-G., Liardet P., Collet P., Lutton E. & Schoenauer M. (Eds.), Artificial Evolution: 7th International Conference, Evolution Artificielle, EA 2005, Revised Selected Papers. Lecture Notes in Computer Science, 3871, pp. 131–142. Berlin–Heidelberg: Springer. DOI: http://doi.org/10.1007/11740698_12.
Minella G., Ruiz R. & Ciavotta M. (2008). A review and evaluation of multiobjective algorithms for the flowshop scheduling problem. INFORMS Journal on Computing, 20(3), pp. 451–471. DOI: http://doi.org/10.1287/ijoc.1070.0258.
Rudy J. & Żelazny 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 – ICTM 2012, pp. 247–261. URL: https://ictm2012.edukacja.wroc.pl/ICTM2012_Proceedings.pdf [21.08.2026].
Talbi E.-G., Mostaghim S., Okabe T., Ishibuchi H., Rudolph G. & Coello Coello C.A. (2008). Parallel approaches for multiobjective optimization. In: Branke J., Deb K., Miettinen K. & Słowiński R. (Eds.), Multiobjective Optimization: Interactive and Evolutionary Approaches. Lecture Notes in Computer Science, 5252, pp. 349–372. Berlin–Heidelberg: Springer. DOI: http://doi.org/10.1007/978-3-540-88908-3_13.
Sun Y. & Shen G. (2008). Improved NSGA-II multi-objective genetic algorithm based on hybridization-encouraged mechanism. Chinese Journal of Aeronautics, 21(6), pp. 540–549. DOI: http://doi.org/10.1016/S1000-9361(08)60172-7.
