[PhD Vacancy] I am looking for PhD/MSc/Honours/Summer Research students in Evolutionary Computation and Machine Learning for Scheduling and Combinatorial Optimisation. If you have similar research interests with me, please do not hesitate to contact me.
Biography
Yi Mei is a Senior Lecturer at the School of Engineering and Computer Science, Victoria University of Wellington, Wellington, New Zealand. He is leading the Evolutionary Computation for Combinatorial Optimisation (ECCO) Research Group. He holds a PhD in Computer Science (2010) and a BSc in Mathematics (2005, in the Special Class for the Gifted Young [Wikipedia], a special undergraduate program selecting top 50 high-school students no older than age 15 nationwide) from University of Science and Technology of China (USTC). Before his current appointment, he worked as a Provost’s Research Associate (2010-2012, Financial Optimisation) at Chinese University of Hong Kong, and ARC Discovery Research Fellow (2012-2015, Large Scale Optimisation) at RMIT University, Australia.
Design effective divide-and-conquer algorithms to solve large scale global optimisation.
Grants & Awards
Grants
2017-2020, “Automatic Design of Heuristics for Dynamic Arc Routing Problem with Genetic Programming”, 16-VUW-079, Marsden Fund Fast-Start Grant, $300,000 NZD. (Sole PI)
2017-2020, “Cooperative Co-evolution for Large Scale Black Box Optimisation”, 61673194, National Natural Science Foundation of China, ¥610,000 RMB (Overseas AI)
2018, “Real-Time Tourist Trip Recommendation using Genetic Programming”, University Research Fund, Victoria University of Wellington, $28,720 NZD (Sole PI)
2016-2018, “Digital Data in Schools: An Exploration of Research and Practice”, Victoria University of Wellington Digital Future Grant, $20,000 NZD (Co-PI)
2017, “Evolving Interpretable Flexible Job Shop Scheduling Rules with GP”, Research Establishment Grant, Victoria University of Wellington, $10,000 NZD (Sole PI)
2014, RMIT Near-miss grant ($25,000 AUD awarded for being ranked top 10% of the unsuccessful applications for the 2014 ARC DECRA funding)
2018, Victoria University of Wellington Early Research Excellence Award
2018, Australasian Joint Conference on Artificial Intelligence Best Paper Runner-Up Award (paper)
2018, International Conference on Web Services (ARC/CORE Rank A) Best Paper Runner-Up (paper)
2017, IEEE Transactions on Evolutionary Computation (top journal in EC, IF = 10.629) Outstanding
Paper Award (paper)
2016, European Conference on Evolutionary Computation in Combinatorial Optimization Best Paper Nomination (paper)
2014, 2nd Prize, Competition at IEEE World Congress on Computational Intelligence: Optimisation
of Problems with Multiple Interdependent Components (as sole algorithm designer and programmer)
2010, Chinese Academy Of Sciences Dean’s Award (Top 200 postgraduates all over China)
Identification of variable interaction is essential for an efficient implementation of a divide-and-conquer algorithm for large-scale black-box optimization. In this paper, we propose an improved variant of the differential grouping algorithm, which has a better efficiency and grouping accuracy. The proposed algorithm, DG2, finds a reliable threshold value by estimating the magnitude of roundoff errors. With respect to efficiency, DG2 reuses the sample points that are generated for detecting interactions and saves up to half of the computational resources on fully separable functions. We mathematically show that the new sampling technique achieves the lower bound with respect to the number of function evaluations. Unlike its predecessor, DG2 checks all possible pairs of variables for interactions and has the capacity to identify overlapping components of an objective function. On the accuracy aspect, DG2 outperforms the state-of-the-art decomposition methods on the latest large-scale continuous optimization benchmark suites. DG2 also performs reliably in the presence of imbalance among contribution of components in an objective function. Another major advantage of DG2 is the automatic calculation of its threshold parameter (ǫ), which makes it parameter-free. Finally, the experimental results show that when DG2 is used within a cooperative co-evolutionary framework, it can generate competitive results as compared to several state-of-the-art algorithms.
Genetic programming has been a powerful technique for automated design of production scheduling heuristics. Many studies have shown that heuristics evolved by genetic programming can outperform many existing heuristics manually designed in the literature. The flexibility of genetic programming also allows it to discover very sophisticated heuristics to deal with complex and dynamic production environments. However, as compared to other applications of genetic programming or scheduling applications of other evolutionary computation techniques, the configurations and requirements of genetic programming for production scheduling are more complicated. In this paper, a unified framework for automated design of production scheduling heuristics with genetic programming is developed. The goal of the framework is to provide the researchers with the overall picture of how genetic programming can be applied for this task and the key components. The framework is also used to facilitate our discussions and analyses of existing studies in the field. Finally, this paper shows how knowledge from machine learning and operations research can be employed and how the current challenges can be addressed.
This paper proposes a competitive divide-and-conquer algorithm for unconstrained large scale black-box optimization, which has an unavailable algebraic model for the problem and thousands of decision variables. Assuming that the overall problem is composed of a number of smaller independent sub-problems, the proposed algorithm addresses two important issues in solving large scale black-box optimization: (1) identifying the independent sub-problems and (2) solving the identified black-box sub-problems. First, a Global Differential Grouping (GDG) method is proposed based upon the differential grouping method to find near optimal decomposition of the decision variables and the corresponding sub-problems. Then, a variant of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is adopted to solve the nonseparable sub-problems due to its rotation invariance property. GDG and CMA-ES work together under the cooperative co-evolution framework. The resultant algorithm named CC-GDG-CMAES is then evaluated on the CEC’2010 large scale global optimization (LSGO) benchmark functions, which have a thousand decision variables and black-box objective functions. The experimental results show that on most test functions, GDG manages to obtain an ideal decomposition of the variables, and CC-GDG-CMAES outperformed the state-of-the-art results. Besides, the competitive performance of the well-known CMA-ES is extended from low-dimensional to high-dimensional black-box problems.
Cooperative co-evolution has been introduced into evolutionary algorithms with the aim of solving increasingly complex optimization problems through a divide-and-conquer paradigm. In theory, the idea of co-adapted subcomponents is desirable for solving large-scale optimization problems. However in practice, without prior knowledge about the problem, it is not clear how the problem should be decomposed. In this paper we propose an automatic decomposition strategy called differential grouping that can uncover the underlying interaction structure of the decision variables and form subcomponents such that the interdependence between them is kept to a minimum. We show mathematically how such a decomposition strategy can be derived from a definition of partial separability. The empirical studies show that such near-optimal decomposition can greatly improve the solution quality on large-scale global optimization problems. Finally, we show how such an automated decompo- sition allows for a better approximation of the contribution of various subcomponents, leading to a more efficient assignment of the computational budget to various subcomponents.
In this paper, a divide-and-conquer approach is proposed to solve the Large-Scale Capacitated Arc Routing Problem (LSCARP) more effectively. Instead of considering the problem as a whole, the proposed approach adopts the Cooperative Co- evolution (CC) framework to decompose it into smaller ones and solve them separately. An effective decomposition scheme called the Route Distance Grouping (RDG) is developed to decompose the problem. Its merit is twofold: Firstly, it employs the route information of the best-so-far solution, so that the quality of the decomposition is upper bounded by that of the best-so-far solution. Thus, it can keep improving the decomposition by updating the best-so-far solution during the search. Secondly, it defines a distance between routes, based on which the potentially better decompositions can be identified. Therefore, RDG is able to obtain promising decompositions and focus the search on the promising regions of the vast solution space. Experimental studies verified the efficacy of RDG on the instances with a large number of tasks and tight capacity constraints, where it managed to obtain significantly better results than its counterpart without decomposition in a much shorter time. Furthermore, the best- known solutions of the EGL-G LSCARP instances were much improved.
The capacitated arc routing problem (CARP) is a challenging combinatorial optimization problem with many real-world applications, e.g., salting route optimization and fleet management. There have been many attempts at solving CARP using heuristic and meta-heuristic approaches, including evolutionary algorithms. However, almost all such attempts formulate CARP as a single-objective problem although it usually has more than one objective, especially considering its real-world applications. This paper studies multiobjective CARP (MO-CARP). A new memetic algorithm (MA) called decomposition-based MA with extended neighborhood search (D-MAENS) is proposed. The new algorithm combines the advanced features from both the MAENS approach for single-objective CARP and multiobjective evolutionary optimization. Our experimental studies have shown that such combination outperforms significantly an off-the-shelf multiobjective evolutionary algorithm, namely nondominated sorting genetic algorithm II, and the state-of-the-art multiobjective algorithm for MO-CARP (LMOGA). Our work has also shown that a specifically designed multiobjective algorithm by combining its single-objective version and multiobjective features may lead to competitive multiobjective algorithms for multiobjective combinatorial optimization problems.
I am a supervisor of 14 PhD students and 4 Master students, as well as a number of honours and summer research students (full list).
Professional Services
Editorship
Editorial Board Member of International Journal of Bio-Inspired Computation
Associate Editor of International Journal of Applied Evolutionary Computation
Guest Editor of Special Issue on Automated Design and Adaptation of Heuristics for Scheduling and Combinatorial Optimisation, Genetic Programming and Evolvable Machines, 2016
Conference Organisation
Proceedings Chair, IEEE Congress on Evolutionary Computation (CEC) 2019
Tutorial Co-chair, Pacific Rim International Conferences on Artificial Intelligence (PRICAI) 2019
Sponsorship Chair, Australasian Joint Conference on Artificial Intelligence 2018
Technical Co-chair, International Conference on Data Intelligence and Security (ICDIS) 2018
Organisational Committee Member, International Conference on Computers and Industrial Engineering (CIE) 2018
Co-chair of Special Session on Evolutionary Scheduling and Combinatorial Optimisation, IEEE Congress on Evolutionary Computation (CEC) 2016, 2017, 2018, 2019
Co-chair of Special Session on Evolutionary Computation for Service-Oriented Computing, IEEE Congress on Evolutionary Computation (CEC) 2017, 2018, 2019
Co-chair of Special Session on Transfer Learning in Evolutionary Computation, IEEE Congress on Evolutionary Computation (CEC) 2016
Co-chair of Special Session on Computational Intelligence for Scheduling and Combinatorial Optimization, Asia-Pacific Symposium on Intelligent and Evolutionary Systems (IES) 2016
Conference Program Committee Member
I serve as a PC member of ~40 international conferences (full list).
Journal Reviewer
I serve as a reviewer of ~30 international journals, including the top/major journals in the EC/OR fields (full list).
An automatic model fitting software: Eureqa. It has an academic 30-day trial version.
Datasets
Capacitated Arc Routing Problem
The gdb dataset: 23 small instances (~30 nodes and ~60 required edges).
The val dataset: 10 groups of medium to large instances (~50 nodes and ~100 required edges). Each group contains 3 or 4 instances (denoted as A, B, C, D), which are based on the same graph but different vehicle capacity.
The egl dataset: 8 groups of large instances (~150 nodes and ~200 required edges). The former 4 groups (e1 to e4) and the latter 4 groups (s1 to s4) are based on the same graph, but different subsets of required edges. Each group contains 3 instances (denoted as A, B, C), based on the same graph and required edges, but with different vehicle capacity.
The EGL-G dataset: 2 groups of large instances (~250 nodes and ~400 required edges). Each group contains 5 instances (denoted as A, B, C, D, E), based on the same graph and required edges, but with different vehicle capacity.
Vehicle Routing Problems: benchmark instances for different problem variants can be found from Dr. T. Vidal’s page.
