Simulated annealing

Sepuh lindap berimak 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 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 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.