Metaheuristik

Dalam bidang Ilmu Komputer dan Optimasi Matematika, metaheuristik (bahasa Inggris: metaheuristic) didefinisikan sebagai suatu prosedur tingkat tinggi atau pendekatan heuristik yang dirancang agar dapat menemukan, menghasilkan, mengoptimalkan, atau memilih suatu heuristik (algoritma pencarian parsial) yang dapat memberikan solusi yang memadai terhadap suatu permasalahan optimasi atau pemelajaran mesin. Secara khusus, metaheuristik digunakan pada permasalahan yang memiliki keterbatasan informasi atau ketidaklengkapan data, atau dengan kapasitas (sumber daya) komputasi yang terbatas.^[1][2] Metaheuristik memungkinkan pengambilan sampel dari subkumpulan solusi yang dengannya memungkinkan calon-calon solusi tersebut dapat dievaluasi secara efisien. Metaheuristik juga mungkin dapat membuat asumsi dengan jumlah yang relatif sedikit terkait masalah optimasi yang sedang dipecahkan, sehingga ia dapat digunakan untuk berbagai jenis permasalahan.^[3]

Jika dibandingkan dengan algoritma optimasi dan algoritma iteratif, metaheuristik tidak dapat menjamin ditemukannya solusi optimal yang berlaku secara global pada beberapa jenis permasalahan.^[3] Hal ini disebabkan oleh banyaknya metode metaheuristik yang menerapkan optimasi stokastik, sehingga solusi yang ditemukan bergantung pada himpunan variabel acak yang dihasilkan.^[1] Sebagai contoh, pada kasus optimasi kombinatorial, suatu algoritma mencari solusi di dalam himpunan besar yang berisi kandidat-kandidat solusi. Dalam kasus ini, metaheuristik sering kali dapat menemukan solusi yang bagus dengan usaha komputasi yang lebih sedikit, jika dibandingkan dengan algoritma optimasi, metode iteratif, atau heuristik sederhana.^[3] Oleh karena itu, pendekatan metaheuristik ini bermanfaat dalam masalah optimasi ^[1] dan sudah banyak buku dan makalah survei telah diterbitkan mengenai hal tersebut.^[1][3] Terkait dengan awal penemuannya, studi literatur terkait optimasi metaheuristik, ^[4] mengemukakan bahwa Fred Glover-lah yang awalnya menemukan kata “metaheuristik” pertama kali.^[5]

Kebanyakan literatur terkait metaheuristik bersifat eksperimental. Dengan cara mendeskripsikan hasil empiris berdasarkan eksperimen komputer dengan algoritma yang diteliti. Namun, terdapat juga beberapa hasil teoretis formal terkait hal ini yang sering kali mengenai konvergensi dan sejauh mana kemungkinan algoritma tersebut mampu menemukan optimal global.^[3] Banyak metode metaheuristik telah diterbitkan dengan klaim kebaruan (novelty) dan kemanjuran praktis. Meskipun bidang ini banyak menyajikan penelitian dengan kualitas tinggi, tetapi banyak juga publikasi yang berkualitas buruk. Hal ini disebabkan karena ketidakjelasan, kurangnya elaborasi konseptual, eksperimen yang buruk, dan minimnya pengetahuan terhadap literatur sebelumnya. ^[6]

Berikut adalah sifat-sifat yang menjadi ciri sebagian besar metaheuristik:^[3]

• Metaheuristik adalah strategi yang memandu proses pencarian.
• Metaheuristik bertujuan untuk mengeksplorasi ruang pencarian secara efisien untuk menemukan solusi yang mendekati optimal.
• Teknik yang membentuk algoritma metaheuristik berkisar antara prosedur pencarian lokal yang sederhana hingga proses pemelajaran yang kompleks.
• Algoritma metaheuristik bersifat perkiraan dan biasanya bersifat non-deterministik.
• Metaheuristik tidak spesifik terhadap suatu masalah.

Terdapat berbagai jenis metaheuristik ^[1] dan sejumlah karakteristik yang dapat digunakan untuk mengklasifikasikannya.^[3]

