Operation Research and Analysis

Mengenal Sejarah Optimasi Koloni Semut Part 1

Dipublikasikan oleh Dias Perdana Putra pada 19 Februari 2024


Algoritma optimasi koloni semut

Dalam dunia ilmu komputer dan riset operasi, algoritma Ant Colony Optimization (ACO) menonjol sebagai teknik probabilistik untuk memecahkan masalah komputasi yang dapat direduksi menjadi menemukan jalur optimal dalam grafik. Inspirasi utama ACO berasal dari perilaku semut biologis, dimana komunikasi berbasis feromon sering dijadikan paradigma utama. Kombinasi semut buatan dan algoritma pencarian lokal telah menjadi pilihan pertama untuk berbagai tugas optimasi termasuk perutean kendaraandan perutean Internet.

Misalnya, optimasi koloni semut adalah suatu kelas algoritma yang terinspirasi oleh tindakan koloni semut. Semut buatan bertindak sebagai agen simulasi untuk menjelajahi ruang parameter guna menemukan solusi optimal, mirip dengan semut biologis yang mengeluarkan feromon untuk memandu semut lain menuju sumber daya.Dalam simulasi, semut buatan mencatat posisi dan kualitas solusi sehingga semut dapat menemukan solusi yang lebih baik pada iterasi berikutnya. Varian dari pendekatan ini adalah algoritma lebah, yang mencerminkan pola mencari makan lebah madu dan serangga sosial lainnya.

ACO pertama kali diusulkan oleh Marco Dorigo pada tahun 1992 dan pada awalnya dirancang untuk menemukan jalur optimal dalam grafik berdasarkan perilaku semut biologis. Seiring waktu, ide dasar ini berkembang untuk memecahkan berbagai masalah numerik dengan memanfaatkan berbagai aspek perilaku semut. Sebagai anggota keluarga algoritma koloni semut, metode kecerdasan gerombolan, dan optimasi metaheuristik, ACO melakukan pencarian berbasis model dan memiliki kesamaan dengan algoritma distribusi.

Gambaran Umum

Di alam, semut dari beberapa spesies awalnya berkeliaran tanpa pandang bulu dan, setelah menemukan makanan, kembali ke koloninya, meninggalkan jejak feromon. Jejak kaki ini menjadi petunjuk saat mencari semut lain; Jika mereka menemukan jejak, kemungkinan besar mereka akan mengikuti jejak feromon tersebut, kembali dan memperkuatnya ketika mereka akhirnya menemukan makanan (lihat komunikasi semut). Namun, seiring berjalannya waktu, jejak feromon tersebut menghilang sehingga mengurangi daya tariknya.Semakin lama semut menempuh jalur tersebut, semakin banyak waktu yang dimiliki feromon untuk menguap.

Rute yang lebih pendek lebih menarik karena lebih sering dilalui, sehingga kepadatan feromon lebih tinggi pada rute yang lebih pendek dibandingkan dengan rute yang lebih panjang.Penguapan feromon juga bermanfaat untuk menghindari konvergensi menuju solusi optimal lokal. Tanpa penguapan, jalur yang dipilih semut pertama kemungkinan besar akan terlalu menarik bagi semut berikutnya, sehingga sulit menjelajahi ruang solusi. Meskipun pengaruh penguapan feromon dalam sistem semut alami masih belum jelas, namun hal ini penting dalam sistem buatan.

Ketika semut menemukan jalur yang baik dari koloni menuju sumber makanan, semut lain umumnya cenderung mengikuti jalur tersebut, dan umpan balik positif pada akhirnya menyebabkan banyak semut mengambil jalur yang sama. Ide di balik algoritma koloni semut adalah untuk meniru perilaku ini melalui “simulasi semut” yang dijalankan di sekitar grafik yang mewakili masalah yang sedang dipecahkan.

Jaringan ambien objek cerdas

