Saputra, Widya (2019) Perbandingan Metode Penyelesaian Permasalahan Optimasi Lintas Domain Dengan Pendekatan Hyper-Heuristic Menggunakan Algoritma Self Adaptive Learning – Great Deluge. Other thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05211540000150-Undergraduate_Theses.pdf Download (4MB) | Preview |
Abstract
Di literatur, hampir semua permasalahan optimasi dalam kelas NP-hard diselesaikan dengan pendekatan meta-heuristics. Akan tetapi, pendekatan ini memiliki kekurangan dimana diperlukan parameter tuning untuk setiap domain permasalahan yang berbeda maupun instance yang berbeda pada permasalahan yang sama. Pendekatan ini dirasa kurang efektif dalam penyelesaian permasalahan tersebut. Oleh karena itu, diperlukan pendekatan baru, yaitu pendekatan hyper-heuristics yang mampu menyelesaikan permasalahan lintas domain tersebut. Hyper-heuristic merupakan salah satu metode pencarian approximate dimana mampu memberikan solusi permasalahan NP-hard dimana memberikan hasil yang cukup baik dan dapat diterima dalam waktu yang relatif cepat. Metode ini memiliki dua sifat ruang pencarian, yakni pemilihan LLH dan penerimaan solusi (move acceptance). Pendekatan ini bekerja pada domain barier daripada langsung bekerja pada domain permasalahan. Dengan sifat tersebut, hyper-heuristic mampu menyelesaikan permasalahan pada domain yang berbeda. Selain itu, hyper-heuristic memiliki mekanisme pembelajaran melalui umpan balik dari solusi yang telah dihasilkan sebelumnya. Tugas akhir ini menerapkan algoritma hyper-heuristic pada enam domain permasalahan optimasi kombinatorial, yaitu Satisfiability, Bin Packing, Flow Shop, Personnel Scheduling, TSP, dan VRP. Metode yang akan digunakan dalam pengerjaan tugas akhir ini adalah Self Adaptive – Great Deluge (SADGED). Mekanisme Self Adaptive digunakan untuk melakukan seleksi LLH yang akan digunakan, sedangkan Great Deluge digunakan dalam penentuan penerimaan solusi (move acceptance) dalam kerangka hyper-heuristic. Hasil uji coba dibandingkan dengan Algoritma yang sudah ada dan digunakan sebelumnya yaitu Simple Random – Simulated Annealing. Dari hasil pengujian, Penerapan algoritma SADGED tersebut mampu memberikan hasil yang lebih baik dan lebih optimal. Algoritma SADGED mampu memberikan kinerja yang lebih baik berdasarkan nilai median sebesar 83% dibandingkan dengan algoritma Simple Random – Simulated Annealing.
=================================================================================================================================
Almost all optimization problems in NP-hard classes are solved by the meta-heuristics approach. However, this approach has the disadvantages of requiring tuning parameters for each of the different problem domains and different instances on the same problem. This approach is considered less effective in resolving these problems. Therefore, a new approach is needed, namely a hyper-heuristics approach, that is able to solve cross-domain problems. Hyper-heuristic is one of the approximate search methods which is able to provide solutions for NP-hard problems in polynomial time, and provide good enough results. This method has two search space properties, namely LLH selection and acceptance acceptance (move acceptance). This approach works on the barrier domain rather than directly working on the problem domain. With these properties, hyper-heuristic is able to solve problems in different domains. Moreover, hyper-heuristic has a learning mechanism through feedback from previous solutions. This final project tries to implement a hyper-heuristic algorithm on six combinatorial optimization problem domains, namely Satisfiability, Bin Packing, Flow Shop, Scheduling, TSP, and VRP. The method to be used in this final project is Self Adaptive - Great Deluge (SADGED). The Self Adaptive mechanism is used to conduct LLH selection to be used, while the Great Deluge is used in determining acceptance (move acceptance) within the hyper-heuristic framework. The results then compared with Simple Random - Simulated Annealing Algorithm. From the test results, SADGED algorithm is able to provide better and more optimal results. The SADGED algorithm is able to provide better performance based on the median value of 83%.compared to Simple Random – Simulated Annealing.
| Item Type: | Thesis (Other) |
|---|---|
| Additional Information: | RSSI 004 Sap p-1 2019 |
| Uncontrolled Keywords: | Meta-heuristic, Hyper-heuristic, Self-adaptive Learning, Great Deluge, Optimasi Lintas Domain |
| Subjects: | T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 57201-(S1) Undergraduate Thesis |
| Depositing User: | Widya Saputra |
| Date Deposited: | 30 Sep 2024 07:36 |
| Last Modified: | 30 Sep 2024 07:36 |
| URI: | http://repository.its.ac.id/id/eprint/64462 |
Actions (login required)
 |
View Item |