標題: Heterogeneous selection genetic algorithms for 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;heterogeneous pairing selection;family competition;genetic algorithm;neighbor-join mutation;traveling salesman problem
公開日期: 1-Jun-2003
摘要: This paper proposes a genetic algorithm, called the heterogeneous selection genetic algorithm (HSGA), integrating local and global strategies via family competition and edge similarity, for the traveling salesman problem (TSP). Local strategies include neighbor-join mutation and family competition, and global strategies consist of heterogeneous pairing selection and edge assembly crossover. Based on the mechanisms of preserving and adding edges, the search behaviors of neighbor-join mutation and edge assembly crossover are studied. The proposed method has been implemented and applied to 17 well-known TSPs whose numbers of cities range from 101 to 13,509. Experimental results indicate that this approach, although somewhat slower, performs very robustly and is very competitive with other approaches in the best surveys. This approach is able to find the optimum, and the average solution quality is within 0.00048 above the optima of each test problem.
URI: http://dx.doi.org/10.1080/0305215031000109622
http://hdl.handle.net/11536/27818
ISSN: 0305-215X
DOI: 10.1080/0305215031000109622
期刊: ENGINEERING OPTIMIZATION
Volume: 35
Issue: 3
起始頁: 297
結束頁: 311
Appears in Collections:Articles


Files in This Item:

  1. 000183911700005.pdf