İçeriğe atla
Arama sonuçlarına dön

Sağlam Benzetilmiş Tavlama — Belirsizlik altında iyi kalan çözümler bulma

Ortaya koyan
Kirkpatrick, Gelatt & Vecchi (SA basis); robust formulation developed across the operations research community
Yıl
1983 (SA); robust variant emerged 1990s–2000s
Tür
Metaheuristic with robustness evaluation
Aile
Simulation / optimization

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Sağlam Benzetilmiş Tavlama (SBT), klasik benzetilmiş tavlama meta-sezgisini, sadece nominal koşullar altında değil, aynı zamanda belirsiz veya düşmanca parametre değerlerinin tüm aralığında iyi performans gösteren çözümler aramak üzere uyarlar.

En kötü durum, beklenen durum veya pişmanlık temelli bir sağlamlık değerlendirmesini SA kabul adımına yerleştirerek, SBT, nominal optimaliteden bir miktar ödün vererek dayanıklılık elde eder; bu da problem parametrelerinin kesin olarak bilinmediği veya çevresel varyasyona tabi olduğu durumlarda değerli olmasını sağlar.

Yöntemin mantığı

Benzetilmiş tavlama, karmaşık çözüm uzaylarındaki yerel optimumlardan kaçmak için metallerin fiziksel soğumasını taklit eder. Sağlam BT, 'iyi' bir çözüm olarak neyin sayıldığını değiştirerek bu sezgiyi genişletir: varsayılan nominal veriler altında en iyi görünen çözüm yerine, algoritma gerçeklik varsayımlardan farklı olduğunda en az bozulan çözümü arar. Her SA iterasyonunda, aday çözüm tek bir nesnel değerlendirme ile değil, bir sağlamlık kriteriyle puanlanır — örneğin, bir dizi makul senaryo veya örneklenmiş parametre gerçekleşmeleri üzerindeki en kötü durum hedefi — bu da aramaya ham performans yerine istikrara yönelik açık bir önyargı verir.

Tarih

Benzetilmiş tavlama, istatistiksel mekanik için Metropolis algoritmasına dayanarak Kirkpatrick, Gelatt ve Vecchi (1983) tarafından tanıtıldı. 1990'lar ve 2000'ler boyunca, sağlam optimizasyonun — özellikle Ben-Tal ve Nemirovski tarafından resmileştirilerek — önem kazanmasıyla, araştırmacılar belirsizlik altında optimizasyonla başa çıkmak için sağlam değerlendirme kriterlerini SA arama döngülerine yerleştirmeye başladılar ve bu da sağlam SA'nın yöneylem araştırması ve mühendislik tasarımında tanınmış pratik bir çerçeve olarak ortaya çıkmasına yol açtı.

Ne zaman kullanılır?

Önemli parametre belirsizliği (tedarik değişkenliği, talep dalgalanması, ölçüm gürültüsü) olan sistemleri optimize ederken, nominal olarak optimal ancak kırılgan bir çözümün kabul edilemez olduğu durumlarda Sağlam SA kullanın. Tam sağlam optimizasyonun hesaplama açısından çok pahalı olduğu orta ila büyük boyutlu kombinatoryal ve sürekli problemler için çok uygundur. Paydaşlar çözüm kalitesi hakkında garanti veya güven aralıkları talep ettiğinde düz SA yerine RSA'yı tercih edin. Belirsizliğin ihmal edilebilir olduğu, iç sağlamlık değerlendirmesinin mevcut hesaplama gücüne göre aşırı pahalı olduğu veya problemin dışbükey olduğu ve tam sağlam programlama yöntemlerine uygun olduğu durumlarda RSA'dan kaçının.

