Title: A real adjacency matrix-coded evolution algorithm for highly linkage-based routing problems

Authors: Hang Wei; Han Huang; Zhi-Feng Hao; Qin-Qun Chen; Witold Pedrycz; Gang Li

Addresses: School of Medical Information Engineering, Guangzhou University of Chinese Medicine, Guangzhou, 510006, China ' School of Software Engineering, South China University of Technology, Guangzhou, 510006, China ' School of Mathematics and Big Data, Foshan University, Foshan, 528000, China ' School of Medical Information Engineering, Guangzhou University of Chinese Medicine, Guangzhou, 510006, China ' Department of Electrical and Computer Engineering, University of Alberta, Edmonton, Alberta T6R 2V4 AB, Canada ' Foshan Jiuzhang Intelligent Technology Co., Ltd., Foshan, 528000, China

Abstract: In routing problems, the contribution of a variable to fitness often depends on the states of other variables. This phenomenon is referred to as linkage. High linkage level typically makes a routing problem more challenging for an evolutionary algorithm (EA). An entire linkage measure, named entire linkage index (ELI), has been proposed in this paper for such routing problems. Aiming at solving high linkage-based routing problems, we presented a real adjacency matrix-coded evolution algorithm (RAMEA) that is capable of learning and evolving correlation matrix of decision variables. The efficiency of RAMEA was tested on two familiar routing problems: travelling salesman problem (TSP) and generalised travelling salesman problem (GTSP). The experimental results show that the RAMEA is promising for those highly linkage-based routing problems, especially for those of large-scale.

Keywords: linkage; routing problems; evolutionary optimisation; real adjacency matrix-coding mechanism.

DOI: 10.1504/IJBIC.2021.117426

International Journal of Bio-Inspired Computation, 2021 Vol.18 No.1, pp.1 - 12

Accepted: 14 Aug 2020
Published online: 06 Sep 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article