Simulated Annealing

10 11 2009

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.


Actions

Information

6 responses

21 02 2014
marto

pak,
saya mau tanya,
apa kelebihan SA ini lengkapnya pak….
dan bagaimana bedanya dengan Harmony Search…
trima kasih.

15 06 2013
Indra

trim’s

31 01 2013
Agung K

Apakah bisa metode ini diterapkan untuk mengetahui parameter optimal proses injeksi plastik terkait presure, temperatur dan time?

6 01 2011
reynaldydhaka

Ma’af pak saya mau tanya tentang penerapan algoritma SA pada penjadwalan matakuliah. Bagaimana caranya?

16 02 2011
Yudi Agusta

Simulated annealing adalah salah satu metode searching dalam permasalahan optimasi. Untuk masalah penjadwalan kuliah, tentunya perlu untuk dirumuskan dulu permasalahan yang menjadi dasar penjadwalan kuliah tersebut. Misalnya berapa kelas yang bisa dilakukan paralel, berapa dosen yang tersedia, mata kuliah apa yang tidak boleh diambil dulu dibandingkan mata kuliah yang lain, mata kuliah mana yang ada prakteknya dll. Setelah semuanya bisa diformulasikan, Simulated Annealing digunakan untuk mencari solusi mana yang paling baik.

Demikian semoga membantu.

3 03 2011
reynaldydhaka

trima kasih.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: