A Combined Genetic Algorithm for Symmetric Travelling Salesman Problem

Avik Mitra, Baiduryya Sarkar, Somnath Bhattacharyya

Abstract


There has been significant work on solving Travelling Salesman Problem and its variants using heuristic approach as the algorithms for finding exact solutions are computationally hard. Among the heuristics, genetic algorithms have shown promising result in terms simplicity in implementation and computational complexity. In this paper, we propose Combined Genetic Algorithm that uses partially mapped crossover and exchange mutation to progressively eliminate the weaker solution. Computational performance in our setting has shown quadratic time complexity.

Keywords


Travelling Salesman Problem; NP-Hard; Optimization; Heuristic; Genetic Algorithm

Full Text:

PDF


DOI: https://doi.org/10.26483/ijarcs.v8i5.3517

Refbacks

  • There are currently no refbacks.




Copyright (c) 2017 International Journal of Advanced Research in Computer Science