Penerapan Hiperheuristik Berbasis Metode Simulated Annealing untuk Penyelesaian Permasalahan Optimasi Lintas Domain

Authors

  • Nisa Dwi Angresti Institut Teknologi Sepuluh Nopember
  • Arif Djunaidy Institut Teknologi Sepuluh Nopember
  • Ahmad Mukhlason Institut Teknologi Sepuluh Nopember

DOI:

https://doi.org/10.25077/TEKNOSI.v5i1.2019.33-40

Keywords:

Hiperheuristik, Optimasi, Pencarian Komputasional, Simulated Annealing, HyFlex

Abstract

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.

References

[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.

Downloads

Submitted

2017-12-18

Accepted

2019-01-28

Published

2019-04-30

How to Cite

[1]
N. D. Angresti, A. Djunaidy, and A. Mukhlason, “Penerapan Hiperheuristik Berbasis Metode Simulated Annealing untuk Penyelesaian Permasalahan Optimasi Lintas Domain”, TEKNOSI, vol. 5, no. 1, pp. 33–40, Apr. 2019.

Issue

Vol. 5 No. 1 (2019): April 2019

Section

Articles

License

Hak cipta untuk artikel ini ditransfer ke Jurnal Nasional Teknologi dan Sistem Informasi (TEKNOSI) jika dan ketika artikel diterima untuk publikasi. Yang bertanda tangan di bawah ini dengan ini mentransfer setiap dan semua hak di dalam dan ke kertas termasuk tanpa batasan semua hak cipta untuk TEKNOSI. Yang bertanda tangan di bawah ini dengan ini menyatakan dan menjamin bahwa makalah tersebut asli dan bahwa ia adalah pembuat makalah, kecuali untuk bahan yang secara jelas diidentifikasi sebagai sumber aslinya, dengan pemberitahuan izin dari pemilik hak cipta jika diperlukan. Yang bertanda tangan di bawah ini menyatakan bahwa ia memiliki kekuatan dan wewenang untuk membuat dan melaksanakan penugasan ini.

Kami menyatakan bahwa:

  1. Makalah ini belum diterbitkan dalam bentuk yang sama di tempat lain.
  2. Makalah ini tidak akan dikirimkan di tempat lain untuk publikasi sebelum penerimaan/penolakan oleh Jurnal ini
  3. Izin hak cipta diperoleh untuk materi yang diterbitkan di tempat lain dan yang memerlukan izin ini untuk reproduksi.

 Selanjutnya, Saya/kami dengan ini mentransfer hak publikasi yang tidak terbatas dari makalah yang disebutkan di atas secara keseluruhan kepada TEKNOSI. Transfer hak cipta mencakup hak untuk mereproduksi dan mendistribusikan artikel, termasuk cetak ulang, terjemahan, reproduksi foto, mikroform, bentuk elektronik (offline, online) atau reproduksi lain yang serupa.

Penulis yang sesuai menandatangani dan menerima tanggung jawab untuk merilis materi ini atas nama setiap dan semua penulis bersama. Perjanjian ini harus ditandatangani oleh setidaknya salah satu penulis yang telah memperoleh persetujuan dari rekan penulis jika berlaku. Setelah pengajuan perjanjian ini ditandatangani oleh penulis yang sesuai, perubahan kepengarangan atau dalam urutan penulis yang tercantum tidak akan diterima.

Hak / Syarat dan Ketentuan yang dipertahankan :

  1. Penulis memiliki semua hak kepemilikan dalam setiap proses, prosedur, atau artikel manufaktur yang dijelaskan dalam Karya ini.
  2. Penulis dapat mereproduksi atau mengotorisasi orang lain untuk mereproduksi karya  ini atau karya turunannya untuk penggunaan pribadi penulis atau untuk penggunaan perusahaan, dengan ketentuan bahwa sumber dan menyatakan hak cipta dimiliki TEKNOSI, salinan tidak digunakan dengan cara apa pun yang menyiratkan pengesahan TEKNOSI atas suatu produk atau layanan dari pihak mana pun, dan salinannya sendiri tidak ditawarkan untuk dijual.
  3. Meskipun penulis diizinkan untuk menggunakan kembali semua atau sebagian dari karya ini dalam karya lain, ini tidak termasuk mengabulkan permintaan pihak ketiga untuk mencetak ulang, menerbitkan ulang, atau jenis penggunaan ulang lainnya.

Similar Articles

> >> 

You may also start an advanced similarity search for this article.