Tavlama Benzetimi

Tavlama benzetimi, Kirkpatrick Gelatt ve Vecchi (1983) tarafından önerilen ve Cerny (1985) tarafından bağımsız olarak ortaya konan tek-çözüm tabanlı bir metaheuristiktir; metalin yavaş soğutulmasıyla düşük-enerji kristal yapı oluşumunu taklit eder. Algoritma yüksek bir başlangıç sıcaklığı T₀ ile başlar ve komşuluk hamlesini şu kurala göre değerlendirir: Δ = f(yeni) − f(mevcut) ise iyileştirici hamleleri (Δ < 0) her zaman, kötüleştirici hamleleri (Δ > 0) Metropolis kuralı ile P = exp(−Δ / T) olasılığıyla kabul eder. Bu kötüleştirici hamle kabulü algoritmanın yerel optimum havzalarından kaçabilmesini sağlar — temel ayırt edici özellik. Sıcaklık zamanla soğutma çizelgesine göre düşer: geometrik T_k+1 = αT_k (α ∈ [0.85, 0.99]), logaritmik (Geman ve Geman 1984 ile yakınsama garantili ama yavaş), veya uyarlanabilir. Soğuma çizelgesi, başlangıç sıcaklığı (ilk hamlelerde %80 kabul oranı pratik kural), her sıcaklıkta yapılan deneme sayısı ve durdurma kriteri ayarlanması gereken kritik parametrelerdir. Genetik algoritmadan farkı: tek bir aday çözüm ile çalışır, popülasyon yoktur, bellek minimumdur. Uygulamaları: VLSI yerleşim, araç rotalama, çizelgeleme, tesis yerleşim. Kombinatoryal problemlerde tabu arama ile yarışır. Referanslar: Aarts ve Korst (1989), Henderson Jacobson Johnson (2003).