Penerapan Hiperheuristik Berbasis Metode Simulated Annealing untuk Penyelesaian Permasalahan Optimasi Lintas Domain
(1) Institut Teknologi Sepuluh Nopember
(2) Institut Teknologi Sepuluh Nopember
(3) Institut Teknologi Sepuluh Nopember
(*) Corresponding Author
Abstrak
Permasalahan optimasi lintas domain merupakan permasalahan optimasi yang sangat rumit karena masing-masing permasalahan mempunyai karakteristik yang berbeda. Penyelesaian terhadap permasalahan optimasi lintas domain tersebut melibatkan metode pencarian komputasional untuk memperoleh hasil yang mendekati optimal. Beberapa peneliti terdahulu mengembangkan metode hiperheutistik untuk memperoleh solusi generik yang diharapkan mampu memberikan hasil yang mendekati optimal. Hasil penelitian terdahulu mengidikasikan bahwa strategi hiperheuristik yang lebih baik diperlukan guna memperoleh solusi yang mendekati optimal untuk lintas domain permasalahan. Dalam penelitian ini, upaya untuk mendapatkan solusi generik yang mendekati optimal terhadap permasalahan optimasi lintas domain dilakukan dengan mengembangkan strategi pencarian komputasional pada tatanan High Level Heuristics (HLH) dalam mengatur proses seleksi pada rangkaian Low Level Heuristics (LLH) kemudian melakukan mekanisme penerimaan solusi. Penelitian ini menguji metode Simulated Annealing (SA) sebagai mekanisme penerimaan solusi dalam tatanan HLH agar dapat menghasilkan solusi mendekati optimal pada berbagai domain masalah optimasi yang dikombinasikan dengan metode seleksi LLH. Penelitian ini melakukan eksperimen untuk menentukan nilai parameter yang tepat untuk mengotomatiskan parameter kontrol SA dalam menyelesaikan permasalahan optimasi lintas domain. Strategi yang digunakan dalam penelitian ini diuji coba untuk menyelesaikan enam permasalahan optimasi domain yang berbeda yang diperoleh dari HyFlex, yaitu Satisfiability (SAT), Bin Packing, Flow Shop, Personnel Scheduling, Travelling Salesmen Problem (TSP), dan Vehicle Routing Problem (VRP). Dari hasil pengujian terhadap enam permasalahan optimasi tersebut, nilai parameter untuk suhu awal T adalah 100 dan faktor penurunan suhu α adalah 0,995.
Kata Kunci
Teks Lengkap:
PDFReferensi
[1] G. Lindfield dan J. Penny, “An Introduction to Optimization,” in Introduction to Nature-Inspired Optimization, Elsevier, 2017, pp. 1–18.
[2] M. Gendreau dan J.-Y. Potvin, Eds., Handbook of metaheuristics, 2. ed. New York, NY: Springer, 2010.
[3] E. K. Burke, Search methodologies. New York: Springer, 2013.
[4] 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.
[5] 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.
[6] R. Bai dan G. Kendall, “An Investigation of Automated Planograms Using a Simulated Annealing Based Hyper-Heuristic,” in Metaheuristics: Progress as Real Problem Solvers, vol. 32, T. Ibaraki, K. Nonobe, and M. Yagiura, Eds. New York: Springer-Verlag, 2005, pp. 87–108.
[7] B. Bilgin, E. Özcan, dan E. E. Korkmaz, “An Experimental Study on Hyper-heuristics and Exam Timetabling,” in Practice and Theory of Automated Timetabling VI, vol. 3867, E. K. Burke and H. Rudová, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 394–412.
[8] K. A. Dowsland, E. Soubeiga, dan E. Burke, “A simulated annealing based hyperheuristic for determining shipper sizes for storage and transportation,” Eur. J. Oper. Res., vol. 179, no. 3, pp. 759–774, Jun. 2007.
[9] 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.
[10] 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.
[11] R. Qu, “Meta-heurisitic Agorithm.” Apr-2016.
[12] M. Hyde, G. Ochoa, J. A. Vazquez-Rodriguez, and T. Curtois, “A HyFlex Module for the MAX-SAT Problem,” p. 4.
[13] M. Hyde, G. Ochoa, J. A. Vazquez-Rodriguez, and T. Curtois, “A HyFlex Module for the One Dimensional Bin Packing Problem,” p. 5.
[14] J. A. Vazquez-Rodrıguez, G. Ochoa, T. Curtois, and M. Hyde, “A HyFlex Module for the Permutation Flow Shop Problem,” p. 4.
[15] T. Curtois, G. Ochoa, M. Hyde, and J. A. Vázquez-Rodríguez, “A HyFlex Module for the Personnel Scheduling Problem,” p. 12.
[16] A. Lehrbaum, “A New Hyperheuristic Algorithm for Cross-Domain Search Problems,” in Learning and Intelligent Optimization, vol. 7219, Y. Hamadi and M. Schoenauer, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 437–442.
[17] E. K. Burke et al., “The cross-domain heuristic search challenge–an international research competition,” in International Conference on Learning and Intelligent Optimization, 2011, pp. 631–634.
Artikel Statistik
PDF telah dilihat : 1098 kali
Refbacks
- Saat ini tidak ada refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
 | Alamat Redaksi : Departemen Sistem Informasi, Fakultas Teknologi Informasi Universitas Andalas Kampus Limau Manis, Padang 25163, Sumatera Barat email: teknosi@fti.unand.ac.id |
Jumlah Pengunjung :
This work by JSI-Unand and licensed under a CC BY-SA 4.0 International License.