Simulated annealing

Simulated Annealing (SA) adalah salah satu algoritma untuk untuk optimisasi yang bersifat generik. Berbasiskan probabilitas dan mekanika statistik, algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial, dimana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu. Publikasi tentang pendekatan ini pertama kali dilakukan oleh S. Kirkpatrick, C. D. Gelatt dan M. P. Vecchi, diaplikasikan pada desain optimal hardware komputer, dan juga pada salah satu masalah klasik Ilmu Komputer yaitu Traveling Salesman Problem.

Annealing adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan dalam mempelajari proses pembentukan kristal dalam suatu materi. Agar dapat terbentuk susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan terkendali dari materi tersebut. Pemanasan materi di awal proses annealing, memberikan kesempatan pada atom-atom dalam materi itu untuk bergerak secara bebas, mengingat tingkat energi dalam kondisi panas ini cukup tinggi. Proses pendinginan yang perlahan-lahan memungkinkan atom-atom yang tadinya bergerak bebas itu, pada akhirnya menemukan tempat yang optimum, dimana energi internal yang dibutuhkan atom itu untuk mempertahankan posisinya adalah minimum.

Simulated Annealing , berjalan berdasarkan analogi dengan proses annealing yang telah dijelaskan diatas. Pada awal proses SA, dipilih suatu solusi awal, yang merepresentasikan kondisi materi sebelum proses dimulai. Gerakan bebas dari atom-atom pada materi, direpresentasikan dalam bentuk modifikasi terhadap solusi awal/solusi sementara. Pada awal proses SA, saat parameter suhu (T) diatur tinggi, solusi sementara yang sudah ada diperbolehkan untuk mengalami modifikasi secara bebas.

Kebebasan ini secara relatif diukur berdasarkan nilai fungsi tertentu yang mengevaluasi seberapa optimal solusi sementara yang telah diperoleh. Bila nilai fungsi evaluasi hasil modifikasi ini membaik (dalam masalah optimisasi yang berusaha mencari minimum berarti nilainya lebih kecil/downhill) solusi hasil modifikasi ini akan digunakan sebagai solusi selanjutnya. Bila nilai fungsi evaluasi hasil modifikasi ini memburuk, pada saat temperatur annealing masih tinggi, solusi yang lebih buruk (uphill) ini masih mungkin diterima. Dalam tahapan selanjutnya saat temperatur sedikit demi sedikit dikurangi, maka kemungkinan untuk menerima langkah modifikasi yang tidak memperbaiki nilai fungsi evaluasi semakin berkurang. Sehingga kebebasan untuk memodifikasi solusi semakin menyempit, sampai akhirnya diharapkan diperoleh solusi yang mendekati solusi optimal.

Pseudo Code

  SolusiSementara         = Pilih Suatu Solusi Awal (Random Initialization)
  NilaiEvaluasiSementara  = Evaluasi(SolusiSementara)
  T                       = Suhu awal 

  WHILE (belum tercapai konvergensi yang diinginkan) :

        SolusiBaru        = Modifikasi(SolusiSementara)
        NilaiEvaluasiBaru = Evaluasi(SolusiBaru)
        IF ( SolusiBaru lebih baik ) :
               SolusiSementara        = SolusiBaru
               NilaiEvaluasiSementara = NilaiEvaluasiBaru
        ELSE :
               Delta = SolusiBaru - SolusiSementara
               IF exp(-Delta/T) > Random(0 ..1) :
                   SolusiSementara        = SolusiBaru
                   NilaiEvaluasiSementara = NilaiEvaluasiBaru

        T = 0.9*T       // Turunkan temperatur sesuai jadwal tertentu