Penyelesaian Permasalahan Optimasi Lintas Domain dengan Pendekatan Hyperheuristic Berbasis Algoritma Self Adaptive

Aurelius, Ian (2021) Penyelesaian Permasalahan Optimasi Lintas Domain dengan Pendekatan Hyperheuristic Berbasis Algoritma Self Adaptive. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

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

Abstract

Permasalahan optimasi lintas domain merupakan suatu permasalahan optimasi kompleks karena pada tiap permasalahan yang ada memiliki karakteristik yang berbeda-beda. Salah satu solusi untuk menyelesaikan permasalahan optimasi lintas domain adalah dengan menggunakan pendekatan meta-heuristics. Namun, pendekatan ini masih memiliki kekurangan dengan dibutuhkannya parameter tuning untuk permasalahan domain yang berbeda maupun domain permasalahan yang sama dengan instance berbeda. Oleh karena itu, beberapa peneliti terdahulu mengembangkan suatu pendekatan baru yakni pendekatan dengan metode hyperheuristics. Metode ini memiliki dua sifat ruang pencarian, yaitu LLH (low level heuristics) dan penerimaan solusi (move acceptance) yang tidak langsung bekerja pada domain permasalahan melainkan pada domain barrier terlebih dahulu. Dengan sifat tersebut, hyperheuristic diharapkan dapat menghasilkan solusi generik yang dapat memberikan solusi mendekati optimal untuk permasalahan optimasi dengan domain yang berbeda. Tetapi, hasil penelitian yang sudah ada mengindikasikan bahwa masih diperlukan strategi hiperheuristik yang lebih baik guna memperoleh solusi yang mendekati optimal untuk permasalahan optimasi lintas domain. Dalam tugas akhir ini, dilakukan upaya pengembangan strategi pencarian komputasional pada tatanan HLH (high level heuristics) untuk mengatur proses seleksi rangkaian LLH dan akan dilanjutkan dengan melakukan mekanisme penerimaan solusi. Metode yang akan digunakan dalam pengerjaan tugas akhir ini adalah pendekatan hyperheuristic size stochastic move acceptance (SM) sebagai mekaisme penerimaan solusi dalam tatanan HLH dengan harapan dapat menghasilkan solusi general yang mendekati optimal pada berbagai domain masalah optimasi yang dikombinasikan dengan metode seleksi LLH self-adaptive (SAD). Tugas akhir ini melakukan eksperimen guna menentukan nilai parameter yang tepat untuk dapat mengotomisasi parameter kontrol SM yang dapat menyelesaikan permasalahan optimasi lintas domain. Strategi yang digunakan dalam tugas akhir ini adalah melakukan uji coba pada enam permasalahan optimasi domain yang berbeda yang didapatkan dari kerangka kerja HyFlex, yakni Boolean Satisfiability Problem (SAT), Bin Packing (BP), Flow Shop, Personnel Scheduling, Travelling Salesmen Problem (TSP), dan Vehicle Routing Problem (VRP). Hasil dari uji coba SADSM didapatkan bahwa performa yang dihasilkan pada kerangka kerja HyFlex masih kurang jika dibandingkan dengan algoritma pembanding.
================================================================================================
Cross domain optimization problem is one of complex optimization problem because in each of the problem contains a different characteristic. One of the solution to solve cross domain optimaztion problem is with the use of meta-heuristic. But this approach still has a lot of flaw and needed a parameter tuning for different problem domain or problem in the same domain but different instance. So, past research developed a new approach with the use of hyperheuristics method. Hyperheuristic method has two kind of search space, which are low level heuristic (LLH) and move acceptance that do not work directly in the problem domain but instead in the domain barrier first. With these properties, hyperheuristics are expected to produce generic solutions that can provide near-optimal solutions for optimization problems with different domains. However, the results of existing research indicate that a better hyperheuristic strategy is still needed in order to obtain a near-optimal solution for cross-domain optimization problems. In this final project, an effort is made to develop a computational search strategy in the HLH (high level heuristics) order to regulate the selection process for the LLH series and will be followed by a solution acceptance mechanism. The method that will be used in this final project is the hyperheuristic size stochastic move acceptance (SM) approach as a solution acceptance mechanism in the HLH setting with the hope of producing a general solution that is close to optimal in various optimization problem domains combined with the self-adaptive LLH selection method (SAD). This final project conducts experiments to determine the appropriate parameter values to be able to automate SM control parameters that can solve cross-domain optimization problems. The strategy used in this final project is to conduct trials on six different domain optimization problems obtained from the HyFlex framework, namely the Boolean Satisfiability Problem (SAT), Bin Packing (BP), Flow Shop, Personnel Scheduling, Traveling Salesmen Problem (TSP), and Vehicle Routing Problem (VRP). The results of the SADSM trial show that the performance generated on the HyFlex framework is still lacking when compared to the comparison algorithm.

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	Hyperheuristic, Self-Adaptive, Size Stochastic Move Acceptance, Optimasi Lintas Domain, HyFlex
Subjects:	T Technology > T Technology (General) > T57.84 Heuristic algorithms.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 57201-(S1) Undergraduate Thesis
Depositing User:	Aurelius Ian
Date Deposited:	16 Aug 2021 18:56
Last Modified:	16 Aug 2021 18:56
URI:	http://repository.its.ac.id/id/eprint/87218

Actions (login required)

View Item