Benzetimli Tavlama (Simulated Annealing)

benzetimli tavlama nedir?

Benzetimli tavlama, çok sayıda olası çözüm arasından en iyisini (ya da en iyiye yakınını) bulmaya çalışan bir optimizasyon yöntemidir. Adını metalürjiden alır: bir metal ısıtılıp yavaşça soğutulduğunda atomları en düşük enerjili, en düzenli kristal yapısına yerleşir. Hızlı soğutulursa kusurlu, dengesiz bir yapı ortaya çıkar. Algoritma bu fiziksel süreci taklit eder.

nasıl çalışır?

Algoritma yüksek bir "sıcaklık" değeriyle başlar. Her adımda mevcut çözümde küçük bir değişiklik dener. Yeni çözüm daha iyiyse kabul edilir; daha kötüyse yine de belli bir olasılıkla kabul edilebilir. Kilit nokta bu: kötü hamleleri de ara ara kabul etmek, algoritmanın yerel bir tepeye (local optimum) takılıp kalmasını engeller.

Sıcaklık yüksekken kötü çözümlerin kabul olasılığı fazladır, yani algoritma cesurca dolaşır. Sıcaklık bir soğutma programına (cooling schedule) göre kademeli düştükçe seçicilik artar ve algoritma yavaşça en iyi çözüme yerleşir. Yaygın soğutma yöntemi geometriktir: her adımda sıcaklık sabit bir oranla (α) çarpılarak azaltılır. Soğutma çok hızlıysa çözüm yerel optimumda takılır; çok yavaşsa süreç gereksiz uzar.

neden önemli?

Gradient descent gibi yöntemler pürüzsüz, türevlenebilir problemlerde iyi çalışır ama karmaşık, çok tepeli çözüm uzaylarında yerel minimuma saplanabilir. Benzetimli tavlama türev bilgisi gerektirmez ve kötü hamleleri kontrollü biçimde kabul ederek bu tuzaktan kurtulabilir. Bu yüzden kombinatoryal ve düzensiz problemlerde güçlü bir alternatiftir.

kullanım alanları

Gezgin satıcı problemi (en kısa turu bulma), çip yerleşimi ve devre tasarımı, lojistik ve rota optimizasyonu, hiperparametre araması ve zamanlama (scheduling) problemleri klasik uygulama alanlarıdır. Kesin çözümün pratikte hesaplanamayacağı kadar büyük olduğu her yerde, "yeterince iyi" çözümü makul sürede bulmak için tercih edilir.