Algoritma Genetika Menentukan Jalur Jalan dengan Lintasan Terpendek (Shortest Path)

Authors

  • Melladia Melladia Universitas Nahdlatul Ulama Sumatera Barat

Keywords:

genetic algorithm, shortest path, TSP

Abstract

The shortest route (shortest path) is a problem to find the minimum route from the initial point (node) to the destination point (node). One of the artificial intelligence that can be used to solve the problem of finding the shortest route is the Genetic Algorithm. To get the right solution for optimization problems with one variable or multiple variables. The problem of traveling salesman problem (TSP) is one of the combinatorial optimization problems. TSP is a difficult problem when viewed from the point of computation. Several methods have been used to solve the problem and are a solution in determining the shortest trip through another city only once and returning to the city of origin of departure. Search techniques are carried out at the same time on a number of solutions known as populations. Individuals in a population are called chromosomes. This genetic algorithm consists of several main procedures, namely the selection procedure, crossover, mutation and elitism. Based on research results, the shortest path is 1-2-3-6-5-4-7-8-9-10 where the path is Sunur, Kurai Taji, Lapai, Jati, Pasar Pariaman, Gelombang, Rawang, Pauh, Sei Pasak, dan Koto Marapak with a path length of 55.8342.

References

[1] Amozhita, K. K., Suyitno, S., Mashuri., (2019). Menyelesaikan Travelling Salesman Problem Dengan Metode Dua Sisi Optimal Pada PT. Es Malindo Boyolali. UNNES Journal of Mathematics, 8(1), 21-29.
[2] Utomo, R. G., Maylawati, D. S., Alam, C. N., (2018). Implementasi Algoritma Cheapest Insertion Heuristic (CIH) dalam Penyelesaian Travelling Salesman Problem (TSP). JOIN (Jurnal Online Informatika), 3 (1), 61-67.
[3] Simanjuntak, O.S., Seminar Nasional Informatika 2012 (semnasIF 2012). In : UPN “Veteran”, Pengembangan Shortest Path Algorithm (SPA) Dalam Rangka Pencarian Lintasan Terpendek Pada Graf Bersambung Berarah Terurai, Yogyakarta, 30 Juni 2012. UPN “Veteran”: Yogyakarta.
[4] Salaki, D. T., (2011). Penentuan Lintasan Terpendek Dari FMIPA ke Rektorat dan Fakultas di UNSRAT manado Menggunakan Algoritma Djikstra. Jurnal Ilmiah Sains. 11(1), 73-78
[5] Melladia, M., & Mardani, I. R., (2018). Implementasi Algoritma Backpropagation Prediksi Kegagalan Siswa Pada Mata Pelajaran Matematika. Jurnal RESTI (Rekayasa Sistem Dan Teknologi Informasi), 2(3), 753 - 759. https://doi.org/10.29207/resti.v2i3.588.
[6] Suyanto. (2005). Algoritma Genetika dalam MATLAB. Yogyakarta : Andi.
[7] Saputro, Nico., (2003). Pengenalan Huruf dengan Memakai Algoritma Genetik. Integral, Vol 8 No.2, Oktober 2003.
[8] Syamsudin, Aries., (2004). Pengenalan Algoritma Genetik. (IlmuKomputer.com)
[9] Utami, P. Y., Suhery, C., Ilhamsyah., (2014). Aplikasi Pencarian Rute Terpendek Menggunakan Algoritma Genetika. Jurnal Coding Sistem Komputer Universitas Tangjungpura, 02(1), 19-25.
[10] Febriyana, R., Mahmudy, W. F., (2016). Penjadwalan Kapal Penyeberangan Menggunakan Aloritma Genetika. Jurnal Teknologi Informasi dan Ilmu Komputer (JTIIK), 3(1), 43-50.

Downloads

Published

2020-08-19

How to Cite

Melladia, M. (2020). Algoritma Genetika Menentukan Jalur Jalan dengan Lintasan Terpendek (Shortest Path). Prosiding SISFOTEK, 4(1), 112 - 117. Retrieved from http://seminar.iaii.or.id/index.php/SISFOTEK/article/view/162