Please use this identifier to cite or link to this item:
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)
Issue 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.
Appears in Collections:Computer Science
Dept of Computer Science 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.