Title: Multi-parent extension of sequential constructive crossover for the travelling salesman problem

Authors: Zakir Hussain Ahmed

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

Abstract: Crossover operator plays a vital role in genetic algorithms. This paper proposes the multi-parent sequential constructive crossover (MPSCX), which generalises the two-parent sequential constructive crossover (SCX) to a multi-parent crossover for the travelling salesman problem (TSP). Experimental results on five TSPLIB instances show that MPSCX significantly improves SCX by up to 4.60% in average tour value with maximum 4.01% away from the exact optimal solution. Finally, the efficiency of the MPSCX is compared as against multi-parent partially mapped crossover (MPPMX). Experimental results show that the MPSCX is better than the MPPMX.

Keywords: TSP; travelling salesman problem; NP complete; heuristics; GAs; genetic algorithms; multi-parent crossover; SCX; sequential constructive crossover; selection survivor; mutation; crossover operator.

DOI: 10.1504/IJOR.2011.041347

International Journal of Operational Research, 2011 Vol.11 No.3, pp.331 - 342

Published online: 14 Feb 2015 *

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