Simulated Annealing

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 :

clip_image002

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.

Iklan

11 thoughts on “Simulated Annealing

  1. Terima kasih telah membaca tulisan saya ini. InsyaAllah, akan terus diperbarui.

    Semangat Belajar!

  2. Terima kasih tulisannya, saya lagi coba2 maen dengan SA Inversion. Tapi untuk diterapkan dengan teori inversi masih banyak yang belum bsa saya mengerti. Thanks

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s