DOI: 10.17587/prin.16.462-469

Dominance Ranking Algorithms for Solving Multi-Objective Optimization Problems Using Genetic Algorithms

A. G. Yurtaev, Postgraduate Student, agyurtaev@mail.ru, Yuri Gagarin State Technical University of Saratov, Saratov, 410054, Russian Federation

Corresponding author: Alexander G. Yurtaev, Postgraduate Student, Yuri Gagarin State Technical University of Saratov, Saratov, 410054, Russian Federation, E-mail: agyurtaev@mail.ru

The article provides a comprehensive theoretical and experimental analysis of the principal dominance-based ranking algorithms used in multi-criteria optimization with genetic algorithms. Four fundamentally different approaches are examined: the classic pairwise comparison method; KD-trees built after an initial sort by a single criterion; a variant of the KD-tree approach that employs a linear-time median-finding algorithm; and the recursive "divide-and-conquer" method. For each algorithm, asymptotic estimates of time complexity and memory usage are derived and justified, and their dependence on the population size is demonstrated. In the methodology section, the author's system for generating synthetic test samples is described. It relies on predetermined a priori metrics: geometric balance (the ratio of points below to above the median along each axis), coefficient of variation, skewness coefficient, and normalized entropy of the point distribution in D-dimensional space. This framework makes it possible to model a broad spectrum of scenarios — from uniformly distributed samples to highly clustered or extremely sparse ones — thus ensuring reproducibility and objectivity in the empirical evaluation of algorithmic performance. The experimental phase comprises a series of trials on populations of fixed size (N = 200) over 54 combinations of target metric values (625 distinct test sets in total). Each test was repeated multiple times for statistical robustness, and the results were averaged. All timing measurements were conducted in a Python environment on a single personal computer. According to the results, the KD-tree algorithm with initial sorting achieved the best average performance (minimum runtime -0.0017 s, maximum -0.026 s), although its efficiency is highly sensitive to the input data's balance. The median-finding variant proved less dependent on distribution characteristics but, on average, lags behind the sorting-based implementa­tion in speed. The divide-and-conquer method yielded more consistent runtimes (-0.0123—0.0133 s), outperforming the naive pairwise comparison algorithm (-0.033—0.034 s) under all tested conditions; however, in worst-case scenarios it can exhibit quadratic behavior, restricting its applicability to large populations. The novelty of this research lies in the development of an experimental methodology for comparing four fast dominance-based ranking approaches in multi-objective optimization and in the creation of a test-generation procedure based on statis­tical distribution metrics. The findings enable a well-justified selection of the most appropriate ranking algorithm according to specific runtime requirements and input-data characteristics, and they establish a foundation for further development of adaptive hybrid methods. Future work will extend the analysis to real-world multidimensional datasets and explore parallel and hardware-accelerated implementations of the examined algorithms.

Keywords: genetic algorithms, multi-criteria optimization, domination-based ranking, Pareto front, pairwise comparison, KD-tree, divide and conquer, recursive algorithms, asymptotic complexity, geometric balance, coefficient of variation, coefficient of asymmetry, normalized entropy

pp. 462—469

For citation:
Yurtaev A. G. Dominance Ranking Algorithms for Solving Multi-Objective Optimization Problems Using Genetic Algorithms, Programmnaya Ingeneria, 2025, vol. 16, no. 9, pp. 462—469. DOI: 10.17587/prin.462-469. (in Russian).

References:

