METODE MINIMISASI SIMULATED ANNEALING

Metode Simulated Annealing adalah metode minimisasi yang biasa dipakai untuk mencari harga minimum global suatu fungsi. Yang dimaksud dengan harga minimum global adalah harga minimum terendah suatu fungsi.

Metode Simulated Annealing dikembangkan dengan analogi proses termodinamika pendinginan logam. Pada suhu tinggi, molekul-molekul logam dapat bergerak bebas dan mempunyai sistem energi yang berharga besar. Jika logam tersebut didinginkan secara perlahan-lahan (disebut proses annealing), maka molekul-molekul logam akan bisa menjadi kristal, tetapi jika didinginkan secara cepat (disebut proses quenching), maka molekul-molekul logam tersebut akan bisa menjadi amorf. Pada keadaan kristal, molekul-molekul logam mempunyai energi paling rendah (identik dengan minimum global), dan pada keadaan amorf, molekul-molekul logam mempunyai energi yang sedikit lebih tinggi dari keadaan paling rendah (identik dengan minimum lokal).

Berdasarkan analogi di atas, jika ada suatu fungsi f(x) yang hendak diminimisasi terhadap variabel x dengan menggunakan Metode Simulated Annealing, maka algoritmanya dapat dijabarkan sebagai berikut:

1. Memasukkan awal suhu T dan variabel awal x₀.

2. Menganggap variabel awal x₀ sebagai variabel sekarang x_i.

3. Menghitung fungsi sekarang f (x_i).

4. Membangkitkan variabel baru x_i+1 secara acak.

5. Menghitung fungsi baru f = f (x_i+1).

6. Membangkitkan bilangan acak p yang berharga antara 0 – 1.

7. Membuat pilihan :

(1) jika harga p < exp { (f (x_i).- f (x_i+1))/T }, maka variabel baru dan fungsi baru diterima serta ditetapkan sebagai variabel sekarang dan fungsi sekarang.

(2) jika tidak, maka variabel baru dan fungsi baru ditolak.

8. Membuat pilihan :

(1) jika proses sudah mencapai kriteria berhenti, maka program dihentikan.

(2) jika belum, maka dilakukan penurunan harga suhu T secara perlahan lalu mengulangi lagi langkah ke-4.

Kriteria berhenti dapat berupa : jika iterasi mencapai jumlah tertentu atau jika selisih harga antara fungsi sekarang dan fungsi sebelumnya lebih kecil dari harga tertentu.

Pustaka :

• Basuki, A., Huda, M., Santoso, T. B., 2004, Modeling dan Simulasi, IPTAQ Mulia Media, Jakarta.
• Kusumadewi, S. dan Purnomo, H., 2005, Penyelesaian Masalah Optimasi Menggunakan Teknik-teknik Heuristik, Graha Ilmu, Yohyakarta.
• Press, W.H., Flannery, B.P., Teukolsky, S.A. dan Vetterling, W.T., 2007, Numerical Recipes, The Art of Scientific Computing, Cambridge University Press, Cambridge.