MOEAs Are Stuck in a Different Area at a Time

In this paper, we show that when dealing with multi-objective combinatorial optimisation problems, the search, in different executions of a multi-objective evolutionary algorithm (MOEA), e.g., NSGA-II, tends to stagnate in different areas in the search space. In other words, the final populations obtained by an MOEA under multiple executions, which can be very close in the objective space, are located far away from each other in the search space. This phenomenon becomes more apparent with the increase of some type of problem complexity (e.g., the ruggedness level of problem landscape). Interestingly, the phenomenon only happens to combinatorial optimisation problems, but not to continuous ones. In this study, we consider three well-established MOEAs (NSGA-II, SMS-EMOA and MOEA/D) on two representative combinatorial optimisation problems (NK-landscape and TSP) and on two commonly used continuous problem suites (DTLZ and WFG). Experimental results show a clear difference between multi-objective combinatorial and continuous problems and suggest a need of more efforts to be put on developing effective MOEAs for combinatorial problems.