Combinatorial Optimisation Can be Different from Continuous Optimisation for MOEAs

This tutorial explores the differences between multi-objective combinatorial optimisation problems and continuous problems through the lens of evolutionary algorithms. It aims to guide researchers and practitioners in designing effective multi-objective evolutionary algorithms (MOEAs) for multi-objective combinatorial optimisation problems.

In the first part of the tutorial, we will show an interesting yet unwelcome behaviour of MOEAs in handling combinatorial optimisation problems. That is, when dealing with such problems, the search, in different executions of an 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 one another in the search space. This is not the case for MOEAs in dealing with continuous problems.

In the second part, we will extend this discussion by introducing multi-objective local search heuristics, and show that the behaviour of MOEAs can even be more “localised” than local search methods. Following this, we will delve into key questions:

• Are MOEAs less promising in tackling combinatorial optimisation problems?
• What went wrong with current MOEAs?
• How to improve them, and what distinguishes the design of MOEAs for multi-objective combinatorial problems versus continuous problems?

These insights aim to provide actionable strategies for enhancing MOEA performance in combinatorial settings.