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, I 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 when dealing with continuous problems.
In the second part, I 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, I will delve into key questions:
• Are MOEAs less hopeful for 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 (https://sites.google.com/view/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 fundamental and applied problems.
In his foundational research, Dr. Li tackles general challenging problems (e.g. problems with many objectives, complex constraints, expensive to evaluate, or combinatorial object). Some of his algorithms (e.g., GrEA and SDE) are among the most widely used ones in the area. On the applied front, he collaborates with experts in diverse areas, including software engineering, high-performance computing, neural architecture search, mechanical engineering, and chemical engineering, developing innovative methods to address real-world problems. Many of these projects have appeared in high-profile journals, with some being among the most cited ones since their publication (e.g., TPDS’2016 and TOSEM’2016).
Dr. Li’s work has received Best Paper Awards/Nominations at major conferences in evolutionary computation (GECCO, CEC, and SEAL). He was the founding chair of the IEEE CIS Task Force on Many-Objective Optimisation and currently 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 CEC, ICSE, and FSE.