Metaheuristik: Perbedaan antara revisi

Pendekatan pertama yang dapat digunakan untuk mengklasifikasikan algoritma metaheuristik adalah dari sisi strategi pencarian yang digunakanditerapkan.<ref name="blum03metaheuristics" /> Salah satu jenis strategi pencarian adalah perbaikan terhadap algoritma pencarian lokal yang bersifat sederhana. Salah satu algoritma pencarian lokal yang terkenal adalah metodealgoritma ''[[Hill climbing (algoritma)|hill climbing]]'' yang digunakan untuk mencari solusi optimumoptimal lokal. NamunMeskipun begitu, algoritma tersebut tidak dapat menjamin ditemukannyauntuk menemukan solusi optimal global.

Banyak ide-ide metode metaheuristik yang diajukan untuk meningkatkanmemperbaiki metode heuristik pencarian lokal guna menemukan solusi yang lebih baik. Metaheuristik tersebut mencakup [[Simulated annealing|''simulated annealing'']], ''[[Pencarian tabu|tabu search]]'', ''[[Pencarian lokal diulangberulang|iterated local search]]'', ''[[variable neighborhood search]]'', dan [[Prosedur pencarian adaptif acak yang serakah|GRASP]].<ref name="blum03metaheuristics" /> MetideMetode-metdodemetode metaheuristik ini dapat diklasifikasikan sebagai metaheuristik berbasis pencarian lokal atau pencarian global.

