Simulated annealing

Latar Belakang

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, di mana 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, di mana 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.

Pemodelan dengan SA

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

• Representasi yang akurat dari konfigurasi dalam suatu permasalahan.
• Proses modifikasi, langkah acak atau perubahan apa yang harus dilakukan terhadap elemen-elemen konfigurasi untuk menghasilkan konfigurasi berikutnya.
• Fungsi evaluasi atau fungsi objektif yang dapat menyatakan baik-buruknya suatu solusi terhadap permasalahan
• Jadwal penurunan suhu dalam proses annealing, dan berapa lama proses ini harus dilakukan.

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
         

Keterangan Pseudo Code

Evaluasi : Fungsi evaluasi (cost function). Contoh dalam Traveling Salesman Problem (TSP) fungsi ini adalah jarak yang harus ditempuh oleh si penjaja keliling.

Modifikasi : Mekanisme sederhana untuk mengubah solusi yang sudah ada, untuk menghasilkan solusi baru yang berbeda tidak terlalu jauh dengan solusi yg sudah ada. Biasanya disebut neighbour solution. Contoh dalam TSP bila solusi sementara dari TSP dengan 3 kota adalah : A B C. Hasil fungsi modifikasi adalah solusi baru dengan urutan A C B.

exp(-Delta/T) : Probabilitas bahwa langkah/solusi baru yang tidak lebih baik, akan diterima sebagai solusi sementara. Perhatikan tanda minus dalam kurung. Delta bernilai positif, yang berarti solusi baru pada tahap ini lebih buruk daripada solusi sementara yang sudah ada. Expresi ini menyatakan bahwa semakin buruk solusi baru, kemungkinan diterima sebagai solusi sementara semakin kecil. Tetapi pada awal proses Annealing, karena faktor T sebagai pembagi masih bernilai besar, probabilitas ini akan tetap cukup besar. Tidak demikian halnya setelah T menurun, dalam proses pendinginan.

T = 0.9*T : hanya merupakan salah satu contoh jadwal penurunan temperatur. Sebenarnya tidak selalu harus seperti ini. Biasanya juga dalam implementasi SA, diadakan perulangan proses modifikasi dan update solusi sementara untuk suhu tertentu. (Jadi mestinya ada loop lagi didalam while ini, untuk mengulang simulasi pada suhu yang sama).

Referensi

• S. Kirkpatrick and C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, Vol 220, Number 4598, pages 671-680, 1983. http://citeseer.ist.psu.edu/kirkpatrick83optimization.html.