Heterogenous selection genetic algorithms for traveling salesman problems

Heterogenous selection genetic algorithms for traveling salesman problems

0.00 Avg rating0 Votes
Article ID: iaor20042254
Country: United Kingdom
Volume: 35
Issue: 3
Start Page Number: 297
End Page Number: 311
Publication Date: Jun 2003
Journal: Engineering Optimization
Authors: , , ,
Keywords: optimization, programming: travelling salesman
Abstract:

This paper proposes a genetic algorithm, called the heterogeneous selection genetic algorithm, 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.0048 above the optima of each test problem.

Reviews

Required fields are marked *. Your email address will not be published.