Open AccessA Genetic Method using Hybrid Crossover for Solving Travelling Salesman Problem
Author(s) -
Anubhav Kumar Prasad,
Dharmendra Singh,
• Pankaj
Publication year - 2019
Publication title -
international journal of recent technology and engineering
Language(s) - English
Resource type - Journals
ISSN - 2277-3878
DOI - 10.35940/ijrte.b1897.078219
Subject(s) - crossover , travelling salesman problem , genetic algorithm , mutation , population , mathematical optimization , path (computing) , computer science , position (finance) , 2 opt , mathematics , algorithm , artificial intelligence , biology , biochemistry , demography , finance , sociology , economics , gene , programming language
This paper proposes a Genetic approach using Hybrid Crossover for Solving the Travelling Salesman Problem. Proposed hybrid method generates an initial population using Nearest Neighbor (NN) approach which is modified using “Sub-Path Mutation” (SPM) process. Modified population undergoes Distance Preserving Crossover (DPX) [2] and 2-opt Optimal mutation (2-opt) [1] to check for possible refinement. SPM searches position for the minimum distant city within a given path. This work is motivated by the algorithm developed by [3] who performed DPX and 2-opt mutation on the initial population generated using NN. For performance comparison, standard TSPLIB data is taken. The proposed hybrid method performances better in terms of % best error. It performs better than methods reported in [3 - 11].