Simulated annealing
Simulated Annealing (SA) adalah algoritma optimasi generik. Berdasarkan probabilitas dan mekanika statistik, algoritma ini dapat digunakan untuk menemukan perkiraan solusi optimal global terhadap suatu masalah. Permasalahan yang memerlukan pendekatan SA adalah permasalahan optimasi kombinatorial dimana ruang pencarian solusi yang ada terlalu besar sehingga hampir tidak mungkin menemukan solusi yang tepat dari permasalahan tersebut. Pendekatanini pertama kali diterbitkan oleh S. Kirkpatrick, C.D. Gelatt dan M. P. Vecchi, diterapkan pada desain perangkat keras komputer yang optimal dan juga pada salah satu masalah klasik ilmu komputer, yaitu masalah penjual.
Annealing merupakan salah satu teknik terkenal di bidang metalurgi yang digunakan untuk mempelajari proses pembentukan kristal pada suatu material. Untuk membentuk struktur kristal yang sempurna, bahan perlu dipanaskan sampai tingkat tertentu kemudian didinginkan secara perlahan dan terkendali. Pemanasan material pada awal proses annealing memberikan peluang bagi atom-atom dalam material untuk bergerak bebas, mengingat tingkat energi pada keadaan panasini cukup tinggi. Proses pendinginan yang lambat memungkinkan atom-atom yang sebelumnya bergerak bebas akhirnya menemukan lokasi optimal di mana energi internal yang dibutuhkan atom untuk mempertahankan posisinya minimal.
Simulated Annealing berjalan berdasarkan analogi dengan proses annealing yang telah dijelaskan di atas. 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, sedangkan pada saat temperatur annealing sudah relatif rendah, solusi hasil modifikasi yang lebih buruk ini mungkin tidak dapat 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 dapat diperoleh solusi yang mendekati solusi optimal. Pada temperatur rendah ini, SA biasanya menggunakan konsep Hill-Climbing.
Disadur dari: https://id.wikipedia.org/wiki/Simulated_annealing