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, mengemukakan bahwa Fred Glover-lah yang awalnya menemukan kata “
Metaheuristik” pertama kali.
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
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, 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 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 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, seringkali 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 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.
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
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.
Pranala luar
"Metaheuristics". Scholarpedia.
EU/ME forum for researchers in the field.
