Penerapan Dan Penjelasan Algoritma Simulated Annealing

Algoritma optimasi adalah prosedur yang dijalankan secara iteratif dengan membandingkan berbagai solusi sampai diperoleh solusi yang optimal. Ada berbagai jenis algoritma optimasi yang digunakan saat ini.

Deterministic Methods
Stochastic Methods
Nature Inspired Techniques

Artikel ini membahas tentang teknik Simulated annealing yang umumnya merupakan metode stokastik.

Simulated Annealing (SA) : Ini adalah teknik probailistik untuk mendekati optimum global dari fungsi yang diberikan.

"Annealing" mengacu pada analogi dengan termodinamika, khususnya dengan cara logam mendingin dan melebur. Simulasi anil adalah bentuk optimasi yang efektif dan umum. Hal ini berguna dalam menemukan optima global di hadapan sejumlah besar optima lokal. Simulasi anil menggunakan fungsi tujuan sebagai masalah optimasi, bukan energi material.

Implementasi dari simulasi anil ternyata sangat sederhana. Algoritme pada dasarnya adalah mendaki bukit kecuali alih-alih memilih langkah terbaik, algoritma ini memilih langkah acak. Jika langkah yang dipilih meningkatkan solusi, maka itu selalu diterima. Jika tidak, algoritme tetap bergerak dengan probabilitas kurang dari 1.

Probabilitas menurun secara eksponensial dengan buruknya pergerakan, yang merupakan jumlah deltaE yang memperburuk solusi (yaitu energi meningkat).

Prob( menerima gerakan menanjak)~ 1-exp( deltaE / KT ), di mana k harus berada di antara 0,8 hingga 0,99 .

Parameter T juga digunakan untuk menentukan probabilitas. Hal ini analog dengan suhu. dalam sistem anil. Pada nilai T yang lebih tinggi, gerakan menanjak seperti terjadi. Karena T cenderung nol, mereka menjadi semakin tidak mungkin, sampai algo. berperilaku seperti mendaki bukit.

Dalam masalah optimasi SA, T dimulai pada tinggi dan secara bertahap menurun sesuai dengan penjadwalan anil.

Simulasi Algoritma Annealing

SA membedakan antara local optima yang berbeda.

SA adalah algoritme tanpa memori, algoritme tidak menggunakan informasi apa pun yang dikumpulkan selama pencarian.

SA adalah algoritme peningkatan iteratif.

Aplikasi

Partisi sirkuit dan penempatan
Partisi grafik
Pemrosesan gambar
VLSI: penempatan, perutean
Partisi perangkat keras/perangkat lunak
Penjadwalan strategi untuk produk modal dengan struktur produk yang kompleks
Situasi pembelajaran berbasis peristiwa.

Keuntungan:

dapat menangani dengan sistem arbitrer dan fungsi biaya
secara statistik jaminan untuk menemukan solusi optimal
Ini relatif mudah dikodekan dan bahkan untuk masalah kompleks
Umumnya memberikan baik solusi.

Kekurangan:

Untuk masalah di mana energi lanskap halus, atau hanya ada sedikit minimum lokal, SA berlebihan.
Anil berulang kali dengan 1/log(k) jadwal sangat lambat, terutama jika fungsi biaya mahal untuk dihitung.

Kesimpulan:

Simulated annealing menjamin konvergensi setelah menjalankan sejumlah iterasi yang cukup besar.
Algoritma simulasi annealing biasanya lebih baik daripada algoritma serakah dalam hal masalah yang memiliki banyak solusi optimal lokal.