← Ana Sayfaya Dön

🔥 Tavlama Benzetimi Nedir?

Tavlama Benzetimi (Simulated Annealing - SA), katı bir malzemenin önce belirli bir sıcaklığa kadar ısıtılıp sonra soğutulması yoluyla malzemenin kalitesinin artırılmasını sağlayan fiziksel tavlama sürecinin taklidine dayanmaktadır.

🔬 Fiziksel Süreç: Metal gibi bir katı madde yüksek bir sıcaklığa kadar ısıtılır ve erimiş bir hale getirilir. Atomlar bu durumda özgürce hareket edebilir. Sıcaklığın düşürülmesiyle atomların hareketleri kısıtlanır. Sıcaklık azaldıkça atomlar daha az hareket eder ve kristal formları mümkün olan en az dahili enerjiye sahip olur.

🔑 Temel Kavramlar

  • Sıcaklık (T): Sistemin enerji seviyesi, algoritmanın keşif yeteneğini kontrol eder
  • Enerji (E): Amaç fonksiyonunun değeri, minimize edilmeye çalışılır
  • Soğutma: Sıcaklığın yavaş ve kontrollü azaltılması (tavlama)
  • Yerel Komşuluk: Mevcut çözümün yakınındaki çözüm uzayı
  • Kabul Olasılığı: Kötü çözümlerin kabul edilme şansı

⚡ Algoritmanın Mantığı

Tavlama benzetimi, genel bir minimum noktası bulmak amacıyla problemin farklı zamanlarındaki sonuçlarını elde ederek bu sonuçlardan iyi olan değere doğru hareket edip birden fazla çözümü test ederek en iyi sonucu bulmaya yardımcı olan bir optimizasyon yöntemidir.

📐 Matematiksel Formül

Boltzmann Dağılımı: Daha iyi olmayan çözümün kabul edilme olasılığı:

P = e-ΔE/T

Burada:

  • ΔE: Enerji farkı = E(yeni) - E(mevcut)
  • T: Sistemin mevcut sıcaklığı
  • P: Kabul olasılığı (0-1 arası)

Kural: ΔE < 0 ise (iyileşme) → Her zaman kabul et
ΔE ≥ 0 ise (kötüleşme) → P olasılığıyla kabul et

📊 SA Algoritma Adımları

  1. Başlatma:
    • Rastgele başlangıç çözümü x0 oluştur
    • Başlangıç sıcaklığı T0'ı belirle (yüksek)
    • Soğutma oranı α'yı belirle (0.8-0.99 arası)
  2. İterasyon:
    • Mevcut çözümün komşuluğundan yeni çözüm üret
    • Enerji farkını hesapla: ΔE = E(yeni) - E(mevcut)
  3. Kabul/Red:
    • Eğer ΔE < 0 → Yeni çözümü kabul et
    • Eğer ΔE ≥ 0 → P = e-ΔE/T olasılığıyla kabul et
  4. Soğutma:
    • Belirli sayıda iterasyondan sonra: T = α × T
    • Sıcaklık azaldıkça kötü çözüm kabul olasılığı düşer
  5. Durdurma: T minimum sıcaklığa ulaşınca veya maksimum iterasyon

🎯 Soğutma Programları

  • Doğrusal: T = T - ΔT
  • Geometrik (En yaygın): T = α × T (α: 0.8-0.99)
  • Logaritmik: T = T0 / log(1 + k)
  • Üstel: T = T0 × αk

✅ SA'nın Avantajları

  • Lokal minimumlardan kaçabilir
  • Basit ve anlaşılır yapı
  • Çok çeşitli problemlere uygulanabilir
  • Kombinatoryal optimizasyonda başarılı
  • Teorik olarak global optimuma yakınsama garantisi

⚠️ Dezavantajları

  • Parametre seçimi kritik (T0, α, durdurma kriteri)
  • Yavaş yakınsama olabilir
  • Çok yavaş soğutma gerekir (zaman alıcı)
  • Çok hızlı soğutma yerel minimumda takılabilir

🔧 Uygulama Alanları

  • Gezgin satıcı problemi (TSP)
  • Çizelgeleme problemleri
  • VLSI tasarımı
  • Yerleşim problemleri
  • Graf renklendirme
  • Protein katlanması
💡 Önemli Not: Tavlama Benzetimi'nin başarısı, soğutma programının ve başlangıç sıcaklığının doğru seçilmesine bağlıdır. Yüksek başlangıç sıcaklığı daha iyi keşif sağlar, yavaş soğutma daha iyi sonuçlar verir ancak daha uzun sürer.

