An evolutionary algorithm for large traveling salesman problems
檔案
- 000222721000009.pdf (522.2 KB, Adobe PDF)
日期
2004-08-01
類型
期刊名稱
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS
卷期與頁次
第 34 卷第 4 期,頁 1718–1729
ISSN
1083-4419
語言
英文
摘要
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.
關鍵詞
edge assembly crossoverevolutionary algorithmfamily competitionheterogeneous pairing selectionLin-Kernighan (LK) heuristictraveling salesman problem所屬典藏
期刊論文引用此條目
Tsai, H., Yang, J., Tsai, Y., & Kao, C. (2004). An evolutionary algorithm for large traveling salesman problems. IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 34(4), 1718–1729. https://doi.org/10.1109/TSMCB.2004.828283
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/26514