1. Nogin V. D. The Pareto Set and Principle: Textbook. 2nd edition, revised and expanded, St. Petersburg, Izdatel'sko poligraficheskaya Assotsiatsiya Vysshikh Uchebnykh Zavedeniy, 2022, 110 p. (in Russian).
2. Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979, 340 p.
3. Gladkov L. A., Kureychik V. V., Kureychik V. M. Genetic Algorithms / Edited by V. M. Kureychik. 2nd ed., revised and expanded. Moscow, FIZMATLIT, 2010, 368 p. (in Russian).
4. Wirsansky E. Genetic Algorithms in Python / translated from Eng­lish by A. A. Slinkina. Moscow, DMK Press, 2020, 286 p. (in Russian).
5. Garagulova A. K., Gorbacheva D. O., Chirkov D. V. Comparison of the Genetic Algorithms MOGA and NSGA-II for the Optimization of the Form of a Hydro Turbine Runner, Vychislitel'nye Tekhnologii, 2018, vol. 23, no. 5, pp. 21—36. DOI: 10.25743/ICT.2018.23.5.003 (in Russian).
6. Kuvayskova Yu. E., Nemykin A. A. Application of Evolutionary and Genetic Algorithms in the Formation of Neural Network Model Architectures for Predicting the Condition of a Technical Object, Izvestiya Samarskogo nauchnogo tsentra Rossiiskoi akademii nauk, 2024, vol. 26, no. 4—3 (120), pp. 383—394 (in Russian).
7. Mahbub Md. Sh., Ahmed Sh. Sh., Ali K. I., Imam Md. T. A Multi-Objective Optimization Approach for Solving AUSTClass-timetable Problem Considering Hard and Soft Constraints, International Journal of Mathematical Sciences and Computing, 2020, vol. 6, no. 5, pp. 1—14. DOI: 10.5815/ijmsc.2020.05.01.
8. Sosedov V. A. Combined hierarchical crossover in a genetic algorithm for last-mile delivery: efficiency analysis, Control Sciences, 2024, no. 1, pp. 18—27. DOI: 10.25728/cs.2024.1.3.
9. Zakharov A. O., Kovalenko Yu. V. Construction and reduction of the Pareto set in asymmetric travelling salesman problem with two criteria, Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 2018, vol. 14, no. 4, pp. 378—392.
10. Chaudhary N., Sangwan O. P. Multi Objective Test Suite Reduction for GUI Based Software Using NSGA-II, International Journal of Information Technology and Computer Science, 2016, vol. 8, no. 8, pp. 59—65. DOI: 10.5815/ijitcs.2016.08.07.
11. Saeidi Sh. A Multi-objective Mathematical Model for Job Scheduling on Parallel Machines Using NSGA-II, International Journal of Information Technology and Computer Science, 2016, vol. 8, no. 8, pp. 43—49. DOI: 10.5815/ijitcs.2016.08.05.
12. Deb K., Pratap A., Agarwal S., Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 2002, vol. 6, no. 2, pp. 182—197.
13. Alekseev V. B. Introduction to the Theory of Algorithm Complexity (Textbook for Students). Moscow, Izdatel'skiy otdel f-ta VMiKMGU, 2002, 82 p. (in Russian).
14. Abramov S. A. Lectures on Algorithm Complexity, Moscow, MTSNMO, 2009, 256 p. (in Russian).
15. Samet H. Foundations of multidimensional and metric data structures, Morgan Kaufmann, 2006, 1024 p.
16. Gladkikh D. A., Vikhtenko E. M. Application of Spatial Partitioning Algorithms in Computational Geometry, Inzhenernyy Vestnik Dona.2024, 2024, no. 1 (109), pp. 101—114 (in Russian).
17. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Algorithms: Construction and Analysis, 2nd ed. Translated from English, Moscow, Vilyams, 2011, 1296 p. (in Russian).
18. de Berg M., Cheong O., van Kreveld M., Overmars M. Computational Geometry: Algorithms and Applications, Springer, 2008, 386 p.
19. Soltys M. Introduction to Algorithm Analysis / translated from English by A. V. Logunova, Moscow, DMK Press, 2019, 278 p. (in Russian).
20. Aho A. V., Hopkroft J. E., Ullman J. D. Data Structures and Algorithms. Translated from English, Moscow, Vilyams, 2000, 384 p. (in Russian).
21. Brassard G., Bratley P. Fundamental of Algorithmics, Prentice-Hall, 1996, 524 p.
22. Bentley J. L. Multidimensional binary search trees used for associative searching, Communications of the ACM, 1975, vol. 18, no. 9, pp. 509—517. DOI: 10.1145/361002.361007.
23. Ott R. L., Longnecker M. An introduction to statistical methods and data analysis.Cengage Learning, 2015, 1296 р.
24. Johnson R. A., Wichern D. W. Applied Multivariate Statistical Analysis, Pearson, 2007, 808 p.
25. Cover T. M., Thomas J. A. Elements of information theory, Wiley, 2006, 542 p.