Pendekatan pertama yang dapat digunakan untuk mengklasifikasikan algoritma metaheuristik adalah dari sisi strategi pencarian yang diterapkan.^[3] Salah satu jenis strategi pencarian adalah perbaikan terhadap algoritma pencarian lokal sederhana. Salah satu algoritma pencarian lokal yang terkenal adalah algoritma hill climbing yang digunakan untuk mencari solusi optimal lokal. Meskipun begitu, algoritma tersebut tidak dapat menjamin untuk menemukan solusi optimal global.

Banyak ide-ide metode metaheuristik yang diajukan untuk memperbaiki metode heuristik pencarian lokal guna menemukan solusi yang lebih baik. Metaheuristik tersebut mencakup simulated annealing, tabu search, iterated local search, variable neighborhood search, dan GRASP.^[3] Metode-metode metaheuristik ini dapat diklasifikasikan sebagai metaheuristik berbasis pencarian lokal atau pencarian global.

Metaheuristik pencarian global lainnya yang tidak berbasis pencarian lokal biasanya merupakan metaheuristik berbasis populasi. Metaheuristik tersebut meliputi optimasi koloni semut, komputasi evolusioner seperti algoritma genetika atau evolution strategy, particle swarm optimization, rider optimization algorithm ^[8] dan algoritma bacterial foraging.^[9]

Metode klasifikasi lainnya adalah pencarian solusi tunggal atau berbasis populasi.^[3] Pendekatan solusi tunggal berfokus terhadap modifikasi dan perbaikan kualitas kandidat solusi tunggal. Pendekatan ini mencakup algoritma simulated annnealing, iterated local search, variable neighborhood search, dan guided local search. Sedangkan untuk pendekatan berbasis populasi, metode yang dipakai adalah mempertahankan dan memperbaiki kualitas banyak kandidat solusi. Bahkan, sering kali menggunakan karakteristik populasi untuk memandu proses pencarian. Metaheuristik yang menggunakan pendekatan ini mencakup komputasi evolusioner dan particle swarm optimization. Kategori metaheuristik lainnya adalah kecerdasan gerombolan atau swarm intelligence yang merupakan perilaku kolektif dari agen-agen yang terdesentralisasi dan terorganisir secara mandiri dalam suatu populasi atau gerombolan. Optimasi koloni semut, ^[10] particle swarm optimization, social cognitive optimization, dan algoritma bacterial foraging ^[9] adalah contoh dari kategori ini.

Metaheuristik hibrid adalah metode yang menggabungkan metaheuristik dengan pendekatan optimasi lainnya, seperti algoritma pemrograman matematika, constraint programming, dan pembelajaran mesin. Kedua komponen metaheuristik hibrid dapat berjalan secara bersamaan dan dapat bertukar informasi untuk memandu proses pencarian.

Di sisi lain, algoritma Memetika adalah metode metaheuristik yang merepresentasikan sinergi pendekatan evolusioner atau pendekatan berbasis populasi dengan pembelajaran individu yang terpisah atau prosedur perbaikan lokal untuk pencarian solusi di suatu masalah. Contoh algoritma memetik adalah penggunaan algoritma pencarian lokal sebagai pengganti atau tambahan operator mutasi dasar di dalam algoritma evolusioner.

Metaheuristik paralel adalah metode metaheuristik yang menggunakan teknik-teknik pemrograman paralel untuk menjalankan beberapa pencarian metaheuristik secara paralel; ini dapat berkisar dari skema terdistribusi sederhana hingga pencarian yang dilakukan secara bersamaan yang berinteraksi untuk meningkatkan solusi secara keseluruhan.

