標題: An evolutionary algorithm for large traveling salesman problems
作者: Tsai, HK
Yang, JM
Tsai, YF
Kao, CY
生物科技學系
生物資訊及系統生物研究所
Department of Biological Science and Technology
Institude of Bioinformatics and Systems Biology
關鍵字: edge assembly crossover;evolutionary algorithm;family competition;heterogeneous pairing selection;Lin-Kernighan (LK) heuristic;traveling salesman problem
公開日期: 1-Aug-2004
摘要: 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.
URI: http://dx.doi.org/10.1109/TSMCB.2004.828283
http://hdl.handle.net/11536/26514
ISSN: 1083-4419
DOI: 10.1109/TSMCB.2004.828283
期刊: IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS
Volume: 34
Issue: 4
起始頁: 1718
結束頁: 1729
Appears in Collections:Articles


Files in This Item:

  1. 000222721000009.pdf