Open Access   Article Go Back

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

R.K. Singh1 , V.K. Panchal2 , B.K. Singh3

Section:Research Paper, Product Type: Journal Paper
Volume-7 , Issue-1 , Page no. 509-512, Jan-2019

CrossRef-DOI:   https://doi.org/10.26438/ijcse/v7i1.509512

Online published on Jan 31, 2019

Copyright © R.K. Singh, V.K. Panchal, B.K. Singh . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

View this paper at   Google Scholar | DPI Digital Library

XML View
PDF Download

How to Cite this Paper

  • IEEE Citation
  • MLA Citation
  • APA Citation
  • BibTex Citation
  • RIS Citation

IEEE Style Citation: R.K. Singh, V.K. Panchal, B.K. Singh, “Analysis of GA Performance on Its Various Parameters for Solving Travelling Salesman NP-Hard Problem,” International Journal of Computer Sciences and Engineering, Vol.7, Issue.1, pp.509-512, 2019.

MLA Style Citation: R.K. Singh, V.K. Panchal, B.K. Singh "Analysis of GA Performance on Its Various Parameters for Solving Travelling Salesman NP-Hard Problem." International Journal of Computer Sciences and Engineering 7.1 (2019): 509-512.

APA Style Citation: R.K. Singh, V.K. Panchal, B.K. Singh, (2019). Analysis of GA Performance on Its Various Parameters for Solving Travelling Salesman NP-Hard Problem. International Journal of Computer Sciences and Engineering, 7(1), 509-512.

BibTex Style Citation:
@article{Singh_2019,
author = {R.K. Singh, V.K. Panchal, B.K. Singh},
title = {Analysis of GA Performance on Its Various Parameters for Solving Travelling Salesman NP-Hard Problem},
journal = {International Journal of Computer Sciences and Engineering},
issue_date = {1 2019},
volume = {7},
Issue = {1},
month = {1},
year = {2019},
issn = {2347-2693},
pages = {509-512},
url = {https://www.ijcseonline.org/full_paper_view.php?paper_id=3533},
doi = {https://doi.org/10.26438/ijcse/v7i1.509512}
publisher = {IJCSE, Indore, INDIA},
}

RIS Style Citation:
TY - JOUR
DO = {https://doi.org/10.26438/ijcse/v7i1.509512}
UR - https://www.ijcseonline.org/full_paper_view.php?paper_id=3533
TI - Analysis of GA Performance on Its Various Parameters for Solving Travelling Salesman NP-Hard Problem
T2 - International Journal of Computer Sciences and Engineering
AU - R.K. Singh, V.K. Panchal, B.K. Singh
PY - 2019
DA - 2019/01/31
PB - IJCSE, Indore, INDIA
SP - 509-512
IS - 1
VL - 7
SN - 2347-2693
ER -

VIEWS PDF XML
433 383 downloads 142 downloads
  
  
           

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.

Key-Words / Index Term

NP-Complete, Genetic Algorithm, Genetic Parameters

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.