Sınırlar ve dikkat edilmesi gerekenler

  • İç sağlamlık değerlendirmesi (senaryo örneklemesi veya numaralandırması) hesaplama maliyetini artırır: her SA iterasyonu hedefi birçok kez değerlendirmeyi gerektirir.
  • Performans, algoritma parametrelerine güçlü bir şekilde bağlıdır: soğutma programı, başlangıç sıcaklığı, komşuluk yapısı ve sağlamlık senaryolarının sayısı ayarlanmalıdır.
  • Küresel olarak optimal sağlam çözümü bulma garantisi yoktur; sonuç kalitesi çalışma süresine ve rastgeleliğe bağlıdır.
  • Sağlamlık kriterinin seçimi (en kötü durum vs. beklenen vs. pişmanlık) bulunan çözümü önemli ölçüde etkiler ve açık alan uzmanlığı gerektirir.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Tam sağlam optimizasyonun imkansız olduğu dışbükey olmayan, türevlenemeyen ve kombinatoryal çözüm uzaylarını ele alır.
  • Esnek sağlamlık kriteri: en kötü durum, beklenen değer, CVaR veya pişmanlık, algoritmayı yeniden yapılandırmadan eklenebilir.
  • Daha kötü çözümlerin olasılıksal kabulü, sağlam hedef uzayındaki yerel optimumlardan kaçmaya yardımcı olur ve açgözlü sağlam aramaya göre çözüm kalitesini artırır.
  • Mevcut herhangi bir SA kod tabanını bir senaryo değerlendirme sarmalayıcısı ile genişleterek kavramsal olarak uygulaması basittir.
  • Çok çeşitli alanlara uygulanabilir: çizelgeleme, rotalama, tesis yerleşimi, mühendislik tasarımı ve finansal portföy optimizasyonu.

Uygulama alanları

  • Belirsiz işlem süreleri ve makine kullanılabilirliği altında sağlam üretim çizelgeleme
  • Stokastik seyahat süreleri ve talep değişkenliği altında dayanıklı araç rotalama
  • Belirsiz müşteri talep dağılımları altında sağlam tesis yerleşimi planlaması
  • Tolerans ve üretim belirsizliği ile mühendislik tasarım optimizasyonu
  • Senaryo tabanlı piyasa belirsizliği altında finansal portföy optimizasyonu
  • Belirsiz bağlantı kapasiteleri veya arıza olasılıkları ile ağ tasarımı

Nasıl çalışır?

Nasıl çalışır?

1

Belirsiz parametrelerle optimizasyon problemini tanımlayın: x karar vektörü ve xi belirsiz girdileri temsil ederken f(x, xi) hedef fonksiyonu. xi üzerinde bir belirsizlik kümesi veya olasılık dağılımı belirtin. Bir sağlamlık kriteri seçin: en kötü durum (minimax), beklenen değer, koşullu riske maruz değer veya maksimum pişmanlık.

2

Her aday çözüm x için, örneklenmiş veya numaralandırılmış belirsizlik gerçekleşmeleri boyunca f(x, xi) değerlendirilerek sağlamlık ölçüsü R(x) hesaplanır. Senaryo tabanlı sağlamlık için, R(x) = max_s f(x, xi_s); stokastik sağlamlık için, R(x) = E[f(x, xi)]. Bu iç değerlendirme, Monte Carlo örneklemesi veya senaryo numaralandırması gerektirebilir.

3

Uygulanabilir bir başlangıç çözümü x_0 ve bir başlangıç sıcaklığı T_0 ile başlatın. Her iterasyonda, probleme özgü bir hareket operatörü (örneğin, takas, pertürbasyon) aracılığıyla komşu bir çözüm x' oluşturun. Seçilen sağlamlık ölçüsünü kullanarak R(x')'i değerlendirin.

4

Eğer R(x') R(x)'i iyileştiriyorsa, komşu x'i koşulsuz olarak kabul edin. Kötüleşen bir hareketi exp(-(R(x') - R(x)) / T) olasılığıyla kabul edin; burada T mevcut sıcaklıktır. Bu Metropolis kabul kuralı, sağlam hedef uzayındaki yerel optimumlardan kaçışı sağlar.

5

Soğutma programına göre sıcaklığı azaltın, genellikle geometrik soğutma T_{k+1} = alpha * T_k, alpha (0.9, 0.99) aralığında, veya kabul oranlarına göre ayarlanan adaptif programlar kullanın. Maksimum iterasyon, minimum sıcaklık eşiği veya durgunluk gibi bir durdurma kriteri karşılanana kadar devam edin.

6

