Algoritma Hibrida: Heuristik dan Deterministik pada Permasalahan Komputasi Ekspektasi Waktu Tempuh dalam Kasus Labirin Berdimensi Dua

Yendri, Sheinna (2023) Algoritma Hibrida: Heuristik dan Deterministik pada Permasalahan Komputasi Ekspektasi Waktu Tempuh dalam Kasus Labirin Berdimensi Dua. Masters thesis, Institut Teknologi Sepuluh Nopember.

Text 6025212005-Master_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2025. Download (2MB) | Request a copy

Abstract

Perhitungan ekspektasi waktu tempuh untuk keluar dari sebuah grid atau labirin berdimensi dua tidak mudah dilakukan apabila peluang pergerakan serta skenario rute perjalanannya tidak diketahui. Tanpa adanya definisi skenario kejadian yaitu rute perjalanan beserta peluang terjadinya, maka perhitungan nilai ekspektasi tidak dapat dilakukan. Hal ini berarti, skenario kejadian perlu ditentukan terlebih dahulu agar perhitungan nilai ekspektasi dapat dilakukan. Akan tetapi, ada banyak kemungkinan skenario kejadian yang akan membutuhkan waktu sangat lama apabila ditelusuri satu per satu secara deterministik. Oleh karena itu, pada penelitian ini akan diusulkan sebuah algoritma hibrida yaitu penggabungan algoritma deterministik dan heuristik untuk menyelesaikan permasalahan komputasi waktu ekspektasi minimal dalam labirin berdimensi dua. Dalam algoritma hibrida, metode deterministik bertugas untuk melakukan perhitungan nilai ekspektasi waktu tempuh, sedangkan metode heuristik bertugas untuk mendapatkan nilai probabilitas pergerakan agen yang optimal. Algoritma hibrida ini diawali oleh metode heuristik yaitu penentuan probabilitas pergerakan agen yang menjadi masukan pada metode deterministik untuk dikonstruksi menjadi suatu persamaan matriks dan diselesaikan untuk mendapatkan nilai ekspektasi waktu tempuh keluar dari labirin. Kemudian nilai ekspektasi ini akan digunakan kembali oleh metode heuristik untuk menentukan probabilitas pergerakan agen yang optimal. Proses kerja algoritma hibrida dalam penelitian ini ada pada penggunaan metode heuristik dan deterministik secara bergantian tersebut. Pada proses pengujian, dilakukan uji coba kebenaran dan kinerja algoritma hibrida menggunakan data uji lokal maupun data uji yang ada pada situs Sphere Online Judge. Pada skenario uji coba, dilakukan juga beberapa perbandingan yaitu perbandingan metode heuristik yaitu Hill Climbing dengan Simulated Annealing, serta perbandingan metode pemilihan starting point: secara acak atau intuitif. Dipilih dua metode heuristik tersebut karena keduanya merupakan metode heuristik sederhana yang sering digunakan dalam melakukan optimasi seperti pada permasalahan dalam tesis ini. Sedangkan perbandingan metode pemilihan starting point bertujuan untuk mengetahui apakah penentuan starting point berpengaruh terhadap kinerja metode heuristik. Dari seluruh skenario uji coba yang dilakukan, kinerja algoritma hibrida terbaik didapatkan dengan menggunakan metode heuristik Hill Climbing dan pemilihan starting point secara intuitif dalam waktu dan memori rata-rata sebesar 2.45 detik dan 5.31MB.
==============================================================================================================================
The calculation of expected time travel to escape from a two-dimensional maze is not easy to do if the movement probabilities and travel route scnearios are unknown. Without the definition of the possible scenarios, namely the travel route and the probability of its occurrence, the calculation of the expected value cannot be carried out. In other words, the event scenario needs to be pre-determined so that the calculation of the expected value can be done. However, there are so many possible scenarios that would take a very long time to trace one by one in a deterministic manner. Therefore, in this study, a hybrid algorithm is proposed, a combination of deterministic and heuristic algorithms to compute the minimum expected escape time from a two-dimenstional maze. In the proposed hybrid algorithm, the deterministic method is for calculating the expected value of travel time, while the heuristic method is for obtaining the optimal agent movement probability value. This hybrid algorithm is preceded by the heuristic method, determining the probability of agent movement which will be the input for the deterministic method to be constructed into a matrix equation and solved to obtain the expected escape time of the maze. Then the output will be retrieved by the heuristic method to determine the optimal agent movement probability. The working process of the hybrid algorithm in this research is the use of heuristic and deterministic methods alternately. For evaluation purposes, the validity and performance examinations of the hybrid algorithm were carried out using local test data as well as test data available on the Sphere Online Judge website. As the test scenario, several comparisons were also made, namely a comparison of heuristic methods: Hill Climbing with Simulated Annealing, as well as a comparison of the starting point selection method: randomly or intuitively. These two heuristic methods were chosen because both are simple heuristic methods that are often used in optimization problems. While the comparison of starting point selection method aims to determine whether starting point selection affects the performance of the heuristic method. Of all the test scenarios performed, the best performance of the hybrid algorithm was obtained using the Hill Climbing heuristic method and intuitively selected starting point with average time and memory of 2.45 seconds and 5.31MB.

Item Type:	Thesis (Masters)
Uncontrolled Keywords:	expected value, hybrid, routes, hibrida, nilai ekspektasi, rute perjalanan.
Subjects:	Q Science > QA Mathematics > QA166 Graph theory Q Science > QA Mathematics > QA184 Algebra, Linear T Technology > T Technology (General) > T57.84 Heuristic algorithms.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55101-(S2) Master Thesis
Depositing User:	Sheinna Yendri
Date Deposited:	01 Feb 2023 02:13
Last Modified:	01 Feb 2023 02:13
URI:	http://repository.its.ac.id/id/eprint/95925

Actions (login required)

View Item