1. Title
A Unified Framework of Graph-based Evolutionary Multitasking Hyper-Heuristic

2. Authors
Xingxing Hao, Xuefu Road 1, Xi’an 710127, Shaanxi, China, xingxing.hao@nwu.edu.cn, (86)18729209093.
Rong Qu, School of Computer Science, University of Nottingham, Nottingham, NG8 1BB, UK, rong.qu@nottingham.ac.uk.
Jing Liu, P.O. Box 224, Xidian University, Xi'an 710071, Shaanxi, China, neouma@mail.xidian.edu.cn, (86)18291891141

3. Corresponding author
Rong Qu, rong.qu@nottingham.ac.uk

4. Abstract
In recent research, hyper-heuristics have attracted increasing attention in various fields. The most appealing feature of hyper-heuristics is that they aim to provide more generalized solutions to optimization problems by searching in a high-level space of heuristics instead of direct problem domains. Despite the promising findings in hyper-heuristics, the design of more general search methodologies still presents a key research. Evolutionary multitasking is a relatively new evolutionary paradigm which attempts to solve multiple optimization problems simultaneously. It exploits the underlying similarities among different optimization tasks by transferring information among them, thus accelerating the optimization of all tasks. Inherently, hyperheuristics and evolutionary multitasking are similar in the following three ways: 1) they both operate on third-party search spaces; 2) high-level search methodologies are universal; and 3) they both conduct cross-domain optimization. To integrate their advantages effectively, i.e., the knowledge-transfer and cross-domain optimization of evolutionary multitasking and the search in the heuristic spaces of hyper-heuristics, in this article, a unified framework of evolutionary multitasking graph-based hyper-heuristic (EMHH) is proposed. To assess the generality and effectiveness of the EMHH, population-based graph-based hyper-heuristics integrated with evolutionary multitasking to solve exam timetabling and graph-coloring problems, separately and simultaneously, are studied. The experimental results demonstrate the effectiveness, efficiency, and increased the generality of the proposed unified framework compared with single-tasking hyper-heuristics.

5. List of claimed criteria
B, D, F, G

6. Justification of the claims
(B)
The new evolutionary multitasking algorithm produced better overall results for three variants of benchmark timetabling problems, consuming a much less time than that of competitor algorithms. The three benchmark problems with different objectives and constraints have been extensively studied in the literature for more than five decades.
(D)
The competitive overall results for different problems themselves, independently of that they have been mechanically obtained, produced new results in automated algorithm design with enhanced reusability and generality in timetabling and graph coloring. The results for one of the three problems can be verified by the evaluation executable available at http://www.cs.nott.ac.uk/~pszrq/data.htm.
(F)
The majority of existing heuristic algorithms are tailor made, usually addressing one particular problem. Our new algorithm utilises knowledge learned online on similar heuristic search space, rather than specific solutions. The competitive results for different problems are due to the knowledge transfer of heursitics when solving multiple tasks simultaneously, also accelerating the convergence of the evolution.
(G)
Manually creating timetables is very time-consuming, often failing to produce feasible results. In practice, previous timetables are often adapted; however, they are only applicable to the specific institutes. Our new algorithm not only improved human results, but also further advances towards optimizing multiple tasks simultaneously. The practical significance is threefold:
- Firstly, transferable knowledge learned online from other tasks. Instances / problems of the same or even different institute can be optimized together.
- Secondly, singificantly reduced computational costs. It solves the same number of optimization problems using half of the time compared to single-task competitors.
- Finally, parallel optimization. It can be deployed in the cloud, potentially handling and learning from multiple user requests at the same time.

7. Full citation of the paper
Xingxing Hao, Rong Qu, and Jing Liu. “A unified framework of graph-based evolutionary multitasking hyper-heuristic.” IEEE Transactions on Evolutionary Computation, vol. 25, no. 1, pp. 35-47, Feb. 2021.

8.
Any prize money, if any, is to be divided equally among the co-authors.

9. We believe that our entry would be the “best” for the following reasons.
(1) It is not only effective, but also inherently general.
The concept of unified representation scheme is extended to heuristic space, i.e. not limited to specific solution representation. It can thus be adapted to handle multiple tasks simultaneously.
(2) It finds the evidence of knowledge transfer in evolutionary computation.
The new algorithm identifies and visualizes the underlying knowledge of communalities in the heuristic spaces to enhance solving intradomain or cross-domain problems.
(3) It not only achieved better results, but also with a significantly reduced computational time.
This demonstrates that there is still a scope to exploit the no free-lunch theorem.
(4) It is inherently parallel.
It has a great potential to be deployed to cloud services, addressing multiple concurrent requests from multiple users in practice.

10. The evolutionary computation technique used
GA

11. The date of publication
Feb. 2021