10.14489/vkit.2026.01.pp.003-011

DOI: 10.14489/vkit.2026.01.pp.003-011

Юртаев А. Г.
ОБОСНОВАНИЕ ЦЕЛЕСООБРАЗНОСТИ ПРИМЕНЕНИЯ ЭВРИСТИЧЕСКИХ АЛГОРИТМОВ ПРИ РЕШЕНИИ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ МЕТОДОМ ПОИСКА ПАРЕТО-ФРОНТА
(с. 3-11)

Аннотация. Обоснована необходимость применения генетических алгоритмов при решении задач многокритериальной оптимизации методом поиска Парето-фронта. Теоретически доказано, что решающая версия задачи полного построения Парето-фронта (DEC-PF) принадлежит классу NP и к ней полиномиально сводится классическая NP-полная задача Subset Sum, что делает ее NP-полной, а задачу полного перечисления Парето-фронта – NP-трудной. На практике это означает недопустимо высокую стоимость прямого перебора параметров даже при умеренных размерах дискретного пространства решений. Описана структура используемого многоцелевого генетического алгоритма NSGA-II. Приведена строгая математическая постановка дискретной трехкритериальной задачи многокритериальной оптимизации и вычислительных задач полного и приближенного построения Парето-фронта. Проведены эксперименты на трехкритериальных наборах объемом 106 и 2  106 точек: полный перебор формирует фронт из 1495 и 1799 точек за 734 с и 2339 с соответственно, тогда как генетический алгоритм аппроксимирует фронт за 4,0…4,4 с, обеспечивая покрытие по метрике гиперобъема на уровне 91…93 %. Полученные результаты демонстрируют экспоненциальный рост затрат при полном построении фронта и практически константную эффективность генетических алгоритмов, что подтверждает практическую целесообразность эвристических методов для задач многокритериальной оптимизации методом поиска Парето-фронта.

Ключевые слова: генетические алгоритмы; многокритериальная оптимизация; Парето-фронт; асимптотическая сложность; NP-полнота; NP-трудность; гиперобъем.

Yurtaev A. G.
JUSTIFICATION OF THE FEASIBILITY OF USING HEURISTIC ALGORITHMS FOR SOLVING MULTI-OBJECTIVE OPTIMIZATION PROBLEMS VIA PARETO-FRONT SEARCH
(pp. 3-11)

Abstract. The article justifies the need to employ genetic algorithms for solving discrete multi-objective optimization problems via Pareto-front search. From a theoretical standpoint, the decision version of the full Pareto-front construction problem (Decision Pareto Front, DEC-PF) is formulated as follows, and it is proved that DEC-PF belongs to NP – since verifying any candidate solution reduces to computing two linear combinations and performing two comparisons in polynomial time – and that the classical NP-complete Subset Sum problem admits a polynomial-time reduction to DEC-PF, establishing both the NP-completeness of the decision version and the NP-hardness of the full enumeration of all Pareto-optimal points. The structure of the applied multi-objective genetic algorithm NSGA-II is also described. A formal mathematical formulation of the discrete three-objective optimization problem and the computational tasks of exact and approximate Pareto-front construction is provided. The practical infeasibility of deterministic exhaustive search is illustrated on three-objective test sets of size 106 and 2  106 points. In the first case, exhaustive enumeration identifies 1495 Pareto-optimal solutions in 734 s; in the second, 1799 points in 2339 s. By contrast, the classical NSGA-II genetic algorithm approximates the Pareto front in just 4,0…4,4 s, achieving a hypervolume coverage of 91…93 %. These empirical results demonstrate the exponential growth in computational cost of full enumeration as the solution space expands, versus the near-constant complexity of genetic algorithms while preserving high approximation quality. Thus, the combination of a rigorous theoretical proof of DEC-PF’s NP-hardness and compelling experimental evidence confirms the practical expediency and effectiveness of genetic algorithms for multi-objective optimization via Pareto-front search. This approach constitutes a versatile tool for a broad class of real-world applications that require balancing conflicting objectives under limited computational resources.

Keywords: Genetic algorithms; Multi-criteria optimization; Pareto front; Asymptotic complexity; NP-completeness; NP-hardness; Hypervolume.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

