Evolutionary multitasking in permutation-based combinatorial optimization problems: Realization with TSP, QAP, LOP, and JSP

Abstract

Evolutionary computation (EC) has gained increasing popularity in dealing with permutation-based combinatorial optimization problems (PCOPs). Traditionally, EC focuses on solving a single optimization task at a time. However, in complex multi-echelon supply chain networks (SCNs), there usually exist various kinds of PCOPs at the same time, e.g., travel salesman problem (TSP), job-shop scheduling problem (JSP), etc. So, it is desirable to solve several PCOPs at once with both effectiveness and efficiency. Very recently, a new paradigm in EC, namely, multifactorial optimization (MFO) has been introduced to explore the potential of evolutionary multitasking, which can serve the purpose of simultaneously optimizing multiple PCOPs in SCNs. In this paper, the evolutionary multitasking of PCOPs is studied. In particular, based on a recently proposed multitasking engine known as the multifactorial evolutionary algorithm (MFEA), two novel mechanisms, namely, a new unified representation and a new survivor selection procedure, are introduced to better adapt to PCOPs. Experimental results obtained on well-known benchmark problems not only show the benefits of the two new mechanisms but also verify the promise of evolutionary multitasking for PCOPs. In addition, the results on a test case involving four optimization tasks demonstrate the potential scalability of evolutionary multitasking to many-task environments.