Analysis of GA Performance on Its Various Parameters for Solving Travelling Salesman NP-Hard Problem

Authors

  • Singh RK Department of Computer Science, Al-Falah University, Faridabad, Haryana, India
  • Panchal VK Department of Computer Science, Al- Falah University, Faridabad, Haryana, India
  • Singh BK Department of Computer Science, Satyug Darshan Institute of Engineering & Technology, Faridabad, Haryana, India

DOI:

https://doi.org/10.26438/ijcse/v7i1.509512

Keywords:

NP-Complete, Genetic Algorithm, Genetic Parameters

Abstract

Genetic Algorithm (GA) is a well-known heuristic algorithm inspired by theory of adaptation. GA is applicable to solve many problems of science and engineering. GA performs its operations such as selection, reproduction and mutation to solve a problem. The genetic parameters such as population size, cross over rate and mutation rate control the performance and effectiveness of GA to solve a problem. In this paper, GA is applied to solve Traveling Salesman Problem (TSP). TSP problem is an optimization problem and it is a member of the set NP-Hard problems. In this paper the performance of GA on its parameters is analyzed to solve TSP problem.

References

[1] S. Sharma and K. Gupta, "Solving the traveling salesmen problem through genetic algorithm with new variation order crossover," 2011 International Conference on Emerging Trends in Networks and Computer Communications (ETNCC), Udaipur, 2011, pp. 274-276.

[2] B. H. Hasan and M. S. Mustafa, "Comparative Study of Mutation Operators on the Behavior of Genetic Algorithms Applied to Non-deterministic Polynomial (NP) Problems," 2011 Second International Conference on Intelligent Systems, Modelling and Simulation, Kuala Lumpur, 2011, pp. 7-12.

[3] M. A. H. Akhand, S. Akter, S. Sazzadur Rahman and M. M. Hafizur Rahman, "Particle Swarm Optimization with partial search to solve Traveling Salesman Problem," 2012 International Conference on Computer and Communication Engineering (ICCCE), Kuala Lumpur, 2012, pp. 118-121.

[4] H. ElAarag and S. Romano, "Animation of the Traveling Salesman Problem," 2013 Proceedings of IEEE Southeastcon, Jacksonville, FL, 2013, pp. 1-6.

[5] S. Cui and S. Han, "Ant Colony Algorithm and Its Application in Solving the Traveling Salesman Problem," 2013 Third International Conference on Instrumentation, Measurement, Computer, Communication and Control, Shenyang, 2013, pp. 1200-1203.

[6] Q. Bai, G. Li and Q. Sun, "An improved hybrid algorithm for traveling salesman problem," 2015 8th International Conference on Biomedical Engineering and Informatics (BMEI), Shenyang, 2015, pp. 806-809.

[7] M. Munlin and M. Anantathanavit, "Hybrid K-means and Particle Swarm Optimization for symmetric Traveling Salesman Problem," 2015 IEEE 10th Conference on Industrial Electronics and Applications (ICIEA), Auckland, 2015, pp. 671-676.

[8] Muhao Chen, Chen Gong, Xiaolong Li and Zongxin Yu, "Research on solving Traveling Salesman Problem based on virtual instrument technology and genetic-annealing algorithms," 2015 Chinese Automation Congress (CAC), Wuhan, 2015, pp. 1825-1827.

[9] J. Stastný, V. Skorpil and L. Cizek, "Traveling Salesman Problem optimization by means of graph-based algorithm," 2016 39th International Conference on Telecommunications and Signal Processing (TSP), Vienna, 2016, pp. 207-210.

[10] M. Khalil, J. Li, Y. Wang and A. Khan, "Algorithm to solve travel salesman problem efficently," 2016 13th International Computer Conference on Wavelet Active Media Technology and Information Processing (ICCWAMTIP), Chengdu, 2016, pp. 123-126.

[11] Q. Hao, L. Fang and S. Tao, "A Discrete Fruit Fly Optimization Algorithm for Traveling Salesman Problem," 2017 International Conference on Industrial Informatics - Computing Technology, Intelligent Technology, Industrial Information Integration (ICIICII), Wuhan, 2017, pp. 254-257.

[12] I. B. K. Widiartha, S. E. Anjarwani and F. Bimantoro, "Traveling salesman problem using multi-element genetic algorithm," 2017 11th International Conference on Telecommunication Systems Services and Applications (TSSA), Lombok, 2017, pp. 1-4.

[13] A. H. M. Alaidi and A. Mahmood, "Distributed hybrid method to solve multiple traveling salesman problems," 2018 International Conference on Advance of Sustainable Engineering and its Application (ICASEA), Wasit, 2018, pp. 74-78.

[14] Z. Pan, Y. Chen, W. Cheng and D. Guo, "Improved fruit fly optimization algorithm for traveling salesman problem," 2018 33rd Youth Academic Annual Conference of Chinese Association of Automation (YAC), Nanjing, 2018, pp. 466-470.

[15] M. Bandyopadhyay, S. Chattopadhyay , A. Das, “Emphasis on Genetic Algorithm (GA) Over Different PID Tuning Methods of Controlling Servo System Using MATLAB”, International Journal of Scientific Research in Computer Science and Engineering, Vol.1, Issue.3, pp.8-13, 2013.

[16] Rajeev Ranjan , P.J. Pawar, “Assembly Line Balancing Using Real Coded Genetic Algorithm”, International Journal of Scientific Research in Computer Science and Engineering, Vol.2, Issue.4, pp.1-5, 2014.

Downloads

Published

2019-01-31
CITATION
DOI: 10.26438/ijcse/v7i1.509512
Published: 2019-01-31

How to Cite

[1]
R. Singh, V. Panchal, and B. Singh, “Analysis of GA Performance on Its Various Parameters for Solving Travelling Salesman NP-Hard Problem”, Int. J. Comp. Sci. Eng., vol. 7, no. 1, pp. 509–512, Jan. 2019.

Issue

Vol. 7 No. 1 (2019): IJCSE January Edition

Section

Research Article

License

Creative Commons License

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

Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.