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

摘要

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.

关键词