|
DOI: 10.14489/vkit.2025.09.pp.003-013
Юртаев А. Г.
АНАЛИЗ МЕТОДОВ ПОИСКА ОБЪЕДИНЕННОГО ПАРЕТО-ФРОНТА ПРИ РЕШЕНИИ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ ГЕНЕТИЧЕСКИМИ АЛГОРИТМАМИ
(с. 3-13)
Аннотация. Проведен анализ алгоритмов поиска объединенного Парето‑фронта, образующегося в результате слияния локальных фронтов, найденных генетическими алгоритмами при решении задач многокритериальной оптимизации. Рассмотрены различные подходы, в том числе методы попарного сравнения, «разделяй и властвуй», sweep-line алгоритм, а также алгоритмы, основанные на поиске в KD‑деревьях. Особое внимание уделено принципам работы каждого метода, их асимптотическим оценкам в худшем и среднем случаях. Проведены синтетические тесты на наборах данных различной геометрии распределения и плотности недоминируемых решений. При этом размерность генотипов фиксировалась: каждое решение описывалось вектором из трех параметров. Для моделирования разнообразия распределений использовались априорные характеристики – геометрический баланс, коэффициент вариации, коэффициент асимметрии и нормированная энтропия. Выполнено 800 типов независимых экспериментов с различными комбинациями размеров популяции, доли точек в выходном фронте и десяти уровней значений каждой априорной метрики. В частности, рассматривались размеры популяции 200, 400, 800 и 1600, а доля точек в выходном фронте варьировалась в диапазоне 10…90 %. Каждое испытание запускалось несколько десятков раз, полученные значения усреднялись для обеспечения статистической достоверности. На основе теоретических и эмпирических результатов сформированы рекомендации по выбору оптимальных алгоритмических подходов, обеспечивающих наилучшее соотношение производительности и вычислительных затрат в зависимости от характеристик входных данных и требований к качеству решения.
Ключевые слова: генетические алгоритмы; многокритериальная оптимизация; Парето-фронт; попарное сравнение; KD-дерево; метод «разделяй и властвуй»; sweep-line; рекурсивные алгоритмы; асимптотическая сложность; геометрический баланс; коэффициент вариации; асимметрия распределения; нормированная энтропия.
Yurtaev A. G.
ANALYSIS OF METHODS FOR SEARCHING THE UNIFIED PARETO FRONT IN SOLVING MULTI-OBJECTIVE OPTIMIZATION PROBLEMS USING GENETIC ALGORITHMS
(pp. 3-13)
Abstract. The article presents a comparative analysis of algorithms for computing the unified Pareto front obtained by merging local fronts generated by genetic algorithms in multi-objective optimization problems. Various approaches are examined, including pairwise comparison methods, divide-and-conquer strategies, the sweep-line algorithm, and KD-tree–based search techniques. Special attention is paid to the theoretical analysis of each method’s operating principles and their asymptotic time complexities in worst-case and average-case scenarios. Subsequently, synthetic tests were performed on data sets varying in distribution geometry and the density of non-dominated solutions. In these experiments, the genotype dimensionality was fixed: each solution was represented by a three-parameter vector. To model distributional diversity, four a priori characteristics were employed: geometric balance, coefficient of variation, skewness, and normalized entropy. A total of 800 independent experiments were conducted with different combinations of population sizes, proportions of solutions in the resulting front, and ten levels for each a priori metric. Specifically, population sizes of 200, 400, 800, and 1600 were tested, with front proportions ranging from 10 % to 90 %. Each experiment was repeated several dozen times, and results were averaged to ensure statistical reliability. Based on the theoretical and empirical findings, recommendations are formulated for selecting the most appropriate algorithmic approaches that optimize the trade-off between computational performance and cost, depending on input-data characteristics and solution-quality requirements.
Keywords: genetic algorithms; multi-criteria optimization; Pareto front; pairwise comparison; KD‑tree; Metod “divide and conquer”; sweep-line; recursive algorithms; asymptotic complexity; geometric balance; coefficient of variation; distribution skewness; normalized entropy.
А. Г. Юртаев (Саратовский государственный технический университет имени Ю. А. Гагарина, Саратов, Россия) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
A. G. Yurtaev (Yuri Gagarin State Technical University of Saratov, Saratov, Russia) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Белецкая С. Ю. Методы оптимизации в автоматизированных системах: учеб. пособие. Воронеж: Воронежский государственный технический университет, 2017. 154 с.
2. Верещага А. Н. Методы оптимального проектирования и междисциплинарной оптимизации. Основы. Саров: РФЯЦ–ВНИИЭФ, 2023. 336 с.
3. Ногин В. Д. Множество и принцип Парето: учеб. пособие. 2-е изд., испр. и доп. СПб.: Издательско-полиграфическая ассоциация высших учебных заведений, 2022. 110 с.
4. Ватутин Э. И. Решение дискретных комбинаторных оптимизационных задач с использованием эвристических методов: методические указания по выполнению лабораторных и практических работ по дисциплине «Основы комбинаторной оптимизации». Курск: Юго-Западный государственный университет, 2016. 30 с.
5. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы; под ред. В. М. Курейчика. 2-е изд., испр. и доп. М.: ФИЗМАТЛИТ, 2010. 368 с.
6. Алексеев В. Б. Введение в теорию сложности алгоритмов (учебное пособие для студентов). М.: Издательский отдел факультета ВМиК МГУ, 2002. 82 с.
7. Абрамов С. А. Лекции о сложности алгоритмов. М.: МЦНМО, 2009. 256 с.
8. Börzsönyi S., Kossmann D., Stocker K. The Skyline Operator // Proceedings of the 17th International Conference on Data Engineering. Hiedelberg. 2–6 April 2001. P. 421–430.
9. Brassard G., Bratley P. Fundamental of Algorithmics. Prentice-Hall, 1996. 524 p.
10. Солтис М. Введение в анализ алгоритмов; пер. с англ. А. В. Логунова. М.: ДМК-Пресс, 2019. 278 с.
11. Ахо А. В., Хопкрофт Д.Э., Ульман Дж. Д. Структуры данных и алгоритмы; пер. с англ. М.: Вильямс, 2000. 384 с.
12. Быкова В. В. Математические методы анализа рекурсивных алгоритмов // Журнал Сибирского федерального университета. Сер.: Математика и физика. 2008. Т. 1, № 3. С. 236–246.
13. Samet H. Foundations of multidimensional and metric data structures. Morgan Kaufmann, 2006. 1024 p.
14. Гладких Д. А., Вихтенко Э. М. Применение алгоритмов пространственного разбиения в задачах вычислительной геометрии // Инженерный вестник Дона. 2024. № 1(109). С. 101–114.
15. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ; пер. с англ. 2-е изд. М.: Вильямс, 2011. 1296 с.
16. De Berg M., Cheong O., van Kreveld M., Overmars M. Computational Geometry: Algorithms and Applications. 3d ed. Berlin: Springer-Verlag Berlin Heidelberg, 2008. 386 p.
17. Грэм Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики; пер. с англ. М.: Мир, 1998. 703 с.
18. Preparata F. P., Shamos M. I. Computational geometry: an introduction. Berlin: Springer, 1985. 398 p.
19. Bentley J. L. Multidimensional binary search trees used for associative searching // Communications of the ACM. 1975. № 18(9). P. 509–517.
20. Ott R. L., Longnecker M. T. Introduction to Statistical Methods and Data Analysis. Cengage Learning, 2015. 1296 p.
21. Johnson R. A., Wichern D. W. Applied Multivariate Statistical Analysis. 6th ed. Pearson, Prentice Hall, 2007. 773 p.
22. Cover T. M., Thomas J. A. Elements of information theory. 2d ed. Hoboken, New Jersey: A John Wiley & Sons Inc., 2006. 542 p.
1. Beletskaya, S. Yu. (2017). Optimization methods in automated systems: Textbook. Voronezh State Technical University. [in Russian language]
2. Vereshchaga, A. N. (2023). Optimal design methods and multidisciplinary optimization. Fundamentals. RFNC-VNIIEF. [in Russian language]
3. Nogin, V. D. (2022). Set and Pareto principle: Textbook (2nd ed.). Publishing and Printing Association of Higher Educational Institutions. [in Russian language]
4. Vatutin, E. I. (2016). Solving discrete combinatorial optimization problems using heuristic methods: Methodological instructions for laboratory and practical work in the discipline "Fundamentals of combinatorial optimization". Southwest State University. [in Russian language]
5. Gladkov, L. A., Kureichik, V. V., & Kureichik, V. M. (2010). Genetic algorithms (V. M. Kureichik, Ed.; 2nd ed.). FIZMATLIT. [in Russian language]
6. Alekseev, V. B. (2002). Introduction to the theory of algorithm complexity (Textbook for students). Publishing Department of the Faculty of Computational Mathematics and Cybernetics, Moscow State University. [in Russian language]
7. Abramov, S. A. (2009). Lectures on algorithm complexity. MTSNMO. [in Russian language]
8. Börzsönyi, S., Kossmann, D., & Stocker, K. (2001). The Skyline Operator. Proceedings of the 17th International Conference on Data Engineering, 421–430.
9. Brassard, G., & Bratley, P. (1996). Fundamental of algorithmics. Prentice-Hall.
10. Soltis, M. (2019). Introduction to algorithm analysis (A. V. Logunov, Trans.). DMK Press. [in Russian language]
11. Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (2000). Data structures and algorithms (Trans. from English). Williams. [in Russian language]
12. Bykova, V. V. (2008). Mathematical methods for analyzing recursive algorithms. Zhurnal Sibirskogo Federalnogo Universiteta. Seriya: Matematika i Fizika, 1(3), 236–246. [in Russian language]
13. Samet, H. (2006). Foundations of multidimensional and metric data structures. Morgan Kaufmann.
14. Gladkikh, D. A., & Vikhrenko, E. M. (2024). Application of spatial partitioning algorithms in computational geometry problems. Inzhenernyy Vestnik Dona, (1), 101–114. [in Russian language]
15. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2011). Algorithms: Construction and analysis (Trans. from English; 2nd ed.). Williams. [in Russian language]
16. De Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. (2008). Computational geometry: Algorithms and applications (3rd ed.). Springer-Verlag.
17. Graham, R., Knuth, D., & Patashnik, O. (1998). Concrete mathematics. Foundation of computer science (Trans. from English). Mir. [in Russian language]
18. Preparata, F. P., & Shamos, M. I. (1985). Computational geometry: An introduction. Springer.
19. Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509–517.
20. Ott, R. L., & Longnecker, M. T. (2015). Introduction to statistical methods and data analysis. Cengage Learning.
21. Johnson, R. A., & Wichern, D. W. (2007). Applied multivariate statistical analysis (6th ed.). Pearson Prentice Hall.
22. Cover, T. M., & Thomas, J. A. (2006). Elements of information theory (2nd ed.). John Wiley & Sons.
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 700 руб. (в том числе НДС 20%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2025.09.pp.003-013
и заполните форму
Отправляя форму вы даете согласие на обработку персональных данных.
.
This article is available in electronic format (PDF).
The cost of a single article is 700 rubles. (including VAT 20%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please copy the article doi:
10.14489/vkit.2025.09.pp.003-013
and fill out the form
.
|
Current Issue
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»