Pada saat “kecerdasan” tidak lagi terpusat tetapi dapat ditemukan pada objek-objek yang sangat kecil, diperlukan suatu konsep baru. Kini perlu ditinjau kembali konsep antroposentris yang sebelumnya memusatkan pengolahan data dan perhitungan kekuatan di unit kendali. Model otak manusia telah menjadi visi utama dalam pengembangan komputer. Namun, konsep ini berubah secara signifikan dengan munculnya jaringan objek cerdas dan sistem informasi generasi baru berbasis nanoteknologi. Meskipun perangkat kecil tidak menghasilkan kecerdasan tinggi secara individual, namun jika dihubungkan bersama, perangkat tersebut dapat menghasilkan kecerdasan kolektif, mirip dengan koloni semut atau lebah.

Contoh dari alam menunjukkan bahwa organisme yang sangat kecil, jika mengikuti aturan dasar yang sama, dapat menciptakan kecerdasan kolektif pada tingkat makroskopis. Koloni serangga sosial, bekerja sama dengan unit independen yang berperilaku sederhana, mewakili model masyarakat yang berbeda dengan manusia. Mereka bergerak untuk melakukan tugas dengan sedikit informasi. Analoginya dapat ditemukan pada jaringan benda-benda disekitarnya, dimana fleksibilitas dan kemampuan beradaptasi terhadap perubahan lingkungan sangatlah penting. Sama seperti koloni semut yang memiliki kemampuan beradaptasi dan kekuatan kolektif, jaringan seluler yang berkembang juga dapat memperoleh manfaat dari fleksibilitas serupa.Paket informasi yang bergerak melalui jaringan objek dapat dibandingkan dengan pergerakan semut yang bergerak melalui node dengan tujuan mencapai tujuan akhirnya secepat mungkin. Oleh karena itu, penggunaan konsep-konsep ini dalam situasi tertentu dapat membuka pintu menuju kecerdasan yang lebih tinggi dibandingkan dengan sistem terpusat tradisional.

Sistem Feromom Buatan

Sistem feromon buatan telah menjadi fokus penelitian karena komunikasi berbasis feromon telah terbukti menjadi salah satu alat komunikasi paling efektif yang banyak digunakan di alam. Serangga sosial seperti lebah, semut, dan rayap menggunakan feromon untuk berkomunikasi antar agen dan dalam kawanan agen. Efektivitas komunikasi ini mendorong penggunaan feromon buatan dalam pengembangan sistem robot gerombolan dan multi-robot.

Penerapan komunikasi berbasis feromon dapat dilakukan dengan berbagai metode, baik kimia maupun fisika. Contohnya adalah penggunaan cahaya yang diproyeksikan, seperti yang dijelaskan dalam artikel IEEE oleh Garnier, Simon et al. dari tahun 2007.Studi ini menjelaskan pengaturan eksperimental dengan mikrorobot otonom untuk menyelidiki komunikasi berbasis feromon. Pendekatan lain adalah dengan menyebarkan feromon melalui layar LCD horizontal, dan robot dilengkapi dengan sensor cahaya yang menghadap ke bawah untuk merekam pola pada permukaan di bawahnya. Meskipun mereka berhasil menciptakan kembali beberapa aspek komunikasi feromon alami, aplikasi ini gagal mereplikasi sepenuhnya kompleksitas seluruh sistem feromonseperti yang terlihat di alam.

 

Disadur dari : https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms

Selengkapnya
Mengenal Sejarah Optimasi Koloni Semut Part 1

Operation Research and Analysis

Mengenal dan Algoritma Pencarian Lokal Berkali-kali

Dipublikasikan oleh Dias Perdana Putra pada 19 Februari 2024


Pencarian Lokal Teriterasi

Pencarian lokal berulang (ILS) adalah istilah dalam matematika terapan dan ilmu komputer yang mendefinisikan modifikasi metode pencarian atau penskalaan lokal untuk memecahkan masalah optimasi diskrit.Metode pencarian lokal bisa terjebak dalam kondisi minimum lokal di mana tidak ada tetangga terbaik yang tersedia.

