JUSTIFICATION OF THE FEASIBILITY OF USING HEURISTIC ALGORITHMS FOR SOLVING MULTI-OBJECTIVE OPTIMIZATION PROBLEMS VIA PARETO-FRONT SEARCH

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.