Sadece son mevcut çözüm değil, tüm iterasyonlar boyunca R(x)'e göre bulunan en iyi çözümü döndürün. İsteğe bağlı olarak, en iyi sağlam çözümden başlayarak onu iyileştirmek için son bir yerel arama yapın. Sağlamlık-optimalite dengesini iletmek için hem nominal performans f(x*, xi_nominal) hem de sağlam performans R(x*) raporlayın.

Sık yapılan hatalar

  • Sağlamlık değerlendirmesinde çok az senaryo örneği kullanmak, kabul kriterine gürültü katarak algoritmanın yanıltıcı bir şekilde 'sağlam' çözümler peşinde koşmasına neden olur.
  • Çok hızlı soğutma (yüksek alfa), yerel bir sağlam optimuma erken yakınsamaya neden olur; çok yavaş soğutma, orantılı kalite kazançları olmaksızın çalışma süresini artırır.
  • Nominal optimaliteyi sağlam optimalite ile karıştırmak: yöntemin amacını bozan, sağlam olarak en iyi çözüm yerine karşılaşılan nominal olarak en iyi çözümü raporlamak.
  • Raporlamada sağlamlık-optimalite dengesini göz ardı etmek: okuyucuların sağlamlık için neyin feda edildiğini değerlendirebilmeleri için her zaman hem R(x*) hem de f(x*, xi_nominal) değerlerini açıklayın.

Sık sorulan sorular

Sağlam SA, Stokastik SA'dan nasıl farklıdır?

Stokastik SA, sabit bir hedefin yerel optimumlarından kaçmak için hareket üretimi veya değerlendirmesinde rastgelelik kullanır. Sağlam SA, hedefin kendisini değiştirir: belirsiz parametreler üzerinde bir sağlamlık ölçüsünü (en kötü durum, beklenen veya pişmanlık) optimize eder, arama sürecindeki sadece gürültü yerine parametre varyasyonuna dayanıklı çözümler arar.

Sağlamlık değerlendirmesinde kaç senaryoya ihtiyaç vardır?

Bu, belirsizlik yapısına ve gerekli hassasiyete bağlıdır. Ayrık senaryo kümeleri için, tüm senaryoları veya en düşmanca senaryoları numaralandırın. Sürekli dağılımlar için, değerlendirme başına 50-500 Monte Carlo örneği pratikte yaygındır ve örneklem büyüklüğünü doğrulamak için yakınsama teşhisleri kullanılır. Daha fazla örnek doğruluk sağlar ancak çalışma süresini orantılı olarak artırır.

Sağlam SA, sağlamlığın yanı sıra birden fazla hedefi ele alabilir mi?

Evet, ancak problem önemli ölçüde daha karmaşık hale gelir. Bir yaklaşım, sağlamlığı ek bir hedefe dönüştürmek ve çok amaçlı bir SA (örneğin, Pareto-SA) çalıştırmaktır. Alternatif olarak, sağlamlık, ağırlıklı bir toplu hedefe eklenen bir kısıtlama veya ceza terimi olarak ele alınır.

Sağlam SA'yı Sağlam Tabu Arama veya Sağlam GA'ya ne zaman tercih etmeliyim?

Sağlam SA, çözüm uzayının oldukça engebeli olduğu ve aramanın tuzaklardan kaçmak için daha kötü çözümlerin ara sıra kabulünden faydalandığı durumlarda sıklıkla tercih edilir. Tabu Arama, hareket geçmişi bilgilendirici olduğunda daha güçlü olabilir. Genetik algoritmalar, popülasyon çeşitliliği problemlerinde üstündür. Seçim genellikle ampirik ve probleme özgüdür.

Paralel bir uygulama faydalı mıdır?

Evet. İç sağlamlık değerlendirmesi (senaryo örneklemesi) utanç verici derecede paraleldir: bir aday çözüm için tüm senaryolar eşzamanlı olarak değerlendirilebilir. Bu iç döngüyü paralelleştirmek, algoritmanın mantığını değiştirmeden gerçek zamanı önemli ölçüde azaltır.

İlgili yöntemler

Kaynaklar

  1. Kirkpatrick, S., Gelatt, C. D., Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.

    DOI kaynağını aç
    Kopyalandı.
  2. Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.

    ISBN: 9780691143682
    Kopyalandı.