Travelling Salesman Problem Solved using Genetic Algorithm Combined Data Perturbation

Authors

  • J Kanimozhi  Department of Computer Science, Pondicherry University, Puducherry, Tamil Nadu, India
  • R Subramanian  Department of Computer Science, Pondicherry University, Puducherry, Tamil Nadu, India

Keywords:

Travelling Salesman Problem, Genetic algorithm, Data perturbation, Cost function

Abstract

Traveling Salesman Problem (TSP) is a challenging problem in combinatorial optimization. The important of this problem is due to the fact that it is used in many fields such as transportation, logistics, semiconductor industry, problem of routing etc. In this paper Travelling Salesman Problem (TSP) is solved using Genetic Algorithm (GA) combined with data perturbation (DP) and the algorithm named as Perturbed GA. DP is a technique used to avoid local optima and to increase the diversity property of the problem. Efficiency of the algorithm is calculated in terms of fitness, convergence and error rate and from the result analysis, it’s proved that Perturbed GA outperforming GA to solve TSP.

References

  1. Kylie Bryant, A. Benjamin, “Genetic Algorithms and the Traveling Salesman Problem”, Department of mathematic Harvey Mudd college, December, 2000.
  2. X. Meng, J. Li, S. Member, X. Dai, and J. Dou, “Variable Neighborhood Search for a Colored Traveling Salesman Problem,” IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, vol. 19, no. 4, pp. 1018–1026, 2018.
  3. Philip, “A Genetic Algorithm for Solving Travelling Salesman Problem,” International Journal of Advanced Computer Science and Applications,vol. 2, no. 1, pp. 26–29, 2011.
  4. A. Kai, “A simple algorithm for solving travelling salesman problem”, 2012 Second IEEE Conference on Instrumentation & Measurement, Computer, Communication and Control, pp. 1–5, 2012.
  5. S. G. E. Brucal and E. P. Dadios, “Comparative Analysis of Solving Traveling Salesman Problem using Artificial Intelligence Algorithms,” IEEE, 2017.
  6. R. Takahashi, “Quantitative Evaluation of Iterative Extended Changing Crossover Operators to Solve the Traveling Salesman Problem”, 10th International Conference on Natural Computation, pp. 235–244, 2014.
  7. A. Al-dallal, “Using Genetic Algorithm with Combinational Crossover to Solve Travelling Salesman Problem.” Ahlia University, (n.a).
  8. L. Settat, “A new approach based a genetic algorithm for the Selective Travelling Salesman Problem”, IEEE, no. 2, pp. 785–788, 2016.
  9. S. Lianshuan, “An Improved Pareto Genetic Algorithm for Multi-Objective TSP”, Fifth International Conference on Natural Computation, pp. 585–588, 2009, pp. 585–588, 2009.
  10. GOKTURK UCOLUK, “Genetic Algorithm Solution of the TSP Avoiding Special Crossover and Mutation.” Middle East Technical University, (n.a).
  11. A. Hussain, “Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator”, Computational Intelligence and Neuroscience, Volume 2017 (2017).
  12. C. R. Lopes, “Using Genetic Algorithms to minimize the distance and balance the routes for the multiple Traveling Salesman Problem”, IEEE, pp. 3171–3178, 2015.
  13. Jean Yves, “Genetic Algorithm to solve TSP”, Annals of Operations Research 63(1996)339-370, (1996).
  14. Y. Expressway, G. Noida, G. Nagar, and U. Pradesh, “A Survey?: Swarm Intelligence vs . Genetic Algorithm”, International Journal of Science and Research, vol. 3, no. 5, pp. 231–235, 2014.
  15. Xu, M., Li, S., & Guo, J. (2017). Optimization of Multiple Traveling Salesman Problem Based on Simulated Annealing Genetic Algorithm, 25.
  16. Y. Expressway, G. Noida, G. Nagar, and U. Pradesh, “A Survey?: Swarm Intelligence vs . Genetic Algorithm”, International Journal of Science and Research, vol. 3, no. 5, pp. 231–235, 2014.
  17. T. Lust and J. Teghem, “Two-phase Pareto local search for the biobjective traveling salesman problem”, Springer Science, pp. 475–510, 2010, 2009.
  18. M. Cornu, T. Cazenave , D. Vanderpooten, “Perturbed Decomposition Algorithm applied to the multi-objective Traveling Salesman Problem. Computers & Operations Research, 79, 1–17. https://doi.org/10.1016/j.cor.2016.04.025, 2016.
  19. T. Lust and A. Jaszkiewicz, “Speed-up techniques for solving large-scale biobjective TSP,” Comput. Oper. Res., vol. 37, no. 3, pp. 521–533, 2010.
  20. T. Lust and A. FNRS, “New metaheuristics for solving {MOCO} problems?: application to the knapsack problem, the traveling salesman problem and {IMRT} optimization,” 2010.
  21. L. Paquete and T. Stutzle, “A two-phase local search for the biobjective traveling salesman problem,” Evol. Multi-Criterion Optim. Proc., vol. 2632, pp. 479–493, 2003.

International Journal of Scientific Research in Science, Engineering and Technology

Downloads

Published

2018-04-30

Issue

Volume 4, Issue 4, March-April-2018

Section

Research Articles

License

Copyright (c) IJSRSET

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
J Kanimozhi, R Subramanian, " Travelling Salesman Problem Solved using Genetic Algorithm Combined Data Perturbation, International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 4, Issue 4, pp.1239-1247, March-April-2018.