Penyelesaian Travellinng Thief Problem Menggunakan Metode Hyperheuristic dengan Algoritma Tree Physiology Optimization

Nugraha, Lanang Alun (2021) Penyelesaian Travellinng Thief Problem Menggunakan Metode Hyperheuristic dengan Algoritma Tree Physiology Optimization. Masters thesis, Institut Teknologi Sepuluh Nopember.

Text 05211850012003-Master_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2023. Download (2MB) | Request a copy

Abstract

Travelling thief problem (TTP) merupakan gabungan dari permasalahan travelling salesman problem dan knapsack problem. travelling thief problem sendiri merupakan permasalahan NP-Hard sehingga permasalahan sebagian besar diselesaikan menggunakan algoritma heuristik dan terus berkembang seiring berjalanya waktu.
Algoritma yang digunakan pada penelitian ini adalah simple random untuk pemilihan low level heuristic (LLH) dan tree physiology optimization (TPO) untuk langkah move acceptance dengan menggunakan model Hyper-Heuristics. Pada penelitian yang telah dilakukan sebelumnya algoritma TPO mampu menghasilkan nilai yang cukup kompetitif dengan waktu komputasi yang baik, sedangkan pemodelan Hyper-Heuristics dapat menghasilkan nilai yang konsisten pada data yang beragam. Penelitian diawali dengan memodelkan algoritma TPO menjadi Hyper-Heuristics dan diuji coba dengan data dari TSPLib. Dari hasil uji coba yang dilakukan dapat dilihat bagaimana performa algoritma baru pada data yang diuji.
Berdasarkan hasil yang didapat dari penelitian ini dapat disimpulkan bahwa algoritma LLH TPO dapat mengolah data TTP dengan ukuran di bawah 100 dengan cukup baik terbukti dengan hasil yang lebih baik dari metode genetic programming based hyper-heuristic (GPHS) yang telah ada sebelumnya, namun pada data di atas 100 performa LLH TPO menurun jika dibandingkan dengan metode GPHS.
===================================================================================================
Traveling thief problem is a combination of the traveling salesman problem and the knapsack problem. traveling thief problem itself is an NP-Hard problem, so most of the problems are solved using a heuristic algorithm and it continues to grow over time.
The algorithm used in this study is simple random for the selection of low level heuristics (LLH) and tree physiology optimization (TPO) for the move acceptance step using the Hyper-Heuristics model.. In previous research, the TPO algorithm is able to produce competitive values with good computation time, while Hyper-Heuristics modeling can produce consistent values on various data. The research was started by modeling the TPO algorithm into Hyper-Heuristics and tested it with data from TSPLib. From the results of the trials conducted, it can be seen how the performance of the new algorithm on the data being tested.
Based on the results obtained from this study, it can be concluded that the LLH TPO algorithm can process TTP data with sizes below 100 quite well, as evidenced by better results than the previous genetic programming based hyper-heuristic (GPHS) method, but the data above 100 LLH TPO performance decreased when compared to the GPHS method.

Item Type:	Thesis (Masters)
Uncontrolled Keywords:	Travelling Salesman Problem, Knapsack Probelm, Travelling Thief Problem, Tree Physiology Optimization
Subjects:	T Technology > T Technology (General) > T57.84 Heuristic algorithms.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 59101-(S2) Master Thesis
Depositing User:	lanang alun nugraha
Date Deposited:	21 Aug 2021 13:26
Last Modified:	21 Aug 2021 13:26
URI:	http://repository.its.ac.id/id/eprint/88300

Actions (login required)

View Item