Simulated Annealing

Simulated Annealing adalah optimasi dari algoritma Stochastic dan Metaheuristic. Dan simulated annealing adalah adaptasi dari algoritma Metropolis-Hasting Montecarlo dan digunakan dalam fungsi pengoptimalan. Sebagaimana algoritma Genetik, Simulated Annealing juga menjadi basis untuk pengembangan dari algoritma yang lebih khusus seperti Parallel Simulated Annealing, Fast Simulated Annealing dan Adaptive Simulated Annealing.
Inspirasi
Simulated Annealing terinspirasi oleh proses peleburan logam dalam metalurgi. Dalam proses alami ini material logam dipanaskan pada suhu tinggi hingga mencair dan kemudian didinginkan secara perlahan dalam kondisi terkontrol untuk memperbesar ukuran kristal logam dan mengurangi cacat pada kristal logam tersebut. Hasil dari proses ini adalah meningkatnya kekuatan dan ketahanan dari material logam tersebut. Suhu panas meningkatkan energi atom menjadikannya bergerak bebas dan pendinginan perlahan yang terkontrol memungkinkan konfigurasi energi yang kecil yang didapat.
Strategi
Tujuan teknik pemrosesan informasi ini adalah untuk menghasilkan konfigurasi harga minimum dalam pencarian. Rancangan aksi algoritma ini adalah untuk secara probabilistik membuat sampling dari permasalahan, dimana penerimaan sampel baru ke sampel yang sedang dikerjakan diatur oleh fungsi probabilistik harga sampel yang lebih cerdas, fungsi ini menerima eksekusi berulangkali dalam algoritma ini. Keputusan probabilistik ini berdasar pada metropolis-hasting untuk menyimulasikan sampel-sampel dalam sistem thermodinamika.
Persamaan yang digunakan untuk fungsi probabilisik ini adalah persamaan Boltzman, yaitu
p(ΔΕ)=e-ΔΕ/kT
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

Prosedur
Algorithm 4.2.1: Pseudocode for Simulated Annealing.
Input: ProblemSize, iterationsmax , tempmax
Output: Sbest
1 Scurrent ← CreateInitialSolution(ProblemSize);
2 Sbest ← Scurrent ;
3 for i = 1 to iterationsmax do
4 Si ← CreateNeighborSolution(Scurrent );
5 tempcurr ← CalculateTemperature(i, tempmax );
6 if Cost(Si ) ≤ Cost(Scurrent ) then
7 Scurrent ← Si ;
8 if Cost(Si ) ≤ Cost(Sbest ) then
9 Sbest ← Si ;
10 end
11 else if Exp(Cost(Scurrent ) – Cost(Si ) / tempcurr ) > Rand () then
12 Scurrent ← Si ;
13 end
14 end
15 return Sbest ;

Heuristik

  • Simulated Annealing (SA) di desain untuk digunakan dengan kombinasi masalah optimasi. Meskipun telah diadaptasi untuk fungsi berkelanjutan masalah optimasi.
  • Hasil pembuktian meyakinkan bahwa dengan periode pendinginan yang cukup lama, maka sistem akan mencapai pada global optimum. Kelemahan teori pencarian ini adalah jumlah sampel yang diambil untuk mencapai nilai optimum pada suatu masalah bisa lebih banyak daripada keseluruhan enumerasi pencarian.
  • Peningkatan kinerja dapat diberikan dengan memindah skema kandidat yang terseleksi dengan yang lebih tinggi harganya.
  • Mengulang jadwal pendinginan menggunakan solusi terbaik yang ditemukan dapat mengarahkan untuk meningkatkan hasil.
  • Memungkinkan menerima solusi yang lebih jelek, karena pertimbangan dari kandidat yang dimungkinkan oleh delta E.
  • Besarnya neighborhood dipertimbangkan dalam menurunkan kandidat solusi, bisa juga berubah setiap kali dieksekusi, dipengaruhi oleh temperatur, jauh dekatnya inisial permulaan.
  • Masalah Metode heuristik tertentu dapat digunakan untuk menyediakan titik awal pencarian

ref: banyak sumber dan belum sempat ditulis

About Author:

kadang NgeBlog, kadang baca buku, Pengguna linux biasa yang kadang ngajar tentang IT, kadang matematika dan kadang juga tentang web

Leave A Comment