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

Penulis

Anang Firdaus, Ahmad Muklason, Vicha Azthanty Supoyo

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.


Teks Lengkap:

PDF

Referensi


BURKE, E.K, HYDE, M., KENDALL, OCHOA, G., OZCAN, E., and WOODWARD, J. R., “Handbook of Metaheuristics,” Handb. Metaheuristics, 2006.

BURKE, E.K. and KENDALL, G., Search Methodologies. 2013.

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

DJUNAIDY, A., ANGRESTI, N.D. and MUKHLASON, A., Hyper-heuristik untuk Penyelesaian Masalah Optimasi Lintas Domain dengan Seleksi Heuristik berdasarkan Variable Neighborhood Search. Khazanah Informatika: Jurnal Ilmu Komputer dan Informatika, 5(1), pp.51-60, 2019.

DRAKE, J.H., KHEIRI, A., OZCAN, E. and BURKE, E.K., 2019. Recent advances in selection hyper-heuristics. European Journal of Operational Research, 285 (2), p.405-428, 2020.

HARMAN, M. and CHICANO, F., “Search Based Software Engineering (SBSE),” J. Syst. Softw., vol. 103, p. 266, 2015.

HIDAYATUL, Y. S., DJUNAIDY, A., & MUKLASON, A. Solving Multi-objective Vehicle Routing Problem Using Hyper-heuristic Method By Considering Balance of Route Distances. In 2019 International Conference on Information and Communications Technology (ICOIACT), pp. 937-942, 2019.

HILLIER, F. and LIEBERMAN, G., Introduction to Operation Research. 2010.

KUMARI, A.C. and SRIVINAS, K.. Hyper-heuristic approach for multi-objective software module clustering. Journal of Systems and Software, 117, pp.384-401, 2016.

KUSUMAWARDANI, D., MUKLASON, A. and SUPOYO, V.A., July.

Examination Timetabling Automation and Optimization using Greedy-Simulated Annealing Hyper-heuristics Algorithm. In 2019 12th International Conference on Information & Communication Technology and System (ICTS),pp. 1-6. 2019

MADI, M., MARKOVI, D., and RADOVANOVI, M., “Comparison of Meta-Heuristic Algorithms for,” Facta Univ., vol. 11, no. 1, pp. 29–44, 2013.

MCCOLLUM, B. et al., “The Cross-Domain Heuristic Search Challenge – An International Research Competition,” 2011

MUKLASON, A., IRIANTI, R.G. and MAROM, A., Automated Course Timetabling Optimization Using Tabu-Variable Neighborhood Search Based Hyper-Heuristic Algorithm. Procedia Computer Science, 161, pp.656-664, 2019.

MUKLASON, A., SYAHRANI, G.B. and MAROM, A., Great Deluge Based Hyper-heuristics for Solving Real-world University Examination Timetabling Problem: New Data set and Approach. Procedia Computer Science, 161, pp.647-655, 2019

OZCAN, E., BYKOV, Y., BIRBEN, M., and BURKE, E.K., “Examination timetabling using late acceptance hyper-heuristics,” 2009 IEEE Congr. Evol. Comput. CEC 2009, pp. 997–1004, 2009.

OCHOA, G, M. H. G., “The Cross-domain Heuristic Search Challenge (CHeSC 2011),” 2011. [Online]. Available: http://www.asap.cs.nott.ac.uk/chesc2011/.

OCHOA, G. et al., “HyFlex: A benchmark framework for cross-domain heuristic search,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 7245 LNCS, pp. 136–147, 2012.

OCHOA, G. and N.D.., Search-based Approaches and Hyper-heuristics. 2014.

REGO, C., GAMBOA, D., GLOVER, F., and OSTERMAN, C., “Traveling salesman problem heuristics: Leading methods, implementations and latest advances,” Eur. J. Oper. Res., vol. 211, no. 3, pp. 427–441, 2011.

SUTTON, R. and BARTO, A., Reinforcement Learning, An Introduction. 2010.

SZEPESVARI, C., “Algorithms for Reinforcement Learning,” Synth. Lect. Artif. Intell. Mach. Learn., vol. 4, no. 1, pp. 1–103, 2010.




DOI: http://dx.doi.org/10.25126/jtiik.2021853263