Simulated Annealing (Benzetimli Tavlama)

#optimizasyon #meta-sezgisel #kombinatoryal #hiperparametre

Benzetimli Tavlama, metal soğuma sürecini taklit eden ve küresel optimumu bulmak için yerel minimumlara takılmaktan kaçınan olasılıksal bir optimizasyon algoritmasıdır.

Benzetimli Tavlama (Simulated Annealing), fizikteki metal tavlama sürecinden esinlenen olasılıksal bir optimizasyon algoritmasıdır. Metal tavlama işleminde erimiş metal yavaşça soğutularak atom dizilişi minimum enerji durumuna ulaşır; benzer şekilde bu algoritma da çözüm uzayında küresel minimumu (veya maksimumu) aramak için kontrollü bir soğuma stratejisi kullanır. Algoritma 1983 yılında Scott Kirkpatrick, C. Daniel Gelatt Jr. ve Mario P. Vecchi tarafından Science dergisinde yayımlanmıştır. Temel çalışma prensibi Metropolis-Hastings kabulüne dayanır: yeni çözüm daha iyiyse kesinlikle kabul edilir; daha kötüyse exp(-(ΔE)/T) olasılığıyla kabul edilir. Burada ΔE kötüleşme miktarı, T ise anlık sıcaklık değeridir. Başlangıçta yüksek T, kötü adımları bile kabul ederek geniş alanı keşfeder; T azaldıkça algoritma yerel arama moduna geçer. Bu mekanizma, gradyan tabanlı yöntemlerin çözemediği çok modlu (non-convex) problemlerde güçlü bir avantaj sunar. Pratik uygulamalarda son derece geniş bir kapsama sahiptir: gezgin satıcı problemi (TSP), çizelgeleme optimizasyonu, VLSI devre yerleşimi, portföy optimizasyonu ve protein katlama simülasyonlarında yıllardır başvuru algoritması olma özelliğini korumaktadır. Hiperparametre araması ve Sinir Mimarisi Araması (Neural Architecture Search) gibi derin öğrenme görevlerinde de kullanılmaktadır. Gradient descent ile karşılaştırıldığında türevlenebilir bir hedef fonksiyonu gerektirmez; kara kutu optimizasyonu için idealdir. Genetik algoritmalardan farklı olarak tek çözüm üzerinde iterasyon yapar ve bellek gereksinimi düşüktür. 2023-2026 döneminde kuantum tavlama (Quantum Annealing) yaklaşımları, fiziksel kuantum süperpozisyonunu kullanarak tünel etkisiyle yerel tuzakları aşmaktadır; D-Wave gibi donanımlar belirli kombinatoryal problemlerde klasik SA'yı geride bırakmaktadır. Python'da scipy.optimize.dual_annealing standart bir uygulama sunarken nelderoptimize ve inspyred kütüphaneleri özel soğuma programları için esneklik sağlar. Soğuma programının seçimi algoritma performansını doğrudan belirler. Geometrik soğuma (T ← α·T, 0.80 < α < 0.99) en yaygın yaklaşımdır; çok hızlı soğuma lokal minimuma hapsolmaya, çok yavaş soğuma ise aşırı uzun çalışma sürelerine yol açar.

Benzetimli Tavlama Nedir?

Benzetimli Tavlama, erimiş metalin yavaşça soğutulmasıyla atom dizilişinin en düşük enerji durumuna ulaşması ilkesini optimizasyon alanına taşır. 1983'te Kirkpatrick, Gelatt ve Vecchi tarafından Science dergisinde tanıtılan algoritma, o tarihten bu yana kombinatoryal optimizasyonun temel araçlarından biri hâline gelmiştir. Temel avantajı, gradyan bilgisi gerektirmeden non-convex (çok modlu) problemlerde küresel optimumu arayabilmesidir.

Metropolis Kriteri ve Soğuma Planı

Algoritmanın kalbinde Metropolis-Hastings kabul kuralı yatar. Mevcut çözümün komşuluğunda rastgele bir aday üretilir; aday daha iyiyse kesinlikle kabul edilir. Daha kötüyse exp(-(ΔE)/T) olasılığıyla kabul edilir — burada ΔE kötüleşme miktarı, T ise sıcaklık değeridir. Yüksek T'de bu olasılık büyük olduğundan algoritma geniş alanı keşfeder; T azaldıkça yalnızca gerçek iyileşmeler kabul edilir. Soğuma planı geometrik (T ← α·T, 0.80 < α < 0.99), logaritmik veya adaptive olabilir; seçim problem boyutuna ve zaman kısıtına göre yapılır.

