Very Fast Non-Dominated Sorting

• Autorzy: Czesław Smutnicki , Jarosław Rudy , Dominik Żelazny
• 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. (original abstract)

Słowa kluczowe

EN

Algorithms; Pareto optimality; Multiple-criteria decision making

PL

Algorytmy; Optimum Pareto; Wielokryterialne podejmowanie decyzji

• Czasopismo: Decision Making in Manufacturing and Services
• Rocznik: 2014
• Tom: 8
• Numer: nr 1/2
• Strony: 13--23

Twórcy

autor

Czesław Smutnicki

• Wrocław University of Technology

autor

Jarosław Rudy

• Wrocław University of Technology

autor

Dominik Żelazny

• Wrocław University of Technology

Bibliografia

• 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.

Identyfikatory

DOI

10.7494/dmms.2014.8.1.13