Hyper-heuristik untuk Penyelesaian Masalah Optimasi Lintas Domain dengan Seleksi Heuristik berdasarkan Variable Neighborhood Search

Abstract

State-of-the-art dari metode yang digunakan untuk menyelesaikan permasalahan optimasi kombinatorik, yang diketahui sebagai permasalahan NP-hard, adalah meta-heuristics. Kelemahan dari metode meta-heuristics adalah dibutuhkanya parameter tunning yang spesifik untuk setiap problem domain berbeda. Hal ini menyebabkan pendekatan meta-heuristics kurang efektif untuk menyelesaikan permasalahan lintas problem domain. Untuk mengatasi permasalahan tersebut, muncul pendekatan baru yaitu hyper-heuristics. Dengan meningkatkan level search space dari solution space ke low-level heuristics space, hyper-heuristics diharapkan dapat menjadi pendekatan yang lebih general dan efektif untuk menyelesaikan permasalahan lintas problem domain. Penelitian ini bertujuan untuk menginvestigasi performa algoritma variable neighbourhood search (VNS) sebagai strategi untuk memilih low-level heuristics dalam kerangka kerja hyper-heuristics. Hal ini berbeda dengan penelitian-penelitian sebelumnya dimana VNS digunakan dalam kerangka kerja meta-heuristics. Metode yang diusulkan dalam penelitian ini diujicoba pada 6 problem domain yang berbeda yaitu satisfiability (SAT), one dimensional bin packing, permutation flow shop, personel scheduling, travelling salesman problem (TSP), dan vehicle routing problem (VRP). Hasil komputasi menunjukkan bahwa metode VNS ini memiliki performa lebih baik dibandingkan dengan metode seleksi low-level heuristics pembanding, yaitu Simple Random. Secara lebih spesifik, VNS lebih unggul pada 5 dari 6 problem domain.

Keywords

• hyperheuristics, variable neighbourhood search, optimasi