tag kombinatoryal

Simulated Annealing (Benzetimli Tavlama)

Bu sayfada kombinatoryal (Simulated Annealing (Benzetimli Tavlama)) etiketi ile işaretlenmiş 1 yapay zeka kavramını bulabilirsiniz.

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.

thermostat

Simulated Annealing (Benzetimli Tavlama)

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.

arrow_forward