Kajian Algoritma Genetika Dan Algoritma A* Dalam Mencari Rute Terpendek

Nugroho, Dimas Ari (2020) Kajian Algoritma Genetika Dan Algoritma A* Dalam Mencari Rute Terpendek. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

Text 06111640000081-Undergraduate_Thesis.pdf Restricted to Repository staff only Download (5MB) | Request a copy

Abstract

Mencari rute terpendek merupakan masalah yang kerap kali dijumpai pada game yang terkait dengan Artifcial Intelligence (AI). Tugas Akhir ini meneliti tentang bagaimana algoritma genetika dioptimalkan untuk mencari rute terpendek. Permasalahan ini akan divisualisasikan berupa prototype game yang disimulasikan menggunakan Unity 3D. Sedangkan sebagai pembanding Algoritma Genetika, Algoritma A* dipilih karena merupakan algoritma eksak untuk mencari rute terpendek. Disini, graf input dipilih sebagai sampel permasalahan yang dibuat oleh peneiliti untuk membandingkan kedua algoritma. Hasil perbandingan dari segi waktu komputasi yang didapat adalah Algoritma Genetika adalah 1,029 detik sedangkan Algoritma A* adalah 0,00156 detik. Dari segi memori Algoritma Genetika menghasilkan rata-rata memori sebesar 12,56 MB sedangkan Algoritma A* sebesar 9,12 MB. Dari segi jarak yang dihasilkan Algoritma Genetika adalah 1% mendekati jarak optimal yang dihasilkan Algoritma A* dengan masing-masing jarak adalah sebesar 36 dan 35,5.

=====================================================================================================

Find the shortest path is a problem which often encountered in games related to Articial Intelligence(AI). This final project is studied how genetic algorithm optimized to find the shortest path. This problem which will be visualized in the form of a game prototype that will be simulated using Unity 3D. Meanwhile, as a comparison of the Genetic Algorithm, A* Algorithm will be selected as an exact algorithm to find the graph searching. Here, the input of graph is selected as a sample of the problems that created by the researcher to compare both algorithms. The comparison result in terms of computation time obtained is the Genetic Algorithm is 1.029 seconds while Algorithm A* is 0,00156 seconds. In terms of memory, the Genetic Algorithm produces an average memory of 12.56 MB while Algorithm A* is 9.12 MB. The result that generated by Genetic Algorithm is 1% near optimal to A* Algorithm, the optimal distance that produced by A* Algorithm is 35.5 and 36 by Genetic Algorithm.

Item Type:	Thesis (Undergraduate)
Additional Information:	RSMa 511.8 Nug k-1 • Nugroho, Dimas Ari
Uncontrolled Keywords:	Algoritma genetika, Algoritma A*, Memori, Waktu, Jarak, Genetic Algorithms, A* Algorithms, Memory, Time, Cost
Subjects:	Q Science > QA Mathematics > QA402.5 Genetic algorithms. Interior-point methods. Q Science > QA Mathematics > QA76.9 Computer algorithms. Virtual Reality. Computer simulation. T Technology > T Technology (General) > T57.84 Heuristic algorithms.
Divisions:	Faculty of Mathematics, Computation, and Data Science > Mathematics > 44201-(S1) Undergraduate Thesis
Depositing User:	Dimas Ari Nugroho
Date Deposited:	27 Aug 2020 07:14
Last Modified:	20 Oct 2020 00:45
URI:	http://repository.its.ac.id/id/eprint/81192

Actions (login required)

View Item