On bi-objective combinatorial optimization with heterogeneous objectives

The heterogeneity among objectives in multi-objective optimization can be viewed from several perspectives. In this paper, we are interested in the heterogeneity arising in the underlying landscape of the objective functions, in terms of multi-modality and search difficulty. Building on recent efforts leveraging the so-called single-objective NK-landscapes to model such a setting, we conduct a three-fold empirical analysis on the impact of objective heterogeneity on the landscape properties and search difficulty of bi-objective optimization problems. Firstly, for small problems, we propose two techniques based on studying the distribution of the solutions in the objective space. Secondly, for large problems, we investigate the ability of existing landscape features to capture the degree of heterogeneity among the two objectives. Thirdly, we study the behavior of two state-of-the-art multi-objective evolutionary algorithms, namely MOEA/D and NSGA-II, when faced with a range of problems with different degrees of heterogeneity. Although one algorithm is found to consistently outperform the other, the dynamics of both algorithms vary similarly with respect to objective heterogeneity. Our analysis suggests that novel approaches are needed to understand the fundamental properties of heterogeneous bi-objective optimization problems and to tackle them more effectively.