Bidang penelitian yang sangat aktif di bidang ini adalah desain metaheuristik yang terinspirasi dari alam. Banyak metaheuristik terkini, khususnya algoritma berbasis komputasi evolusioner, terinspirasi oleh alam. Dengan pendekatan ini, alam bertindak sebagai sumber konsep, mekanisme, dan prinsip yang digunakan untuk merancang sistem komputasi buatan untuk menangani masalah komputasi yang kompleks. Metaheuristik yang menggunakan pendekatan ini mencakup simulated annealing, algoritma evolusioner, optimasi koloni semut dan particle swarm optimization. Sebagian besar metaheuristik yang berbasis metafora, baru-baru ini mulai menarik kritik dari komunitas riset karena menyembunyikan kurangnya pembaruan (novelty) di balik metafora yang rumit.^[6]

Metaheuristik adalah pendekatan yang digunakan untuk menyelesaikan berbagai jenis masalah optimasi, termasuk masalah yang melibatkan variabel kontinu, variabel bilangan bulat, atau kombinasi keduanya. Dalam konteks optimasi kombinatorial, berfokus pada pencarian solusi optimal di dalam ruang pencarian yang terdiri dari pilihan diskrit. Sebagai contoh, kita dapat mempertimbangkan permasalahan penjual keliling yang kita harus mencari rute terbaik untuk mengunjungi sejumlah lokasi dengan efisiensi terbaik. Masalah ini memungkinkan bertambahnya jumlah kemungkinan solusi secara eksponensial seiring dengan bertambahnya ukuran permasalahan (dalam kasus ini adalah jumlah kota dan rute yang mungkin). Dengan kata lain, mencari solusi optimal dengan mengevaluasi setiap kemungkinan secara menyeluruh menjadi tidak mungkin atau tidak efisien seiring dengan bertambahnya kompleksitas masalah. Selain itu, masalah kombinatorial multidimensi, termasuk sebagian besar masalah desain di bidang teknik ^{[11] [12] [13]} yang dalam rangka mencari bentuk atau perilaku optimal yang melibatkan ruang pencarian yang sangat besar sehinga mengalami kutukan dimensi (curse of dimensionality), yang juga membuatnya tidak layak untuk pencarian capai (exhaustive search) atau metode analitis.

Metaheuristik juga sering kali digunakan untuk menyelesaikan masalah penjadwalan yang salah satu contoh klasiknya adalah penjadwalan job shop. Penjadwalan job shop melibatkan penentuan urutan langkah kerja untuk setiap pekerjaan di stasiun pemrosesan yang sedemikian sehingga semua pekerjaan diselesaikan tepat waktu dan dalam waktu sesingkat mungkin.^{[14] [15]} Dalam praktiknya, seringkali terdapat pembatasan seperti batasan urutan langkah kerja dengan alur kerja yang telah ditentukan,^[16] atau batasan pemanfaatan sumber daya, misalnya, dalam hal penggunaan energi.^{[17] [18]} Metaheuristik banyak digunakan untuk masalah kombinatorial, termasuk algoritma genetika oleh Holland et al., scatter search, dan pencarian tabu oleh Glover.

Pengaplikasian besar lainnya dari metaheuristik adalah dalam tugas pengoptimalan di ruang pencarian bilangan bulat kontinu atau campuran. Terdapat berbagai aplikasi di bidang optimasi desain ^{[19] [20] [21]} atau berbagai tugas keteknikan.^{[22] [23] [24]} Salah satu contoh yang mencakup keduanya adalah perencanaan jalur gerak yang optimal untuk robot industri.^{[25] [26]}

Kerangka Kerja Optimasi Metaheuristik atau Metaheuristic Optimization Frameworks (MOF) dapat didefinisikan sebagai ''seperangkat perangkat lunak yang menyediakan implementasi yang benar dan dapat digunakan kembali dari serangkaian metaheuristik, dan mekanisme-mekanisme dasar untuk mempercepat implementasi heuristik bawahan (mungkin termasuk pengkodean solusi dan operator teknik tertentu), yang diperlukan untuk menyelesaikan suatu masalah tertentu dengan menggunakan teknik yang telah disediakan''.

