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

Jika dibandingkan dengan algoritma optimasi dan algoritma iteratif, metaheuristik tidak dapat menjamin ditemukannya solusi optimal yang berlaku secara global pada beberapa jenis permasalahan. Hal ini disebabkan oleh banyaknya metode metaheuristik yang menerapkan optimasi stokastik, sehingga solusi yang ditemukan bergantung pada himpunan variabel acak yang dihasilkan. 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. Oleh karena itu, pendekatan metaheuristik ini bermanfaat dalam masalah optimasi  dan sudah banyak buku dan makalah survei telah diterbitkan mengenai hal tersebut. Terkait dengan awal penemuannya, studi literatur terkait optimasi metaheuristik, X. S. Yang, Metaheuristic optimization, Scholarpedia, 6(8):11472 (2011). mengemukakan bahwa Fred Glover-lah yang awalnya menemukan kata “metaheuristik” pertama kali.Glover F., (1986). 

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

 Sifat-sifat 
Berikut adalah sifat-sifat yang menjadi ciri sebagian besar metaheuristik:  

 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.

 Klasifikasi 
jmpl| Diagram Euler tentang klasifikasi metaheuristik yang berbeda. Classification of metaheuristics
Terdapat berbagai jenis metaheuristik  dan sejumlah karakteristik yang dapat digunakan untuk mengklasifikasikannya.  

 Pencarian lokal vs. pencarian global 
Pendekatan pertama yang dapat digunakan untuk mengklasifikasikan algoritma metaheuristik adalah dari sisi strategi pencarian yang diterapkan. 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. 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  dan algoritma bacterial foraging.

 Solusi tunggal vs. berbasis populasi 
Metode klasifikasi lainnya adalah pencarian solusi tunggal atau berbasis populasi.  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, M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992. particle swarm optimization, social cognitive optimization, dan algoritma bacterial foraging  adalah contoh dari kategori ini.

 Algoritma hibridisasi dan memetika 
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 
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.

 Metaheuristik yang terinspirasi dari alam dan berbasis metafora 

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.

 Aplikasi 
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 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.     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.  Dalam praktiknya, sering kali terdapat pembatasan seperti batasan urutan langkah kerja dengan alur kerja yang telah ditentukan, atau batasan pemanfaatan sumber daya, misalnya, dalam hal penggunaan energi.  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    atau berbagai tugas keteknikan.   Salah satu contoh yang mencakup keduanya adalah perencanaan jalur gerak yang optimal untuk robot industri. 

 Kerangka Kerja Optimasi Metaheuristik 
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.

 Kontribusi 
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,  dan Dueck dan Scheuer,  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. M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.
 1995: Wolpert dan Macready membuktikan teorema no free lunch .    

 Lihat juga 

 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

 Referensi 

 Bacaan lebih lanjut 



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


 EU/ME forum for researchers in the field.
Kategori:Pemeliharaan CS1: Banyak nama: authors list