Perubahan sederhana adalah mengulangi panggilan ke rutinitas pencarian lokal, setiap kali dimulai dengan konfigurasi awal yang berbeda. Ini disebut pencarian lokal berulang dan berarti bahwa pengetahuan yang diperoleh pada tahap pencarian lokal sebelumnya tidak digunakan. Pembelajaran berarti mengevaluasi sejarah sebelumnya, seperti ingatan tentang nilai minimum lokal yang ditemukan sebelumnya, untuk menciptakan titik awal yang lebih baik untuk penelusuran lokal.Asumsi implisitnya adalah distribusi minimum lokal yang disamakan: ketika meminimalkan suatu fungsi, menentukan minimum lokal yang baik akan lebih mudah jika Anda memulai dari minimum lokal dengan nilai yang rendah dibandingkan jika Anda memulai dari titik acak. Satu-satunya batasan adalah menghindari pembatasan pada wadah penarik tertentu. Oleh karena itu, tendangan untuk menjadikan minimer lokal sebagai titik awal untuk putaran berikutnya harus cukup kuat, tetapi tidak terlalu kuat, sehinggaterhindar dari serangan balik. untuk reboot secara acak dari memori.

Algoritma Perturbasi

Menemukan algoritma perturbasi untuk pencarian lokal teriterasi (ILS) bukanlah tantangan yang mudah. Tujuan utamanya adalah untuk menghindari ketergantungan pada nilai minimum lokal yang sama dan untuk memastikan pencapaian properti ini, operasi penghapusan dilarang. Namun banyak hal yang perlu diperhatikan dalam merancang permutasi yang efektif karena ada dua jenis permutasi yang dianggap buruk. Pertama, permutasinya terlalu lemah, yang mungkin mengakibatkan penggunaan minimum lokal yang sama,. Kedua, permutasinya terlalu kuat, sehingga menyebabkan restart secara acak dan menyulitkan pencarian solusi optimal.Oleh karena itu, menciptakan algoritma perturbasi yang seimbang dan efisien sangat penting untuk mengoptimalkan kinerja pencarian lokal berulang.

Gangguan tolok ukur

Prosedurnya adalah menetapkan sekumpulan nilai gangguan sedemikian rupa sehingga nilai-nilai ini signifikan untuk suatu peristiwa: probabilitas sedang dan tidak jarang. Kemudian dimungkinkan untuk memeriksa grafik referensi pada waktu proses untuk mendapatkan gambaran rata-rata dari kejadian sebelumnya.

Gangguan adaptif
Karena tidak ada fungsi apriori yang menentukan nilai mana yang paling sesuai untuk suatu kelainan tertentu, pendekatan terbaik adalah menjadikannya adaptif. Misalnya, Battiti dan Protasi dalam mengusulkan algoritma pencarian reaktif untuk MAX-SAT, yang cocok dengan kerangka ILS. Mereka melakukan skema gangguan “terarah” yang diimplementasikan menggunakan algoritma pencarian Tabu dan menerapkan algoritma penurunan lokal standar setelah setiap gangguan. Cara lain untuk beradaptasi terhadap gangguan adalah dengan mengubah kekuatannya secara deterministik selama pencarian.

Optimalkan gangguan

Pendekatan lainnya adalah mengoptimalkan subbagian masalah dengan menjaga properti No Undo tetap aktif. Jika metode ini memungkinkan, solusi apa pun yang dihasilkan setelah gangguan mungkin akan sangat baik. Selain itu, suku cadang baru juga dioptimalkan.

Disadur dari : https://en.wikipedia.org/wiki/Iterated_local_search

Selengkapnya
Mengenal dan Algoritma Pencarian Lokal Berkali-kali

Operation Research and Analysis

Latar Belakang, Penjelasan Beserta Contoh Tabu Search

Dipublikasikan oleh Dias Perdana Putra pada 19 Februari 2024


Tabu Search

Tabu Search (TS) adalah metode pencarian metaheuristik yang menggunakan metode pencarian lokal untuk optimasi matematis. Metode ini diciptakan oleh Fred W. Glover pada tahun 1986 dan diformalkan pada tahun 1989.

