Dimensionality Reduction in Multiobjective Optimization: The Minimum Objective Subset Problem

Abstract. Most of the available multiobjective evolutionary algorithms (MOEA) for approximating the Pareto set have been designed for and tested on low dimen-sional problems ( ≤ 3 objectives). However, it is known that problems with a high number of objectives cause additional difficulties in terms of the quality of the Pareto set approximation and running time. Furthermore, the decision making process becomes the harder the more objectives are involved. In this context, the question arises whether all objectives are necessary to preserve the problem char-acteristics. One may also ask under which conditions such an objective reduction is feasible, and how a minimum set of objectives can be computed. In this pa-per, we propose a general mathematical framework, suited to answer these three questions and corresponding algorithms, exact and heuristic ones. The heuristic variants are geared towards direct integration into the evolutionary search pro-cess. Moreover, extensive experiments for four well-known test problems show that substantial dimensionality reductions are possible on the basis of the pro-posed methodology.