NSGA-II — Çok Amaçlı Ayrışmamış Genetik Algoritma II
- Yıl
- 2002
- Tür
- Evolutionary multi-objective optimisation algorithm
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
NSGA-II (Çok Amaçlı Ayrışmamış Genetik Algoritma II), çok amaçlı evrimsel optimizasyon için standart referans algoritmadır; Deb, Pratap, Agarwal ve Meyarivan tarafından 2002 yılında tanıtılmıştır.
Birbirine rakip birden fazla amacı tek bir puana indirgemek yerine, aday çözümlerden oluşan bir popülasyonu nesiller boyunca evrimleştirir ve hızlı ayrışmamış sıralama ile çeşitliliği korumak için bir yığılma mesafesi metriği kullanarak bir dizi Pareto-optimal ödünleşme çözümü — Pareto cephesi — döndürür.
Yöntemin mantığı
Eş zamanlı olarak mümkün olduğunca ucuz ve dayanıklı bir ürün tasarlamak istediğinizi hayal edin. Daha ucuz genellikle daha az dayanıklı anlamına gelir, bu nedenle tek bir mükemmel cevap yoktur — bir dizi makul ödünleşme vardır. NSGA-II, rakip tasarımlardan oluşan bir popülasyon gibi çalışır: her nesilde, diğerleri tarafından her amaçta baskılanan zayıf tasarımlar elenir ve hayatta kalanlar, tek bir köşeye kümelenmek yerine ödünleşme aralığının tamamını kapsayacak şekilde yayılır. Yeterli nesilden sonra, önceliklerinize uyan seçenekler zengin bir menüsü — Pareto cephesi — ile baş başa kalırsınız.
Tarih
NSGA-II, 2002 yılında Kalyanmoy Deb ve Hint Teknoloji Enstitüsü Kanpur'daki meslektaşları tarafından orijinal NSGA'nın (Srinivas & Deb, 1994) düzeltilmiş ve önemli ölçüde geliştirilmiş bir ardılı olarak yayınlandı. Temel yenilikler, O(MN²) karmaşıklığına sahip hızlı bir ayrışmamış sıralama prosedürü, bir paylaşım parametresi olmadan çözüm çeşitliliğini korumak için açık bir yığılma mesafesi operatörü ve seçkinci bir seçim mekanizmasıydı. 2002 tarihli IEEE Transactions on Evolutionary Computation makalesi, evrimsel hesaplama alanındaki en çok atıf alan çalışmalardan biri haline geldi ve NSGA-II'yi çok amaçlı evrimsel algoritmalar için fiili kıyaslama standardı olarak belirledi. Daha sonraki varyantlar — NSGA-III (2014) ve diğerleri — çerçeveyi çok amaçlı problemlere genişletir.
Ne zaman kullanılır?
NSGA-II, iki veya daha fazla rakip amaç fonksiyonunun bilgi kaybı olmadan tek bir kritere indirgenemediği her durumda uygulanır. Karar değişkenleri sürekli, ikili veya kategorik olabilir ve amaç manzarası üzerinde herhangi bir dağılım varsayımı gerekmez. Algoritma, tek bir optimumdan daha yararlı bir ödünleşme çözümleri spektrumunun olduğu mühendislik tasarımı, kaynak tahsisi, zamanlama ve portföy sorunları için uygundur. İyi bir cephe kapsamı elde etmek için yeterli sayıda nesil (tipik olarak yüzlerce veya daha fazla) gerekir; çok az nesil çalıştırmak ana hata modudur.
Sınırlar ve dikkat edilmesi gerekenler
- Performans, amaç sayısı üç veya dördü aştıkça düşer — yığılma mesafesi yüksek boyutlarda zayıf bir çeşitlilik ölçüsü haline gelir.
- Popülasyon boyutu ve nesil sayısının dikkatli ayarlanmasını gerektirir; çok az nesil yeterli cephe kapsamını engeller.
- Pahalı simülasyonları içeren amaç fonksiyonlarını değerlendirmek, algoritmayı hesaplama açısından maliyetli hale getirir.
- Sonuçlar stokastiktir: farklı rastgele tohumlar farklı Pareto cepheleri üretebilir, bu nedenle birden fazla çalıştırma ve istatistiksel karşılaştırma (örneğin, hiperhacim) önerilir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Tek bir çalıştırmada çeşitli Pareto-optimal ödünleşme çözümleri üretir, farklı ağırlıklarla optimizasyonun tekrarlanması ihtiyacını ortadan kaldırır.
- Hızlı ayrışmamış sıralama O(MN²) zamanda çalışır (M amaç, N popülasyon boyutu), bu da onu orta düzey problem boyutları için çözülebilir hale getirir.
- Seçkinci seçim, erken bulunan iyi çözümlerin asla atılmamasını sağlar.
- Dağılım varsayımları olmadan sürekli, ikili ve kategorik karar değişkenlerine uygulanabilir.
- Mühendislik, operasyon araştırması ve hesaplamalı bilim alanlarında yaygın olarak doğrulanmıştır.
Uygulama alanları
- Mühendislik tasarımı: mekanik bileşenlerde ağırlığı eş zamanlı olarak en aza indirme ve yapısal mukavemeti en üst düzeye çıkarma.
- Çevresel ve enerji sistemleri: güç şebekesi veya yenilenebilir enerji planlamasında maliyet, emisyon ve güvenilirliği dengeleme.
- Sağlık hizmetleri ve operasyon araştırması: hasta bekleme süresini, kaynak kullanımını ve maliyeti eş zamanlı olarak optimize eden zamanlama.
- Finansta portföy optimizasyonu ve işletmede proje seçimi: getiriyi, riski ve likiditeyi dengeleme.
- Makine öğrenmesinde hiperparametre ayarı: doğruluğu model karmaşıklığına veya çıkarım süresine karşı optimize etme.
Nasıl çalışır?
Nasıl çalışır?
Aday çözümlerden oluşan bir popülasyon, karar değişkenlerinin sınırları dahilinde rastgele (veya tasarıma göre) örneklenmesiyle oluşturulur. Popülasyon boyutu, en başından itibaren amaç uzayında çeşitliliği sağlamak için yeterince büyük ayarlanır.
Her aday çözüm karar değişkeni değerlerine çözülür ve her amaç fonksiyonu değerlendirilir. Sonuç, birey başına amaç puanlarından oluşan bir vektördür. Amaçlar simülasyonları veya pahalı modelleri içerdiğinde bu adım genellikle hesaplama darboğazıdır.
Çözümler ayrışmamış sıralama ile derecelendirilir: ilk cephe, başka hiçbir çözüm tarafından her amaçta baskılanmayan tüm çözümleri içerir; ikinci cephe, yalnızca ilk cephedekiler tarafından baskılanan çözümleri içerir; ve bu böyle devam eder. Her cephe içinde, bir çözümün komşularından ne kadar izole olduğunu ölçmek için bir yığılma mesafesi puanı hesaplanır — daha yüksek yığılma mesafesi, çözümün cephenin daha az kalabalık bir bölgesini işgal ettiği anlamına gelir.
Seçkinci bir seçim stratejisi, mevcut popülasyonu yavrularla birleştirir ve en iyi N bireyi tutar, cepheleri sırayla doldurur ve son kabul edilebilir cephedeki eşitlikleri bozmak için yığılma mesafesini kullanır. Bu, önceki nesillerde bulunan iyi çözümlerin asla kaybolmamasını garanti eder.
Seçilen bireyler, yeni bir yavru popülasyonu üreten genetik operatörler — ikili turnuva seçimi, simüle edilmiş ikili çaprazlama (SBX) ve polinom mutasyonu — aracılığıyla ürerler. Bu operatörler, umut verici çözümlerin komşuluğunu keşfederken anlamlı değişimi korur.
Adımlar, belirli sayıda nesil boyunca evrimleşmek için tekrarlanır. Yakınsama, Pareto cephesinin görsel incelemesi veya hiperhacim göstergesi takibi ile değerlendirilir. Nihai çıktı, gerçek Pareto cephesini yaklaştıran ayrışmamış çözüm kümesidir.
Sık yapılan hatalar
- Genellikle birkaç yüz nesilden az çalıştırmak eksik bir Pareto cephesi verir; hesaplama bütçesi kısıtlıysa, bunun yerine ağırlıklı tek amaçlı optimizasyonu düşünün.
- Tek bir amacı olan bir problemi çok amaçlı olarak ele almak gereksizdir — tek amaçlı bir optimize edici kullanın.
- Makul değişken sınırlarını belirlememek, popülasyonların hiçbir zaman arama alanının geçerli veya anlamlı bölgelerine ulaşmamasına neden olur.
- Pareto cephesinin yalnızca bir çözümünü, tam cepheyi açıklamadan raporlamak, NSGA-II'nin ortaya çıkarmak için tasarlandığı ödünleşme yapısını gizler.
Sık sorulan sorular
NSGA-II kaç nesil gerektirir?
Evrensel bir kural yoktur, ancak birkaç yüz nesilden az çalıştırmak tipik olarak eksik bir Pareto cephesi üretir. Pratik bir yaklaşım, nesiller boyunca hiperhacim göstergesini çizmek ve stabil hale geldiğinde durmaktır. Hesaplama bütçesi buna izin vermiyorsa, ağırlıklı tek amaçlı bir optimize edici daha güvenli bir alternatiftir.
Pareto cephesi nedir?
Pareto cephesi, bir amaçta iyileştirmenin en az bir diğerini kötüleştirmeden mümkün olmadığı çözümler kümesidir. NSGA-II bu cepheyi yaklaştırır, size tek bir cevap yerine dengeli ödünleşmelerin tam menüsünü sunar.
NSGA-II ikiden fazla amacı işleyebilir mi?
Evet, ancak yığılma mesafesi — çeşitlilik mekanizması — amaç sayısı üç veya dördü aştıkça (yani 'çok amaçlı' rejim) daha az etkili hale gelir. Beş veya daha fazla amacı olan problemler için genellikle NSGA-III veya MOEA/D gibi ayrıştırma tabanlı algoritmalar tercih edilir.
NSGA-II deterministik midir?
Hayır. Genetik operatörler ve başlangıç popülasyonu rastgelelik içerir, bu nedenle farklı rastgele tohumlarla yapılan farklı çalıştırmalar farklı Pareto cephesi yaklaşımları üretebilir. En iyi uygulama, algoritmayı birden çok kez çalıştırmak ve hiperhacim göstergesini kullanarak cephe kalitesini karşılaştırmaktır.
İ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ı.Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.
DOI kaynağını açKopyalandı.