Pencarian lokal mengambil solusi potensial untuk suatu masalah dan memeriksa tetangga-tetangganya secara langsung (solusi yang mirip kecuali beberapa detail kecil) dengan harapan menemukan solusi yang lebih baik. Metode pencarian lokal memiliki kecenderungan untuk terjebak di wilayah suboptimal atau di dataran tinggi di mana banyak solusi memiliki tingkat kecocokan yang sama.

Tabu Search meningkatkan kinerja pencarian lokal dengan melonggarkan aturan dasarnya. Pertama, pada setiap langkah, gerakan yang memperburuk solusi dapat diterima jika tidak ada gerakan yang memperbaiki yang tersedia (seperti ketika pencarian terjebak pada minimum lokal yang ketat). Selain itu, larangan (dari situlah istilah "tabu" berasal) diberlakukan untuk mencegah pencarian kembali ke solusi yang sudah dikunjungi sebelumnya.

Implementasi dari Tabu Search menggunakan struktur memori yang menggambarkan solusi yang telah dikunjungi atau aturan-aturan yang diberikan oleh pengguna. Jika solusi potensial telah dikunjungi dalam periode waktu tertentu atau telah melanggar suatu aturan, maka solusi tersebut ditandai sebagai "tabu" (dilarang), sehingga algoritma tidak mempertimbangkan kemungkinan tersebut secara berulang-ulang.

Latar Belakang

Tabu Search adalah algoritma metaheuristik untuk memecahkan masalah optimasi kombinatorial (masalah yang memerlukan konfigurasi optimal dan pemilihan opsi).Aplikasi Tabu Search saat ini mencakup bidang-bidang seperti perencanaan sumber daya, telekomunikasi, desain VLSI, analisis keuangan, penjadwalan, perencanaan ruang, distribusi energi, teknik molekuler, logistik, pemilahan pola, manufaktur fleksibel, pengelolaan limbah, eksplorasi mineral, analisis biomedis, dan lingkungan. . Konservasi alam dan banyak lagi. Dalam beberapa tahun terakhir, jurnal dari berbagai bidang telah menerbitkan artikel tutorial dan studi komputasi yang mendokumentasikan keberhasilan Tabu Search dalam memperluas batas-batas masalah yang dapat diatasi secara efektif dan menghasilkan solusi yang kualitasnya seringkali jauh melebihi metode yang digunakan sebelumnya. Daftar lengkap penerapannya, termasuk penjelasan singkat tentang manfaat yang dihasilkan dari penerapan praktis.

Tipe Memory

Tabu Search, sebuah algoritma metaheuristik untuk optimasi kombinatorial, membawa inovasi dalam penanganan masalah kompleks dengan memanfaatkan metode pencarian lokal. Struktur memori Tabu Search, terbagi menjadi memori jangka pendek, menengah, dan panjang, memberikan keunggulan dalam mengatasi kendala-kendala yang umumnya dihadapi oleh metode pencarian lokal tradisional. Memori jangka pendek mencatat solusi-solusi terkini, melarang revisi hingga kadaluwarsa, sementara memori jangka menengah dan panjang menentukan aturan intensifikasi dan diversifikasi untuk membimbing pencarian ke arah yang optimal. Implementasinya mencakup struktur memori yang merinci solusi-solusi yang sudah dikunjungi atau aturan-aturan pengguna. Keberhasilan Tabu Search terlihat dalam berbagai aplikasi, termasuk perencanaan sumber daya, desain VLSI, logistik, dan sektor lainnya, sering kali menghasilkan solusi yang melampaui kualitas metode-metode sebelumnya. Dengan penekanan pada struktur memori yang adaptif, Tabu Search memberikan kontribusi berharga dalam penyelesaian efisien masalah optimasi kompleks.

Contoh : Traveling Salesman Problem

