Algoritma Optimasi Simulated Annealing

A.    APA ITU SIMULATED ANNEALING?

Simulated Annealing (SA) adalah metode optimasi yang dapat digunakan untuk memecahkan masalah (Numerical Recipes 3rd Edition, 2007). Simulated Annealing sendiri merupakan algoritma untuk optimisasi yang bersifat generik. Dengan menggunakan probabilitas dan mekanika statik, algoritma ini dapat digunakan untuk mencari pendekatan terhadapa solusi optimum global dari suatu permasalahan. Namun, SA tidak selamanya sempurnya sebagai metode optimasi dalam pemecahan masalah, terdapat beberapa kekurangan yang mempengaruhi hasil akhir.  Pendekatan SA dilakukan oleh S. Kirkpatric, C. D. Gelatt dan M. P. Vecchi.

Penggunaan Simulated Annealing beride terkait dengan pemrosesan logam. Kata Annealing didefinisikan sebagai memansakan kemudian mendinginkan. SA memanfaatkan analogi antara cara pendinginan dan pembekuan suatu bahan metal agar menjadi sebuah strujtur kristal dengan energi yang minimal (proses penguatan) dan juga untuk mencari state tujuan minimal dalam proses pencarian. Pada SA, terdapat beberapa parameter penting yang sangat menentukan, diantaranya Temperatur untuk terjadinya banyak perulangan serta perbandingan. Juga Pembangkitan bilangan random yang akan bersangkut paut dengan adanya probabilitas.

 

B.    Proses Simulated Annealing

SA dianjurkan untuk masalah optimasi yang kompleks, Maka dari Itu algoritma dimulai pada suhu tertentu, Seiring berjalanya waktu, suhu secara bertahap akan menurun mengikuti jadwal pendinginan yang dapat dilihat pada gambar dibawah ini.

Terilihat dalam gambar, bahwa suatu temperatur yang tinggi (ilustrasi : pada saat logam panas) maka ada suatu titik yang dimana akan jadi batas penguatan/kristalisasi yang ditandai dengan nilai terendah. Karena Logam tersebut panas, maka akan semakin mudah untuk dibentuk. Seiring berjalannya waktu maka temperatur akan turun karena adanya perubahan suhu (di analogikan sebagai iterasi dalam algoritma), maka atom dan molekul logam akan saling mengikat kembali, dan mereka akan menemukan cara untuk saling mengikat dengan energi yang paling minimal.

Salah satu ciri utama SA adalah selalu memberikan solusi, meski solusinya mungkin tidak optimal. Untuk beberapa masalah optimasi yang tidak mudah dimodelkan, SA dapat memberikan pilihan praktis untuk menyelesaikannya.

 

C.       Permodelan dengan SA

Menurut Kirkpatrick, ada empat hal utama yang perlu diperhatikan dalam penggunaan SA untuk memodelkan suatu permasalahan :

  • Representasi yang akurat dari wujud dalam suatu permasalahan.
  • Proses modifikasi, langkah acak atau perubahan yang harus dilakukan terhadap elemen-elemen untuk menghasilkan nilai lainnya.
  • Fungsi yang dapat menentukan baik-buruknya suatu solusi terhadap permasalahan.
  • Jadwal Penurunan suhu dalam proses annealing, dan waktu proses ini harus dilakukan.

Dengan Bahasa lain, hal terpenting dan berpengaruh dalam penggunaan SA didalam pengimplementasiannya (algoritma) ada 3 hal yaitu :

  • Nilai Awal untuk Temperatur yang ditetapkan cukup besar.
  • Kriteria yang dipakai untuk memutuskan apakah temperature sistem seharusnya dikurangi atau tidak.
  • Berapa besarnya pengurangan temperature dalam setiap waktu.

D.      Prosedur Pencarian Simulated Annealing

Berikut merupakan prosedur pencarian dalam Simulated Annealing:

  1. Inisialisasi minimal 2 buah variabel yang nilainya dipilih secara random.
  2. Menetapkan suhu awal temperature.
  3. Menetapkan nilai pendinginan temperature.
  4. Menetapkan Fungsi hitung
  5. Membuat Pengkondisian Looping ketika Temperatur Masih Tinggi, ada 2 kondisi :

– Jika proses sudah mencapai kriteria, program terhenti, dan keluar dari looping

– Jika Proses belum mencapai kriteria, maka program akan melakukan perulangan terus dan membandingkan nilai terus.

  1. Menginisialisasi kembali 2 buah variabel yang bernilai random (ini akan menjadi nilai baru pembanding selama perulangan).
  2. Menetapkan Fungsi hitung
  3. Membuat pengkondisian hasil fungsi terkecil, terdapat 3 kondisi :

– Jika Nilai Fungsi Baru ternyata Lebih Kecil dari nilai Fungsi Sekarang,maka Nilai Baru di masukkan ke variabel Fungsi Sekarang. (Mendapatkan nilai terkecil).

– Jika Nilai Fungsi Baru ternyata Lebih Besar dari nilai Fungsi Sekarang, maka Nilai Baru akan dihitung Probabiltias nya, apakah dia nilai yang optimum atau tidak dengan kondisi apakah exp(-ΔE) > |0…1|* . Jika Benar, ,maka Nilai Baru di masukkan ke variabel Fungsi Sekarang. (Mendapatkan nilai optimum).

– Jika Nilai Fungsi Baru ternyata Lebih Besar dari nilai Fungsi Sekarang dan Tidak Optimum, maka Nilai Terkecil dan teroptimum tetap di pegang olehFungsi Sekarang.

  1. Menghitung penentu Iterasi Temperature, dengan mendinginkan Temperatur (temperature * pendingin).
  2. Mengeluarkan nilai terkecil/teroptimum.

* Keterangan = ΔE adalah (Nilai Terbesar – Nilai Terkecil/Temp)

 

Berikut Merupakan Pseudocode Pencarian dalam Simlated Annealing :

 

VariabelSolusiSementara = Pilih Suatu Solusi Awal (Random Initialization)

NilaiFungsi Sementara   = Evaluasi(SolusiSementara)/ Hasil Fungsi

Temperature             = Suhu awal

Coolingr ate            = Pendinginan Suhu

 

WHILE (belum tercapai konvergensi yang diinginkan) :

Variabel SolusiBaru  = Modifikasi(SolusiSementara)

NilaiFungsiBaru      = Evaluasi(SolusiBaru)

IF ( SolusiBaru lebih baik ) :

VaribelSolusiSementara   = variabelSolusiBaru

NilaiFunbgsiSementara    = NilaiFungsiBaru

ELSE :

Delta = NilaiFungsiBaru – NilaiFungsiLama

IF exp(-Delta/T) > Random(0 ..1) :

VariabelSolusiSementara = VariabelSolusiBaru

NilaiFungsiSementara    = NilaiFungsuiBaru

Temperature = temperature * coolingrate // Turunkan temperatur sesuai jadwal tertentu (iterasi)

Keluarkan NilaiFungsiSementara

Keluarkan VariabelSolusiSementra

 

Mungkin sekian dulu pembahasan singkat untuk simulated Annealing. Ditunggu post selanjutnya ya untuk contoh studi kasus dan kesimpulannnya

 

 

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *