Simulated annealing

Sepuh lindap berimak (bahasa Inggris: simulated annealing, SA) adalah salah satu algoritme untuk optimisasi yang bersifat awam. Berdasarkan peluang dan mekanika statistik, algoritme 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, diterapkan pada rancangan optimal peranti keras komputer, dan juga pada salah satu masalah klasik ilmu komputer yaitu Traveling Salesman Problem.

Sepuh lindap adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan dalam mempelajari proses pembentukan kristal dalam suatu bahan. 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 sepuh lindap, memberikan kesempatan pada atom-atom dalam materi itu untuk bergerak secara bebas, mengingat tingkat tenaga 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 (sepuh lindap) yang telah dijelaskan di atas. Pada awal proses SA, dipilih suatu solusi awal, yang mewakilkan kondisi materi sebelum proses dimulai. Gerakan bebas dari atom-atom pada materi, diwakilkan dalam bentuk oprek terhadap solusi awal/solusi sementara. Pada awal proses SA, saat parameter suhu (T) diatur tinggi, solusi sementara yang sudah ada diperbolehkan untuk mengalami oprek 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 oprek ini membaik (dalam masalah optimisasi yang berusaha mencari minimum berarti nilainya lebih kecil/downhill) solusi hasil oprek ini akan digunakan sebagai solusi selanjutnya.

Bila nilai fungsi evaluasi hasil oprek ini memburuk, pada saat suhu sepuh lindap masih tinggi, solusi yang lebih buruk (uphill) ini masih mungkin diterima, sedangkan pada saat suhu sepuh lindap sudah relatif rendah, solusi hasil oprek yang lebih buruk ini mungkin tidak dapat diterima. Dalam tahapan selanjutnya saat suhu sedikit demi sedikit dikurangi, maka kemungkinan untuk menerima langkah oprek yang tidak memperbaiki nilai fungsi evaluasi semakin berkurang. Sehingga kebebasan untuk mengoprek solusi semakin menyempit, sampai akhirnya diharapkan dapat diperoleh solusi yang mendekati solusi optimal. Pada suhu rendah ini, SA biasanya menggunakan konsep Hill-Climbing.

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

• Pewakilan yang cermat dari konfigurasi dalam suatu permasalahan.
• Proses oprek, 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 sepuh lindap, dan berapa lama proses ini harus dilakukan.

  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 suhu sesuai jadwal tertentu
         

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

Modifikasi atau oprek: 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): Peluang 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 sepuh lindap, karena faktor T sebagai pembagi masih bernilai besar, peluang 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 suhu. 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 di dalam while ini, untuk mengulang simulasi pada suhu yang sama).

• 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.