Terdapat banyak kandidat alat optimzasi yang dapat dianggap sebagai MOF dengan berbagai macam fitur: Comet, EvA2, evolvica, Evolutionary::Algorithm, GAPlayground, jaga, JCLEC, JGAP, jMetal, n-genes, Open Beagle, Opt4j, ParadisEO/EO, Pisa, Watchmaker, FOM, Hypercube, HotFrame, Templar, EasyLocal, iOpt, OptQuest, JDEAL, Optimization Algorithm Toolkit, HeuristicLab, MAFRA, Localizer, GALIB, DREAM, Discropt, MALLBA, MAGMA, Metaheuristics.jl, UOF, dan OptaPlanner.

Beberapa kontribusi paling signifikan di bidang metaheuristik mencakup pengembangan berbagai algoritma dan pendekatan yang telah memberikan dampak besar pada penyelesaian masalah optimasi yang kompleks. Berikut adalah beberapa kontribusi signifikan di bidang ini:

• 1952: Penelitian Robbins dan Monro dalam metode optimasi stokastik.
• 1954: Barricelli melakukan simulasi pertama dari proses evolusi dan menggunakannya pada masalah optimasi umum.
• 1963: Rastrigin mengusulkan pencarian acak atau random search.
• 1965: Matyas mengusulkan optimasi acak (random optimization).
• 1965: Nelder dan Mead mengusulkan heuristik simpleks, yang kemudian ditunjukkan oleh Powell bahwa algoritma tersebut dapat konvergen ke titik-titik non-stasioner pada beberapa masalah.
• 1965: Ingo Rechenberg menemukan algoritma Strategi Evolusi yang pertama.
• 1966: Fogel dkk. mengusulkan pemrograman evolusioner .
• 1970: Hastings mengusulkan algoritma Metropolis–Hastings .
• 1970: Cavicchio mengusulkan adaptasi parameter kontrol untuk pengoptimalisasi.
• 1970: Kernighan dan Lin mengusulkan metode partisi grafik, terkait dengan pencarian kedalaman variabel dan pencarian berbasis larangan (tabu) .
• 1975: Holland mengusulkan algoritma genetika .
• 1977: Glover mengusulkan scatter search
• 1978: Mercer dan Sampson mengusulkan metaplan untuk menyetel parameter pengoptimal dengan menggunakan pengoptimal lain.
• 1980: Smith mengemukakan genetic programming.
• 1983: Kirkpatrick dkk. mengusulkan simulated annealing.
• 1986: Glover mengusulkan tabu search, penyebutan pertama istilah metaheuristik .
• 1989: Moscato mengusulkan algoritma memetika .
• 1990: Moscato dan Fontanari, ^[27] dan Dueck dan Scheuer, ^[28] secara independen mengusulkan aturan pembaruan deterministik untuk simulated annealing yang dapat mempercepat proses pencarian. Hal ini menyebabkan penentuan ambang batas penerimaan suatu metaheuristik.
• 1992: Dorigo memperkenalkan optimasi koloni semut dalam tesis PhD-nya. ^[10]
• 1995: Wolpert dan Macready membuktikan teorema no free lunch .

• Pencarian stokastik
• Optimasi meta
• Mateuristik
• Hiper-heuristik
• Kecerdasan gerombolan
• Algoritma evolusioner dan khususnya algoritma genetika, pemrograman genetik, atau strategi evolusi.
• Simulated annealing
• Pemodelan tenaga kerja

