Belirsizlik Altında Stokastik NSGA-II — Evrimsel Çok Amaçlı Optimizasyon
- Ortaya koyan
- Deb, K. et al. (NSGA-II base); Hughes, E. J. and subsequent researchers for stochastic extensions
- Yıl
- 2001–2002
- Tür
- Evolutionary multi-objective optimization under uncertainty
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Stokastik NSGA-II, NSGA-II evrimsel algoritmasını, gürültülü, belirsiz veya olasılıksal amaç fonksiyonlarını işlemek üzere genişletir.
Stokastik amaçları birden çok değerlendirme üzerinden ortalayarak veya örnekleyerek, belirsizliğe karşı dayanıklı Pareto-optimal çözümler belirler, bu da onu gerçek dünya değişkenliğinin önemli olduğu mühendislik tasarımı, tedarik zinciri ve politika optimizasyonu problemleri için uygun hale getirir.
Yöntemin mantığı
NSGA-II, çok amaçlı problemlerde çeşitli Pareto-optimal ödünleşme çözümleri bulmak için en etkili algoritmalardan biridir. Ancak, standart sürüm deterministik amaç değerlendirmelerini varsayar. Pratikte, simülasyonlar, deneyler ve gerçek sistemler genellikle gürültülü çıktılar döndürür. Stokastik NSGA-II, her çözümün gerçek uygunluğunu yeniden örnekleyerek veya istatistiksel olarak tahmin ederek bu sorunu ele alır, ardından gürültüye rağmen Pareto cephesini güvenilir bir şekilde gezinmek için NSGA-II'nin hızlı baskın olmayan sıralamasını ve kalabalıklaşma mesafesi seçimini uygular. Temel fikir, çözümleri beklenen performansa göre — veya baskınlık olasılıklarına göre — sıralamanın, bireysel değerlendirmeler güvenilmez olduğunda bile doğru Pareto yapısını kurtarmasıdır.
Tarih
NSGA-II, 2002 yılında Deb ve arkadaşları tarafından hızlı, elitist bir çok amaçlı genetik algoritma olarak tanıtıldı ve hızla bir referans standardı haline geldi. Stokastik uzantılar, simülasyon gürültüsünü işlemek isteyen mühendislik optimizasyon toplulukları tarafından yönlendirilerek kısa süre sonra ortaya çıktı. Hughes (2001), belirsizlik altında çok amaçlı sıralamayı biçimlendirdi. 2000'lerin ortalarından bu yana, uyarlanabilir yeniden örnekleme, baskınlık olasılığı ve gürültü altında beklenen hiperhacim iyileştirmesini kapsayan çok sayıda varyant ortaya çıktı.
Ne zaman kullanılır?
Amaçların simülasyon, deney veya gürültülü sensörler aracılığıyla değerlendirildiği ve yalnızca ortalamada değil, belirsizlik aralığında iyi kalan çözümlere ihtiyaç duyduğunuz çok amaçlı bir optimizasyon problemiyle karşılaştığınızda Stokastik NSGA-II'yi kullanın. Özellikle üretim toleransları altındaki mühendislik tasarımı, talep belirsizliği ile tedarik zinciri optimizasyonu ve stokastik girdilere sahip çevresel veya politika modelleri için uygundur. Amaçların deterministik ve değerlendirmesi ucuz olduğu durumlarda (standart NSGA-II yeterlidir), güvenilir tahmin için gereken kopya sayısı toplam bütçeyi karşılanamaz hale getirdiğinde veya problem tek amaçlı olduğunda (bunun yerine stokastik tek amaçlı EA'lar kullanın) KULLANMAYIN. Gürültü dağılımının son derece durağan olmadığı veya i.i.d. örnekleme varsayımını ihlal eden şekillerde yapılandırıldığı durumlardan kaçının.
Sınırlar ve dikkat edilmesi gerekenler
- Hesaplama maliyeti, kopya sayısı r ile çarpı popülasyon büyüklüğü ve nesiller ile ölçeklenir — pahalı simülasyonlar için elverişsiz hale gelebilir.
- Doğru kopya sayısı r'yi seçmek önemsiz değildir: çok azı sıralama hatalarına neden olur, çok fazlası bütçeyi boşa harcar.
- Gerçek stokastik Pareto cephesine yakınsama için resmi garantiler yoktur; kalite bütçeye ve gürültü seviyesine bağlıdır.
- Tahmin edilen ortalamaları kullanarak baskınlık karşılaştırmaları, tahmin belirsizliğini göz ardı eder, bu da yüksek gürültü altında yanlış sıralamaya neden olabilir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Baskın olmayan sıralama ve kalabalıklaşma mesafesi aracılığıyla NSGA-II'nin güçlü Pareto cephesi keşfi ve çeşitlilik korumasını miras alır.
- Amaç fonksiyonu gürültüsünü açıkça hesaba katar, gerçek dünya dağıtımında dayanıklı ve güvenilir çözümler üretir.
- Esnek çerçeve — stokastik tahmin, çekirdek algoritmayı değiştirmeden ortalama alma, kantil tabanlı dayanıklılık veya baskınlık olasılığını kullanabilir.
- Gradyan bilgisinin mevcut olmadığı kara kutu simülasyon modellerine uygulanabilir.
- Tek bir çözüm yerine tam bir Pareto cephesi üretir, karar vericilere açık ödünleşme seçenekleri sunar.
Uygulama alanları
- Dayanıklı mühendislik tasarımı: üretim toleransları ve yük değişkenliği altında yapısal veya mekanik bileşenlerin optimizasyonu.
- Tedarik zinciri ağ tasarımı: talep ve arz miktarlarının stokastik olduğu durumlarda maliyet ve teslim süresini en aza indirme.
- Çevresel politika modellemesi: iklim etkisi modellerinin belirsiz parametrelere sahip olduğu durumlarda Pareto-optimal emisyon azaltma stratejileri bulma.
- Portföy optimizasyonu: varlık getirilerinin stokastik süreçleri izlediği durumlarda beklenen getiriyi ve riski dengeleme.
- Sağlık hizmeti kaynak tahsisi: belirsiz hasta varış oranları ve tedavi etkinliği altında maliyet ve hasta sonuçlarını optimize etme.
- Enerji sistemleri planlaması: stokastik rüzgar ve güneş üretimi profilleri altında yenilenebilir enerji kurulumlarının boyutlandırılması.
Nasıl çalışır?
Nasıl çalışır?
k stokastik amaç fonksiyonu f_1(x,xi), ..., f_k(x,xi) ile çok amaçlı optimizasyon problemini tanımlayın, burada xi bilinen veya tahmin edilen bir dağılımdan çekilen rastgele parametreleri temsil eder. Karar değişkeni sınırlarını, kısıtlamaları ve her amacın beklenen değerini tahmin etmek için kullanılan tekrar eden değerlendirme (kopya) sayısı r'yi belirtin.
Uygun karar alanında rastgele N aday çözüm popülasyonunu başlatın. Her birey için, sıfıra başlatılmış k uzunluğunda bir uygunluk tahmin vektörü ayırın. Nesil sayacı g = 0 olarak ayarlayın ve durdurma kriterlerini (maksimum nesiller G_max veya yakınsama toleransı) tanımlayın.
Popülasyondaki her birey x_i için, xi'yi dağılımından örnekleyerek (veya r simülasyon kopyası çalıştırarak) her amaç f_j(x_i, xi)'yi tam olarak r kez değerlendirin. Gerçek amaç, örnek ortalaması olarak tahmin edilir: f_j_hat(x_i) = (1/r) * sum_{l=1}^{r} f_j(x_i, xi_l). İsteğe bağlı olarak uyarlanabilir yeniden örnekleme stratejilerine bilgi vermek için standart hataları hesaplayın.
Tahmin edilen amaç vektörlerine hızlı baskın olmayan sıralama uygulayın. Çözüm x_a, x_b'yi tüm j'ler için f_j_hat(x_a) <= f_j_hat(x_b) ve en az bir j için kesin olarak daha az ise baskın kılar. Her çözümü, F_1'in başka herhangi bir şey tarafından baskın olmayan çözümleri içerdiği bir Pareto cephesi sırası F_1, F_2, ... olarak atayın.
Ebeveynleri Pareto sırası ve kalabalıklaşma mesafesine (çeşitliliği korumak için) dayalı ikili turnuva seçimi kullanarak seçin. Bir offspring popülasyonu Q boyut N oluşturmak için genetik operatörler — simüle edilmiş ikili çaprazlama (SBX) ve polinom mutasyonu — uygulayın. Ebeveyn ve offspring popülasyonlarını (boyut 2N) birleştirin, stokastik amaçları yeniden değerlendirin, yeniden sıralayın ve sıra ardından kalabalıklaşma mesafesine göre en iyi N çözümü seçin.
g'yi artırın. Eğer g < G_max ise ve Pareto cephesi stabilize olmamışsa, stokastik değerlendirme adımından tekrarlayın. Aksi takdirde, baskın olmayan dayanıklı çözümler kümesi olarak son Pareto cephesi F_1'i döndürün. Karar verici seçimi için amaç uzayında yaklaşık Pareto cephesini raporlayın.
Sık yapılan hatalar
- Birey başına tek bir kopya (r=1) kullanmak, gürültüyü sinyal olarak ele alır, çalıştırmalar arasında son derece kararsız Pareto cephelerine yol açar — her zaman minimum r >= 3 kullanın ve yakınsamayı doğrulayın.
- Stokastik amaçların varyansını göz ardı etmek, ortalamada iyi görünen ancak kuyruk senaryolarında kötü performans gösteren çözümleri seçebilir — kuyruk riski önemli olduğunda kantil tabanlı veya en kötü durum amaç formülasyonlarını düşünün.
- Gürültünün durağan olup olmadığını kontrol etmeden yöntemi uygulamak: eğer gürültü özellikleri karar değişkeni değerleriyle değişirse, uyarlanabilir yeniden örnekleme veya heteroskedastik modeller gereklidir.
- Çıktı Pareto cephesini nihai karar olarak ele almak, örnek dışı dayanıklılığı değerlendirmeden — önerilen çözümleri her zaman ayrılmış simülasyon çalıştırmalarıyla doğrulayın.
Sık sorulan sorular
Bireysel değerlendirme başına kaç kopya r kullanmalıyım?
Amaç fonksiyonunun değişim katsayısına bağlı olarak yaygın bir başlangıç noktası r = 5–30'dur. Elit çözümlere daha fazla kopya ayıran veya bir güven kriteri karşılanana kadar sıralı örnekleme kullanan uyarlanabilir stratejiler daha verimlidir. Pahalı simülasyonlar için, büyük bir popülasyonla r = 3–5 genellikle pratik bir uzlaşmadır.
Stokastik NSGA-II, standart NSGA-II'den nasıl farklıdır?
Tek yapısal fark amaç değerlendirmesindedir: standart NSGA-II f(x)'i bir kez değerlendirir ve sonucun kesin olduğunu varsayar, oysa Stokastik NSGA-II f(x, xi)'yi r kez değerlendirir ve etkili amaç olarak örnek ortalamasını (veya başka bir dayanıklılık istatistiğini) kullanır. Tüm sıralama, seçim ve genetik operatör mekaniği aynı kalır.
Stokastik NSGA-II'yi ortalama amaçlar yerine baskınlık olasılığı ile kullanabilir miyim?
Evet. Baskınlık olasılığı yaklaşımları, deterministik baskınlık karşılaştırmalarını, yüksek gürültü altında daha ilkeli olan stokastik baskınlık olasılıklarıyla değiştirir. Bu, karşılaştırma başına daha fazla örnek gerektirir ancak gürültü amaç farklılıklarına göre büyük olduğunda daha güvenilir sıralamalar üretir.
Simülasyonum birden fazla kopya için çok pahalıysa ne olur?
Yardımcı vekil yaklaşımları düşünün: amaç fonksiyonunun bir Gauss süreci veya sinir ağı metamodeli oluşturun, hem ortalamayı hem de varyansı ucuza tahmin etmek için kullanın ve tekrarlanan doğrudan değerlendirmeler yerine beklenen iyileşme veya iyileşme olasılığı kriterlerini uygulayın.
Stokastik NSGA-II'nin gerçek stokastik Pareto cephesini bulması garanti midir?
Hayır. Tüm evrimsel algoritmalar gibi, gerçek cepheye sonlu zaman yakınsama garantisi olmayan bir sezgiseldir. Pratik rehberlik: birden fazla bağımsız deneme çalıştırın, sonuçta elde edilen cepheleri hiperhacim göstergeleri kullanarak karşılaştırın ve cepheler çalıştırmalar arasında önemli ölçüde farklıysa popülasyon büyüklüğünü veya nesilleri artırın.
İ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ı.Hughes, E. J. (2001). Evolutionary multi-objective ranking with uncertainty and noise. In Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization (EMO 2001), Lecture Notes in Computer Science, vol. 1993, pp. 329–343. Springer.
DOI kaynağını açKopyalandı.