Perbandingan Metode Penyelesaian Permasalahan Optimasi Lintas Domain dengan Pendekatan Hyper-Heuristic Menggunakan Algoritma Reinforcement-Late Acceptance

Abstrak

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. 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 meningkatkan kinerja, penelitian ini menguji pengaruh dari adaptasi algoritma Reinforcement Learning (RL) sebagai strategi seleksi LLH dikombinasikan dengan algoritma Late Acceptance sebagai move acceptance, selanjutnya disebut algoritma Reinforcement Learning-Late acceptance (RL-LA). Untuk mengetahui efektivitas performa dari algoritma RL-LA, performa algoritma RL-LA yang diusulkan dibandingkan dengan algoritma Simple Random-Late Acceptance (SR-LA). Hasil dari penelitian ini menunjukan bahwa algoritma yang diusulkan, i.e. RL-LA lebih unggul dari SR-LA pada  4 dari 6 domain permasalahan uji coba, yaitu SAT, personnel scheduling, TSP, dan VRP, sedangkan pada domain lainnya seperti bin packing dan flow shop mengalami penurunan. Secara lebih spesifik, RL-LA dapat meningkatkan peforma pencarian dalam menemukan solusi optimal pada 18 instance dari 30 instance atau sebesar 64%, dan jika dilihat dari nilai median dan minimum metode RL-LA lebih unggul 28% dari metode SR-LA.  Kontribusi utama dari penelitian ini adalah studi performa algoritma hibrida reinforcement learning dan late acceptance dalam kerangka kerja hyper-heuristics untuk menyelesiakan permasalahan optimasi lintas domain.

Abstract

An organization sometimes needs solutions to cross domain optimization problems. The problem of cross domain optimization is a problem that has different characteristics, for example between domain optimization scheduling, vehicle routes, bin packing, and SAT. This optimization is used to support an organization's decision making. In solving these optimization problems, a computational search method is needed. In the literature, almost all optimization problems in NP-hard class are solved by meta-heuristics approach. However, this meta-heuristic has drawbacks, namely tuning parameters are needed for each different problem domain. So this approach is considered less effective. Therefore a new approach is needed, namely the hyper-heuristics approach. Hyper-heuristic method is an approximate computational search method that can solve cross domain optimization problems faster. In this final project there are six cross domain problems to be solved, namely satisfaction (SAT), one dimensional bin packing, permutation flow shop, personnel scheduling, traveling salesman problem (TSP), and vehicle routing problem (VRP). In improving performance, this study examines the effect of the adaptation of the Reinforcement Learning (RL) algorithm as LLH selection combined with the Late Acceptance algorithm as a move acceptance. The results of this study indicate that there are 4 out of six problem domains that have improved performance, namely the SAT, personnel scheduling, TSP, and VRP, while in other domains such as bin packing and flow shop has decreased.