In a traveling salesman problem (TSP), the contribution of a variable to fitness depends on the state of other variables. This characteristic can be referred to as entire linkage, utilizing which evolutionary algorithms can significantly enhance performance, especially in cases of large scale problems. In this paper, a construction graph-based evolutionary algorithm (CGEA) to learn variable interactions in TSP is presented. The proposed method employs real adjacency matrix-coding based on construction graph to make population individuals as carriers of variable interaction degrees through evolution. Iteratively, variable interactions are discovered by a parameterless search scheme, called matrix recombination-difference. In order to explore features of CGEA, an entire linkage index (ELI) is proposed to measure the entire linkage level of TSP. The experimental results show CGEA is promising for TSP, especially with a high entire linkage level.
展开▼
