Simulated Annealing merupakan metode searching yang memanfaatkan teori probabilitas untuk mencari global minimum dari suatu permasalahan optimasi. Simulated annealing umumnya digunakan untuk variabel yang bersifat categorical. Target dari metode ini adalah menemukan solusi bagus yang bisa diterima, bukan untuk mencari solusi yang terbaik. Nama annealing berasal dari keilmuan metallurgy, di mana proses tersebut akan berusaha mencari suatu posisi suhu tertentu yang optimal untuk mengurangi kerusakan dan menambah ukuran kristal di dalam suatu material.
Analogi dengan proses tersebut, metode Simulated Annealing ini juga berusaha untuk mencari solusi dengan berpindah dari solusi yang satu ke solusi yang lainnya, dan apabila solusi baru yang diuji mempunyai nilai fungsi ‘energy’ yang lebih kecil, maka solusi yang sedang diuji akan menggantikan solusi yang lama. Umumnya solusi baru yang dipilih merupakan solusi yang ada di dekat/sekitar solusi yang lama. Fungsi energi ini sangat bergantung pada parameter-parameter seperti parameter T (yang sering disebut dengan parameter “Temperature”). Metode ini merupakan adaptasi dari algoritma Metropolis-Hasting, yang merupakan suatu jenis metode Monte Carlo, untuk menciptakan sample state yang diperlukan.
Dalam metode ini, beberapa parameter terkait harus didefinisikan termasuk, the state space (umumnya berupa vector yang terdiri dari beberapa karakteristik), fungsi energy, prosedur untuk menciptakan solusi baru, fungsi probabilitas untuk menerima atau menolak, dan fungsi jadwal annealing dengan keterangan sebagai berikut:
- The state space umumnya ditentukan dengan melihat pada objek yang menjadi domain space pencarian.
- Fungsi energy umumnya menyesuaikan pada state space dan beberapa parameter kaitan lainnya.
- Prosedur untuk menciptakan solusi baru harus ditentukan seefisien mungkin dengan memikirkan karakteristik yang menjadi objek optimasi. Metode swapping antar karakteristik juga menjadi salah satu solusinya.
- Fungsi probabilitas untuk menerima atau menolak umumnya mempunyai bentuk tertentu dan bergantung pada apakah objek optimasi dapat merupakan fungsi probabilitas atau tidak. Fungsi probabilitas yang sering digunakan adalah fungsi probabilitas yang terkait dengan algoritma Metropolis-Hastings.
- Sedangkan untuk rate jadwal annealing umumnya ditentukan dengan melihat permasalahan yang ada pada objek optimasi dan ditentukan secara empiris.
Referensi:
[1] Kirkpatrick, S., Gelatt C. D., Vecchi M. P. (1983). Optimization by Simulated Annealing. Science. New Series 220 (4598): pp. 671 – 680. ISSN: 00368075.
[2] Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E. (1953). Equations of State Calculations by Fast Computing Machines. Journal of Chemical Physics, 21 (6): pp. 1087 – 1092.
Recent Comments