🆚 Diğer Yöntemlerle Karşılaştırma

  • Hill Climbing vs SA: HC her zaman iyileşme arar, SA kötü çözümleri de kabul edebilir
  • GA vs SA: GA popülasyon kullanır, SA tek çözüm üzerinde çalışır
  • Tabu Search vs SA: Tabu hafıza kullanır, SA olasılıksal kabul kullanır

✍️ Test Soruları

Soru 1: Tavlama Benzetimi hangi fiziksel süreçten esinlenmiştir?

  • A) Kristalizasyon
  • B) Metallerin ısıtılıp soğutulması
  • C) Kimyasal reaksiyon
  • D) Atomların çarpışması

Soru 2: SA'da sıcaklık (T) neyi kontrol eder?

  • A) Popülasyon büyüklüğü
  • B) Kötü çözüm kabul olasılığı
  • C) İterasyon sayısı
  • D) Mutasyon oranı

Soru 3: Boltzmann dağılımı formülü nedir?

  • A) P = ΔE/T
  • B) P = e^(-ΔE/T)
  • C) P = T/ΔE
  • D) P = e^(ΔE/T)

Soru 4: ΔE < 0 olduğunda ne yapılır?

  • A) Çözüm reddedilir
  • B) Çözüm her zaman kabul edilir
  • C) Olasılıkla kabul edilir
  • D) Algoritma durur

Soru 5: Geometrik soğutma programı nasıl çalışır?

  • A) T = T - ΔT
  • B) T = α × T
  • C) T = T / 2
  • D) T = T + ΔT

Soru 6: α (soğutma katsayısı) genellikle hangi aralıkta seçilir?

  • A) 0.1-0.3
  • B) 0.4-0.6
  • C) 0.8-0.99
  • D) 1.0-1.5

Soru 7: SA'nın avantajı nedir?

  • A) Çok hızlı yakınsar
  • B) Lokal minimumdan kaçabilir
  • C) Hiç parametre gerektirmez
  • D) Popülasyon kullanır

Soru 8: Yüksek sıcaklıkta ne olur?

  • A) Sadece iyi çözümler kabul edilir
  • B) Kötü çözümler de yüksek olasılıkla kabul edilir
  • C) Algoritma durur
  • D) Hiçbir çözüm kabul edilmez

Soru 9: SA hangi tür problemlerde başarılıdır?

  • A) Sadece doğrusal problemler
  • B) Kombinatoryal optimizasyon
  • C) Sadece sürekli problemler
  • D) Sadece ikili problemler

Soru 10: SA'da yeni çözüm nasıl üretilir?

  • A) Rastgele
  • B) Popülasyondan seçilir
  • C) Mevcut çözümün komşuluğundan
  • D) En iyi çözümden

🎴 Flashcards - Tıklayarak Çevir

Tavlama Benzetimi
Simulated Annealing - Metallerin ısıtılıp soğutulması sürecinden esinlenen optimizasyon algoritması
Sıcaklık (T)
Sistemin enerji seviyesi, kötü çözüm kabul olasılığını kontrol eder
Boltzmann Dağılımı
Kötü çözüm kabul olasılığı: P = e^(-ΔE/T)
ΔE (Delta E)
Enerji farkı = E(yeni) - E(mevcut), çözüm kalitesi değişimi
Soğutma Programı
Sıcaklığın nasıl azaltılacağını belirleyen program (geometrik, doğrusal, vb.)
α (Alpha)
Soğutma katsayısı, genellikle 0.8-0.99 arası, T = α × T
Yerel Komşuluk
Mevcut çözümün yakınındaki çözüm uzayı, yeni çözüm buradan üretilir
Tavlama
Sıcaklığın yavaş ve kontrollü biçimde azaltılması süreci
Kristalizasyon
Atomların en düşük enerji durumunda düzenli yapı oluşturması
Geometrik Soğutma
En yaygın soğutma: T = α × T, üstel azalma
Kabul Kriteri
ΔE<0: her zaman kabul, ΔE≥0: P olasılığıyla kabul
Yüksek Sıcaklık
Keşif fazı, kötü çözümler yüksek olasılıkla kabul edilir
Düşük Sıcaklık
Sömürü fazı, sadece iyi çözümler kabul edilir
SA Avantajı
Lokal minimumdan kaçabilir, global optimuma yakınsama şansı
TSP
Gezgin Satıcı Problemi, SA'nın başarılı olduğu klasik problem