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
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
How to Cite
Issue
Section
License
Remeber to prepeare, sign and scan copyright statement
The content of the journal is freely available according to the Creative Commons License Attribution 4.0 International (CC BY 4.0)
