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 Annealing
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: en.wikipedia.org