1. ^ ^{a b c d e} Bianchi, Leonora; Marco Dorigo; Luca Maria Gambardella; Walter J. Gutjahr (2009). "A survey on metaheuristics for stochastic combinatorial optimization" (PDF). Natural Computing. 8 (2): 239–287. doi:10.1007/s11047-008-9098-4.  Parameter |s2cid= yang tidak diketahui akan diabaikan (bantuan)
2. ^ R. Balamurugan; A.M. Natarajan; K. Premalatha (2015). "Stellar-Mass Black Hole Optimization for Biclustering Microarray Gene Expression Data". Applied Artificial Intelligence. 29 (4): 353–381. doi:10.1080/08839514.2015.1016391 .  Parameter |s2cid= yang tidak diketahui akan diabaikan (bantuan)
3. ^ ^{a b c d e f g h i j} Blum, C.; Roli, A. (2003). "Metaheuristics in combinatorial optimization: Overview and conceptual comparison". 35 (3). ACM Computing Surveys: 268–308. 
4. ^ X. S. Yang, Metaheuristic optimization, Scholarpedia, 6(8):11472 (2011).
5. ^ Glover F., (1986).
6. ^ ^{a b} Sörensen, Kenneth (2015). "Metaheuristics—the metaphor exposed" (PDF). International Transactions in Operational Research. 22: 3–18. doi:10.1111/itor.12001. Diarsipkan dari versi asli (PDF) tanggal 2013-11-02.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
7. ^ Classification of metaheuristics
8. ^ D, Binu (2019). "RideNN: A New Rider Optimization Algorithm-Based Neural Network for Fault Diagnosis in Analog Circuits". IEEE Transactions on Instrumentation and Measurement. 68 (1): 2–26. Bibcode:2019ITIM...68....2B. doi:10.1109/TIM.2018.2836058. 
9. ^ ^{a b} Pang, Shinsiong; Chen, Mu-Chen (2023-06-01). "Optimize railway crew scheduling by using modified bacterial foraging algorithm". Computers & Industrial Engineering (dalam bahasa Inggris). 180: 109218. doi:10.1016/j.cie.2023.109218. ISSN 0360-8352. 
10. ^ ^{a b} M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.
11. ^ Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II.
12. ^ Ganesan, T.; Elamvazuthi, I.; Ku Shaari, Ku Zilati; Vasant, P. (2013-03-01). "Swarm intelligence and gravitational search algorithm for multi-objective optimization of synthesis gas production". Applied Energy. 103: 368–374. doi:10.1016/j.apenergy.2012.09.059. 
13. ^ Ganesan, T.; Elamvazuthi, I.; Vasant, P. (2011-11-01). "Evolutionary normal-boundary intersection (ENBI) method for multi-objective optimization of green sand mould system". 2011 IEEE International Conference on Control System, Computing and Engineering. hlm. 86–91. doi:10.1109/ICCSCE.2011.6190501. ISBN 978-1-4577-1642-3. 
14. ^ Jarboui, Bassem; Siarry, Patrick; Teghem, Jacques, ed. (2013). Metaheuristics for production scheduling. Automation - control and industrial engineering series. London: ISTE. ISBN 978-1-84821-497-2. 
15. ^ Xhafa, Fatos; Abraham, Ajith, ed. (2008). Metaheuristics for Scheduling in Industrial and Manufacturing Applications. Studies in Computational Intelligence (dalam bahasa Inggris). 128. Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-540-78985-7. ISBN 978-3-540-78984-0. 
16. ^ Jakob, Wilfried; Strack, Sylvia; Quinte, Alexander; Bengel, Günther; Stucky, Karl-Uwe; Süß, Wolfgang (2013-04-22). "Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing". Algorithms (dalam bahasa Inggris). 6 (2): 245–277. doi:10.3390/a6020245. ISSN 1999-4893. 
17. ^ Kizilay, Damla; Tasgetiren, M. Fatih; Pan, Quan-Ke; Süer, Gürsel (2019). "An Ensemble of Meta-Heuristics for the Energy-Efficient Blocking Flowshop Scheduling Problem". Procedia Manufacturing (dalam bahasa Inggris). 39: 1177–1184. doi:10.1016/j.promfg.2020.01.352. 
18. ^ Grosch, Benedikt; Weitzel, Timm; Panten, Niklas; Abele, Eberhard (2019). "A metaheuristic for energy adaptive production scheduling with multiple energy carriers and its implementation in a real production system". Procedia CIRP (dalam bahasa Inggris). 80: 203–208. doi:10.1016/j.procir.2019.01.043. 
19. ^ Gupta, Shubham; Abderazek, Hammoudi; Yıldız, Betül Sultan; Yildiz, Ali Riza; Mirjalili, Seyedali; Sait, Sadiq M. (2021). "Comparison of metaheuristic optimization algorithms for solving constrained mechanical design optimization problems". Expert Systems with Applications (dalam bahasa Inggris). 183: 115351. doi:10.1016/j.eswa.2021.115351. 
20. ^ Quinte, Alexander; Jakob, Wilfried; Scherer, Klaus-Peter; Eggert, Horst (2002), Laudon, Matthew, ed., "Optimization of a Micro Actuator Plate Using Evolutionary Algorithms and Simulation Based on Discrete Element Methods", International Conference on Modeling and Simulation of Microsystems: MSM 2002, Cambridge, Mass: Computational Publications: 192–197, ISBN 978-0-9708275-7-9 
21. ^ Parmee, I. C. (1997), Dasgupta, Dipankar; Michalewicz, Zbigniew, ed., "Strategies for the Integration of Evolutionary/Adaptive Search with the Engineering Design Process", Evolutionary Algorithms in Engineering Applications (dalam bahasa Inggris), Berlin, Heidelberg: Springer: 453–477, doi:10.1007/978-3-662-03423-1_25, ISBN 978-3-642-08282-5, diakses tanggal 2023-07-17 
22. ^ Valadi, Jayaraman; Siarry, Patrick, ed. (2014). Applications of Metaheuristics in Process Engineering (dalam bahasa Inggris). Cham: Springer International Publishing. doi:10.1007/978-3-319-06508-3. ISBN 978-3-319-06507-6. 
23. ^ Sanchez, Ernesto; Squillero, Giovanni; Tonda, Alberto (2012). Industrial Applications of Evolutionary Algorithms. Intelligent Systems Reference Library (dalam bahasa Inggris). 34. Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-27467-1. ISBN 978-3-642-27466-4. 
24. ^ Akan, Taymaz; Anter, Ahmed M.; Etaner-Uyar, A. Şima; Oliva, Diego, ed. (2023). Engineering Applications of Modern Metaheuristics. Studies in Computational Intelligence (dalam bahasa Inggris). 1069. Cham: Springer International Publishing. doi:10.1007/978-3-031-16832-1. ISBN 978-3-031-16831-4. 
25. ^ Blume, Christian (2000), Cagnoni, Stefano, ed., "Optimized Collision Free Robot Move Statement Generation by the Evolutionary Software GLEAM", Real-World Applications of Evolutionary Computing, Lecture Notes in Computer Science (dalam bahasa Inggris), Berlin, Heidelberg: Springer, 1803: 330–341, doi:10.1007/3-540-45561-2_32, ISBN 978-3-540-67353-8, diakses tanggal 2023-07-17 
26. ^ Pholdee, Nantiwat; Bureerat, Sujin (2018-12-14), "Multiobjective Trajectory Planning of a 6D Robot based on Multiobjective Meta Heuristic Search", International Conference on Network, Communication and Computing (ICNCC 2018) (dalam bahasa Inggris), ACM: 352–356, doi:10.1145/3301326.3301356, ISBN 978-1-4503-6553-6 
27. ^ Moscato, P.; Fontanari, J.F. (1990), "Stochastic versus deterministic update in simulated annealing", Physics Letters A, 146 (4): 204–208, Bibcode:1990PhLA..146..204M, doi:10.1016/0375-9601(90)90166-L 
28. ^ Dueck, G.; Scheuer, T. (1990), "Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing", Journal of Computational Physics, 90 (1): 161–175, Bibcode:1990JCoPh..90..161D, doi:10.1016/0021-9991(90)90201-B, ISSN 0021-9991 

• Sörensen, Kenneth; Sevaux, Marc; Glover, Fred (2017-01-16). "A History of Metaheuristics" (PDF). Dalam Martí, Rafael; Panos, Pardalos; Resende, Mauricio. Handbook of Heuristics. Springer. ISBN 978-3-319-07123-7. 

• Ashish Sharma (2022), Nature Inspired Algorithms with Randomized Hypercomputational Perspective. Information Sciences. https://doi.org/10.1016/j.ins.2022.05.020.

• "Metaheuristics". Scholarpedia. 
• EU/ME forum for researchers in the field.