Lompat ke isi

Metaheuristik: Perbedaan antara revisi

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
kTidak ada ringkasan suntingan
Tag: VisualEditor Suntingan perangkat seluler Suntingan peramban seluler
 
(2 revisi perantara oleh 2 pengguna tidak ditampilkan)
Baris 24: Baris 24:
</ref>
</ref>


Jika dibandingkan dengan [[Optimisasi|algoritma optimasi]] dan [[Metode iteratif|algoritma iteratif]], metaheuristik tidak dapat menjamin ditemukannya [[Maksimum dan minimum|solusi optimal yang berlaku secara global]] pada beberapa jenis permasalahan.<ref name="blum03metaheuristics" /> Hal ini disebabkan oleh banyaknya metode metaheuristik yang menerapkan [[optimasi stokastik]], sehingga solusi yang ditemukan bergantung pada himpunan [[variabel acak]] yang dihasilkan.<ref name="Bianchi2009"/> Sebagai contoh, pada kasus [[optimasi kombinatorial]], suatu algoritma mencari solusi di dalam himpunan besar yang berisi [[Solusi yang layak|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.<ref name="blum03metaheuristics" /> Oleh karena itu, pendekatan metaheuristik ini bermanfaat dalam masalah optimasi <ref name="Bianchi2009" /> dan sudah banyak buku dan makalah survei telah diterbitkan mengenai hal tersebut.<ref name="Bianchi2009" /><ref name="blum03metaheuristics" /> Terkait dengan awal penemuannya, studi literatur terkait optimasi metaheuristik, <ref>X. S. Yang, Metaheuristic optimization, Scholarpedia, 6(8):11472 (2011).</ref> mengemukakan bahwa Fred Glover-lah yang awalnya menemukan kata “metaheuristik” pertama kali. <ref>Glover F., (1986). </ref>
Jika dibandingkan dengan [[Optimisasi|algoritma optimasi]] dan [[Metode iteratif|algoritma iteratif]], metaheuristik tidak dapat menjamin ditemukannya [[Maksimum dan minimum|solusi optimal yang berlaku secara global]] pada beberapa jenis permasalahan.<ref name="blum03metaheuristics" /> Hal ini disebabkan oleh banyaknya metode metaheuristik yang menerapkan [[optimasi stokastik]], sehingga solusi yang ditemukan bergantung pada himpunan [[variabel acak]] yang dihasilkan.<ref name="Bianchi2009"/> Sebagai contoh, pada kasus [[optimasi kombinatorial]], suatu algoritma mencari solusi di dalam himpunan besar yang berisi [[Solusi yang layak|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.<ref name="blum03metaheuristics" /> Oleh karena itu, pendekatan metaheuristik ini bermanfaat dalam masalah optimasi <ref name="Bianchi2009" /> dan sudah banyak buku dan makalah survei telah diterbitkan mengenai hal tersebut.<ref name="Bianchi2009" /><ref name="blum03metaheuristics" /> Terkait dengan awal penemuannya, studi literatur terkait optimasi metaheuristik, <ref>X. S. Yang, Metaheuristic optimization, Scholarpedia, 6(8):11472 (2011).</ref> mengemukakan bahwa Fred Glover-lah yang awalnya menemukan kata “metaheuristik” pertama kali.<ref>Glover F., (1986). </ref>


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 [[Deret konvergen|konvergensi]] dan sejauh mana kemungkinan algoritma tersebut mampu menemukan optimal global.<ref name="blum03metaheuristics" /> 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. <ref name="Sörensen2013">{{Cite journal|last=Sörensen|first=Kenneth|year=2015|title=Metaheuristics—the metaphor exposed|url=http://antor.ua.ac.be/system/files/mme.pdf|journal=[[International Transactions in Operational Research]]|volume=22|pages=3–18|doi=10.1111/itor.12001|archive-url=https://web.archive.org/web/20131102075645/http://antor.ua.ac.be/system/files/mme.pdf|archive-date=2013-11-02|url-status=dead}}</ref>
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 [[Deret konvergen|konvergensi]] dan sejauh mana kemungkinan algoritma tersebut mampu menemukan optimal global.<ref name="blum03metaheuristics" /> 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. <ref name="Sörensen2013">{{Cite journal|last=Sörensen|first=Kenneth|year=2015|title=Metaheuristics—the metaphor exposed|url=http://antor.ua.ac.be/system/files/mme.pdf|journal=[[International Transactions in Operational Research]]|volume=22|pages=3–18|doi=10.1111/itor.12001|archive-url=https://web.archive.org/web/20131102075645/http://antor.ua.ac.be/system/files/mme.pdf|archive-date=2013-11-02|url-status=dead}}</ref>
Baris 42: Baris 42:


=== Pencarian lokal vs. pencarian global ===
=== Pencarian lokal vs. pencarian global ===
Pendekatan pertama untuk mengklasifikasikan algoritma metaheuristik adalah dari sisi strategi pencarian yang digunakan.<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 metode ''[[Hill climbing (algoritma)|hill climbing]]'' yang digunakan untuk mencari solusi optimum lokal. Namun, algoritma tersebut tidak dapat menjamin ditemukannya solusi optimal global.
Pendekatan pertama yang dapat digunakan untuk mengklasifikasikan algoritma metaheuristik adalah dari sisi strategi pencarian yang diterapkan.<ref name="blum03metaheuristics" /> Salah satu jenis strategi pencarian adalah perbaikan terhadap algoritma pencarian lokal sederhana. Salah satu algoritma pencarian lokal yang terkenal adalah algoritma ''[[Hill climbing (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 meningkatkan heuristik pencarian lokal guna menemukan solusi yang lebih baik. Metaheuristik tersebut mencakup [[Simulated annealing|''simulated annealing'']], ''[[Pencarian tabu|tabu search]]'', ''[[Pencarian lokal diulang|iterated local search]]'', ''[[variable neighborhood search]]'', dan [[Prosedur pencarian adaptif acak yang serakah|GRASP]].<ref name="blum03metaheuristics" /> Metide-metdode metaheuristik ini dapat diklasifikasikan sebagai metaheuristik berbasis pencarian lokal atau pencarian 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|''simulated annealing'']], ''[[Pencarian tabu|tabu search]]'', ''[[Pencarian lokal berulang|iterated local search]]'', ''[[variable neighborhood search]]'', dan [[Prosedur pencarian adaptif acak yang serakah|GRASP]].<ref name="blum03metaheuristics" /> Metode-metode metaheuristik ini dapat diklasifikasikan sebagai metaheuristik berbasis pencarian lokal atau pencarian global.


Metaheuristik pencarian global lainnya yang tidak berbasis pencarian lokal biasanya adalah 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>
Metaheuristik pencarian global lainnya yang tidak berbasis pencarian lokal biasanya merupakan 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'']], ''[[particle swarm optimization]]'', ''[[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>


=== Solusi tunggal vs. berbasis populasi ===
=== Solusi tunggal vs. berbasis populasi ===
Metode klasifikasi lainnya adalah pencarian solusi tunggal atau [[Model populasi (algoritma evolusioner)|berbasis populasi]].<ref name="blum03metaheuristics" /> Pendekatan solusi tunggal fokus terhadap modifikasi dan meningkatkan kualitas kandidat solusi tunggal. Pendekatan ini mencakup [[Simulated annealing|''simulated annnealing'']], ''[[Pencarian lokal diulang|iterated local search]]'', ''[[Pencarian Lingkungan Variabel|variable neighborhood search]]'', dan ''[[guided local search]]''. Sedangkan untuk pendekatan berbasis populasi, metode ini mempertahankan dan meningkatkan banyak kandidat solusi, sering kali menggunakan karakteristik populasi untuk memandu proses pencarian, metaheuristik 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 sendiri 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 optimizations|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.
Metode klasifikasi lainnya adalah pencarian solusi tunggal atau [[Model populasi (algoritma evolusioner)|berbasis populasi]].<ref name="blum03metaheuristics" /> Pendekatan solusi tunggal berfokus terhadap modifikasi dan perbaikan kualitas kandidat solusi tunggal. Pendekatan ini mencakup algoritma [[Simulated annealing|''simulated annnealing'']], ''[[Pencarian lokal berulang|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 [[Computational Swarm Intelligence|kecerdasan gerombolan]] atau ''swarm intelligence'' yang merupakan perilaku kolektif dari agen-agen yang terdesentralisasi dan terorganisir secara 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> ''[[particle swarm optimization]]'', [[Social coginitive optimization|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.


=== Algoritma hibridisasi dan memetika ===
=== Algoritma hibridisasi dan memetika ===
Baris 61: Baris 61:
=== Metaheuristik yang terinspirasi dari alam dan berbasis metafora ===
=== Metaheuristik yang terinspirasi dari alam dan berbasis metafora ===
{{Main|Kecerdasan gerombolan|Daftar metode metaheuristik berbasis metafora}}
{{Main|Kecerdasan gerombolan|Daftar metode metaheuristik 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 sistem alam. Dengan pendekatan ini, alam bertindak sebagai sumber konsep, mekanisme, dan prinsip 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]]''. Sejumlah besar metaheuristik yang terinspirasi dari metafora baru-baru ini mulai [[Daftar metaheuristik yang terinspirasi metafora|menarik kritik dari komunitas riset]] karena menyembunyikan kurangnya kebaruan di balik metafora yang rumit.<ref name="Sörensen2013" />
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|''simulated annealing'']], [[algoritma evolusioner]], [[Algoritma semut|optimasi koloni semut]] dan ''[[particle swarm optimization]]''. Sebagian besar metaheuristik yang berbasis metafora, baru-baru ini mulai [[Daftar metaheuristik yang terinspirasi metafora|menarik kritik dari komunitas riset]] karena menyembunyikan kurangnya pembaruan (''novelty'') di balik metafora yang rumit.<ref name="Sörensen2013" />


== Aplikasi ==
== 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, fokusnya adalah 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]], di mana kita mencari rute terbaik untuk mengunjungi sejumlah lokasi dengan efisiensi maksimal. Masalah ini menunjukkan karakteristik di mana jumlah kemungkinan solusi tumbuh secara eksponensial seiring dengan bertambahnya ukuran masalah. Dengan kata lain, mencari solusi optimal dengan memeriksa setiap kemungkinan secara menyeluruh menjadi tidak mungkin atau tidak efisien seiring pertambahan 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> di mana mencari bentuk atau perilaku optimal melibatkan ruang pencarian yang sangat besar sehinga mengalami [[kutukan dimensi]], yang juga membuatnya tidak layak untuk pencarian mendalam atau [[Ekspresi bentuk tertutup|metode analitis]].
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 [[Matematika diskrit|diskrit]]. Sebagai contoh, kita dapat mempertimbangkan [[Permasalahan Penjual Keliling|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 [[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> 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 [[Ekspresi bentuk tertutup|metode analitis]].


Metaheuristik juga sering digunakan untuk menyelesaikan masalah penjadwalan, di mana salah satu contoh klasiknya adalah penjadwalan ''job shop''. Penjadwalan ''job shop'' melibatkan penentuan urutan langkah kerja untuk setiap pekerjaan di stasiun pemrosesan 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 melalui 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 terkait 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 populer untuk masalah kombinatorial termasuk [[Algoritma genetik|algoritma genetika]] oleh Holland et al., ''scatter search,'' dan ''tabu search'' oleh Glover.
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.<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 dengan 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 batasan 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 banyak digunakan untuk masalah kombinatorial, termasuk [[Algoritma genetik|algoritma genetika]] oleh Holland et al., ''scatter search,'' dan pencarian tabu oleh Glover.


Penerapan besar lainnya dari metaheuristik terjadi 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 teknik. <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 ini 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>
Pengaplikasian besar lainnya dari metaheuristik adalah 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 keteknikan.<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 keduanya 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 Optimasi Metaheuristik ==
== Kerangka Kerja Optimasi Metaheuristik ==
Kerangka 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>.
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>.


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.
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.
Baris 78: Baris 78:
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:
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: Pekerjaan Robbins dan Monro dalam metode optimasi stokastik.
* 1952: Penelitian Robbins dan Monro dalam metode optimasi stokastik.
* 1954: [[Nils Aall Barricelli|Barricelli]] melakukan simulasi pertama dari proses [[evolusi]] dan menggunakannya pada masalah optimasi umum.
* 1954: [[Nils Aall Barricelli|Barricelli]] melakukan simulasi pertama dari proses [[evolusi]] dan menggunakannya pada masalah optimasi umum.
* 1963: Rastrigin mengusulkan [[pencarian acak]] atau ''random search''.
* 1963: Rastrigin mengusulkan [[pencarian acak]] atau ''random search''.
Baris 103: Baris 103:
* [[Pencarian stokastik]]
* [[Pencarian stokastik]]
* [[Optimasi meta]]
* [[Optimasi meta]]
* [[Matematika|Meteuristik]]
* [[Mateuristik]]
* [[Hiper-heuristik]]
* [[Hiper-heuristik]]
* [[Computational Swarm Intelligence|Kecerdasan gerombolan]]
* [[Kecerdasan gerombolan komputasional|Kecerdasan gerombolan]]
* [[Algoritma evolusioner]] dan khususnya [[Algoritma genetik|algoritma genetika]], ''[[Pemrograman genetik|genetic programming]]'', atau<nowiki><i>evolution strategies</i></nowiki> .
* [[Algoritma evolusioner]] dan khususnya [[Algoritma genetik|algoritma genetika]], [[pemrograman genetik]], atau [[strategi evolusi]].
* ''[[Simulated annealing]]''
* ''[[Simulated annealing]]''
* [[Pemodelan tenaga kerja]]
* [[Pemodelan tenaga kerja]]
Baris 147: Baris 147:


* Ashish Sharma (2022), Nature Inspired Algorithms with Randomized Hypercomputational Perspective. ''Information Sciences.'' https://doi.org/10.1016/j.ins.2022.05.020.
* Ashish Sharma (2022), Nature Inspired Algorithms with Randomized Hypercomputational Perspective. ''Information Sciences.'' https://doi.org/10.1016/j.ins.2022.05.020.
== Pranala luar ==


== Tautan eksternal ==


* {{Scholarpedia|title=Metaheuristics}}
* {{Scholarpedia|title=Metaheuristics}}
* [http://www.metaheuristics.eu EU/ME] forum for researchers in the field.
* [http://www.metaheuristics.eu EU/ME] forum for researchers in the field.
{{Optimization algorithms|heuristic}}
[[Kategori:Pemeliharaan CS1: Banyak nama: authors list]]
[[Kategori:Pemeliharaan CS1: Banyak nama: authors list]]

Revisi terkini sejak 3 Maret 2024 04.54

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[sunting | sunting sumber]

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[sunting | sunting sumber]

Diagram Euler tentang klasifikasi metaheuristik yang berbeda. [7]

Terdapat berbagai jenis metaheuristik [1] dan sejumlah karakteristik yang dapat digunakan untuk mengklasifikasikannya.[3]

Pencarian lokal vs. pencarian global[sunting | sunting sumber]

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 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 [8] dan algoritma bacterial foraging.[9]

Solusi tunggal vs. berbasis populasi[sunting | sunting sumber]

Metode klasifikasi lainnya adalah pencarian solusi tunggal atau berbasis populasi.[3] 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, [10] particle swarm optimization, social cognitive optimization, dan algoritma bacterial foraging [9] adalah contoh dari kategori ini.

Algoritma hibridisasi dan memetika[sunting | sunting sumber]

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[sunting | sunting sumber]

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[sunting | sunting sumber]

Artikel utama: Kecerdasan gerombolan dan Daftar metode metaheuristik 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[sunting | sunting sumber]

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[sunting | sunting sumber]

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[sunting | sunting sumber]

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:

Lihat juga[sunting | sunting sumber]

Referensi[sunting | sunting sumber]

  1. ^ a b c d e Bianchi, Leonora; Marco Dorigo; Luca Maria Gambardella; Walter J. Gutjahr (2009). "A survey on metaheuristics for stochastic combinatorial optimization" (PDF). Natural Computing. 8 (2): 239–287. doi:10.1007/s11047-008-9098-4. 
  2. ^ 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 alt=Dapat diakses gratis. 
  3. ^ a b c d e f g h i j Blum, C.; Roli, A. (2003). "Metaheuristics in combinatorial optimization: Overview and conceptual comparison". 35 (3). ACM Computing Surveys: 268–308. 
  4. ^ X. S. Yang, Metaheuristic optimization, Scholarpedia, 6(8):11472 (2011).
  5. ^ Glover F., (1986).
  6. ^ a b Sörensen, Kenneth (2015). "Metaheuristics—the metaphor exposed" (PDF). International Transactions in Operational Research. 22: 3–18. doi:10.1111/itor.12001. Diarsipkan dari versi asli (PDF) tanggal 2013-11-02. 
  7. ^ Classification of metaheuristics
  8. ^ D, Binu (2019). "RideNN: A New Rider Optimization Algorithm-Based Neural Network for Fault Diagnosis in Analog Circuits". IEEE Transactions on Instrumentation and Measurement. 68 (1): 2–26. Bibcode:2019ITIM...68....2B. doi:10.1109/TIM.2018.2836058. 
  9. ^ a b Pang, Shinsiong; Chen, Mu-Chen (2023-06-01). "Optimize railway crew scheduling by using modified bacterial foraging algorithm". Computers & Industrial Engineering (dalam bahasa Inggris). 180: 109218. doi:10.1016/j.cie.2023.109218. ISSN 0360-8352. 
  10. ^ a b M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.
  11. ^ Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II.
  12. ^ 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. 
  13. ^ 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. ISBN 978-1-4577-1642-3. 
  14. ^ Jarboui, Bassem; Siarry, Patrick; Teghem, Jacques, ed. (2013). Metaheuristics for production scheduling. Automation - control and industrial engineering series. London: ISTE. ISBN 978-1-84821-497-2. 
  15. ^ Xhafa, Fatos; Abraham, Ajith, ed. (2008). Metaheuristics for Scheduling in Industrial and Manufacturing Applications. Studies in Computational Intelligence (dalam bahasa Inggris). 128. Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-540-78985-7. ISBN 978-3-540-78984-0. 
  16. ^ 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. ISSN 1999-4893. 
  17. ^ 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. 
  18. ^ 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. 
  19. ^ Gupta, Shubham; Abderazek, Hammoudi; Yıldız, Betül Sultan; Yildiz, Ali Riza; Mirjalili, Seyedali; Sait, Sadiq M. (2021). "Comparison of metaheuristic optimization algorithms for solving constrained mechanical design optimization problems". Expert Systems with Applications (dalam bahasa Inggris). 183: 115351. doi:10.1016/j.eswa.2021.115351. 
  20. ^ Quinte, Alexander; Jakob, Wilfried; Scherer, Klaus-Peter; Eggert, Horst (2002), Laudon, Matthew, ed., "Optimization of a Micro Actuator Plate Using Evolutionary Algorithms and Simulation Based on Discrete Element Methods", International Conference on Modeling and Simulation of Microsystems: MSM 2002, Cambridge, Mass: Computational Publications: 192–197, ISBN 978-0-9708275-7-9 
  21. ^ Parmee, I. C. (1997), Dasgupta, Dipankar; Michalewicz, Zbigniew, ed., "Strategies for the Integration of Evolutionary/Adaptive Search with the Engineering Design Process", Evolutionary Algorithms in Engineering Applications (dalam bahasa Inggris), Berlin, Heidelberg: Springer: 453–477, doi:10.1007/978-3-662-03423-1_25, ISBN 978-3-642-08282-5, diakses tanggal 2023-07-17 
  22. ^ Valadi, Jayaraman; Siarry, Patrick, ed. (2014). Applications of Metaheuristics in Process Engineering (dalam bahasa Inggris). Cham: Springer International Publishing. doi:10.1007/978-3-319-06508-3. ISBN 978-3-319-06507-6. 
  23. ^ Sanchez, Ernesto; Squillero, Giovanni; Tonda, Alberto (2012). Industrial Applications of Evolutionary Algorithms. Intelligent Systems Reference Library (dalam bahasa Inggris). 34. Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-27467-1. ISBN 978-3-642-27466-4. 
  24. ^ Akan, Taymaz; Anter, Ahmed M.; Etaner-Uyar, A. Şima; Oliva, Diego, ed. (2023). Engineering Applications of Modern Metaheuristics. Studies in Computational Intelligence (dalam bahasa Inggris). 1069. Cham: Springer International Publishing. doi:10.1007/978-3-031-16832-1. ISBN 978-3-031-16831-4. 
  25. ^ Blume, Christian (2000), Cagnoni, Stefano, ed., "Optimized Collision Free Robot Move Statement Generation by the Evolutionary Software GLEAM", Real-World Applications of Evolutionary Computing, Lecture Notes in Computer Science (dalam bahasa Inggris), Berlin, Heidelberg: Springer, 1803: 330–341, doi:10.1007/3-540-45561-2_32, ISBN 978-3-540-67353-8, diakses tanggal 2023-07-17 
  26. ^ Pholdee, Nantiwat; Bureerat, Sujin (2018-12-14), "Multiobjective Trajectory Planning of a 6D Robot based on Multiobjective Meta Heuristic Search", International Conference on Network, Communication and Computing (ICNCC 2018) (dalam bahasa Inggris), ACM: 352–356, doi:10.1145/3301326.3301356, ISBN 978-1-4503-6553-6 
  27. ^ Moscato, P.; Fontanari, J.F. (1990), "Stochastic versus deterministic update in simulated annealing", Physics Letters A, 146 (4): 204–208, Bibcode:1990PhLA..146..204M, doi:10.1016/0375-9601(90)90166-L 
  28. ^ Dueck, G.; Scheuer, T. (1990), "Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing", Journal of Computational Physics, 90 (1): 161–175, Bibcode:1990JCoPh..90..161D, doi:10.1016/0021-9991(90)90201-B, ISSN 0021-9991 

Bacaan lebih lanjut[sunting | sunting sumber]

Pranala luar[sunting | sunting sumber]

Diperoleh dari "https://wiki-indonesia.club/w/index.php?title=Metaheuristik&oldid=25389293"