Pencarian Tabu digunakan untuk menyelesaikan masalah traveling salesman (TSP). TSP sendiri adalah pertanyaan sederhana: Apa rute terpendek yang mengunjungi semua kota dalam daftar kota? Misalnya, jika Kota A dan Kota B berdekatan sedangkan Kota C berjauhan, maka total jarak perjalanan akan lebih pendek jika kota A dan B dikunjungi secara berurutan sebelum mengunjungi Kota C. Karena mencari solusi optimal sangatlah sulit (NP-hard),menggunakan metode pendekatan heuristik seperti pencarian lokal untuk mendapatkan solusi mendekati optimal.Untuk mendapatkan solusi TSP yang baik, penting untuk memanfaatkan struktur grafis.Pencarian Tabu sangat cocok sebagai metode metaheuristik untuk memecahkan masalah ini.

Ada strategi khusus yang terkait dengan pencarian Tabu, yang disebut metode rantai penggusuran, yang memungkinkan diperolehnya solusi TSP berkualitas tinggi secara efisien.Di sisi lain, pencarian tabu sederhana dapat digunakan untuk menemukan solusi yang memuaskan di TSP. Artinya solusi ini memenuhi kriteria cukup, meskipun belum seoptimal solusi yang memanfaatkan struktur grafik dengan baik. Proses pencarian dimulai dengan solusi awal, yang dapat dihasilkan secara acak atau dengan suatu algoritma.Untuk menciptakan solusi baru, kami menukar urutan kunjungan kedua kota tersebut dengan solusi potensial. Total jarak yang ditempuh digunakan untuk mengevaluasi keunggulan suatu solusi dibandingkan dengan solusi lainnya. Untuk menghindari terjebak dalam pola kunjungan berulang atau solusi lokal yang lebih baik, solusi ditambahkan ke daftar tabu ketika solusi tersebut diterima dalam wilayah solusi tertentu.Proses pencarian berlanjut hingga kriteria penghentian tercapai, misalnya sejumlah iterasi tertentu. Setelah pencarian tabu sederhana dihentikan, hasil akhir akan mengembalikan solusi terbaik yang ditemukan selama proses eksekusi.

Disadur dari : https://en.wikipedia.org/wiki/Tabu_search

Selengkapnya
Latar Belakang, Penjelasan Beserta Contoh Tabu Search

Operation Research and Analysis

Apa itu Traveling Salesman Problem dan Bagaimana Sejarahnya

Dipublikasikan oleh Dias Perdana Putra pada 19 Februari 2024


Traveling Salesman Problem

Traveling Salesman Problem (TSP), menanyakan pertanyaan berikut: “Mengingat daftar kota dan jarak antara setiap pasangan kota, rute terpendek manakah yang dapat mengunjungi setiap kota tepat satu kali?” dan untuk kembali? Dia? Kampung halaman?” Ini adalah masalah NP-hard dalam optimasi kombinatorial, penting dalam ilmu komputer teoretis dan riset operasi.Masalah pembelanja yang bepergian dan masalah rute kendaraan merupakan generalisasi dari TSP.

Dalam teori kompleksitas komputasi, versi keputusan TSP (dengan panjang L, tugasnya adalah memutuskan apakah grafik memiliki paling banyak satu jalur dengan panjang L) termasuk dalam kelas masalah NP-lengkap.Oleh karena itu, ada kemungkinan bahwa waktu eksekusi kasus terburuk untuk algoritma TSP meningkat secara superpolinomik (tetapi tidak lebih dari eksponensial) dengan jumlah kota.

Masalah ini pertama kali dirumuskan pada tahun 1930 dan merupakan salah satu masalah optimasi yang paling banyak dipelajari. Ini digunakan sebagai titik referensi untuk banyak metode optimasi. Meskipun permasalahannya sulit secara komputasi, banyak heuristik dan algoritma yang sesuai telah diketahui, sehingga beberapa kejadian dengan puluhan ribu kota dapat diselesaikan sepenuhnya, dan bahkan permasalahan dengan jutaan kota dapat didekati dengan sepersekian 1%.

Sejarah

Asal usul masalah pekerja lapangan tidak jelas. Panduan perjalanan tahun 1832 menyebutkan masalah tersebut dan menyertakan contoh perjalanan di Jerman dan Swiss, tetapi tidak memuat penjelasan matematis.

