Apa itu Simulated Annealing?

Simulated annealing adalah teknik komputer yang dapat menemukan solusi yang baik — meskipun belum tentu optimal — untuk suatu masalah.Dinamakan demikian karena meniru proses metalurgi anil.Pada logam, annealing adalah proses pemurnian dengan cara memanaskan logam kemudian mendinginkannya secara perlahan.Programkomputer“memurnikan” ruang solusi sampai semua yang tersisa adalah solusi terbaik atau hampir terbaik.

Pria memegang komputer

Ada dua faktor penting yang harus ditentukan oleh pengguna program anil simulasi: suhu awal, atau persentase solusi buruk yang dapat dieksplorasi;dan laju pendinginan, yang merupakan laju penurunan persentase tersebut.Suhu awal yang rendah akan sering berakhir dengan hasil yang jauh dari optimal.Memulai pada suhu yang sangat tinggi dapat mengakibatkan pencarian memakan waktu lebih lama dari yang diperlukan.Demikian pula, laju pendinginan yang terlalu tinggi akan menghasilkan hasil yang buruk, sedangkan laju pendinginan yang sangat rendah akan menghasilkan program yang berjalan untuk waktu yang sangat lama.

Status “suhu tinggi” untuk program simulasi anil adalah pengaturan yang memungkinkannya melihat berbagai solusi, termasuk banyak solusi yang lebih buruk daripada solusi yang telah ditemukan.Komputer diizinkan untuk melihat banyak solusi yang lebih buruk daripada solusi saat ini untuk menghindari menempel pada minimum lokal yang jauh lebih buruk daripada yang terbaik.Sebagai contoh, seseorang dapat membayangkan memulai dari puncak bukit atau gunung dengan tujuan mencapai dasarnya.Sepanjang jalan mungkin ada selokan atau jurang.Jika komputer tidak dapat menanjak cukup jauh untuk keluar, komputer akan macet meskipun tidak berada di dekat pangkalan.

Seberapa jauh program dapat berjalan ditentukan oleh persentase solusi yang lebih buruk yang diizinkan untuk diperiksa oleh program.Dengan berlalunya waktu, solusi yang lebih baik secara progresif ditemukan dan risiko jurang yang dalam berkurang, sehingga persentase solusi yang lebih buruk yang dapat dijelajahi komputer berkurang.Mengurangi fraksi ini disebut sebagai “pendinginan”.Ketika suhu mencapai fraksi yang telah ditentukan sebelumnya — yang tidak perlu 0 — pencarian berakhir.

Alasan untuk menggunakan simulasi anil atau teknik pencarian kecerdasan buatan lainnya adalah untuk mengurangi jumlah waktu yang diperlukan untuk menemukan solusi yang mendekati optimal.Untuk banyak masalah, pencarian menyeluruh — pengujian setiap solusi yang mungkin terhadap satu sama lain kemungkinan solusi — bisa memakan waktu berbulan-bulan atau bertahun-tahun.Alternatif yang paling banyak dikenal untuk simulasi anil adalah algoritma genetika.Algoritme pencarian kecerdasan buatan populer lainnya termasuk optimasi koloni semut, optimasi gerombolan partikel, tetangga terdekat dan pengklasifikasi Bayesian.