А. Г. Юртаев (Саратовский государственный технический университет имени Гагарина Ю. А., Саратов, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

A. G. Yurtaev (Yuri Gagarin State Technical University of Saratov, Saratov, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Зак Ю. А. Множество Парето для критериев эффективности, представленных стохастическими и нечеткими данными // Искусственный интеллект и принятие решений. 2014. № 2. С. 89–101.
2. Ногин В. Д. Множество и принцип Парето: учеб. пособие. СПб.: Издательско-полиграфическая ассоциация высших учебных заведений, 2022. 110 с.
3. Брестер К. Ю., Становов В. В., Семенкина О. Э., Семенкин Е. С. О применении эволюционных алгоритмов при анализе больших данных // Искусственный интеллект и принятие решений. 2017. № 3. С. 82–93.
4. Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman and Company, 1979. 340 p.
5. Ehrgott M. Multicriteria Optimization. Springer-Verlag, Berlin–Heidelberg, 2000. 243 p.
6. Zitzler E., Deb K., Thiele L. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results // Evolutionary Computation. 2000. № 8(2). P. 173–195.
7. Ватутин Э. И. Решение дискретных комбинаторных оптимизационных задач с использованием эвристических методов: методические указания по выполнению лабораторных и практических работ по дисциплине «Основы комбинаторной оптимизации». Курск: Юго-Западный государственный университет, 2016. 30 с.
8. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. 2-е изд., исправл. и доп. / под ред. В. М. Курейчика. М.: ФИЗМАТЛИТ, 2010. 368 с.
9. Вирсански Э. Генетические алгоритмы на Python / пер. с англ. А. А. Слинкина. М.: Изд-во ДМК Пресс, 2020. 286 с.
10. Абрамов С. А. Лекции о сложности алгоритмов. М.: МЦНМО, 2009. 256 с.
11. Papadimitriou C. H., Yannakakis M. On the approximability of trade-offs and optimal access of Web sources // Proc. 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2000). 12–14 November 2000. Los Alamitos, California, USA. IEEE Computer Society, 2000. P. 86–92.
12. Deb K., Pratap A., Agarwal S., Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II // IEEE Transactions on Evolutionary Computation. 2002. № 6(2). P. 182–197.

Eng

1. Zak, Yu. A. (2014). Pareto set for efficiency criteria represented by stochastic and fuzzy data. Iskusstvennyi Intellekt i Prinyatie Reshenii, (2), 89–101. [in Russian language]
2. Nogin, V. D. (2022). Pareto set and principle [in Russian language]. Izdatel'sko-poligraficheskaya assotsiatsiya vysshikh uchebnykh zavedenii.
3. Brester, K. Yu., Stanovov, V. V., Semenkina, O. E., & Semenkin, E. S. (2017). On the application of evolutionary algorithms in big data analysis. Iskusstvennyi Intellekt i Prinyatie Reshenii, (3), 82–93. [in Russian language]
4. Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman and Company.
5. Ehrgott, M. (2000). Multicriteria optimization. Springer-Verlag.
6. Zitzler, E., Deb, K., & Thiele, L. (2000). Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation, 8(2), 173–195. https://doi.org/10.1162/106365600568202
7. Vatutin, E. I. (2016). Solving discrete combinatorial optimization problems using heuristic methods: Methodological guidelines for laboratory and practical work in the discipline "Fundamentals of combinatorial optimization". Yugo-Zapadnyi gosudarstvennyi universitet. [in Russian language].
8. Gladkov, L. A., Kureichik, V. V., & Kureichik, V. M. (2010). Genetic algorithms (2nd ed.) FIZMATLIT. [in Russian language].
9. Wirsansky, E. (2020). Genetic algorithms in Python (A. A. Slinkin, Trans.). DMK Press. (Original work published 2020)
10. Abramov, S. A. (2009). Lectures on algorithm complexity. MTsNMO. [in Russian language].
11. Papadimitriou, C. H., & Yannakakis, M. (2000). On the approximability of trade-offs and optimal access of Web sources. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2000) (pp. 86–92). IEEE Computer Society.
12. Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197. https://doi.org/10.1109/4235.996017

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 700 руб. (в том числе НДС 20%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2026.01.pp.003-011

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

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.2026.01.pp.003-011

and fill out the form