An Evolutionary Algorithm for Large Traveling Salesman Problems
Authors:
- Huai-Kuang TsaiHTHuai-Kuang Tsai
- Jinn-Moon YangJYJinn-Moon Yang
- Yuan-Fang TsaiYTYuan-Fang Tsai
- Cheng-Yan KaoCKCheng-Yan Kao
- 19 July 2004
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)
- Vol. 34 (4) , 1718-1729
Abstract
This work proposes an evolutionary algorithm, called the heterogeneous selection evolutionary algorithm (HeSEA), for solving large traveling salesman problems (TSP). The strengths and limitations of numerous well-known genetic operators are first analyzed, along with local search methods for TSPs from their solution qualities and mechanisms for preserving and adding edges. Based on this analysis, a new approach, HeSEA is proposed which integrates edge assembly crossover (EAX) and Lin-Kernighan (LK) local search, through family competition and heterogeneous pairing selection. This study demonstrates experimentally that EAX and LK can compensate for each other's disadvantages. Family competition and heterogeneous pairing selections are used to maintain the diversity of the population, which is especially useful for evolutionary algorithms in solving large TSPs. The proposed method was evaluated on 16 well-known TSPs in which the numbers of cities range from 318 to 13 509. Experimental results indicate that HeSEA performs well and is very competitive with other approaches. The proposed method can determine the optimum path when the number of cities is under 10 000 and the mean solution quality is within 0.0074% above the optimum for each test problem. These findings imply that the proposed method can find tours robustly with a fixed small population and a limited family competition length in reasonable time, when used to solve large TSPs.Keywords
This publication has 21 references indexed in Scilit:
- Solving traveling salesman problems by combining global and local search mechanisms2003
- The GENIE is out! (Who needs fitness to evolve?)2003
- An analysis of edge assembly crossover for the traveling salesman problem2003
- Toward minimal restriction of genetic encoding and crossovers for the two-dimensional Euclidean TSPIEEE Transactions on Evolutionary Computation, 2002
- An effective implementation of the Lin–Kernighan traveling salesman heuristicEuropean Journal of Operational Research, 2000
- Inver-over operator for the TSP1998
- The Traveling Salesrep Problem, Edge Assembly Crossover, and 2-opt1998
- Physical mapping of chromosomes: A combinatorial problem in molecular biologyAlgorithmica, 1995
- An Effective Heuristic Algorithm for the Traveling-Salesman ProblemOperations Research, 1973
- Computer Solutions of the Traveling Salesman ProblemBell System Technical Journal, 1965