Simulated Annealing adalah suatu algoritma optimasi yang mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir kristal atau logam.
Ide Dasar
Apabila suatu materi dipanaskan hingga mencair, kemudian didinginkan secara perlahan maka akan dihasilkan kristal – kristal dengan kualitas baik. sebaliknya, jika materi didinginkan terlalu cepat, maka kristal yang dihasilkan pun tidak akan sempurna. Konsep ini yang kemudian diadaptasi oleh SA untuk menyelesaikan beragam permasalahan optimasi.
SA juga menggunakan persamaan Boltzman dalam sistem termodinamika. Persamaan ini merepresentasikan probabilitas suatu new state lebih buruk dari current state masih mungkin terpilih sebagai next state. Berikut adalah persamaan dari probabilitas yang digunakan :
Dalam persamaan tersebut, k adalah konstanta Boltzman, T adalah temperatur dan r adalah bilangan acak antara 0 dan 1. Sedangkan fungsi biaya, direpresentasikan dengan nilai delta energi. Semakin kecil temperatur (T), maka probabilitasnya pun akan semakin kecil. Berbeda dengan temperatur, nilai delta energi yang semakin besar akan membuat probabilitas semakin kecil. Probabilitas yang semakin kecil menandakan bahwa kemungkinan terpilihnya suatu new state dengan biaya yang lebih besar dari current state akan semakin kecil.
Berikut ini adalah pemetaan dari Physical Annealing ke Simulated Annealing :
| Fisika (termodinamika) | Simulated Annealing |
| Keadaan sistem | Solusi yang mungkin |
| Energi | Biaya |
| Perubahan keadaan | Solusi tetangga |
| Temperatur | Parameter kontrol |
| Keadaan beku | Solusi heuristik |
Penjelasan lebih lanjut mengenai algoritma SA, akan dituliskan pada postingan selanjutnya. Semoga bermanfaat.
