Very Fast Non-Dominated Sorting

• Autorzy: Smutnicki C. , Rudy J. , Żelazny D.

Identyfikatory

DOI

10.7494/dmms.2014.8.1.13

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

parallel algorithms; Pareto sorting; computational complexity; GPU computing; multiple criteria decision analysis; NSGA-II

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Decision Making in Manufacturing and Services
• Rocznik: 2014
• Tom: Vol. 8, no. 1-2
• Strony: 13--23
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Smutnicki C.

• Wrocław University of Technology, Institute of Computer Engineering, Control and Robotics, Poland

autor

Rudy J.

• Wrocław University of Technology, Institute of Computer Engineering, Control and Robotics, Poland

autor

Żelazny D.

• Wrocław University of Technology, Institute of Computer Engineering, Control and Robotics, Poland

Bibliografia

• 1. 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.
• 2. Bożejko, 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.
• 3. Bożejko, W., Uchroński, 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.
• 4. 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.
• 5. 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.
• 6. 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.
• 7. Jozefowicz, 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.
• 8. 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.
• 9. Rudy, J. and Ż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, pp. 247-261.
• 10. 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.
• 11. 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