TSP dirumuskan secara matematis pada abad ke-19 oleh matematikawan Irlandia William Rowan Hamilton dan matematikawan Inggris Thomas Kirkman. Permainan Icosian Hamiltonian adalah teka-teki rekreasional yang didasarkan pada penemuan siklus Hamiltonian. Bentuk umum TSP tampaknya pertama kali dipelajari pada tahun 1930-an oleh ahli matematika di Wina dan Harvard, terutama Karl Menger, yang mendefinisikan masalahnya, mempertimbangkan algoritma brute force yang terdefinisi dengan baik, dan mengamati ketidakoptimalan.

Traveling Salesman Problem (TSP) awalnya muncul pada tahun 1930an ketika Merrill M. Flood mencoba memecahkan tantangan perencanaan rute bus sekolah secara matematis. Menariknya, Hassler Whitney dari Universitas Princeton memberikan sentuhan pribadi pada masalah ini dengan menyebutnya sebagai “masalah 48 negara bagian,” sehingga memicu minat awal terhadap topik tersebut. Pada tahun 1950an dan 1960an, popularitas TSP meningkat setelah RAND Corporation menawarkan hadiah kepada mereka yang dapat menyelesaikannya.

Namun, titik kritis dalam pengembangan TSP terjadi pada tahun 1950an dan 1960an, ketika George Dantzig, Delbert Ray Fulkerson, dan Selmer M.Johnson dari RAND Corporation mengembangkan metode bidang potong untuk mengatasi masalah ini. Meskipun kontribusi ini tidak memberikan solusi algoritmik langsung, kontribusi ini memberikan dasar yang sangat penting untuk pengembangan metode solusi yang lebih akurat di masa depan.

Akhirnya, pada tahun 1959, Jillian Beardwood, JH Halton, dan John Hammersley memberikan solusi praktis dengan teorema Beardwood-Halton-Hammersley, menandai perkembangan lebih lanjut dalam pengobatan PST. Pada tahun 1960-an, ada pendekatan baru yang berfokus pada pembuatan batas bawah dengan mengalikan pohon rentang minimum suatu grafik. Hal ini membuka jalan bagi metode cabang-dan-gabung, yang menjadi pendekatan penting untuk mengatasi TSP.Selama dekade berikutnya, kemajuan signifikan dicapai pada akhir tahun 1970an dan 1980an, ketika Grötschel, Padberg, Rinaldi, dan peneliti lain memecahkan kasus TSP di 2.392 kota. Pada tahun 1990-an, muncul program Concorde dan TSPLIB yang berperan penting dalam pengembangan dan benchmarking algoritma TSP. Sebuah tonggak sejarah dicapai pada tahun 2006 dengan perhitungan rute optimal untuk 85.900 contoh masalah distribusi microchip perkotaan.Semua ini mencerminkan kemajuan luar biasa dalam pengobatan TSP selama beberapa dekade terakhir.

Deskrpsi 

Sebagai Masalah Grafik

TSP dapat dimodelkan sebagai graf tak berarah berbobot, sehingga kota adalah simpul dari graf tersebut, jalan adalah sisinya, dan jarak suatu lintasan adalah bobot sisinya. Ini adalah masalah minimalisasi yang dimulai pada titik tertentu dan berakhir setelah mengunjungi titik lain tepat satu kali. Seringkali modelnya berupa graf lengkap (yaitu setiap pasangan simpul dihubungkan oleh sebuah sisi). Jika tidak ada jalur antara dua kota, menambahkan sisi yang cukup panjang akan melengkapi grafik tanpa mempengaruhi jalur optimal.

Asimetris dan simetris
Pada TSP simetris, jarak antara dua kota sama besar pada setiap arah yang berlawanan sehingga membentuk grafik tidak berarah. Simetri ini mengurangi separuh jumlah solusi yang mungkin. Dalam TSP asimetris, jalur di kedua arah mungkin tidak ada atau jaraknya mungkin berbeda, sehingga menghasilkan grafik berarah. Kemacetan lalu lintas, jalan satu arah, dan tarif penerbangan kota dengan biaya keberangkatan dan kedatangan yang berbeda menjadi pertimbangan nyata yang secara asimetris dapat menimbulkan masalah TSP.

