Firdaus, Anang (2019) Perbandingan Metode Penyelesaian Permasalahan Optimasi Lintas Domain dengan Pendekatan Hyper-heuristic Menggunakan Algoritma Reinforcement Learning-Late Acceptance. Other thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05211540000109-Undergraduate_Theses.pdf Download (3MB) | Preview |
Abstract
Sebuah organisasi terkadang membutuhkan solusi untuk permasalahan optimasi lintas domain. Permasalahan optimasi lintas domain merupakan permasalahan yang memiliki karakteristik berbeda, misalnya antar domain optimasi penjadwalan, rute kendaraan, bin packing, dan SAT. Optimasi tersebut digunakan untuk mendukung pengambilan keputusan sebuah organisasi. Dalam menyelesaikan permasalahan optimasi tersebut, dibutuhkan metode pencarian komputasi. Di literatur, hampir semua permasalahan optimasi dalam kelas NP-hard diselesaikan dengan pendekatan meta-heuristics. Akan tetapi meta-heuristic ini memiliki kekurangan, yaitu diperlukan parameter tunning untuk setiap problem domain yang berbeda. Sehingga pendekatan ini dirasa kurang efektif. Oleh karena itu diperlukan pendekatan baru, yaitu pendekatan hyper-heuristics. Metode hyper-heuristic merupakan metode pencarian komputasi approximate yang dapat menyelesaikan permasalahan optimasi lintas domain dengan waktu lebih cepat. Pada tugas akhir ini lintas domain permasalahan yang akan diselesaikan ada enam, yaitu satisfiability (SAT), one dimensional bin packing, permutation flow shop, personnel scheduling, travelling salesman problem (TSP), dan vehicle routing problem (VRP). Dalam menigkatkan kinerja, tugas akhir ini menguji pengaruh dari adaptasi algoritma Reinforcement Learning (RL) sebagai seleksi LLH dikombinasikan dengan algoritma Late Acceptance sebagai move acceptance. Hasil dari penelitian ini menunjukan algoritma Reinforcement Learning – Late Acceptance mendapatkan skor persentase kinerja sebesar 80% yang diuji coba pada 30 variasi instance data dalam enam domain permasalahan dan RL-LA unggul 8% dibandingkan dengan SR-LA. =================================================================================================================================
An organization sometimes needs solutions to cross-domain optimization problems. Cross domain optimization problem is a problem that has different characteristics, for example between domains of optimization scheduling, vehicle routing problem, bin packing, and SAT. This optimization is used to support the decision making of an organization. In solving the optimization problem, a computational search method is needed. In the literature, almost all optimization problems in NP-hard classes are solved by the meta-heuristics approach. However, this meta-heuristic has its disadvantages, that is, it requires parameters tunning for each different domain problem. So this approach is considered less effective. Therefore a new approach is needed, namely the hyper-heuristics approach. The hyper-heuristic method is an approximate computational search method that can solve cross-domain optimization problems with faster time. In this final project, there are six problem domains to be solved, namely satisfiability (SAT), one dimensional bin packing, permutation flow shop, personnel scheduling, traveling salesman problem (TSP), and vehicle routing problem (VRP). In improving performance, this final project examines the effect of adaptation of the Reinforcement Learning (RL) algorithm as LLH selection combined with the Late Acceptance algorithm as a acceptance acceptance. The results of this study show that the Reinforcement Learning - Late Acceptance algorithm gets a performance percentage score of 80% which is tested on 30 variations of data instances in six problem domains and RL-LA is superior to 8% compared to SR-LA.
| Item Type: | Thesis (Other) |
|---|---|
| Additional Information: | RSSI 658.403 801 1 Fir p-1 2019 |
| Uncontrolled Keywords: | Optimasi Lintas Domain, Hyper-heuristic, High level heuristic, Reinforcement Learning, Late Acceptance |
| Subjects: | T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming |
| Divisions: | Faculty of Information Technology > Information System > 57201-(S1) Undergraduate Thesis |
| Depositing User: | Anang Firdaus |
| Date Deposited: | 15 May 2024 07:08 |
| Last Modified: | 15 May 2024 07:08 |
| URI: | http://repository.its.ac.id/id/eprint/64708 |
Actions (login required)
 |
View Item |