Belirsizlik Altında Çok Amaçlı Optimizasyon için Sağlam NSGA-II
- Ortaya koyan
- Kalyanmoy Deb and Himanshu Gupta
- Yıl
- 2006
- Tür
- Robust evolutionary multi-objective optimization algorithm
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Sağlam NSGA-II, parametrik belirsizliği hesaba katmak için klasik NSGA-II evrimsel algoritmasını genişletir, girdi parametreleri nominal değerlerinden saptığında bile yüksek performanslı kalan Pareto-optimal ödünleşme çözümleri bulur.
Tek bir noktada hedef değerleri optimize etmek yerine, her bir aday çözümü belirsizlik gerçekleşmeleri aralığı veya dağılımı üzerinden değerlendirir ve Pareto üstünlüğünün yanı sıra sağlamlık için seçim yapar.
Yöntemin mantığı
Pratikte, mühendislik tasarımları ve politika kararları belirsiz işletme koşullarıyla karşı karşıyadır: malzeme özellikleri değişir, talep tahminleri gerçeklikten farklılaşır ve çevresel yükler dalgalanır. Nominal parametre değerlerinde optimal görünen bir çözüm, makul sapmalar altında kötü performans gösterebilir. Sağlam NSGA-II, her bir aday çözümü yalnızca tasarım noktasında değil, bir komşuluk veya belirsiz senaryolar örneklemi üzerinden değerlendirerek, ardından her bir hedef için beklenen değer ve varyansı (veya en kötü durum performansını) seçim kriterleri olarak ele alarak bu sorunu çözer. Algoritma böylece nominal performansta küçük bir kayıp karşılığında güvenilirlikte büyük bir kazanç elde eder, belirsizlik altında hem rekabetçi hem de kararlı çözümlerden oluşan bir Pareto cephesi sunar.
Tarih
Sağlam NSGA-II, 2006 yılında Deb ve Gupta tarafından biçimlendirilen sağlam çok amaçlı optimizasyon çerçevesinden ortaya çıktı; bu çerçeve, NSGA-II seçim mekanizmasına açık sağlamlık metrikleri getirdi. Temel NSGA-II algoritması 2002 yılında Deb, Pratap, Agarwal ve Meyarivan tarafından yayınlandı. Mühendislik tasarımı, operasyon araştırması ve enerji sistemleri alanlarındaki araştırmacılar tarafından yapılan sonraki çalışmalar, çerçeveyi stokastik kısıtlamalar, karma belirsizlik türleri ve vekil destekli sağlamlık değerlendirmesi içeren problemlere genişletti.
Ne zaman kullanılır?
Çok amaçlı bir problem belirsiz parametreler (malzeme özellikleri, talep, maliyetler, çevresel koşullar) içerdiğinde ve çözümlerin yalnızca tek bir tasarım noktasında değil, makul sapmalar boyunca kabul edilebilir kalması gerektiğinde Sağlam NSGA-II'yi kullanın. Mühendislik tasarımı, talep belirsizliği altında tedarik zinciri planlaması ve stokastik üretimle enerji sistemi optimizasyonu için uygundur. Hesaplama bütçeleri çok sıkı olduğunda, çünkü birey başına nesil başına M belirsizlik örneğinin değerlendirilmesi fonksiyon değerlendirme maliyetlerini M ile çarpar. Belirsizlikler hedef değişkenliğe göre ihmal edilebilir olduğunda veya aday başına yalnızca iki veya üç hedef fonksiyon değerlendirmesi mümkün olduğunda da kaçının - standart NSGA-II veya vekil destekli yöntemler o zaman daha verimlidir.
Sınırlar ve dikkat edilmesi gerekenler
- Hesaplama maliyeti M (değerlendirme başına belirsizlik örnekleri) ile ölçeklenir, bu da hedef değerlendirmeleri simülasyona dayalı veya zaman alıcı olduğunda pahalı hale getirir.
- Sağlamlık metriği seçimi (ortalama, varyans, en kötü durum) hangi çözümlerin tercih edildiğini önemli ölçüde etkiler ve evrensel olarak doğru bir seçim yoktur.
- Standart NSGA-II ile aynı nedenle üçten fazla hedef için performans düşer - yüksek boyutlu hedef uzayında kalabalıklaşma mesafesi ayırt edici gücünü kaybeder.
- Sağlamlığı güvenilir bir şekilde tahmin etmek yeterince büyük bir M gerektirir, ancak küçük M, Pareto cephesi yaklaşımını yanıltabilecek stokastik gürültü getirir.
- Belirsizlik kümesi süreksiz olduğunda veya belirsiz parametreler arasındaki korelasyonlar karmaşık ve örneklenmesi zor olduğunda uygulamak doğrudan değildir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Belirsizlik altında iyi performans gösterdiği açıkça doğrulanmış Pareto-optimal çözümler üretir, pratikte kötüleşen çözümlerin riskini azaltır.
- Sağlam baskın olmayan çözümlerin nesiller boyunca asla atılmamasını sağlayarak NSGA-II'nin hızlı baskın olmayan sıralama ve seçkinliğini miras alır.
- Sağlamlık metriğinde esneklik: risk tercihine bağlı olarak beklenen değer, varyans cezası, en kötü durum veya olasılıksal kısıtlama ikame edilebilir.
- Temel seçim mekanizmasında değişiklik yapmadan sürekli ve ayrık karar uzayları için çalışır.
- Karar vericilere hem çok amaçlı denge hem de sağlamlık seviyesi açısından farklılaşan ödünleşme seçenekleri sunarak bilinçli tercih ifade etmeyi destekler.
Uygulama alanları
- Değişken atmosferik koşullar altında sürüklenme ve kaldırma ödünleşmelerini optimize eden sağlam aerodinamik tasarım
- Stokastik müşteri talebi altında maliyet ve hizmet seviyesini dengeleyen tedarik zinciri ağı tasarımı
- Belirsiz yenilenebilir üretim ve yük profilleriyle sağlam enerji sistemi planlaması
- İmalat toleranslarını ve yük değişkenliğini hesaba katan çok amaçlı yapısal optimizasyon
- Beklenen getiri ve varyans arasındaki ödünleşmelerle piyasa belirsizliği altında portföy optimizasyonu
- İklim belirsizliği altındaki akış senaryolarında tahsisi ve güvenilirliği optimize eden su kaynakları yönetimi
Nasıl çalışır?
Nasıl çalışır?
N aday çözümden oluşan bir başlangıç popülasyonu P oluşturun ve karar değişken vektörlerini kodlayın. Belirsizlik modelini tanımlayın: hangi parametrelerin belirsiz olduğunu, olasılık dağılımlarını veya pertürbasyon kümelerini ve kullanılacak sağlamlık metriğini (beklenen değer, varyans, en kötü durum veya ağırlıklı bir kombinasyon) belirtin. Temel uygunluğu belirlemek için nominal koşullar altında tüm çözümleri değerlendirin.
Popülasyondaki her bir aday çözüm x için, belirtilen parametre dağılımlarından M sayıda belirsizlik gerçekleşmesi çekin (veya yapılandırılmış bir komşuluğu numaralandırın). Her bir gerçekleşme altında tüm hedef fonksiyonlarını değerlendirin ve sonuçları sağlam hedef tahminlerine göre toplayın. Yaygın toplama: beklenen performans için sağlamlık tahmini olarak ortalamayı kullanın ve varyansı hesaba katmak için standart sapmaya orantılı bir ceza ekleyin, böylece sağlam bir hedef f_robust(x) = mean[f(x, xi)] + lambda * std[f(x, xi)] olur.
Hızlı baskın olmayan sıralamayı, nominal değerler yerine sağlam hedef tahminlerini kullanarak popülasyona uygulayın. Her çözüme, sağlam hedeflerin Pareto üstünlüğüne dayanarak bir baskın olmayan cephe F1, F2 vb. atayın. F1'deki çözümler sağlam bir şekilde baskın değildir: başka hiçbir çözüm tüm sağlam hedeflerde eş zamanlı olarak daha iyi değildir.
Her bir baskın olmayan cephe içinde, her bir çözüm için her bir sağlam hedef ekseni boyunca kalabalıklaşma mesafesini hesaplayın. Kalabalıklaşma mesafesi, bir çözümün sağlam hedef uzayında ne kadar izole olduğunu ölçer, sağlam Pareto cephesi boyunca yayılmayı teşvik eder. Büyük kalabalıklaşma mesafesine sahip çözümler seyrek nüfuslu bölgeleri işgal eder ve çeşitliliği korumak için seçim sırasında tercih edilir.
Sağlam cepheler ve kalabalıklaşma mesafeleri üzerinde kalabalıklaşma karşılaştırma operatörünü kullanarak ikili turnuva seçimi uygulayın. Çaprazlama (simüle edilmiş ikili çaprazlama) ve mutasyon (polinom mutasyon) operatörleri aracılığıyla N boyutunda bir yavru popülasyonu Q oluşturun. Yavru çözümleri, birey başına M belirsizlik örneği ile sağlamlık değerlendirmesi kullanarak yeniden değerlendirin. M büyük olduğunda bu adım çalışma süresini domine eder.
Ebeveyn popülasyonu P ve yavru Q'yu 2N boyutunda birleştirilmiş bir havuzda birleştirin. Sağlam baskın olmayan sıralama ve kalabalıklaşma mesafesine göre yeniden sıralayın. Bir sonraki nesli oluşturmak için en iyi N bireyi seçin, seçkinliği koruyun. Maksimum nesil sınırı aşıldığında, hiperhacim durağanlaştığında veya hesaplama bütçesi tükendiğinde sonlandırın. Son sağlam Pareto cephesini F1 döndürün.
Sık yapılan hatalar
- Değerlendirme başına çok az belirsizlik örneği kullanmak (M 20-30'dan az) baskın olmayan sıralamayı bozan ve güvenilmez bir sağlam Pareto cephesi veren değerlendirme gürültüsü getirir.
- Hedef değerlerinin sağlamlığı ile optimal çözümlerin sağlamlığının karıştırılması: hedef uzayında sağlam olan bir çözüm, uygulaması zor olan kesin karar değişken değerleri gerektirebilir.
- Sağlam hedeflerin orantılı ölçeklerde olup olmadığını kontrol etmeden NSGA-II'nin varsayılan kalabalıklaşma mesafesini sağlam hedef uzayında uygulamak; mesafeleri hesaplamadan önce hedefleri normalleştirin.
- Sonucu kesin olarak kabul ederek tek bir tekrarlama çalıştırmak; stokastik değişimi hesaba katmak için her zaman birden fazla bağımsız tekrarlama çalıştırın ve hiperhacim istatistiklerini raporlayın.
- Hassasiyet analizi olmadan rastgele bir lambda (varyans cezası ağırlığı) seçmek; seçilen lambda, açıkça belirtilmeli ve gerekçelendirilmelidir. risk tutumunu örtük olarak kodlar.
Sık sorulan sorular
Sağlam NSGA-II standart NSGA-II'den nasıl farklıdır?
Standart NSGA-II, her bir aday çözümü nominal parametre değerlerinde değerlendirir ve bu hedef değerlerini Pareto üstünlüğü için kullanır. Sağlam NSGA-II, her bir çözümü belirsiz parametrelerin M gerçekleşmesi üzerinden değerlendirir, sonuçları sağlam hedef tahminlerine (örneğin, ortalama ve varyans) toplar ve baskınlık sıralaması için bu tahminleri kullanır. Bu, hesaplama maliyetini M faktörü kadar artırır ancak parametreler nominal değerlerden saptığında rekabetçi kalan çözümler üretir.
Birey başına kaç belirsizlik örneği M kullanmalıyım?
Evrensel bir kural yoktur. Hedef değerlendirmeleri ucuzsa, yaygın bir başlangıç noktası M = 30 ila 50 Monte Carlo örneğidir. Pahalı değerlendirmeler için M = 5 ila 10 gerekebilir. Bir hassasiyet çalışması yapın: sağlam hedef tahminleri stabilize olana kadar M'yi artırın. Yarı-rastgele (Latin hiperküp veya Sobol) örnekleme, aynı M için tamamen rastgele örneklemeye göre daha iyi kapsama alanı sağlar.
Sağlam NSGA-II'yi üçten fazla hedefle kullanabilir miyim?
Algoritma uygulanabilir, ancak standart NSGA-II ile aynı nedenle performans düşer: kalabalıklaşma mesafesi yüksek boyutlu hedef uzayında ayırt edici gücünü kaybeder ve çoğu çözüm ilk baskın olmayan cephede yer alır. Dört veya daha fazla hedef için, kalabalıklaşma mesafesi yerine referans noktası tabanlı seçimi kullanan NSGA-III'ün sağlam bir varyantını düşünün.
Hangi sağlamlık metriğini seçmeliyim?
Seçim risk tutumuna bağlıdır. Yalnızca ortalama optimizasyonu, değişkenliği cezalandırmadan beklenen performansı hedefler - tekrarlanan kararlar için uygundur. Ortalama artı varyans, istikrarsızlığı cezalandırır ve riskten kaçınan bağlamlara uyar. En kötü durum (minimax) optimizasyonu son derece muhafazakardır ve yalnızca tek bir felaket niteliğindeki gerçekleşme kabul edilemez olduğunda uygundur. Seçimi belgeleyin ve gerekçelendirin, çünkü bu, sağlam Pareto cephesinde hangi çözümlerin göründüğünü önemli ölçüde etkiler.
Döndürülen çözümlerin gerçekten sağlam olduğunu nasıl doğrularım?
Algoritma sonlandırıldıktan sonra, optimizasyon sırasında kullanılan örneklerden bağımsız olarak, her bir Pareto cephesi çözümünü taze, büyük bir örneklem kümesi (örneğin, M = 1000) ile yeniden değerlendirin. Hedef ortalamalarının ve varyanslarının evrimsel çalıştırmadan elde edilen tahminlerle eşleşip eşleşmediğini kontrol edin. Büyük farklılıklar, optimizasyon sırasında M'nin çok küçük olduğunu veya belirsizlik modelinin yanlış belirtildiğini gösterir.
İlgili yöntemler
Kaynaklar
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
DOI kaynağını açKopyalandı.Deb, K., & Gupta, H. (2006). Introducing robustness in multi-objective optimization. Evolutionary Computation, 14(4), 463-494.
DOI kaynağını açKopyalandı.