On Maintaining Diversity in MOEA/D: Application to a Biobjective Combinatorial FJSP

Abstract

MOEA/D is a generic decomposition-based multiobjective optimization framework which has been 
proved to be extremely effective in solving a broad range of optimization problems especially for 
continuous domains. In this paper, we consider applying MOEA/D to solve a bi-objective scheduling 
combinatorial problem in which task durations and due-dates are uncertain. Surprisingly, we find that 
the conventional MOEA/D implementation provides poor performance in our application setting. We 
show that this is because the replacement strategy underlying MOEA/D is suffering some shortcomes 
that lead to low population diversity, and thus to premature convergence. Consequently, we investigate 
existing variants of MOEA/D and we propose a novel and simple alternative replacement component at 
the aim of maintaining population diversity. Through extensive experiments, we then provide a comprehensive 
analysis on the relative performance and the behavior of the considered algorithms. Besides being able to 
outperform existing MOEA/D variants, as well as the standard NSGA-II algorithm, our investigations 
provide new insights into the search ability of MOEA/D and highlight new research opportunities for 
improving its design components.