Uygulama Alanları

  • check_circle Gezgin Satıcı Problemi (TSP): N şehri en kısa toplam mesafeyle dolaşma optimizasyonunda başvuru algoritması; büyük ölçekli TSP örnekleri için yaklaşık çözümler üretir.
  • check_circle VLSI Devre Yerleşimi: Yonga üzerindeki bileşenlerin kablo uzunluğunu ve sinyal gecikmesini minimize edecek biçimde yerleştirilmesi, klasik bir SA uygulama alanıdır.
  • check_circle Çizelgeleme Optimizasyonu: İş emirleri, makine kapasiteleri ve teslim tarihi kısıtlarını dengeleyen NP-zor çizelgeleme problemlerinde etkili sonuçlar verir.
  • check_circle Makine Öğrenimi: Hiperparametre arama, Sinir Mimarisi Araması (NAS) ve maliyet fonksiyonu türevlenemeyen durumlar için kara kutu optimizasyonu olarak kullanılır.
  • check_circle Biyoinformatik: Protein katlama simülasyonunda ve hizalama optimizasyonunda çok modlu enerji yüzeyini keşfetmek için başvurulan yöntemlerden biridir.

Avantajlar ve Kısıtlar

  • check_circle Avantaj: Lokal optimumlardan kaçabilir; küresel optimuma yakınsama garantisi teorik olarak mevcuttur (yeterince yavaş soğuma koşuluyla).
  • check_circle Avantaj: Gradyan bilgisi gerektirmez; kara kutu ve süreksiz optimizasyon problemleri için uygundur.
  • check_circle Avantaj: Uygulama basitliği ve düşük bellek gereksinimi — tek çözüm üzerinde çalışır.
  • check_circle Kısıt: Soğuma programı problem bağımlıdır ve doğru ayar genellikle deneme yanılma gerektirir.
  • check_circle Kısıt: Büyük çözüm uzaylarında gradient descent veya evrimsel algoritmalardan daha yavaş yakınsar.
  • check_circle Kısıt: Paralel hesaplamaya uyumu sınırlıdır; her iterasyon bir öncekine bağımlıdır.

Kuantum Tavlama ve Modern Gelişmeler

Klasik Benzetimli Tavlama termal dalgalanmayı simüle ederken Kuantum Tavlama (Quantum Annealing), fiziksel kuantum süperpozisyonunu ve tünel etkisini kullanarak enerji bariyerlerini aşar. D-Wave Systems'in geliştirdiği özel donanımlar belirli kombinatoryal optimizasyon problemlerinde klasik SA'yı geride bırakmaktadır. 2024-2025 döneminde Parallel Tempering (kümülatif SA) ve Adaptive SA yöntemleri büyük ölçekli problemlerde öne çıkmış; scipy.optimize.dual_annealing fonksiyonu popüler açık kaynak uygulamalar arasında yerini almıştır.

Sık Sorulan Sorular

  • check_circle Benzetimli tavlama ile genetik algoritmalar arasındaki fark nedir? Benzetimli tavlama tek bir çözümü iteratif iyileştirirken genetik algoritmalar bir popülasyon üzerinde çaprazlama ve mutasyon uygular. Her ikisi de lokal minimumlardan kaçabilir; SA daha düşük bellek kullanır, GA paralel değerlendirmeye daha kolay uyum sağlar.
  • check_circle Metropolis-Hastings kabulü neden önemlidir? Bu kural, algoritmanın yüksek sıcaklıkta kötü çözümleri bile olasılıksal kabul etmesini sağlar. Böylece geniş arama uzayı keşfedilir ve lokal minimum tuzaklarından kaçılır. Sıcaklık düştükçe kabul olasılığı azalır ve algoritma keşiften sömürüye geçer.
  • check_circle Soğuma programı nasıl seçilmelidir? Geometrik soğuma (T ← α·T, 0.80 < α < 0.99) en yaygın başlangıç noktasıdır. α = 0.95 ile 1000 yineleme orta büyüklükteki problemler için iyi bir referanstır. Logaritmik soğuma teorik yakınsama garantisi sunar ancak çok yavaştır. Adaptive programlar mevcut kabul oranına göre T'yi dinamik ayarlar.
  • check_circle SA gradient descent'e göre ne zaman tercih edilir? Hedef fonksiyon türevlenemiyorsa, süreksizse veya çok modlu bir yüzeye sahipse SA tercih edilir. Düzgün ve konveks problemlerde gradient descent çok daha hızlı yakınsar; bu yüzden derin öğrenmede ağırlık güncellemesi için değil hiperparametre arama için kullanılır.
  • check_circle Python'da Benzetimli Tavlama nasıl uygulanır? scipy.optimize.dual_annealing fonksiyonu endüstri standardı bir implementasyon sunar: başlangıç sıcaklığı, sınırlar ve hedef fonksiyon tanımlanır; geri kalan parametreler otomatik yönetilir. Özel soğuma planları için inspyred veya scikit-opt kütüphaneleri esneklik sağlar.