標題: Some issues of designing 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;genetic algorithm;neighbor-join mutation;traveling salesman problem
公開日期: 1-十一月-2004
摘要: This paper demonstrates that a robust genetic algorithm for the traveling salesman problem (TSP) should preserve and add good edges efficiently, and at the same time, maintain the population diversity well. We analyzed the strengths and limitations of several well-known genetic operators for TSPs by the experiments. To evaluate these factors, we propose a new genetic algorithm integrating two genetic operators and a heterogeneous pairing selection. The former can preserve and add good edges efficiently and the later will be able to keep the population diversity. The proposed approach was evaluated on 15 well-known TSPs whose numbers of cities range from 101 to 13509. Experimental results indicated that our approach, somewhat slower, performs very robustly and is very competitive with other approaches in our best surveys. We believe that a genetic algorithm can be a stable approach for TSPs if its operators can preserve and add edges efficiently and it maintains population diversity.
URI: http://dx.doi.org/10.1007/s00500-003-0317-8
http://hdl.handle.net/11536/25658
ISSN: 1432-7643
DOI: 10.1007/s00500-003-0317-8
期刊: SOFT COMPUTING
Volume: 8
Issue: 10
起始頁: 689
結束頁: 697
顯示於類別:期刊論文


文件中的檔案:

  1. 000226545500008.pdf