Disadur dari : https://en.wikipedia.org/wiki/Travelling_salesman_problem

Selengkapnya
Apa itu Traveling Salesman Problem dan Bagaimana Sejarahnya

Operation Research and Analysis

Teknik Probabilistik untuk Memperkirakan Optimum Global suatu Fungsi (Simulated annealing)

Dipublikasikan oleh Dias Perdana Putra pada 19 Februari 2024


Simulated Annealing

Simulated Annealing (SA) adalah teknik probabilistik untuk memperkirakan maksimum global suatu fungsi tertentu. Secara khusus, ini adalah metaheuristik untuk memperkirakan optimasi global dalam ruang pencarian masalah optimasi yang besar. Untuk sejumlah besar optima lokal, SA dapat menemukan optima global. Ini sering digunakan ketika ruang pencariannya terpisah (misalnya masalah penjual keliling, masalah kepuasan logis, prediksi struktur protein, dan perencanaan lokakarya). Untuk permasalahan di mana menemukan perkiraan optimal global lebih penting daripada menemukan optimal lokal yang tepat pada waktu yang tetap, simulasi anil bisa lebih baik daripada algoritma yang tepat seperti penurunan gradien atau cabang dan batas.

Nama algoritme ini berasal dari anil dalam metalurgi, suatu teknik di mana suatu material dipanaskan dan didinginkan secara terkendali untuk mengubah sifat fisiknya. Keduanya merupakan sifat material yang bergantung pada energi bebas termodinamikanya. Bahan pemanas dan pendingin mempengaruhi suhu dan energi bebas termodinamika, atau energi Gibbs. Simulasi anil dapat diterapkan pada masalah optimasi yang sulit secara komputasi di mana algoritma yang tepat gagal; Meskipun pendekatan ini umumnya menghasilkan solusi yang mendekati nilai minimum global, namun pendekatan ini cukup untuk memecahkan banyak permasalahan praktis.Masalah yang dipecahkan oleh SA saat ini dirumuskan menggunakan fungsi tujuan multivariabel, yang tunduk pada banyak batasan matematis.Dalam praktiknya, batasan ini dapat dipandang sebagai bagian dari fungsi tujuan.

Teknik serupa telah diperkenalkan secara independen beberapa kali, termasuk Pincus (1970), Khachaturyan et al. (1979,  1981), Kirkpatrick, Gelatt dan Vecchi (1983) dan Cerny (1985). Pada tahun 1983, Kirkpatrick, Gelatt Jr., Vecchi, menggunakan pendekatan ini untuk memecahkan masalah penjual. Mereka juga menyarankan nama saat ini Simulated Annealing.

Gagasan pendinginan lambat yang diterapkan dalam algoritma simulasi anil ditafsirkan sebagai penurunan perlahan dalam kemungkinan menerima solusi yang lebih buruk seiring dengan eksplorasi ruang solusi.Menerima solusi yang lebih buruk memungkinkan pencarian solusi optimal global yang lebih komprehensif. Secara umum, algoritma simulasi anil bekerja sebagai berikut. Suhu turun dari nilai positif awal menjadi nol. Pada setiap langkah waktu, algoritme secara acak memilih solusi yang mendekati solusi saat ini, mengukur kualitasnya, dan bergerak ke arah solusi tersebut sesuai dengan probabilitas yang bergantung pada suhu untuk memilih solusi yang lebih baik atau lebih buruk daripada tetap pada angka 1 selama pencarian
masing-masing solusi. (atau positif). ) dan menurun menuju nol.

Simulasi dapat dilakukan dengan menyelesaikan persamaan kinetik fungsi kepadatan probabilitas atau menggunakan metode stochastic sampling. Metode ini merupakan adaptasi dari algoritma Metropolis-Hastings, metode Monte Carlo untuk menghasilkan keadaan pola sistem termodinamika, yang diterbitkan oleh N. Metropolis et al. pada tahun 1953.

Gambaran umum

