Dalam ilmu komputer dan optimasi matematika, metaheuristik adalah prosedur tingkat tinggi atau heuristik yang dirancang untuk menemukan, menghasilkan, atau memilih heuristik (algoritma pencarian parsial) yang dapat memberikan solusi yang cukup baik untuk masalah optimasi, terutama dengan informasi yang tidak lengkap atau tidak sempurna. atau kapasitas komputasi yang terbatas. Metaheuristik sampel subset dari solusi yang dinyatakan terlalu besar untuk benar-benar dihitung atau dieksplorasi. Metaheuristik dapat membuat asumsi yang relatif sedikit tentang masalah optimasi yang sedang dipecahkan dan mungkin dapat digunakan untuk berbagai masalah.
Dibandingkan dengan algoritma optimasi dan metode iteratif, metaheuristik tidak menjamin bahwa solusi optimal global dapat ditemukan pada beberapa kelas masalah. Banyak metaheuristik menerapkan beberapa bentuk optimasi stokastik, sehingga solusi yang ditemukan bergantung pada himpunan variabel acak yang dihasilkan. Dalam optimasi kombinatorial, dengan mencari lebih dari satu set besar solusi yang layak, metaheuristik sering dapat menemukan solusi yang baik dengan upaya komputasi yang lebih sedikit daripada algoritma optimasi, metode iteratif, atau heuristik sederhana. Dengan demikian, mereka adalah pendekatan yang berguna untuk masalah optimasi. Beberapa buku dan makalah survei telah diterbitkan tentang masalah ini.
Kebanyakan literatur tentang metaheuristik adalah eksperimental di alam, menggambarkan hasil empiris berdasarkan eksperimen komputer dengan algoritma. Tetapi beberapa hasil teoretis formal juga tersedia, seringkali pada konvergensi dan kemungkinan menemukan optimum global. Banyak metode metaheuristik telah diterbitkan dengan klaim kebaruan dan kemanjuran praktis. Sementara bidang ini juga menampilkan penelitian berkualitas tinggi, banyak dari publikasinya memiliki kualitas yang buruk; kekurangan termasuk ketidakjelasan, kurangnya elaborasi konseptual, eksperimen yang buruk, dan ketidaktahuan literatur sebelumnya.
Properti
Ini adalah properti yang menjadi ciri sebagian besar metaheuristik:
- Metaheuristik adalah strategi yang memandu proses pencarian.
- Tujuannya adalah untuk mengeksplorasi ruang pencarian secara efisien untuk menemukan solusi yang mendekati optimal.
- Teknik yang membentuk algoritma metaheuristik berkisar dari prosedur pencarian lokal sederhana hingga proses pembelajaran yang kompleks.
- Algoritma metaheuristik adalah perkiraan dan biasanya non-deterministik.
- Metaheuristik tidak spesifik masalah.
Klasifikasi
Diagram Euler dari klasifikasi yang berbeda dari metaheuristik.
Ada berbagai macam metaheuristik dan sejumlah properti untuk mengklasifikasikannya.
Pencarian lokal vs. pencarian global
Salah satu pendekatannya adalah dengan mengkarakterisasi jenis strategi pencarian. Salah satu jenis strategi pencarian adalah perbaikan pada algoritma pencarian lokal sederhana. Algoritma pencarian lokal yang terkenal adalah metode hill climbing yang digunakan untuk menemukan lokal optimum. Namun, mendaki bukit tidak menjamin menemukan solusi optimal global.
Banyak ide metaheuristik diusulkan untuk meningkatkan heuristik pencarian lokal untuk menemukan solusi yang lebih baik. Metaheuristik tersebut termasuk simulasi anil, pencarian tabu, pencarian lokal berulang, pencarian lingkungan variabel, dan GRASP. Metaheuristik ini dapat diklasifikasikan sebagai metaheuristik pencarian berbasis lokal atau pencarian global.
Metaheuristik pencarian global lainnya yang tidak berbasis pencarian lokal biasanya adalah metaheuristik berbasis populasi. Metaheuristik tersebut meliputi optimasi koloni semut, komputasi evolusioner, optimasi gerombolan partikel, algoritma genetika, dan algoritma optimasi pengendara
Solusi tunggal vs berbasis populasi
Dimensi klasifikasi lainnya adalah solusi tunggal vs pencarian berbasis populasi. Pendekatan solusi tunggal berfokus pada modifikasi dan peningkatan solusi kandidat tunggal; metaheuristik solusi tunggal termasuk simulasi anil, pencarian lokal berulang, pencarian lingkungan variabel, dan pencarian lokal terpandu. Pendekatan berbasis populasi memelihara dan meningkatkan beberapa solusi kandidat, seringkali menggunakan karakteristik populasi untuk memandu pencarian; metaheuristik berbasis populasi meliputi komputasi evolusioner, algoritme genetika, dan optimasi gerombolan partikel. Kategori lain dari metaheuristik adalah Swarm intelligence yang merupakan perilaku kolektif dari agen yang terdesentralisasi dan terorganisir sendiri dalam suatu populasi atau swarm. Pengoptimalan koloni semut, pengoptimalan kawanan partikel, pengoptimalan kognitif sosial adalah contoh dari kategori ini.
Hibridisasi dan algoritma memetika
Sebuah metaheuristik hibrida adalah salah satu yang menggabungkan metaheuristik dengan pendekatan optimasi lainnya, seperti algoritma dari pemrograman matematika, pemrograman kendala, dan pembelajaran mesin. Kedua komponen metaheuristik hibrida dapat berjalan secara bersamaan dan bertukar informasi untuk memandu pencarian.
Di sisi lain, algoritma Memetic mewakili sinergi pendekatan evolusioner atau berbasis populasi dengan pembelajaran individu yang terpisah atau prosedur perbaikan lokal untuk pencarian masalah.
Contoh algoritme memetika adalah penggunaan algoritme pencarian lokal alih-alih operator mutasi dasar dalam algoritme evolusi.
Metaheuristik paralel
Metaheuristik paralel adalah salah satu yang menggunakan teknik pemrograman paralel untuk menjalankan beberapa pencarian metaheuristik secara paralel; ini dapat berkisar dari skema terdistribusi sederhana hingga pencarian bersamaan yang berinteraksi untuk meningkatkan solusi keseluruhan.
Metaheuristik yang terinspirasi alam dan berbasis metafora
Artikel utama: Kecerdasan kawanan dan Daftar metaheuristik yang terinspirasi metafora
Bidang penelitian yang sangat aktif adalah desain metaheuristik yang diilhami alam. Banyak metaheuristik baru-baru ini, terutama algoritma berbasis komputasi evolusioner, terinspirasi oleh sistem alami. Alam bertindak sebagai sumber konsep, mekanisme dan prinsip untuk merancang sistem komputasi buatan untuk menangani masalah komputasi yang kompleks. Metaheuristik tersebut termasuk simulasi anil, algoritma evolusioner, optimasi koloni semut dan optimasi gerombolan partikel. Sejumlah besar metaheuristik yang terinspirasi metafora baru-baru ini mulai menarik kritik di komunitas riset karena menyembunyikan kurangnya kebaruan mereka di balik metafora yang rumit.
Aplikasi
Metaheuristik digunakan untuk optimasi kombinatorial di mana solusi optimal dicari melalui ruang pencarian diskrit. Contoh masalah adalah masalah salesman keliling di mana ruang pencarian solusi kandidat tumbuh lebih cepat daripada eksponensial saat ukuran masalah meningkat, yang membuat pencarian menyeluruh untuk solusi optimal menjadi tidak layak. Selain itu, masalah kombinatorial multidimensi, termasuk sebagian besar masalah desain di bidang teknik seperti pencarian bentuk dan pencarian perilaku, menderita kutukan dimensi, yang juga membuatnya tidak layak untuk pencarian lengkap atau metode analisis. Metaheuristik juga banyak digunakan untuk penjadwalan jobshop dan masalah pemilihan pekerjaan. Metaheuristik populer untuk masalah kombinatorial termasuk simulasi anil oleh Kirkpatrick et al., algoritma genetika oleh Holland et al., pencarian pencar dan tabu search oleh Glover. Tinjauan literatur tentang optimasi metaheuristik, menyarankan bahwa Fred Glover yang menciptakan kata metaheuristik.
Kerangka Pengoptimalan Metaheuristik (MOFs)
MOF dapat didefinisikan sebagai '' seperangkat alat perangkat lunak yang menyediakan implementasi yang benar dan dapat digunakan kembali dari satu set metaheuristik, dan mekanisme dasar untuk mempercepat implementasi heuristik bawahan mitranya (mungkin termasuk pengkodean solusi dan operator khusus teknik) , yang diperlukan untuk memecahkan contoh masalah tertentu menggunakan teknik yang disediakan''.
Ada banyak alat pengoptimalan kandidat yang dapat dianggap sebagai MOF dari berbagai fitur: Comet, EvA2, evolvica, Evolutionary::Algorithm, GAPlayground, jaga, JCLEC, JGAP, jMetal, n-genes, Open Beagle, Opt4j, ParadisEO/EO , Pisa, Pembuat Jam, FOM, Hypercube, HotFrame, Templar, EasyLocal, iOpt, OptQuest, JDEAL, Toolkit Algoritma Pengoptimalan, HeuristicLab, MAFRA, Localizer, GALIB, DREAM, Discropt, MALLBA, MAGMA, Metaheuristics.jl, UOF dan Perencana Opta.
Kontribusi
Banyak metaheuristik yang berbeda ada dan varian baru terus diusulkan. Beberapa kontribusi paling signifikan di bidang ini adalah:
- 1952: Robbins dan Monro bekerja pada metode optimasi stokastik.
- 1954: Barricelli melakukan simulasi pertama dari proses evolusi dan menggunakannya pada masalah optimasi umum.
- 1963: Rastrigin mengusulkan pencarian acak.
- 1965: Matyas mengusulkan optimasi acak.
- 1965: Nelder dan Mead mengusulkan heuristik simpleks, yang ditunjukkan oleh Powell untuk konvergen ke titik non-stasioner pada beberapa masalah.
- 1965: Ingo Rechenberg menemukan algoritma Strategi Evolusi pertama.
- 1966: Fogel dkk. mengusulkan pemrograman evolusioner.
- 1970: Hastings mengusulkan algoritma Metropolis–Hastings.
- 1970: Cavicchio mengusulkan adaptasi parameter kontrol untuk pengoptimal.
- 1970: Kernighan dan Lin mengusulkan metode partisi grafik, terkait dengan pencarian mendalam variabel dan pencarian berbasis larangan (tabu).
- 1975: Holland mengusulkan algoritma genetika.
- 1977: Glover mengusulkan pencarian pencar.
- 1978: Mercer dan Sampson mengusulkan metaplan untuk menyetel parameter pengoptimal dengan menggunakan pengoptimal lain.
- 1980: Smith menjelaskan pemrograman genetik.
- 1983: Kirkpatrick dkk. mengusulkan simulasi anil.
- 1986: Glover mengusulkan pencarian tabu, penyebutan pertama istilah metaheuristik.
- 1989: Moscato mengusulkan algoritma memetika.
- 1990: Moscato dan Fontanari, dan Dueck dan Scheuer, secara independen mengusulkan aturan pembaruan deterministik untuk simulasi anil yang mempercepat pencarian. Hal ini menyebabkan ambang menerima metaheuristik.
- 1992: Dorigo memperkenalkan optimasi koloni semut dalam tesis PhD-nya.
- 1995: Wolpert dan Macready membuktikan teorema tidak ada makan siang gratis.
Sumber Artikel: en.wikipedia.org