Metaheuristik
Metaheuristik adalah prosedur tingkat tinggi atau heuristik dalam ilmu komputer dan optimasi matematika yang digunakan untuk menemukan, menghasilkan, atau memilih heuristik yang dapat memberikan solusi yang cukup baik terhadap masalah optimasi. Hal ini sangat berguna ketika informasi tersedia sebagian atau tidak lengkap atau daya komputasi terbatas.
Metaheuristik bekerja dengan sampel dari subkumpulan solusi yang terlalu besar untuk dihitung atau diperiksa sepenuhnya. Meskipun tidak menjamin solusi optimal secara global, metaheuristik seringkali dapat menemukan solusi yang baik dengan upaya komputasi yang lebih sedikit dibandingkan algoritma optimasi, metode iteratif, atau heuristik sederhana. Sebagian besar literatur dan penelitian di bidang ini bersifat eksperimental dan menggunakan eksperimen komputer untuk mengevaluasi kinerja algoritma.Meskipun banyak metode metaheuristik yang mengklaim kebaruan dan efektivitas praktis, banyak literatur juga memiliki kekurangan, seperti: B. Ketidakjelasan, kurangnya pengembangan konseptual, eksperimen yang buruk, dan kurangnya pemahaman terhadap literatur sebelumnya.
Properti
Metaheuristik mencirikan sejumlah properti khas yang membentuk identitasnya. Pertama, metaheuristik adalah strategi yang mengarahkan proses pencarian, bertujuan untuk menjelajahi ruang pencarian dengan efisien guna menemukan solusi yang mendekati optimal. Kedua, teknik yang membentuk algoritma metaheuristik dapat bervariasi dari prosedur pencarian lokal yang sederhana hingga proses pembelajaran yang kompleks. Ketiga, algoritma metaheuristik bersifat perkiraan dan biasanya non-deterministik, menunjukkan bahwa solusi yang dihasilkan tidak selalu sama dalam setiap percobaan. Terakhir, metaheuristik tidak spesifik terhadap suatu masalah tertentu, menjadikannya dapat diadaptasi untuk berbagai jenis masalah optimasi. Dengan kombinasi properti ini, metaheuristik menjadi pendekatan yang fleksibel dan kuat untuk menangani masalah optimasi yang kompleks.
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 dengan meningkatkan algoritma pencarian lokal sederhana. Algoritma pencarian lokal yang terkenal adalah metode pendakian bukit, yang digunakan untuk mencari nilai maksimum lokal. Namun, mendaki gunung bukanlah jaminan menemukan solusi optimal secara global.
Banyak ide metaheuristik telah diajukan untuk meningkatkan heuristik pencarian lokal dan menemukan solusi yang lebih baik.Metaheuristik ini mencakup simulasi anil, pencarian tabu, pencarian lokal berulang, pencarian lingkungan variabel, dan GRASP. Metaheuristik ini dapat diklasifikasikan sebagai metaheuristik pencarian lokal atau metaheuristik pencarian global.Metaheuristik lain untuk penelusuran global yang tidak didasarkan pada penelusuran lokal biasanya adalah metaheuristik berbasis populasi. Metaheuristik tersebut meliputi optimasi koloni semut, perhitungan evolusi, optimasi kawanan partikel, algoritma genetika, dan algoritma optimasi pengendara.
Solusi tunggal vs berbasis populasi
Dimensi klasifikasi lainnya adalah solusi tunggal versus pencarian populasi. Pendekatan solusi tunggal berfokus pada perubahan dan peningkatan solusi tunggal. Metaheuristik solusi tunggal mencakup simulasi anil, pencarian lokal berulang, pencarian lingkungan variabel, dan pencarian lokal terpandu. Pendekatan berbasis populasi memupuk dan menyempurnakan banyak solusi potensial, sering kali menggunakan karakteristik populasi untuk memandu pencarian. Metaheuristik populasimencakup perhitungan evolusi, algoritma genetika, dan optimasi kawanan partikel. Kategori metaheuristik lainnya adalah kecerdasan gerombolan, yang merupakan perilaku kolektif dari agen-agen yang terdesentralisasi dan terorganisir sendiri dalam suatu populasi atau kawanan. Contoh kategori ini mencakup optimasi koloni semut, optimasi kawanan partikel, dan optimasi kognitif sosial.
Hibridisasi dan algoritma matematika
Metaheuristik hibrid menggabungkan metaheuristik dengan pendekatan pengoptimalan lainnya, seperti algoritma pemrograman matematika, pemrograman kendala, dan pembelajaran mesin. Kedua elemen metaheuristik hybrid dapat bekerja secara bersamaan dan bertukar informasi untuk memandu pencarian.
Di sisi lain, algoritma memetika mewakili sinergi pendekatan evolusioner atau demografis dengan pembelajaran individu yang terpisah atau metode perbaikan lokal untuk menemukan masalah.Contoh algoritma memetika adalah penggunaan algoritma pencarian lokal sebagai pengganti operator mutasi dasar dalam algoritma evolusi.
Metaheuristik paralel
Metaheuristik paralel adalah metaheuristik yang menggunakan teknik pemrograman paralel untuk melakukan beberapa pencarian metaheuristik secara paralel; Hal ini dapat mencakup pola pencarian terdistribusi atau bersamaan yang bekerja sama untuk meningkatkan solusi keseluruhan.
Metaheuristik yang terinspirasi alam dan berbasis metafora
Bidang penelitian yang sangat aktif adalah desain metaheuristik yang terinspirasi dari alam. Banyak metaheuristik modern, terutama algoritma yang didasarkan pada komputasi evolusioner, terinspirasi oleh sistem alam. Alam adalah sumber konsep, mekanisme, dan prinsip desain sistem komputasi buatan untuk memecahkan masalah komputasi yang kompleks. Metaheuristik ini mencakup simulasi anil, algoritma evolusi, optimasi koloni semut, dan optimasi kawanan partikel. Banyak metaheuristik yang terinspirasi olehMetafora baru-baru ini dikritik oleh komunitas riset karena menyembunyikan kurangnya kebaruan di balik metafora yang kompleks.
Aplikasi
Metaheuristik digunakan untuk optimasi kombinatorial, yang mencari solusi optimal dalam ruang pencarian diskrit. Contoh masalahnya adalah masalah travelling salesman, dimana ruang pencarian untuk solusi potensial tumbuh lebih cepat daripada eksponensial seiring dengan bertambahnya ukuran masalah, sehingga pencarian komprehensif untuk solusi optimal menjadi tidak mungkin. Selain itu, masalah kombinatorial berdimensi tinggi, termasuk sebagian besar masalah desain teknis seperti pencarian bentuk dan pencarian perilaku, mengalami kutukan dimensi, yang juga membuatnya tidak dapat digunakan untuk metode pencarian atau analisis yang komprehensif. Metaheuristik juga banyak digunakan dalam masalah penjadwalan tugas dan seleksi. Salah satu metaheuristik yang populer untuk masalah kombinatorial adalah Simulated Annealing oleh Kirkpatrick et al., algoritma genetika Holland et al., pencarian terdistribusi dan pencarian tabu dari Glover. Tinjauan literatur tentang optimasi metaheuristik menunjukkan bahwa Fred Glover menciptakan kata metaheuristik.
Kerangka Pengoptimalan Metaheuristik (MOFs)
MOF dapat didefinisikan sebagai “seperangkat perangkat lunak yang menyediakan implementasi yang benar dan dapat digunakan kembali dari serangkaian metaheuristik dan mekanisme yang mendasarinya untuk mempercepat implementasi subheuristik yang setara (mungkin termasuk pengkodean solusi dan teknik operator khusus) yang digunakan untuk memecahkan suatu masalah. diperlukan.”, misalnya penerapan konkrit dari teknik yang dimaksudkan.
Ada banyak alat pengoptimalan potensial yang dapat dianggap MOF dengan fungsi berbeda: Comet, EvA2, evolvica, Evolutionary::Algorithm, GAPlayground,guard, JCLEC, JGAP, jMetal, n-genes, Open Beagle, Opt4j, ParadisEO/EO , Pisa, Pembuat Jam, FOM, Hypercube, HotFrame, Templar, EasyLocal, iOpt, OptQuest, JDEAL, Toolkit Algoritma Optimasi, HeuristicLab, MAFRA, Localizer, GALIB, DREAM, Discropt, MALLBA, MAGMA, Metaheuristics.jl, UOF dan Opta Planner.
Kontribusi
Seiring berjalannya waktu, dunia metaheuristik telah menyaksikan sejumlah kontribusi signifikan yang membentuk fondasi pendekatan pencarian dan optimasi ini. Sejak tahun 1950-an hingga 1990-an, berbagai tokoh dan peneliti telah mengenalkan metode-metode yang inovatif dan beragam. Robbins dan Monro membuka jalannya dengan metode optimasi stokastik pada tahun 1952, disusul dengan simulasi evolusi oleh Barricelli pada tahun 1954. Rastrigin memperkenalkan konsep pencarian acak pada tahun 1963, sementara Nelder dan Mead menciptakan heuristik simpleks pada tahun 1965. Era ini juga menyaksikan munculnya algoritma genetika oleh Holland pada tahun 1975 dan konsep pencarian tabu oleh Glover pada tahun 1986. Inovasi terus berlanjut dengan penemuan algoritma memetika oleh Moscato pada tahun 1989, serta kontribusi penting lainnya, termasuk optimasi koloni semut oleh Dorigo pada tahun 1992. Selanjutnya, teorema "tidak ada makan siang gratis" yang dibuktikan oleh Wolpert dan Macready pada tahun 1995 memberikan wawasan mendalam tentang batasan metaheuristik. Inilah perjalanan penuh inovasi dan penemuan yang membangun dasar bagi fleksibilitas dan efektivitas pendekatan metaheuristik dalam menangani berbagai masalah optimasi.
Disadur dari: en.wikipedia.org