Simulated Annealing (Benzetimli Tavlama)

#Optimizasyon #MetaSezgisel #KombinatoryalOptimizasyon #Algoritmalar #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 önerilmiştir. Benzetimli Tavlama, yerel minimumlara takılmaktan kaçınmak için başlangıçta yüksek bir sıcaklık parametresiyle çalışır. Bu aşamada kötü çözümleri belirli bir olasılıkla kabul edebilir. Sıcaklık yavaş yavaş azaldıkça (soğuma programı), algoritma giderek daha seçici hale gelir ve yalnızca daha iyi çözümleri kabul etmeye başlar. Bu sayede evrimsel süreçlerde görülen lokal optimallerden kaçış mekanizmasına benzer bir davranış elde edilir. Algoritma, pratik uygulamalarda son derece geniş bir kullanım alanına sahiptir: gezgin satıcı problemi (TSP), çizelgeleme optimizasyonu, devre tasarımı, portföy optimizasyonu ve ağ yönlendirme problemleri bunların başında gelir. Derin öğrenme çağında bile hiperparametre optimizasyonu ve sinir ağı ağırlıklarının başlangıç değerlerini ayarlamak için kullanılmaktadır. Temel parametre olan soğuma hızı (cooling schedule), algoritmanın başarısını doğrudan etkiler. Çok hızlı soğuma lokal minimuma takılmaya; çok yavaş soğuma ise aşırı uzun çalışma sürelerine yol açar.

Algoritma Nasıl Çalışır?

Benzetimli Tavlama'nın çalışma prensibi üç temel adıma dayanır. İlk adımda rastgele bir başlangıç çözümü seçilir ve yüksek bir başlangıç sıcaklığı T atanır. İkinci adımda, mevcut çözümün komşuluğunda rastgele bir yeni çözüm üretilir. Eğer yeni çözüm daha iyiyse kesinlikle kabul edilir; daha kötüyse exp(-(delta_E)/T) olasılığıyla kabul edilir. Bu olasılıksal kabul mekanizması, algoritmanın lokal minimumlara sıkışmamasını sağlar. Üçüncü adımda sıcaklık belirli bir soğuma katsayısıyla azaltılır ve önceden belirlenen bir durdurma kriteri karşılanana kadar işlem tekrarlanır.

Uygulama Alanları

Gezgin Satıcı Problemi

N şehri en kısa yolda dolaşma optimizasyonunda klasik başvuru algoritması

Çizelgeleme

İş, kaynak ve zaman kısıtlarını dengeleme gerektiren NP-zor çizelgeleme problemleri

Devre Tasarımı

VLSI yerleşim optimizasyonu ve PCB bileşen yerleştirme problemleri

Makine Öğrenimi

Hiperparametre arama ve sinir ağı ağırlık başlatma optimizasyonu

Avantajlar ve Kısıtlar

  • check_circle Avantaj: Lokal optimumlardan kaçabilir, küresel optimuma yakınsayabilir
  • check_circle Avantaj: Gradyan bilgisi gerektirmez, kara kutu optimizasyonu için uygundur
  • check_circle Avantaj: Uygulaması basit, az hiperparametreli
  • check_circle Kısıt: Soğuma programı ayarı problem bağımlı ve sezgisel olabilir
  • check_circle Kısıt: Büyük çözüm uzaylarında çalışma süresi uzayabilir
  • check_circle Kısıt: Optimal soğuma hızını bulmak çoğunlukla deneme yanılma gerektirir

Sıkça Sorulan Sorular

  • check_circle Benzetimli tavlama ile genetik algoritmalar arasındaki fark nedir?: Benzetimli tavlama tek bir çözümü iteratif olarak iyileştirirken, genetik algoritmalar bir popülasyon üzerinde çalışır ve çaprazlama/mutasyon işlemlerini kullanır. Her ikisi de lokal minimumlardan kaçabilse de farklı problem türlerinde üstünlük gösterir.
  • check_circle Soğuma programı nasıl seçilmelidir?: Geometrik soğuma (T = alpha*T, 0.8 < alpha < 0.99) en yaygın yaklaşımdır. Hızlı bir keşif için yüksek alpha, hassas bir arama için düşük alpha tercih edilir. Adaptive soğuma programları da popülerdir.
  • check_circle Gradient descent ile benzetimli tavlama ne zaman tercih edilir?: Gradient descent türevlenebilir ve konveks problemlerde çok daha hızlı yakınsarken, benzetimli tavlama türev bilgisi olmayan veya çok modlu (non-convex) optimizasyon problemleri için tercih edilir.