Title: Improved genetic algorithms for the travelling salesman problem

Authors: Zakir Hussain Ahmed

Addresses: Department of Computer Science, Al Imam Mohammad Ibn Saud Islamic University (IMSIU), P.O. Box No. 5701, Riyadh-11432, Saudi Arabia

Abstract: The travelling salesman problem (TSP) is a benchmark problem in which a salesman has to visit all nodes (cities) in a network exactly once except the starting node, come back to the starting node and find the shortest tour. Genetic algorithm (GA) is one of the best algorithms to deal with the travelling salesman problem (TSP). In GA, crossover operator plays a vital role and the sequential constructive crossover (SCX) is one of the best crossover operators for solving the TSP. Several improvements have been proposed for other crossover operators. In this paper we propose four improved genetic algorithms using three local search methods - 2-opt search, a hybrid mutation, and a combined mutation operator, and incorporate them into SCX. The experimental results on some TSPLIB instances show that our improved GAs can significantly improve simple GA using SCX in terms of solution quality.

Keywords: genetic algorithms; sequential constructive crossover; SCX; local search; combinatorial optimisation; 2-opt search; hybrid mutation; combined mutation; travelling salesman problem; TSP; heuristics.

DOI: 10.1504/IJPMB.2014.059449

International Journal of Process Management and Benchmarking, 2014 Vol.4 No.1, pp.109 - 124

Published online: 21 Jun 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article