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]
Sifat-sifat
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.
Klasifikasi
Terdapat berbagai jenis metaheuristik [1] dan sejumlah karakteristik yang dapat digunakan untuk mengklasifikasikannya.[3]
Pencarian lokal vs. pencarian global
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 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.[6]
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[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
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.
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.
^
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)
^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.
^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. ISBN978-1-4577-1642-3.
^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. ISSN1999-4893.
^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.
^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.
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. ISBN978-3-319-07123-7.
Gereja Katolik di Selandia BaruHāhi Katorika ki AotearoaKatedral Hati Kudus, WellingtonPenggolonganGereja Katolik RomaOrientasiLatinBentukpemerintahanEpiskopalPausPaus FransiskusUskup AgungJohn DewWilayah Selandia BaruBahasaInggris, LatinKantor pusatViard House, Sacred Heart Cathedral, WellingtonDidirikan1842 (Vikariat Apostolik)[1]Jumlah pengikut470.919 umat (2018)[2]Situs web resmicatholic.org.nz Bagian dari seriGereja Katolik menurut negara Afrika Afrika Selatan Afrika T…
Norris DivisionSport Hockey su ghiaccio TipoCampionato per club FederazioneNational Hockey League Parte diPrince of Wales (1974-81)Clarence Campbell (1981-93) Paese Canada Stati Uniti OrganizzatoreNational Hockey League CadenzaAnnuale StoriaFondazione1974-1975 Soppressione1993 (sostituita da Central Division) Record vittorie Montreal Canadiens (7) Modifica dati su Wikidata · Manuale La Norris Division della National Hockey League fu fondata nel 1974 come parte della Prince o…
هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يوليو 2019) رودلف كيزر (بالنرويجية: Jakob Rudolf Keyser) معلومات شخصية الميلاد 1 يناير 1803 [1] كريستيانية [لغات أخرى] الوفاة 9 أكتوبر 1864 (61 سنة) كريستيا…
Disambiguazione – Uomo, Uomini e Essere umano rimandano qui. Se stai cercando altri significati, vedi Homo sapiens (disambigua), Uomo (disambigua), Uomini (disambigua) o Essere umano (disambigua). Come leggere il tassoboxEssere umano Da sinistra a destra, femmina adulta, infante e maschio adulto di H. sapiens. Intervallo geologico Pleistocene - oggi PreЄ Є O S D C P T J K Pg N ↓ Stato di conservazione Rischio minimo[1] Classificazione scientifica Dominio…
Canadian Muslim preacher and Imam Shabir AllyShabir Ally in 2013PersonalBorn8 May 1953ReligionIslamDenominationSunniJurisprudenceHanafiMain interest(s)Da'wahEducationLaurentian University (BA)University of Toronto (MA, PhD)Websiteshabirally.comYouTube informationChannel Let The Quran Speak Years activeJune 23, 2008–presentGenreIslamicSubscribers336 thousand[1]Total views40 million[1] Creator Awards100,000 subscribers Last updated: 2 February 2024 Shabir Ally is a Cana…
此條目需要补充更多来源。 (2021年7月4日)请协助補充多方面可靠来源以改善这篇条目,无法查证的内容可能會因為异议提出而被移除。致使用者:请搜索一下条目的标题(来源搜索:美国众议院 — 网页、新闻、书籍、学术、图像),以检查网络上是否存在该主题的更多可靠来源(判定指引)。 美國眾議院 United States House of Representatives第118届美国国会众议院徽章 众议院旗帜…
Species of conifer Greek fir Conservation status Least Concern (IUCN 3.1)[1] Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Gymnospermae Division: Pinophyta Class: Pinopsida Order: Pinales Family: Pinaceae Genus: Abies Species: A. cephalonica Binomial name Abies cephalonicaLoudon Distribution map Abies cephalonica or Greek fir[2] is a fir native to the mountains of Greece, primarily in the Peloponnesos and the island of Kefallonia, intergrading …
American cable news and digital media company This article is about the news website. For the television channel, see Newsmax TV. NewsmaxNewsmax logo as of 2021Type of siteNews and opinionAvailable inEnglishOwnerNewsmax MediaCreated byChristopher RuddyEditorChristopher RuddyKey peopleChristopher Ruddy (CEO)David J. Perel (Director)Kenneth Chandler (Editor)URLwww.newsmax.com CommercialYesRegistrationOptional, but is required to commentLaunchedSeptember 16, 1998; 25 yea…
President of the Philippines from 1946 to 1948 This article is about the Filipino president. For his grandson, see Mar Roxas. For other uses, see Roxas (disambiguation) and President Roxas. In this Philippine name, the middle name or maternal family name is Acuña and the surname or paternal family name is Roxas. His ExcellencyManuel Roxas5th President of the PhilippinesIn officeMay 28, 1946 – April 15, 1948Vice PresidentElpidio QuirinoPreceded bySergio OsmeñaSucceeded b…
International organisation European Atomic Energy Community Европейска общност за атомна енергия (Bulgarian) Europska zajednica za atomsku energiju (Croatian) Evropské společenství pro atomovou energii (Czech) Europæiske Atomenergifællesskab (Danish) Europese Atoomenergie Gemeenschap (Dutch) Euroopa Aatomienergiaühendus (Estonian) Euroopan atomienergiayhteisö (Finnish) Communauté européenne de l'énergie atomique (F…
American former basketball player and coach (born 1932) For the baseball player, see Bob Pettit (baseball). Bob PettitPettit with the St. Louis Hawks in 1961Personal informationBorn (1932-12-12) December 12, 1932 (age 91)Baton Rouge, Louisiana, U.S.Listed height6 ft 9 in (2.06 m)Listed weight205 lb (93 kg)Career informationHigh schoolBaton Rouge(Baton Rouge, Louisiana)CollegeLSU (1951–1954)NBA draft1954: 1st round, 2nd overall pickSelected by the Milwaukee HawksPl…
لوغو يخض مؤسسة المقاييس أفضل مما رسة هي طرق وتقنيات تظهر نتائج فعالة وثم تطبق في الأفعال.[1][2][3] روابط خارجية IETF Best Current Practice RFCs List - Internet Engineering Task Force مراجع ^ Baber، Angela. Using Community Colleges to Build a STEM-Skilled Workforce. NGA Center for Best Practices. مؤرشف من الأصل في 2017-08-15. اطلع عليه بتاريخ 2011-09-22. ^ E…
«Lean On» Sencillo de Major Lazer y DJ Snake con MØdel álbum Peace Is the MissionPublicación 2 de marzo de 2015Formato Descarga digitalGrabación 2014Género(s) EDM, moombahtonDuración 2:58Discográfica Mad Decent, Because Music, Warner Music GroupAutor(es) Karen Ørsted, Thomas Pentz, William Griachine, Philip Meckseper y Martín BressoProductor(es) Major Lazer y DJ SnakeCronología de sencillos de Major Lazer «Come On To Me» (2014) «Lean On» (2015) «Powerful» (2015) Cronología de …
An-NozhaLingkunganNegaraArab SaudiProvinsiProvinsi MakkahPemerintahan • Wali kotaHani Abu Ras[1] • Gubernur kotaMish'al Al-SaudKetinggian12 m (39 ft)Zona waktuUTC+3 (AST) • Musim panas (DST)ASTKode pos(5 kode digit dimulai dari 23; e.g. 23434)Kode area telepon+966-12Situs webwww.jeddah.gov.sa/english/index.php An-Nozha adalah sebuah permukiman padat penduduk di kota Jeddah di Provinsi Makkah, tepatnya di sebelah barat Arab Saudi.[3] L…
The Making of an AmericanIklan untuk film dalam Educational Film MagazineSutradaraGuy HedlundProduserWorcester Film CorporationPemeranEmile De VernyPerusahaanproduksiDepartemen Amerikanisasi Negara Bagian ConnecticutWorcester Film CorporationDistributorWorcester Film CorporationTanggal rilis1920Durasi14 menitNegaraAmerika SerikatBahasaBisu The Making of an American adalah sebuah film pendek tahun 1920 yang dipakai sebagai alat pendidikan dalam inisiatif Amerikanisasi pemerintah untuk mengasimila…
Ancient Roman theatre, a landmark of Rome, Italy Theatre of MarcellusView from Via MontanaraTheatre of MarcellusShown within Augustan RomeClick on the map for a fullscreen viewLocationRegio IX Circus FlaminiusCoordinates41°53′30.88″N 12°28′46.13″E / 41.8919111°N 12.4794806°E / 41.8919111; 12.4794806TypeRoman theatre (structure)HistoryBuilderJulius Caesar Augustus Caesar / Marcus MarcellusFounded13 BC The Theatre of Marcellus (Latin: Theatrum Marcelli, Italian:…
American indie pop singer/songwriter Still WoozyBirth nameSven Eric GamskyBorn (1992-06-23) June 23, 1992 (age 32)OriginOakland, California, U.S.GenresIndie popbedroom popYears active2005–presentLabelsInterscope RecordsFormerly ofFeed Me JackWebsitewww.woozystill.com Musical artist Still Woozy is the solo project of Sven Eric Gamsky (born June 23, 1992), an American singer and songwriter from Moraga, California.[1][2] Gamsky grew up in Moraga, California, in the San Franci…