Metaheuristik pencarian global lainnya yang tidak berbasis pencarian lokal biasanya adalahmerupakan metaheuristik [[Model populasi (algoritma evolusioner)|berbasis populasi]] . Metaheuristik tersebut meliputi [[Algoritma semut|optimasi koloni semut]], [[komputasi evolusioner]] seperti [[Algoritma genetik|algoritma genetika]] atau [[Strategi evolusi|''evolution strategy'']], ''[[Optimasi kawanan partikel|''particle swarm optimization]]'']], ''[[Algoritma optimasi pengendara|rider optimization algorithm]]'' <ref>{{Cite journal|last=D|first=Binu|year=2019|title=RideNN: A New Rider Optimization Algorithm-Based Neural Network for Fault Diagnosis in Analog Circuits|url=https://ieeexplore.ieee.org/document/8370147|journal=IEEE Transactions on Instrumentation and Measurement|volume=68|issue=1|pages=2–26|bibcode=2019ITIM...68....2B|doi=10.1109/TIM.2018.2836058}}</ref> dan algoritma ''bacterial foraging''. <ref name=":0">{{Cite journal|last=Pang|first=Shinsiong|last2=Chen|first2=Mu-Chen|date=2023-06-01|title=Optimize railway crew scheduling by using modified bacterial foraging algorithm|url=https://www.sciencedirect.com/science/article/pii/S0360835223002425|journal=Computers & Industrial Engineering|language=en|volume=180|pages=109218|doi=10.1016/j.cie.2023.109218|issn=0360-8352}}</ref>

Metode klasifikasi lainnya adalah pencarian solusi tunggal atau [[Model populasi (algoritma evolusioner)|berbasis populasi]].<ref name="blum03metaheuristics" /> Pendekatan solusi tunggal fokusberfokus terhadap modifikasi dan meningkatkanperbaikan kualitas kandidat solusi tunggal. Pendekatan ini mencakup algoritma [[Simulated annealing|''simulated annnealing'']], ''[[Pencarian lokal diulangberulang|iterated local search]]'', ''[[Pencarian Lingkungan Variabel|variable neighborhood search]]'', dan ''[[guided local search]]''. Sedangkan untuk pendekatan berbasis populasi, metode iniyang dipakai adalah mempertahankan dan meningkatkanmemperbaiki kualitas banyak kandidat solusi. Bahkan, sering kali menggunakan karakteristik populasi untuk memandu proses pencarian,. metaheuristikMetaheuristik yang menggunakan pendekatan ini mencakup [[komputasi evolusioner]] dan ''[[Optimasi kawanan partikel|particle swarm optimization]]''. Kategori metaheuristik lainnya adalah [[Computational Swarm Intelligence|kecerdasan gerombolan]] atau ''swarm intelligence'' yang merupakan perilaku kolektif dari agen-agen yang terdesentralisasi dan terorganisir sendirisecara mandiri dalam suatu populasi atau gerombolan. [[Algoritma semut|Optimasi koloni semut]], <ref name="M. Dorigo, Optimization, Learning and Natural Algorithms">M. Dorigo, ''Optimization, Learning and Natural Algorithms'', PhD thesis, Politecnico di Milano, Italie, 1992.</ref> ''[[Optimasi kawanan partikel|particle swarm optimization]]'', [[Social coginitive optimizationsoptimization|social cognitive optimization]], dan algoritma ''bacterial foraging'' <ref name=":0">{{Cite journal|last=Pang|first=Shinsiong|last2=Chen|first2=Mu-Chen|date=2023-06-01|title=Optimize railway crew scheduling by using modified bacterial foraging algorithm|url=https://www.sciencedirect.com/science/article/pii/S0360835223002425|journal=Computers & Industrial Engineering|language=en|volume=180|pages=109218|doi=10.1016/j.cie.2023.109218|issn=0360-8352}}</ref> adalah contoh dari kategori ini.

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 sistem 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|''simulated annealing'']], ''[[algoritma evolusioner]]'', [[Algoritma semut|optimasi koloni semut]] dan ''[[Optimasi kawanan partikel|particle swarm optimization]]''. SejumlahSebagian besar metaheuristik yang terinspirasi dariberbasis metafora, baru-baru ini mulai [[Daftar metaheuristik yang terinspirasi metafora|menarik kritik dari komunitas riset]] karena menyembunyikan kurangnya kebaruanpembaruan (''novelty'') di balik metafora yang rumit.<ref name="Sörensen2013" />

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, fokusnya adalahberfokus pada pencarian solusi optimal di dalam ruang pencarian yang terdiri dari pilihan [[Matematika diskrit|diskrit]]. Sebagai contoh, kita dapat mempertimbangkan [[Permasalahan Penjual Keliling|permasalahan penjual keliling]], diyang manakita kitaharus mencari rute terbaik untuk mengunjungi sejumlah lokasi dengan efisiensi maksimalterbaik. Masalah ini menunjukkanmemungkinkan karakteristik di manabertambahnya jumlah kemungkinan solusi tumbuh secara eksponensial seiring dengan bertambahnya ukuran masalahpermasalahan (dalam kasus ini adalah jumlah kota dan rute yang mungkin). Dengan kata lain, mencari solusi optimal dengan memeriksamengevaluasi setiap kemungkinan secara menyeluruh menjadi tidak mungkin atau tidak efisien seiring pertambahandengan bertambahnya kompleksitas masalah. Selain itu, masalah kombinatorial multidimensi, termasuk sebagian besar masalah desain di [[Perekayasaan|bidang teknik]] <ref>Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. [http://www.mdpi.com/1996-1073/6/3/1439/pdf Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II. ] </ref> <ref>{{Cite journal|last=Ganesan|first=T.|last2=Elamvazuthi|first2=I.|last3=Ku Shaari|first3=Ku Zilati|last4=Vasant|first4=P.|date=2013-03-01|title=Swarm intelligence and gravitational search algorithm for multi-objective optimization of synthesis gas production|journal=Applied Energy|volume=103|pages=368–374|doi=10.1016/j.apenergy.2012.09.059}}</ref> <ref>{{Cite book|last=Ganesan|first=T.|last2=Elamvazuthi|first2=I.|last3=Vasant|first3=P.|date=2011-11-01|title=2011 IEEE International Conference on Control System, Computing and Engineering|isbn=978-1-4577-1642-3|pages=86–91|chapter=Evolutionary normal-boundary intersection (ENBI) method for multi-objective optimization of green sand mould system|doi=10.1109/ICCSCE.2011.6190501}}</ref> diyang dalam manarangka 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 mendalamcapai (''exhaustive search'') atau [[Ekspresi bentuk tertutup|metode analitis]].

Metaheuristik juga sering kali digunakan untuk menyelesaikan masalah penjadwalan, di manayang salah satu contoh klasiknya adalah penjadwalan ''job shop''. Penjadwalan ''job shop'' melibatkan penentuan urutan langkah kerja untuk setiap pekerjaan di stasiun pemrosesan yang sedemikian rupa sehingga semua pekerjaan diselesaikan tepat waktu dan dalam waktu sesingkat mungkin. <ref>{{Cite book|date=2013|url=https://www.wiley.com/en-dk/Metaheuristics+for+Production+Scheduling-p-9781848214972|title=Metaheuristics for production scheduling|location=London|publisher=ISTE|isbn=978-1-84821-497-2|editor-last=Jarboui|editor-first=Bassem|series=Automation - control and industrial engineering series|editor-last2=Siarry|editor-first2=Patrick|editor-last3=Teghem|editor-first3=Jacques}}</ref> <ref>{{Cite book|date=2008|url=http://link.springer.com/10.1007/978-3-540-78985-7|title=Metaheuristics for Scheduling in Industrial and Manufacturing Applications|location=Berlin, Heidelberg|publisher=Springer Berlin Heidelberg|isbn=978-3-540-78984-0|editor-last=Xhafa|editor-first=Fatos|series=Studies in Computational Intelligence|volume=128|language=en|doi=10.1007/978-3-540-78985-7|editor-last2=Abraham|editor-first2=Ajith}}</ref> Dalam praktiknya, seringkali terdapat pembatasan seperti batasan urutan langkah kerja melaluidengan alur kerja yang telah ditentukan, <ref>{{Cite journal|last=Jakob|first=Wilfried|last2=Strack|first2=Sylvia|last3=Quinte|first3=Alexander|last4=Bengel|first4=Günther|last5=Stucky|first5=Karl-Uwe|last6=Süß|first6=Wolfgang|date=2013-04-22|title=Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing|journal=Algorithms|language=en|volume=6|issue=2|pages=245–277|doi=10.3390/a6020245|issn=1999-4893}}</ref> atau keterbatasan terkaitbatasan pemanfaatan sumber daya, misalnya, dalam hal penggunaan energi. <ref>{{Cite journal|last=Kizilay|first=Damla|last2=Tasgetiren|first2=M. Fatih|last3=Pan|first3=Quan-Ke|last4=Süer|first4=Gürsel|date=2019|title=An Ensemble of Meta-Heuristics for the Energy-Efficient Blocking Flowshop Scheduling Problem|journal=Procedia Manufacturing|language=en|volume=39|pages=1177–1184|doi=10.1016/j.promfg.2020.01.352}}</ref> <ref>{{Cite journal|last=Grosch|first=Benedikt|last2=Weitzel|first2=Timm|last3=Panten|first3=Niklas|last4=Abele|first4=Eberhard|date=2019|title=A metaheuristic for energy adaptive production scheduling with multiple energy carriers and its implementation in a real production system|journal=Procedia CIRP|language=en|volume=80|pages=203–208|doi=10.1016/j.procir.2019.01.043}}</ref> Metaheuristik populerbanyak digunakan untuk masalah kombinatorial, termasuk [[Algoritma genetik|algoritma genetika]] oleh Holland et al., ''scatter search,'' dan ''pencarian tabu search'' oleh Glover.

PenerapanPengaplikasian besar lainnya dari metaheuristik terjadiadalah dalam tugas pengoptimalan di ruang pencarian bilangan bulat kontinu atau campuran. Terdapat berbagai aplikasi di bidang optimasi desain <ref>{{Cite journal|last=Gupta|first=Shubham|last2=Abderazek|first2=Hammoudi|last3=Yıldız|first3=Betül Sultan|last4=Yildiz|first4=Ali Riza|last5=Mirjalili|first5=Seyedali|last6=Sait|first6=Sadiq M.|date=2021|title=Comparison of metaheuristic optimization algorithms for solving constrained mechanical design optimization problems|url=https://linkinghub.elsevier.com/retrieve/pii/S095741742100779X|journal=Expert Systems with Applications|language=en|volume=183|pages=115351|doi=10.1016/j.eswa.2021.115351}}</ref> <ref>{{Citation|last=Quinte|first=Alexander|title=Optimization of a Micro Actuator Plate Using Evolutionary Algorithms and Simulation Based on Discrete Element Methods|date=2002|journal=International Conference on Modeling and Simulation of Microsystems: MSM 2002|pages=192–197|editor-last=Laudon|editor-first=Matthew|place=Cambridge, Mass|publisher=Computational Publications|isbn=978-0-9708275-7-9|last2=Jakob|first2=Wilfried|last3=Scherer|first3=Klaus-Peter|last4=Eggert|first4=Horst|url=https://www.researchgate.net/publication/228790476}}</ref> <ref>{{Citation|last=Parmee|first=I. C.|title=Strategies for the Integration of Evolutionary/Adaptive Search with the Engineering Design Process|date=1997|url=http://link.springer.com/10.1007/978-3-662-03423-1_25|journal=Evolutionary Algorithms in Engineering Applications|pages=453–477|editor-last=Dasgupta|editor-first=Dipankar|access-date=2023-07-17|place=Berlin, Heidelberg|publisher=Springer|language=en|doi=10.1007/978-3-662-03423-1_25|isbn=978-3-642-08282-5|editor2-last=Michalewicz|editor2-first=Zbigniew}}</ref> atau berbagai tugas teknikketeknikan. <ref>{{Cite book|date=2014|url=https://link.springer.com/10.1007/978-3-319-06508-3|title=Applications of Metaheuristics in Process Engineering|location=Cham|publisher=Springer International Publishing|isbn=978-3-319-06507-6|editor-last=Valadi|editor-first=Jayaraman|language=en|doi=10.1007/978-3-319-06508-3|editor-last2=Siarry|editor-first2=Patrick}}</ref> <ref>{{Cite book|last=Sanchez|first=Ernesto|last2=Squillero|first2=Giovanni|last3=Tonda|first3=Alberto|date=2012|url=http://link.springer.com/10.1007/978-3-642-27467-1|title=Industrial Applications of Evolutionary Algorithms|location=Berlin, Heidelberg|publisher=Springer|isbn=978-3-642-27466-4|series=Intelligent Systems Reference Library|volume=34|language=en|doi=10.1007/978-3-642-27467-1}}</ref> <ref>{{Cite book|date=2023|url=https://link.springer.com/10.1007/978-3-031-16832-1|title=Engineering Applications of Modern Metaheuristics|location=Cham|publisher=Springer International Publishing|isbn=978-3-031-16831-4|editor-last=Akan|editor-first=Taymaz|series=Studies in Computational Intelligence|volume=1069|language=en|doi=10.1007/978-3-031-16832-1|editor-last2=Anter|editor-first2=Ahmed M.|editor-last3=Etaner-Uyar|editor-first3=A. Şima|editor-last4=Oliva|editor-first4=Diego}}</ref> Salah satu contoh yang mencakup kedua aspek inikeduanya adalah perencanaan jalur gerak yang optimal untuk robot industri. <ref>{{Citation|last=Blume|first=Christian|title=Optimized Collision Free Robot Move Statement Generation by the Evolutionary Software GLEAM|date=2000|url=http://link.springer.com/10.1007/3-540-45561-2_32|journal=Real-World Applications of Evolutionary Computing|series=Lecture Notes in Computer Science|volume=1803|pages=330–341|editor-last=Cagnoni|editor-first=Stefano|access-date=2023-07-17|place=Berlin, Heidelberg|publisher=Springer|language=en|doi=10.1007/3-540-45561-2_32|isbn=978-3-540-67353-8}}</ref> <ref>{{Citation|last=Pholdee|first=Nantiwat|title=Multiobjective Trajectory Planning of a 6D Robot based on Multiobjective Meta Heuristic Search|date=2018-12-14|url=https://dl.acm.org/doi/10.1145/3301326.3301356|journal=International Conference on Network, Communication and Computing (ICNCC 2018)|pages=352–356|publisher=ACM|language=en|doi=10.1145/3301326.3301356|isbn=978-1-4503-6553-6|last2=Bureerat|first2=Sujin}}</ref>

== Kerangka Kerja Optimasi Metaheuristik ==

Kerangka Kerja Optimasi Metaheuristik atau ''Metaheuristic Optimization Frameworks'' (MOF) dapat didefinisikan sebagai <nowiki>''</nowiki>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<nowiki>''</nowiki>.

* 1952: PekerjaanPenelitian Robbins dan Monro dalam metode optimasi stokastik.

* [[Matematika|MeteuristikMateuristik]]

* [[ComputationalKecerdasan Swarmgerombolan Intelligencekomputasional|Kecerdasan gerombolan]]

* [[Algoritma evolusioner]] dan khususnya [[Algoritma genetik|algoritma genetika]], ''[[Pemrogramanpemrograman genetik|genetic programming]]'', atau<nowiki><i>evolution strategies</i></nowiki>[[strategi evolusi]].