Combinatorial Optimisation Can be Different from Continuous Optimisation for MOEAs
Description
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.
Organizers
Dr. Miqing Li is an Associate Professor at the University of Birmingham, UK. His research centres on multi-objective optimisation, where he designs population-based randomised algorithms, primarily evolutionary algorithms, to address both basic and applied problems.
In his basic research, Miqing tackles general challenging problems (such as those involving many objectives, expensive evaluations, or combinatorial structures), and investigates fundamental issues in multi-objective optimisation (archiving and performance assessment). Some of the algorithms he developed (e.g., GrEA and SDE) are among the most widely used ones in the area. On the applied side, he collaborates with experts in diverse domains, including software engineering, high-performance computing, neural architecture search, and chemical engineering, to develop effective methods for real-world problems. Many of these collaborations have resulted in publications in high-profile journals, with some papers (e.g., TPDS’2016 and TSE’2022) being among the most cited ones since their publication.
Miqing’s work has received the Best (Student) Paper Awards/Nominations at major conferences in evolutionary computation (GECCO, CEC, EMO, and SEAL). He was the founding chair of the IEEE CIS Task Force on Many-Objective Optimisation and serves as an Associate Editor for IEEE Transactions on Evolutionary Computation. Additionally, he has delivered tutorials at major conferences in evolutionary computation and software engineering, including GECCO, CEC, ICSE, and FSE.