Computational Complexity Measures for Many-objective Optimization Problems

Multi-objectiveOptimization Problems (MOPs) are commonly encountered in the study and design of complex systems. Pareto dominance is the most common relationship used to compare solutions in MOPs, however as the number of objectives grows beyond three, Pareto dominance alone is no longer satisfactory. These problems are termed “Many-Objective Optimization Problems (MaOPs)”. While most MaOP algorithms are modifications of common MOP algorithms, determining the impact on their computational complexity is difficult. This paper defines computational complexity measures for these algorithms and applies these measures to a Multi-Objective Evolutionary Algorithm (MOEA) and its MaOP counterpart.