Simulated Annealing — Olasılıksal Optimizasyon
Simulated Annealing · Ayrıca şöyle bilinir: Benzetimli Tavlama (Simulated Annealing), SA, probabilistic local search
Simulated annealing, 1983 yılında Kirkpatrick, Gelatt ve Vecchi tarafından tanıtılan olasılıksal bir yerel arama meta-sezgisidir. Metalurjideki fiziksel tavlama sürecini — bir malzemenin ısıtılıp ardından yavaşça soğutularak düşük enerjili kristal bir duruma ulaşması — modeller ve bu analojiyi, birleştirilmiş ve sürekli optimizasyon problemlerinde yerel optimumlardan kaçmak için kullanır.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
+9 tane daha
Ne zaman kullanılır
Simulated annealing, çözüm uzayı üzerinde bir komşuluk yapısının tanımlanabildiği, amaç fonksiyonunun türevlenebilir, dışbükey veya analitik olarak ifade edilebilir olup olmadığına bakılmaksızın herhangi bir probleme uygulanabilir. Özellikle birleştirilmiş problemler (çizelgeleme, yönlendirme, grafik problemleri) ve sürekli kara kutu optimizasyonu için uygundur. Eğitim verisi veya normallik varsayımı gerekmez. Soğutma programı ve komşuluk yapısı probleme göre ayarlanmalıdır; kabaca 1.000 iterasyondan az çalıştırmak, erken yerel optimuma yakınsama riski taşır, bu durumda daha basit deterministik bir yerel arama tercih edilmelidir.
Güçlü yönler & sınırlılıklar
- Saf tepe tırmanışının aksine, daha kötü çözümlerin olasılıksal kabulü yoluyla yerel optimumlardan kaçabilir.
- Bir komşuluk yapısı tanımlandığı sürece, birleştirilmiş, sürekli, karma — hemen hemen her problem türüne uygulanır.
- Gradyan bilgisi gerektirmez ve amaç fonksiyonunun matematiksel yapısına kayıtsızdır.
- Yeterince yavaş soğutma (Hajek 1988) altında küresel optimuma yakınsama için teorik bir garantiye sahiptir.
- Az sayıda hiperparametre: başlangıç sıcaklığı, soğutma oranı ve komşuluk yapısı.
- Çözüm kalitesi soğutma programına duyarlıdır; kötü bir program rastgele aramadan daha iyi olmayan sonuçlar verebilir.
- Komşuluk yapısı her problem sınıfı için tasarlanmalıdır, bu da alan uzmanlığı gerektirir.
- Küresel optimuma yakınsama pratikte son derece yavaş soğutma gerektirir, bu da yüksek kaliteli garantiler için çalışma süresini uzun hale getirir.
- Gradyan veya yapısal bilgiden yararlanmaz, bu nedenle düz, türevlenebilir problemler için gradyan tabanlı yöntemler ondan daha iyi performans gösterir.
SSS
Soğutma programını nasıl seçerim?
α'nın 0.90 ile 0.99 arasında olduğu T ← α·T geometrik programı en yaygın başlangıç noktasıdır. Pratik bir yaklaşım, başlangıçta hamlelerin yaklaşık %80'inin kabul edildiği kadar yüksek bir başlangıç sıcaklığı ayarlamak, ardından %1'den az yokuş yukarı hamle kabul edilene kadar azaltmaktır. Nihai çözüm kalitesi zayıfsa, soğutma hızını yavaşlatın (α'yı artırın); çalışma süresi çok uzunsa, hızlandırın. Dayanıklılığı değerlendirmek için her zaman farklı başlangıç çözümlerinden birkaç kez algoritmayı çalıştırın.
Simulated annealing, genetik algoritmalar veya parçacık sürü optimizasyonundan nasıl farklıdır?
Simulated annealing tek bir çözümü korur ve rastgele pertürbasyonlar yoluyla komşuluğu keşfeder, daha kötü çözümleri olasılıksal olarak kabul eder. Genetik algoritmalar ve parçacık sürü optimizasyonu bir çözüm popülasyonunu korur ve popülasyonu geliştirmek için çaprazlama, mutasyon veya sürü hareketi kullanır. Simulated annealing, doğal bir komşuluk yapısına sahip problemler için genellikle daha basittir, oysa popülasyon tabanlı yöntemler yüksek boyutlu sürekli problemler için daha etkili olabilir.
Küresel optimum garanti edilir mi?
Teorik olarak evet, sıcaklığın yeterince yavaş azaldığı koşul altında (logaritmik soğutma). Pratikte, böyle bir soğutma hesaplama açısından uygulanamaz, bu nedenle algoritma optimuma yakın bir çözüm bulur. Sonucun kalitesi daha yavaş soğutma ve daha fazla iterasyon ile iyileşir, ancak sonlu zaman garantisi yoktur. Güven artırmak için birden fazla yeniden başlatma çalıştırmak ve bulunan en iyi çözümü saklamak pratik bir yoldur.
Neden tabu arama veya genetik algoritmayı tercih etmeliyim?
Yakın zamanda ziyaret edilen çözümlerden kaçınan ve kısa bir sürede problem yapısını verimli bir şekilde kullanabilen deterministik, hafıza güdümlü bir arama gerektiğinde tabu aramayı seçin. Problem yüksek boyutlu ve sürekli olduğunda veya optimum araziyi haritalamak için çeşitli çözümlerden oluşan bir popülasyon gerektiğinde genetik algoritma veya parçacık sürü optimizasyonunu seçin. Simulated annealing, açık bir komşuluk yapısına sahip birleştirilmiş problemler ve uygulama basitliğinin önemli olduğu durumlar için güçlü bir varsayılan seçenektir.
Kaynaklar
- Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680. DOI: 10.1126/science.220.4598.671 ↗
- van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer. ISBN: 9789027725431
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 1). Simulated Annealing. ScholarGate. https://scholargate.app/tr/optimization/simulated-annealing
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Karınca Kolonisi OptimizasyonuOptimizasyon↔ karşılaştır
- Differential EvolutionOptimizasyon↔ karşılaştır
- Genetik AlgoritmaOptimizasyon↔ karşılaştır
- Parçacık Sürü Optimizasyonu (PSO)Optimizasyon↔ karşılaştır
- Tabu SearchOptimizasyon↔ karşılaştır