Brunel University Research Archive (BURA) >
Schools >
School of Information Systems, Computing and Mathematics >
School of Information Systems, Computing and Mathematics Research Papers >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/6605

Title: A sequence based genetic algorithm with local search for the travelling salesman problem
Authors: Arshad, S
Yang, S
Li, C
Keywords: Sequence based genetic algorithm (SBGA)
Travelling salesman problem (TSP)
Sequence based inversion mutation (SBIM)
Sequence based order crossover (SBOX)
Simple inversion mutation (SIM)
Inver-over (IO)
Publication Date: 2009
Publisher: University of Nottingham
Citation: 2009 UK Workshop on Computational Intelligence, University of Nottingham, 7-9 September 2009
Abstract: The standard Genetic Algorithm often suffers from slow convergence for solving combinatorial optimization problems. In this study, we present a sequence based genetic algorithm (SBGA) for the symmetric travelling salesman problem (TSP). In our proposed method, a set of sequences are extracted from the best individuals, which are used to guide the search of SBGA. Additionally, some procedures are applied to maintain the diversity by breaking the selected sequences into sub tours if the best individual of the population does not improve. SBGA is compared with the inver-over operator, a state-of-the-art algorithm for the TSP, on a set of benchmark TSPs. Experimental results show that the convergence speed of SBGA is very promising and much faster than that of the inver-over algorithm and that SBGA achieves a similar solution quality on all test TSPs.
URI: http://bura.brunel.ac.uk/handle/2438/6605
Appears in Collections:Information Systems and Computing
School of Information Systems, Computing and Mathematics Research Papers

Files in This Item:

File Description SizeFormat
Fulltext.pdf130.77 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.

 


Library (c) Brunel University.    Powered By: DSpace
Send us your
Feedback. Last Updated: September 14, 2010.
Managed by:
Hassan Bhuiyan