Comparative study of prim and genetic algorithms in minimum spanning tree and travelling salesman problem

Andysah Putera Utama Siahaan*, Zulfi Azhar, M. D.L. Siahaan, Muhammad Iqbal, Zuhri Ramadhan, Wirda Fitriani, Zulham Sitorus, Nova Mayasari, Indri Sulistianingsih, Dedi Purwanto, R. F. Wijaya, Heri Kurniawan, Rio Septian Hardinata, Muslim Muslim, Ressy Dwitias Sari, Mhd Furqan, Ali Ikhwan, Muhammad Khahfi Zuhanda, A. H. Lubis, Phak Len Eh KanK. N.F.K. Azir

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

Optimization is the essential thing in an algorithm. It can save the operational cost of an activity. At the Minimum Spanning Tree, the goal to be achieved is how all nodes are connected with the smallest weights. Several algorithms can calculate the use of weights in this graph. Genetic and Primary algorithms are two very popular algorithms for optimization. Prim calculates the weights based on the shortest distance from a graph. This algorithm eliminates the connected loop to minimize circuit. The nature of this algorithm is to trace all nodes to the smallest weights on a given graph. The genetic algorithm works by determining the random value as first initialization. This algorithm will perform selection, crossover, and mutation by the number of rounds specified. It is possible that this algorithm can not achieve the maximum value. The nature of the genetic algorithm is to work with probability. The results obtained are the most optimal results according to this algorithm. The results of this study indicate that the Prim is better than Genetics in determining the weights at the minimum spanning tree while Genetic algorithm is better for travelling salesman problem. Genetics will have maximum results when using large numbers of rotations and populations.

Original languageEnglish
Pages (from-to)3654-3661
Number of pages8
JournalInternational Journal of Engineering and Technology(UAE)
Volume7
Issue number4
DOIs
Publication statusPublished - 2018
Externally publishedYes

Keywords

  • Artificial intelligent
  • Genetic algorithm
  • Minimum spanning tree
  • Prim

Fingerprint

Dive into the research topics of 'Comparative study of prim and genetic algorithms in minimum spanning tree and travelling salesman problem'. Together they form a unique fingerprint.

Cite this