Benzetimli Tavlama Nedir?

Benzetimli tavlama (simulated annealing), çok sayıda olası çözüm arasından iyi bir çözüm bulmak için kullanılan olasılıksal bir arama yöntemidir. Adını metalürjideki tavlama işleminden alır: metal yüksek sıcaklığa ısıtılıp yavaşça soğutulduğunda atomlar daha düzenli, düşük enerjili bir yapıya yerleşir. Yöntem 1983'te Kirkpatrick ve arkadaşlarının çalışmasıyla yaygınlaştı.

Benzetimli tavlama nedir?

Basit arama yöntemleri yalnızca daha iyi çözümlere geçer ve bu yüzden bir yerel minimuma takılabilir. Benzetimli tavlama ise "sıcaklık" adı verilen bir parametre kullanır. Sıcaklık yüksekken algoritma daha kötü çözümlere geçmeyi de sık sık kabul eder; böylece arama uzayını geniş biçimde keşfeder. Sıcaklık düştükçe kötü hamleleri kabul etme olasılığı azalır ve algoritma iyi bir bölgeye yerleşir.

Nasıl çalışır?

1. Bir başlangıç çözümü ve yüksek bir sıcaklık seçilir.
2. Mevcut çözümün küçük bir değişikliğiyle komşu bir çözüm üretilir.
3. Komşu daha iyiyse kabul edilir; daha kötüyse, farkın büyüklüğüne ve sıcaklığa bağlı bir olasılıkla kabul edilir.
4. Sıcaklık bir soğutma planına göre azaltılır ve adımlar tekrarlanır.

Nelere dikkat etmeli?

Yöntem; çizelgeleme, devre yerleşimi ve rota planlama gibi kombinatoryal problemlerde kullanılır. En önemli tasarım kararı soğutma planıdır: çok hızlı soğutma algoritmayı tepe tırmanma gibi erken takılmaya iter, çok yavaş soğutma ise gereksiz uzun sürer. Teoride çok yavaş soğutmayla en iyi çözüme yaklaşılabileceği gösterilmiştir, ancak pratikte süre kısıtlı olduğundan çoğu zaman "yeterince iyi" bir sonuçla yetinilir.