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

  • Authors

    • Andysah Putera Utam a 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 Kan
    • K. N. F. K. Azir
    https://doi.org/10.14419/ijet.v7i4.21749

  • 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.

  • References

    1. [1] S. Aryza, M. Irwanto, Z. Lubis, A. P. U. Siahaan, R. Rahim, and M. Furqan, “A Novelty Design of Minimization of Electrical Losses in A Vector Controlled Induction Machine Drive,†in IOP Conference Series: Materials Science and Engineering, 2018, vol. 300, no. 1.

      [2] A. P. U. Siahaan et al., “Arduino Uno-based Water Turbidity Meter using LDR and LED Sensors,†Int. J. Eng. Technol., vol. 7, no. 4, pp. 2113–2117, 2018. https://doi.org/10.31227/osf.io/epkxs.

      [3] I. B. A. I. Iswara et al., “Application of Data Encryption Standard and Lempel-Ziv-Welch Algorithm for File Security,†Int. J. Eng. Technol., vol. 7, no. 3.2, pp. 783–785, 2018.

      [4] M. Putri, P. Wibowo, S. Aryza, A. P. U. Siahaan, and Rusiadi, “An Implementation of A Filter Design Passive LC In Reduce a Current Harmonisa,†Int. J. Civ. Eng. Technol., vol. 9, no. 7, pp. 867–873, 2018.

      [5] R. Rahim et al., “Combination Base64 Algorithm and EOF Technique for Steganography,†J. Phys. Conf. Ser., vol. 1007, no. 1, pp. 1–5, 2018. https://doi.org/10.1088/1742-6596/1007/1/012003.

      [6] R. Meiyanti, A. Subandi, N. Fuqara, M. A. Budiman, and A. P. U. Siahaan, “The Recognition of Female Voice Based on Voice Registers in Singing Techniques in Real-Time using Hankel Transform Method and Macdonald Function,†J. Phys. Conf. Ser., vol. 978, no. 1, pp. 1–6, 2018. https://doi.org/10.1088/1742-6596/978/1/012051.

      [7] A. P. U. Siahaan and R. Rahim, “Dynamic Key Matrix of Hill Cipher Using Genetic Algorithm,†Int. J. Secur. It is Appl., vol. 10, no. 8, pp. 173–180, Aug. 2016.

      [8] A. Ikhwan, M. Yetri, Y. Syahra, and J. Halim, “A Novelty of Data Mining for Promoting Education based on FP-Growth Algorithm,†Int. J. Civ. Eng. Technol., vol. 9, no. 7, pp. 1660–1669, 2018.

      [9] Khairul et al., “Effect of Matrix Size in Affecting Noise Reduction Level of Filtering,†Int. J. Eng. Technol., vol. 7, no. 3, pp. 1272–1275, 2018. https://doi.org/10.14419/ijet.v7i3.11333.

      [10] R. Rahim et al., “Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) method for decision support system in top management,†Int. J. Eng. Technol., vol. 7, no. 3.4, pp. 290–293, 2018.

      [11] A. H. Lubis, S. Z. S. Idrus, and A. Sarji, “ICT Usage amongst Lecturers and Its Impact towards Learning Process Quality,†vol. 34, no. 1, pp. 284–299, 2018.

      [12] A. P. U. Siahaan, Rusiadi, P. L. E. Kan, K. N. F. K. Azir, and A. Amir, “Prim and Genetic Algorithms Performance in Determining Optimum Route on Graph,†Int. J. Control Autom., vol. 11, no. 6, pp. 109–122, 2018.

      [13] M. Townsend, Discrete Mathematic: Applied Combinatorics and Graph Theory. The Benjamin/Cummings Publishing Company, 1987.

      [14] M. Negnevitsky, Artificial Intelligence: A Guide to Intelligent System. England: Addison-Wesley, 2005.

      [15] A. P. U. Siahaan, “Heuristic Function Influence to the Global Optimum Value in Shortest Path Problem,†IOSR J. Comput. Eng., vol. 18, no. 05, pp. 39–48, May 2016. https://doi.org/10.9790/0661-1805053948.

      [16] Z. Ramadhan, A. Putera Utama Siahaan, and M. Mesran, “Prim and Floyd-Warshall Comparative Algorithms in Shortest Path Problem,†in Proceedings of the Joint Workshop KO2PI and the first International Conference on Advance & Scientific Innovation, 2018.

      [17] V. N. S. Lestari, H. Djanggih, A. Aswari, N. Hipan, and A. P. U. Siahaan, “Technique for order preference by similarity to ideal solution as decision support method for determining employee performance of sales section,†Int. J. Eng. Technol., vol. 7, no. 2.14 Special Issue 14, 2018.

      [18] D. Kalpanadevi, “Effective Searching Shortest Path in Graph Using Prim’s Algorithm,†Int. J. Comput. Organ. Trends, vol. 3, no. 8, pp. 310–313, 2013.

      [19] A. P. U. Siahaan et al., “Combination of Levenshtein Distance and Rabin-Karp to Improve the Accuracy of Document Equivalence Level,†Int. J. Eng. Technol., vol. 7, no. 2.27, pp. 17–21, 2018.

      [20] R. Rahim et al., “Prototype File Transfer Protocol Application for LAN and Wi-Fi Communication,†Int. J. Eng. Technol., vol. 7, no. 2.13, pp. 345–347, 2018.

      [21] M. Iqbal, A. P. U. Siahaan, N. E. Purba, and D. Purwanto, “Prim’s Algorithm for Optimizing Fiber Optic Trajectory Planning,†Int. J. Sci. Res. Sci. Technol., vol. 3, no. 6, pp. 504–509, 2017.

      [22] C. Connolly, “Fibreâ€opticâ€based sensors bring new capabilities to structural monitoring,†Sens. Rev., vol. 26, no. 3, pp. 236–243, Jul. 2006. https://doi.org/10.1108/02602280610675537.

      [23] T. Eddy, B. Alamsyah, S. Aryza, and A. P. U. Siahaan, “An Effect Phenomena Circle Living Field in Secanggang Langkat,†Int. J. Civ. Eng. Technol., vol. 9, no. 7, pp. 1575–1580, 2018.

      [24] W. S. Purba et al., “Relationships Among Knowledge, Attitude and Behavioral Intention of Waste Management Technology,†Int. J. Civ. Eng. Technol., vol. 9, no. 9, pp. 792–798, 2018.

      [25] S. Suroso et al., “Autoregression Vector Prediction on Banking Stock Return using CAPM Model Approach and Multi-Factor APT,†Int. J. Civ. Eng. Technol., vol. 9, no. 9, pp. 1093–1103, 2018.

      [26] A. Sanusi et al., “GCG SIMULTANEITY EFFECTS, PROFIT MANAGEMENT AND VALUE OF INDONESIAN RETAIL COMPANIES,†Int. J. Civ. Eng. Technol., vol. 9, no. 7, pp. 1506–1518, 2018.

      [27] A. Sanusi et al., “Gravity Model Approach using Vector Autoregression in Indonesian Plywood Exports,†Int. J. Civ. Eng. Technol., vol. 9, no. 10, pp. 409–421, 2018.

      [28] Rusiadi et al., “Dependence of poverty dependence on Indonesian economic fundamentals: Sfavar approach,†Int. J. Civ. Eng. Technol., vol. 9, no. 6, 2018.

      [29] A. I. F. Lubis et al., “Strategy for Improving Science and Welfare through Community Empowerment Technology,†Int. J. Civ. Eng. Technol., vol. 9, no. 9, pp. 1036–1046, 2018.

      [30] Rusiadi et al., “Simultaneous Response of Dividend Policy and Value of Indonesia Manufacturing Companies An Approach of Vector Autoregression,†Int. J. Civ. Eng. Technol., vol. 9, no. 6, pp. 313–323, 2018.

      [31] Rusiadi and A. Novalina, “Monetary Policy Transmission: Does Maintain the Price and Poverty Stability is Effective?†Jejak J. Ekon. dan Kebijak., vol. 11, no. 102, pp. 78–82, 2018.

      [32] A. Novalina et al., “Confirmatory Factor Analysis Specimen in Calculating Independence Element of Coastal Woman,†Int. J. Civ. Eng. Technol., vol. 9, no. 9, pp. 1632–1644, 2018.

      [33] Wikimedia, “Prim Algorithm,†Wikimedia Commons, 2015. [Online]. Available: https://commons.wikimedia.org/wiki/File:Prim_Algorithm_1.svg.

      [34] Z. Ramadhan, “Perbandingan Algoritma Prim dan Algoritma Floyd-Warshall dalam Menentukan Lintasan Terpendek (Shortest Path Problem),†Universitas Sumatera Utara, 2016.

      [35] M. Furqan et al., “A Review of Prim and Genetic Algorithms in Finding and Determining Routes on Connected Weighted Graphs,†Int. J. Civ. Eng. Technol., vol. 9, no. 9, pp. 1755–1765, 2018.

      [36] S. Hartanto, M. Furqan, A. P. U. Siahaan, and W. Fitriani, “Haversine Method in Looking for the Nearest Masjid,†Int. J. Recent Trends Eng. Res., vol. 3, no. 8, pp. 187–195, Aug. 2017. https://doi.org/10.23883/IJRTER.2017.3402.PD61H.

      [37] R. Rahim et al., “Searching Process with Raita Algorithm and its Application,†J. Phys. Conf. Ser., vol. 1007, no. 1, pp. 1–7, 2018. https://doi.org/10.1088/1742-6596/1007/1/012004.

      [38] A. P. U. Siahaan, “Genetic Algorithm in Hill Cipher Encryption,†Am. Int. J. Res. Sci. Technol. Eng. Math., vol. 15, no. 1, pp. 84–89, 2016.

      [39] A. Philip, A. A. Taofiki, and O. Kehinde, “A Genetic Algorithm for Solving Travelling Salesman Problem,†Int. J. Adv. Comput. Sci. Appl., vol. 2, no. 1, pp. 26–29, 2011.

      [40] A. P. U. Siahaan, “Adjustable Knapsack in Travelling Salesman Problem Using Genetic Process,†Int. J. Sci. Technoledge, vol. 4, no. 9, pp. 46–55, 2016.

      [41] S. Gupta and P. Panwar, “Solving Travelling Salesman Problem Using Genetic Algorithm,†Int. J. Adv. Res. Comput. Sci. Softw. Eng., vol. 3, no. 6, pp. 376–380, 2013.

      [42] H. Tabatabaee, “Solving the Traveling Salesman Problem using Genetic Algorithms with the New Evaluation Function,†Bull. Environ. Pharmacol. Life Sci., vol. 4, no. 11, pp. 124–131, 2015.

      [43] Y. F. Waruwu, “Analisis Nilai Mutasi Dinamis pada Algoritma Genetika,†Universitas Sumatra Utara, 2016.

      [44] Y. Deng, Y. Liu, and D. Zhou, “An Improved Genetic Algorithm with Initial Population Strategy for Symmetric TSP,†Math. Probl. Eng., vol. 2015, pp. 1–6, 2015.

      [45] Ş. B. Bozkurt and D. Bozkurt, “On the Number of Spanning Trees of Graphs,†Sci. World J., vol. 2014, pp. 1–5, 2014. https://doi.org/10.1155/2014/294038.

  • Downloads

  • How to Cite

    a Siahaan, A. P. U., Azhar, Z., Siahaan, M. D. L., Iqbal, M., Ramadhan, Z., Fitriani, W., Sitorus, Z., Mayasari, N., Sulistianingsih, I., Purwanto, D., Wijaya, R. F., Kurniawan, H., Hardinata, R. S., Muslim, M., Sari, R. D., Furqan, M., Ikhwan, A., Zuhanda, M. K., Lubis, A. H., … Azir, K. N. F. K. (2018). Comparative study of prim and genetic algorithms in minimum spanning tree and travelling salesman problem. International Journal of Engineering & Technology, 7(4), 3654-3661. https://doi.org/10.14419/ijet.v7i4.21749

    Received date: 2018-11-26

    Accepted date: 2018-11-26