Explicit Evolutionary Multitasking for Combinatorial Optimization : A Case Study on Capacitated Vehicle Routing Problem

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

5 Scopus Citations
View graph of relations

Author(s)

  • Liang Feng
  • Yuxiao Huang
  • Lei Zhou
  • Jinghui Zhong
  • Abhishek Gupta
  • Ke Tang

Detail(s)

Original languageEnglish
Article number9023952
Pages (from-to)3143-3156
Journal / PublicationIEEE Transactions on Cybernetics
Volume51
Issue number6
Online published4 Mar 2021
Publication statusPublished - Jun 2021

Abstract

Recently, evolutionary multitasking (EMT) has been proposed in the field of evolutionary computation as a new search paradigm, for solving multiple optimization tasks simultaneously. By sharing useful traits found along the evolutionary search process across different optimization tasks, the optimization performance on each task could be enhanced. The autoencoding-based EMT is a recently proposed EMT algorithm. In contrast to most existing EMT algorithms, which conduct knowledge transfer across tasks implicitly via crossover, it intends to perform knowledge transfer explicitly among tasks in the form of task solutions, which enables the employment of task-specific search mechanisms for different optimization tasks in EMT. However, the autoencoding-based explicit EMT can only work on continuous optimization problems. It will fail on combinatorial optimization problems, which widely exist in real-world applications, such as scheduling problem, routing problem, and assignment problem. To the best of our knowledge, there is no existing effort working on explicit EMT for combinatorial optimization problems. Taking this cue, in this article, we thus embark on a study toward explicit EMT for combinatorial optimization. In particular, by using vehicle routing as an illustrative combinatorial optimization problem, the proposed explicit EMT algorithm (EEMTA) mainly contains a weighted l1-norm-regularized learning process for capturing the transfer mapping, and a solution-based knowledge transfer process across vehicle routing problems (VRPs). To evaluate the efficacy of the proposed EEMTA, comprehensive empirical studies have been conducted with the commonly used vehicle routing benchmarks in multitasking environment, against both the state-of-the-art EMT algorithm and the traditional single-task evolutionary solvers. Finally, a real-world combinatorial optimization application, that is, the package delivery problem (PDP), is also presented to further confirm the efficacy of the proposed algorithm.

Research Area(s)

  • Evolutionary optimization, knowledge transfer, multitask optimization, routing problem

Citation Format(s)

Explicit Evolutionary Multitasking for Combinatorial Optimization : A Case Study on Capacitated Vehicle Routing Problem. / Feng, Liang; Huang, Yuxiao; Zhou, Lei; Zhong, Jinghui; Gupta, Abhishek; Tang, Ke; Tan, Kay Chen.

In: IEEE Transactions on Cybernetics, Vol. 51, No. 6, 9023952, 06.2021, p. 3143-3156.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review