Tutorial

Evolutionary Machine Learning for Combinatorial Optimisation

The IEEE World Congress on Computational Intelligence (WCCI 2022)/IEEE Congress on Evolutionary Computation (CEC 2022), 18 July - 23 July 2022, Padua, Italy

Tutorial Abstract

Combinatorial optimisation such as scheduling and resource allocation for cloud/grid/high performance computing, has attracted attention from both academics and industry due to its practical value. Evolutionary machine learning, e.g., evolutionary computation techniques including evolutionary algorithms, has been widely used to handle combinatorial optimisation problems. Instead of manually designing heuristics for a specific problem instance, evolutionary machine learning has also been successfully used as hyper-heuristics approaches to select or generate heuristics for a class of problem instances, especially in dynamic problems, such as learning scheduling heuristics for dynamic job shop scheduling.

This tutorial will provide a comprehensive introduction to evolutionary machine learning techniques for combinatorial optimisation problems. This tutorial will cover different types of (advanced) evolutionary machine learning approaches for job shop scheduling and resource allocation in cloud computing. By listening to this tutorial, you are expected to get familiar with evolutionary machine learning in four aspects. First, you will learn the definition of hyper-heuristic learning, and the similarities and differences between heuristic learning and hyper-heuristic learning. Second, you will understand different combinatorial optimisation problems well. The details of job shop scheduling (e.g., static, dynamic, flexible job shop scheduling) and resource allocation in cloud computing will be given. Third, how to use evolutionary algorithms as hyper-heuristic approaches to learn heuristics for combinatorial optimisation will be introduced with examples. Last, this tutorial will show how to use advanced machine learning techniques such as feature selection, surrogate and multitask learning with genetic programming to combinatorial optimisation problems by taking job shop scheduling as an example.

Topic Overview

Combinatorial optimisation problems such as job shop scheduling have attracted attention from both academics and industry due to their practical value for real-world applications. Evolutionary machine learning such as genetic algorithms has been widely used to find solutions for combinatorial optimisation problems directly. Instead of heuristic approaches, hyper-heuristics approaches aim to select or generate a heuristic for a class of problems by searching in heuristic spaces. The combinatorial optimisation problems and evolutionary machine learning techniques investigated in this tutorial are popular investigated problems or techniques in the computational intelligence community.

This tutorial will contribute to the computational intelligence community in three ways. First, this tutorial will promote the development of evolutionary machine learning which is an important branch of computational intelligence by delivering related techniques to researchers. Second, this tutorial will encourage people to bring more machine learning techniques such as feature learning, surrogate, and multitask learning into evolutionary algorithms for handling problems, which can definitely promote the computational intelligence community. Last, this tutorial works on combinatorial optimisation problems, which can enhance the applications of evolutionary machine learning to real-world problems such as climate change and high-value manufacturing, and help build collaborations between academia and industry.

This tutorial is suitable for different types of audiences. This tutorial targets researchers who are not familiar with evolutionary machine learning and combinatorial optimisation as well as experienced researchers who are interested in special research topics.

(1) Researches with a background in evolutionary machine learning, combinatorial optimisation, and industrial engineering, can enjoy this tutorial and explore the interfaces between combinatorial optimisation and machine learning.

(2) Researchers can gain fundamental understandings of the subjects and incrementally explore different applications and machine learning techniques of this tutorial.

(3) Industrial engineering researchers who are familiar with combinatorial optimisation will find a good transition to refresh their knowledge and get used to machine learning before exploring machine learning techniques, and other applications in combinatorial optimisation problems.

(4) Machine learning researchers can familiarise themselves with combinatorial optimisation applications from this tutorial and understand the basic settings for applying machine learning algorithms to combinatorial optimisation problems.

(5) Advanced applications of machine learning presented will be of great interest to many machine learning researchers. Industrial engineering and machine learning practitioners will find it useful to understand how machine learning can be applied to solve combinatorial optimisation problems.

Outline

This tutorial contains five parts:

1. Evolutionary machine learning

   1) Introduction of evolutionary machine learning approaches (e.g., evolutionary algorithms and hyper-heuristics)

   2) Introduction of hyper-heuristics approaches (e.g., genetic programming)

   3) The similarities between heuristics and hyper-heuristics approaches

   4) The differences between heuristics and hyper-heuristics approaches

2. Combinatorial optimisation problems

   1) Job shop scheduling

   2) Resource allocation in cloud computing

3. Evolutionary machine learning approaches for combinatorial optimisation

   1) How to generate scheduling heuristics for job shop scheduling

   2) How to generate allocating rules for allocating resources in cloud computing

4. Advanced machine learning techniques for job shop scheduling

   1) Surrogate

   (1) Surrogate basic concepts

   (2) Phenotype VS Genotype of genetic programming individuals

   (3) K-nearest neighbour based surrogate for genetic programming

   (4) Simplified model based surrogate for genetic programming

   (5) Collaborative multi-fidelity based surrogates for genetic programming

   2) Feature selection

   (1) Feature selection basic concepts

   (2) Feature frequency-based feature selection

   (3) Contribution-based feature selection

   3) Multitask learning

   (1) Multitask basic concepts

   (2) Multitask genetic programming based generative hyper-heuristics

   (3) Surrogate-Assisted evolutionary multitask genetic programming

   (4) Adaptive multitask genetic programming

5. Future directions

   1) Limitations of existing studies in this field

   2) Potential solutions to handle the limitations

Organisers

Dr. Fangfang Zhang, Victoria Univeristy of Wellington
Prof. Mengjie Zhang, Victoria Univeristy of Wellington
Dr. Yi Mei, Victoria Universty of Wellington
Dr. Su Nguyen, La Trobe University