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

Arif Djunaidy(1*), Nisa Dwi Angresti(2), Ahmad Mukhlason(3),

(1) Institut Teknologi Sepuluh Nopember
(2) Institut Teknologi Sepuluh Nopember
(3) Institut Teknologi Sepuluh Nopember
(*) Corresponding Author
DOI: https://doi.org/10.23917/khif.v5i1.7567

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

References

R. Qu, “Meta-heurisitic Agorithm.” Apr-2016.

E. K. Burke, Search methodologies. New York: Springer, 2013.

G. Ochoa, “Search-based Approaches and Hyper-heuristics.”

E. K. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, and J. R. Woodward, “A classification of hyper-heuristic approaches,” in Handbook of metaheuristics, Springer, 2010, pp. 449–468.

E. K. Burke et al., “Hyper-heuristics: a survey of the state of the art,” J. Oper. Res. Soc., vol. 64, no. 12, pp. 1695–1724, Dec. 2013.

S. S. Choong, L.-P. Wong, and C. P. Lim, “Automatic design of hyper-heuristic based on reinforcement learning,” Inf. Sci., vol. 436–437, pp. 89–107, Apr. 2018.

M. Misir, W. Vancroonenburg, K. Verbeeck, and G. V. Berghe, “A selection hyper-heuristic for scheduling deliveries of ready-mixed concrete,” p. 11, 2011.

W. G. Jackson, E. Ozcan, and J. H. Drake, “Late acceptance-based selection hyper-heuristics for cross-domain heuristic search,” 2013, pp. 228–235.

P. Hansen and N. Mladenović, “Variable neighborhood search: Principles and applications,” Eur. J. Oper. Res., vol. 130, no. 3, pp. 449–467, 2001.

Z. Xu and Y. Cai, “Variable neighborhood search for consistent vehicle routing problem,” Expert Syst. Appl., vol. 113, pp. 66–76, Dec. 2018.

Y. Qiu, L. Wang, X. Xu, X. Fang, and P. M. Pardalos, “A variable neighborhood search heuristic algorithm for production routing problems,” Appl. Soft Comput., vol. 66, pp. 311–318, May 2018.

T. Czachórski, E. Gelenbe, K. Grochla, and R. Lent, Eds., “Performance of Selection Hyper-heuristics on the Extended HyFlex Domains,” vol. 659, 2016.

G. Ochoa et al., “Hyflex: A benchmark framework for cross-domain heuristic search,” in European Conference on Evolutionary Computation in Combinatorial Optimization, 2012, pp. 136–147.

N. R. Sabar, M. Ayob, G. Kendall, and Rong Qu, “A Dynamic Multiarmed Bandit-Gene Expression Programming Hyper-Heuristic for Combinatorial Optimization Problems,” IEEE Trans. Cybern., vol. 45, no. 2, pp. 217–228, Feb. 2015.

Muklason, A., Parkes, A.J., Özcan, E., McCollum, B. and McMullan, P.,. Fairness in examination timetabling: Student preferences and extended formulations. Applied Soft Computing, 55, pp.302-318, 2017.

Muklason, A., Andrew J. Parkes, Ender Özcan, Simon N. Kingston, Barry McCollum and Paul McMullan, Hyper-heuristics for Solving a Multi-objective Examination Timetabling Problem, PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling, 2018.

Article Metrics

Abstract view(s): 1000 time(s)
PDF (Bahasa Indonesia): 552 time(s)

Refbacks

  • There are currently no refbacks.