Keadaan suatu sistem fisik dan fungsi E(s) yang harus diminimalkan adalah analog dengan energi dalam sistem dalam keadaan tersebut. Tujuannya adalah untuk membawa sistem dari keadaan awal yang berubah-ubah ke keadaan dengan energi serendah mungkin.

Iterasi dasar
Pada setiap langkah, heuristik anil yang disimulasikan memperhitungkan beberapa keadaan tetangga s* dari keadaan s saat ini dan memutuskan secara probabilistik apakah sistem dipindahkan ke keadaan s* atau tetap dalam keadaan s. Kemungkinan ini pada akhirnya menyebabkan sistem bertransisi ke keadaan energi yang lebih rendah. Biasanya, langkah ini diulangi hingga sistem mencapai kondisi yang cukup baik untuk aplikasi atau hingga anggaran komputasi tertentu habis.

Tetangga suatu negara
Optimalisasi solusi melibatkan evaluasi tetangga dari keadaan masalah, yang merupakan keadaan baru yang diciptakan oleh perubahan konservatif pada keadaan tertentu. Misalnya, dalam masalah penjual, setiap negara bagian biasanya didefinisikan sebagai permutasi kota-kota yang akan dikunjungi, dan tetangga suatu negara bagian adalah himpunan permutasi yang dibuat dengan menukarkan kedua kota tersebut. Cara-cara perubahan negara-negara bagian yang terdefinisi dengan baik untuk menciptakan negara-negara tetangga disebut “pergerakan”, dan pergerakan yang berbeda menghasilkan kumpulan negara-negara tetangga yang berbeda. Langkah-langkah ini umumnya menghasilkan perubahan minimal pada keadaan akhir dalam upaya untuk meningkatkan solusi secara bertahap melalui perbaikan berulang pada bagian-bagiannya (misalnya koneksi kota dalam masalah penjual).
Tidak ada jaminan bahwa heuristik sederhana seperti pendakian bukit, yang bergerak mencari satu demi satu tetangga terbaik dan berhenti ketika mereka telah mencapai solusi yang tidak ada tetangganya, akan menjadi solusi yang lebih baik, tidak dapat dijamin akan mengarah pada solusi yang lebih baik. solusi terbaik yang ada; Hasilnya mungkin hanya berupa optimum lokal, sedangkan solusi terbaik sebenarnya adalah optimum global, yang mungkin berbeda-beda.Metaheuristik menggunakan tetangga suatu solusi untuk mengeksplorasi ruang solusi. Meskipun mereka lebih memilih tetangga yang lebih baik, mereka juga menerima tetangga yang lebih buruk agar tidak terjebak dalam optimal lokal. Mereka dapat menemukan titik optimal global jika dijalankan dalam jangka waktu yang cukup lama.

Jadwal anil

suatu algoritma yang memerlukan integrasi fungsi-fungsi yang berkaitan dengan fluktuasi suhu ke dalam karakteristik operasinya. Algoritma ini memerlukan penurunan suhu secara bertahap selama simulasi, dimulai dari suhu tinggi dan kemudian menurun pada setiap langkah sesuai dengan jadwal anil yang dapat ditentukan pengguna. Pendekatan ini memungkinkan sistem untuk pertama-tama menjelajahi wilayah ruang pencarian yang luas, mengabaikan
fitur kecil dari fungsi energi, kemudian bergerak menuju wilayah energi rendah yang semakin sempit, dan akhirnya turun sesuai dengan heuristik penurunan paling curam. Meskipun bersifat teoritis, kemungkinan algoritma ini mencapai solusi optimal global meningkat hingga mendekati 1 seiring dengan perluasan program anil untuk setiap permasalahan yang terbatas. Namun, hasil teoritis ini penggunaannya terbatas karena waktu yang diperlukan untuk mencapai keberhasilan yang signifikan kemungkinan besar melebihi waktu yang diperlukan untuk melakukan pencarian menyeluruh dalam ruang solusi.

Disadur dari :https://en.wikipedia.org/wiki/Simulated_annealing

Selengkapnya