The Impact of Problem Features on NSGA-II and MOEA/D Performance

Abstract

The multi-objective evolutionary algorithms NSGA-II and MOEA/D are often compared using test problems which combine a number of factors to create a difficult problem. Instead, we study the effect of a variety of factors directly by using problems in which the presence of these factors can be specified, with the purpose of studying the effect of each factor individually. The factors we study are the shape of the objective space and the uniformity of the distribution of solutions therein, the number of objectives and the correlation between them,and the separability of variables. We do some additional experiments to better understand some of our results, especially the phenomena we see when we vary the correlation between objectives at a high number of objectives. Lastly, we investigate the possibility of predicting algorithm performance based on attributes which were measured rather than specified. NSGA-II is non-domination-based while MOEA/D is decomposition-based,which together with the fact that they are both frequently used makes for an especially interesting comparison that may contribute to a further understanding of the differences between their designs, as well as to the ability to choose the best algorithm for any given problem.