Sağlam Genetik Algoritma — Belirsizlik Altında Evrimsel Optimizasyon
- Ortaya koyan
- Jin, Y. and Branke, J. (systematic formalization); roots in Holland (1975)
- Yıl
- 2005 (systematic survey); earlier applications from late 1990s
- Tür
- Metaheuristic evolutionary optimizer with robustness mechanism
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Sağlam Genetik Algoritma (RGA), standart genetik algoritmaları, yalnızca nominal tasarım noktasında değil, aynı zamanda karar değişkenleri, parametreler veya uygunluk değerlendirmelerindeki belirsizliklere maruz kaldığında da iyi performans gösteren çözümler bulacak şekilde genişletir.
Seçim baskısına açık sağlamlık önlemleri dahil ederek RGA, optimalliği pertürbasyona duyarlılığa karşı dengeler ve bu da onu mühendislik tasarımı, çizelgeleme ve gerçek dünya değişkenliği altındaki politika optimizasyonu için uygun hale getirir.
Yöntemin mantığı
Klasik bir genetik algoritma en iyi çözümü arar, ancak ideal koşullar altındaki 'en iyi' çözüm pratikte kırılgan olabilir — girdilerdeki küçük değişiklikler performansı çökertir. Sağlam bir GA farklı bir soru sorar: beklenen bozulmaların tam aralığında hangi çözümler kabul edilebilir derecede iyi kalır? Bunu, uygunluk değerlendirmesi sırasında her bir aday komşuluğunu örnekleyerek ve performansları felaket yerine zarif bir şekilde bozulan adayları ödüllendirerek yapar. Sonuç, yalnızca optimal değil, aynı zamanda gerçekçi çalışma koşulları altında güvenilir bir şekilde tama yakın optimal olan evrimleşmiş bir popülasyondur.
Tarih
Evrimsel hesaplamada sağlam optimizasyon, üretim toleranslarının nominal olarak optimal tasarımları güvenilmez hale getirdiği mühendislik tasarımı problemlerinin etkisiyle 1990'ların sonlarında ortaya çıktı. Jin ve Branke'nin 2005 IEEE incelemesi, belirsizlik türlerini ve sağlamlık önlemlerini ayırt ederek alanı sistematikleştirdi. Beyer ve Sendhoff'un 2007 kapsamlı incelemesi, sağlam EA'yı klasik sağlam optimizasyonla ilişkilendiren teorik temelleri oluşturdu ve Sağlam GA'yı evrimsel hesaplamanın tanınmış bir alt alanı olarak sağlamlaştırdı.
Ne zaman kullanılır?
Optimizasyon problemi parametrelerde belirsizlik, gürültülü uygunluk değerlendirmeleri içerdiğinde veya dağıtılan çözüm değişken gerçek dünya koşulları altında güvenilir bir şekilde performans göstermeliyse — üretim toleranslarına sahip mühendislik tasarımı, talep değişkenliği ile tedarik zinciri çizelgelemesi veya değerlendirme gürültüsünün önemli olduğu hiperparametre ayarı gibi — Sağlam GA'yı kullanın. Klasik optimizasyonun teknik olarak optimal ancak pratik olarak kırılgan çözümler ürettiği durumlarda özellikle değerlidir. Problem tamamen deterministikse ve hesaplama bütçesi kısıtlıysa RGA KULLANMAYIN — tekrarlanan uygunluk örneklemesi değerlendirme maliyetini önemli ölçüde artırır. Belirsizlik modelinin kendisi yetersiz karakterize edilmişse kaçının, çünkü sağlamlık garantileri varsayılan pertürbasyon dağılımının doğruluğuna bağlıdır.
Sınırlar ve dikkat edilmesi gerekenler
- Uygunluk değerlendirme maliyeti, nesil başına birey başına düşen pertürbasyon örneklerinin sayısıyla ölçeklenir, bu da maliyeti yüksek değerlendirilen problemler için hesaplama açısından pahalı hale getirir.
- Sağlamlık sonucu, yalnızca varsayılan belirsizlik dağılımı kadar geçerlidir — yanlış belirtilmiş dağılımlar yanlış güven verebilir.
- Standart GA operatörleri (çaprazlama, mutasyon) doğası gereği sağlamlık için tasarlanmamıştır, bu nedenle dikkatli operatör ayarlaması veya vekil yardımı genellikle gereklidir.
- Yakınsama garantisi yoktur; yöntem yüksek kaliteli ancak kanıtlanmış optimal sağlam çözümler döndürmeyebilir.
- Gürültülü uygunluk manzaraları nedeniyle popülasyon çeşitliliği ve yakınsama hızı arasındaki dengeleme, deterministik GA'dan daha hassastır.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- İyi ve kararlı çözümler bulur, gerçek dünya değişkenliği altında performans düşüşünü azaltır.
- Gradyan tabanlı sağlam optimizasyonun başarısız olduğu dışbükey olmayan, çok modlu ve karma değişkenli arama uzaylarını ele alır.
- Temel algoritmayı yeniden formüle etmeden farklı sağlamlık kriterlerini (beklenti, varyans, en kötü durum) esnek bir şekilde barındırır.
- Optimizasyon ile sağlamlık arasında açıkça takas yapmak için NSGA-II veya diğer çok amaçlı çerçevelerle birleştirilebilir.
- Mühendislik, lojistik, finans, politika analizi gibi çeşitli alanlarda minimum alana özgü modifikasyonla uygulanabilir.
Uygulama alanları
- Üretim ve operasyonel koşul belirsizliği altında aerodinamik şekil optimizasyonu
- Stokastik talep ve teslim süresi değişkenliği ile tedarik zinciri ağı tasarımı
- Gürültülü gradyan tahminleri varlığında sinir ağı hiperparametre ayarı
- Belirsiz sistem modelleri ile dinamik sistemler için sağlam kontrolcü parametre ayarı
- Varlık getirisi dağılımlarının belirsizlikle tahmin edildiği portföy optimizasyonu
- Makine arızası ve işlem süresi değişkenliği ile üretim ortamlarında sağlam çizelgeleme
Nasıl çalışır?
Nasıl çalışır?
Arama uzayını ve belirsizlik kaynağını tanımlayın — bu, amaç fonksiyonu değerlendirmesindeki gürültü, problem parametrelerindeki belirsizlik (çevresel veya üretim toleransları) veya karar değişkeni uygulamasındaki değişkenlik olabilir. Sağlamlığın beklenen performans düşüşünü en aza indirme (beklenti tabanlı) veya en kötü durum sonuçlarını sınırlama (min-maks veya varyans tabanlı) olarak mı çerçevelendiğini belirtin.
Her bir aday çözüm x için bir sağlamlık ölçüsü seçin ve formüle edin. Yaygın seçimler şunları içerir: (1) bir pertürbasyon dağılımı üzerindeki beklenen uygunluk E[f(x+δ)]; (2) ortalama ve varyansın ağırlıklı kombinasyonu E[f] + λ·Var[f]; veya (3) sınırlı bir belirsizlik kümesi üzerinden minimum en kötü durum uygunluğu. Bu ölçü, nominal uygunluk fonksiyonunun yerini alır veya onu tamamlar.
Standart GA başlatma (rastgele, Latin hiperküp veya alana özgü sezgisel yöntemler) kullanarak N aday çözümden oluşan bir popülasyon başlatın. Özellikle sağlamlık ve nominal optimalliğin rekabetçi hedefler olduğu durumlarda, sağlam optimal Pareto cephesinin keşfini desteklemek için popülasyon çeşitliliğini sağlayın.
Her bir birey için, belirsizlik dağılımından s pertürbasyon senaryosu örnekleyerek ve toplu uygunluğu hesaplayarak sağlamlık ölçüsünü tahmin edin. Örnek sayısı s, değerlendirme maliyeti ile istatistiksel doğruluk arasında bir denge kurar. Hesaplama maliyetini yönetmek için yeniden örnekleme tabanlı yaklaşımlar, açık ortalamalar veya vekil modeller kullanılabilir.
Standart GA'daki gibi seçim (turnuva, sıralama tabanlı veya uygunluk-orantılı), çaprazlama ve mutasyon operatörlerini uygulayın. Sağlamlık optimallikle çelişebileceğinden, çok amaçlı formülasyonlar (örneğin, ortalama performansı ve performans varyansını ayrı hedefler olarak ele alan NSGA-II ile) yaygındır. Nişleme veya uygunluk paylaşımı, sağlam-optimal takas cephesi boyunca çeşitliliği koruyabilir.
Durma kriteri karşılanana kadar (nesil sınırı, uygunluk durgunluğu veya hedef sağlamlık eşiği) nesiller boyunca uygunluk değerlendirmesi ve varyasyon operatörlerini tekrarlayın. Nihai popülasyonu veya en iyi-sağlam bireyi çıktı olarak verin, uygulayıcıların bilinçli bir seçim yapabilmeleri için hem nominal performansı hem de sağlamlık metriğini raporlayın.
Sık yapılan hatalar
- Uygunluk değerlendirmesi başına çok az pertürbasyon örneği kullanmak, güvenilmez sağlamlık tahminlerine yol açar ve sağlam olarak görülen kırılgan bireylerin seçimine neden olur.
- Optimizasyon ve sağlamlığın gerçekten çeliştiği durumlarda tek bir skaler sağlamlık ölçüsü uygulamak, önemli takas bilgilerini çökertir — çok amaçlı bir formülasyon tercih edilmelidir.
- Hesaplama bütçesi kısıtlamalarını popülasyon büyüklüğünü ve örnek sayısını ayarlarken göz ardı etmek genellikle RGA'yı pratik olmaktan çıkarır; pahalı değerlendirmeler için vekil destekli varyantları veya uyarlanabilir örneklemeyi kullanın.
- Stokastik GA'yı (gürültüsüz uygunluk ile rastgele arama) Sağlam GA (kasıtlı sağlamlık farkındalığı ile uygunluk) ile karıştırmak — bunlar farklı sorunları ele alır ve birbirinin yerine kullanılmamalıdır.
- Raporlanan sağlamlığın eğitim belirsizlik modeline aşırı uyum sağladığını ortaya çıkarabilecek dağıtım dışı pertürbasyon senaryolarına karşı son çözümleri test ederek sağlamlık iddialarını doğrulayamamak.
Sık sorulan sorular
Sağlam bir GA standart bir genetik algoritmadan nasıl farklıdır?
Standart bir GA, her adayın uygunluğunu nominal tasarım noktasında değerlendirir. Sağlam bir GA, uygunluğu her bir aday etrafındaki pertürbasyon komşuluğu boyunca örnekleyerek değerlendirir, böylece seçim baskısı yalnızca tek bir noktada değil, ortalama olarak (veya en kötü durumda) iyi performans gösteren çözümleri ödüllendirir. Bu, evrim sırasında 'daha iyi'nin ne anlama geldiğini değiştirir.
Birey başına tipik olarak kaç pertürbasyon örneği gerekir?
Gereken sayı, gürültü seviyesine ve sağlamlık tahmini için gereken doğruluğa bağlıdır. Pratikte, orta gürültülü problemler için nesil başına birey başına 10-50 örnek yaygındır. Çok pahalı değerlendirmeler için, istatistiksel doğruluğu korurken doğrudan simülasyon çağrılarını azaltmak üzere vekil modeller veya polinom kaosu genişletmeleri kullanılır.
Sağlam GA çok amaçlı optimizasyonla birleştirilebilir mi?
Evet — bu en pratik kombinasyonlardan biridir. Nominal performansı ve bir sağlamlık ölçüsünü (örneğin, performans varyansı) NSGA-II içinde ayrı hedefler olarak ele almak, sağlam-optimal takasların bir Pareto cephesini verir ve karar vericilerin kararlılık için ne kadar optimallikten vazgeçmeye istekli olduklarını seçmelerine olanak tanır.
Beklenti tabanlı sağlamlık ile RGA'daki en kötü durum sağlamlığı arasındaki fark nedir?
Beklenti tabanlı sağlamlık, örneklenen senaryolar boyunca ortalama performans düşüşünü en aza indirir — belirsizlik sık ancak sınırlı olduğunda uygundur. En kötü durum (min-maks) sağlamlığı, tanımlanmış bir belirsizlik kümesi içindeki en kötü niyetli pertürbasyon altında performansı garanti eder — nadir ancak felaket niteliğindeki arızaların önlenmesi gereken güvenlik açısından kritik veya düşmanca ortamlarda tercih edilir.
Belirsizlik dağılımı bilinmediğinde Sağlam GA uygun mudur?
Yetersiz karakterize edilmiş belirsizlik, sağlam çözümlerin güvenilirliğini baltalar. Dağılım bilinmediğinde, uygulayıcılar sınırlı bir belirsizlik kümesi üzerinde dağılımdan bağımsız veya en kötü durum formülasyonlarını kullanmalı, hangi belirsiz girdilerin en önemli olduğunu belirlemek için RGA'yı duyarlılık analiziyle birleştirmeli ve çözümleri çeşitli senaryolar boyunca ampirik olarak doğrulamalıdır.
İlgili yöntemler
Kaynaklar
Jin, Y., Branke, J. (2005). Evolutionary optimization in uncertain environments — a survey. IEEE Transactions on Evolutionary Computation, 9(3), 303–317.
DOI kaynağını açKopyalandı.Beyer, H.-G., Sendhoff, B. (2007). Robust optimization — A comprehensive survey. Computer Methods in Applied Mechanics and Engineering, 196(33–34), 3190–3218.
DOI kaynağını açKopyalandı.