Simulated Annealing — Olasılıksal Optimizasyon
- Yıl
- 1983
- Tür
- Probabilistic metaheuristic / local search
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
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.
Yöntemin mantığı
Kör bir şekilde tepelik bir arazide en alçak noktayı bulmaya çalıştığınızı hayal edin. Tamamen açgözlü bir arama her zaman yokuş aşağı iner ve bulduğu ilk vadiye takılır — ki bu en derin olanı olmayabilir. Simulated annealing kontrollü bir rastgelelik sunar: başlangıçta, 'sıcaklık' yüksekken, algoritma ara sıra yokuş yukarı adım atmaya isteklidir, şans eseri daha kötü bir çözümü kabul eder. Soğutma programına göre sıcaklık azaldıkça, algoritma giderek daha seçici hale gelir ve bir çözüme yakınsar. Yüksek sıcaklıkta daha kötü hamleleri kabul etme istekliliği, yöntemin sığ yerel optimumlardan kaçmasına ve araziyi daha kapsamlı bir şekilde keşfetmesine olanak tanır.
Tarih
Simulated annealing, 1983'te Science dergisinde yayınlanan ve katıların termodinamik tavlanması ile birleştirilmiş optimizasyon arasında açık bir analoji kuran dönüm noktası niteliğindeki makalelerinde Kirkpatrick, Gelatt ve Vecchi tarafından tanıtıldı. Aynı fikir, Cerny (1985) tarafından gezgin satıcı problemi bağlamında bağımsız olarak önerildi. van Laarhoven ve Aarts (1987), çeşitli soğutma programları altında yakınsama özellikleri kanıtlayarak ilk titiz teorik işlemi sağladılar. O zamandan beri yöntem, mühendislik tasarımı, operasyon araştırması, VLSI yerleşimi ve makine öğrenimi hiperparametre ayarı gibi alanlarda kullanılan en çok incelenen ve uygulanan meta-sezgilerden biri haline geldi.
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.
Sınırlar ve dikkat edilmesi gerekenler
- Çö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.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- 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ı.
Uygulama alanları
- Çözüm uzayının kapsamlı arama için çok büyük olduğu birleştirilmiş çizelgeleme ve zamanlama problemleri.
- Lojistik ve operasyon araştırmalarında gezgin satıcı ve araç rotalama problemleri.
- Elektrik mühendisliğinde VLSI devre yerleşimi ve çip zemin planlaması.
- Hesaplamalı biyolojide protein katlanması ve moleküler konformasyon problemleri.
- Gradyan bilgisinin mevcut olmadığı durumlarda makine öğrenimi modelleri için hiperparametre optimizasyonu.
- Mühendislik ve yönetim bilimlerinde kaynak tahsisi ve atama problemleri.
Nasıl çalışır?
Nasıl çalışır?
Algoritma, bir başlangıç çözümü — arama uzayında herhangi bir uygun nokta — ve yüksek bir başlangıç sıcaklığı ile başlar. Başlangıç çözümü rastgele veya probleme özgü olabilir; başlangıç sıcaklığı tipik olarak başlangıçta neredeyse her komşu çözümün kabul edileceği kadar yüksektir.
Mevcut çözüme küçük bir rastgele değişiklik (bir 'hamle') uygulayarak bir komşu çözüm üretilir. Komşuluk yapısı probleme göre ayarlanmalıdır: bir çizelgeleme problemi için bir hamle iki görevi değiştirebilir; sürekli bir fonksiyon için mevcut parametre vektörüne küçük bir rastgele pertürbasyon ekleyebilir.
Yeni ve mevcut çözüm arasındaki amaç değeri farkı hesaplanır. Yeni çözüm daha iyiyse, her zaman kabul edilir. Daha kötüyse, bozulmanın büyüklüğü ve mevcut sıcaklığa göre azalan bir olasılıkla kabul edilir — tipik olarak exp(−ΔE / T). Bu olasılıksal kabul, erken yakınsamayı önleyen temel mekanizmadır.
Her iterasyondan sonra (veya aynı sıcaklıkta sabit sayıda hamleden sonra), sıcaklık bir soğutma programına göre azaltılır — yaygın olarak T ← α·T geometrik programı, burada α 1'den biraz küçüktür. Soğutma programının seçimi çözüm kalitesini güçlü bir şekilde etkiler: çok hızlı soğutma aramayı yerel bir optimumda hapseder; çok yavaş soğutma hesaplama süresini boşa harcar.
Algoritma, sıcaklık minimum bir eşiğin altına düştüğünde, maksimum sayıda iterasyona ulaşıldığında veya çözüm belirli sayıda adım boyunca iyileşmediğinde durur. Tüm çalıştırma boyunca karşılaşılan en iyi çözüm — sadece son durum değil — sonuç olarak döndürülür.
Sık yapılan hatalar
- Çok az iterasyon çalıştırmak (kabaca 1.000'in altında) soğutma programının düzgün çalışmasını engeller ve aramayı yerel bir optimumda hapseder — çalışma süresi ciddi şekilde kısıtlıysa tabu arama veya deterministik bir yerel arama tercih edin.
- Başlangıç sıcaklığını çok düşük ayarlamak, algoritmanın hemen açgözlü tepe tırmanışı gibi davranmasına ve yerel optimumlardan kaçma yeteneğini kaybetmesine neden olur.
- Soğutma oranını çok agresif ayarlamak (örneğin, α 0.9'un altında) erken yakınsamaya neden olur; birden fazla başlangıç çözümünden yeniden başlatarak nihai çözüm kalitesini doğrulayın.
- Bir problem türü için tasarlanmış bir komşuluk hamlesini farklı bir probleme uygulamak, hamleleri geçersiz veya anlamsız hale getirebilir — her zaman üretilen her komşunun geçerli bir çözüm olduğundan emin olun.
- Çalışma boyunca görülen en iyi çözüm yerine yalnızca son durumu raporlamak, ara bir adımda bulunan gerçek optimumu kaçırabilir.
Sık sorulan sorular
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.
İlgili yöntemler
Kaynaklar
Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.
DOI kaynağını açKopyalandı.van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.
ISBN: 9789027725431Kopyalandı.