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

Area of Science:

• Evolutionary Computation
• Combinatorial Optimization
• Artificial Intelligence

Background:

• Evolutionary multitasking (EMT) solves multiple optimization tasks simultaneously by sharing traits.
• Existing explicit EMT algorithms are limited to continuous problems, failing on combinatorial tasks like scheduling and routing.
• There is a gap in research for explicit EMT applied to combinatorial optimization problems.

Purpose of the Study:

• To develop an explicit evolutionary multitasking algorithm for combinatorial optimization problems.
• To address the limitations of existing autoencoding-based explicit EMT methods.
• To demonstrate the effectiveness of explicit EMT on real-world combinatorial problems.

Main Methods:

• Proposed an explicit EMT algorithm (EEMTA) for combinatorial optimization.
• Utilized a weighted l1-norm-regularized learning process for transfer mapping.
• Implemented a solution-based knowledge transfer across Vehicle Routing Problems (VRPs).

Main Results:

• EEMTA demonstrated efficacy on VRP benchmarks in a multitasking environment.
• Empirical studies showed competitive or superior performance compared to state-of-the-art EMT and single-task solvers.
• The algorithm's effectiveness was further confirmed on a package delivery problem (PDP).

Conclusions:

• The proposed EEMTA effectively extends explicit EMT to combinatorial optimization.
• Explicit knowledge transfer enhances performance in multitasking optimization for VRPs.
• The algorithm shows promise for real-world combinatorial optimization applications.