Çok Amaçlı Genetik Algoritma (MOGA) — Pareto-Optimal Çözümler için Evrimsel Arama
- Ortaya koyan
- Schaffer, J. D. (early MOGA); Goldberg, D. E. (GA foundations)
- Yıl
- 1984
- Tür
- Population-based evolutionary optimizer
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Çok Amaçlı Genetik Algoritma (MOGA), aday çözüm popülasyonunu bir Pareto-optimal cephesine doğru evrimleştiren, aynı anda iki veya daha fazla çelişkili amaç fonksiyonunu optimize eden evrimsel bir hesaplama yöntemidir.
Takasları tek bir puana indirmek yerine, karar vericinin seçebileceği baskın olmayan çözümler kümesi üretir.
Yöntemin mantığı
Aday tasarımların ardışık nesillerini yetiştirmeyi hayal edin; burada tüm hedeflerde açıkça yenilmeyen çözümler hayatta kalır ve ürer. Nesiller boyunca popülasyon, en iyi olası takasların bir cephesine yakınsar — bu Pareto cephesindeki hiçbir çözüm, bir hedefi iyileştiremezken diğerini kötüleştiremez. MOGA'lar, klasik gradyan yöntemlerinin başarısız olduğu yüksek boyutlu, dışbükey olmayan veya süreksiz arama uzaylarında bile bu cepheyi verimli bir şekilde keşfetmek için genetik işlemleri — seçilim, çaprazlama ve mutasyon — kullanır.
Tarih
Çok amaçlı genetik algoritmalar, 1984'te çok amaçlıları açıkça ele alan ilk GA olan Schaffer'ın Vektör Değerlendirmeli Genetik Algoritması'ndan (VEGA) ortaya çıktı. Goldberg'in 1989 ders kitabı, Pareto tabanlı sıralamayı ilkeli uygunluk atama stratejisi olarak biçimlendirdi. Alan, 1993'te Fonseca ve Fleming'in MOGA'sı, 1994'te Srinivas ve Deb'in NSGA'sı ve 2002'de Deb ve diğerlerinin dönüm noktası niteliğindeki NSGA-II'si ile hızla olgunlaştı; bu, alanın standart kıyaslaması haline geldi ve en çok atıfta bulunulan evrimsel çok amaçlı algoritma olmaya devam ediyor.
Ne zaman kullanılır?
Bir problemde iki veya daha fazla çelişkili amaç varsa ve tek bir optimal çözüm yoksa MOGA kullanın — mühendislik tasarımı, tedarik zinciri konfigürasyonu, portföy optimizasyonu ve çevre planlaması tipik alanlardır. Gradyan tabanlı yöntemlerin uygulanamadığı dışbükey olmayan, çok modlu veya kara kutu amaç manzaralarına uygundur. Tek bir iyi tanımlanmış amaç yeterliyse (bunun yerine standart bir GA veya matematiksel programlama kullanın), popülasyon değerlendirmesi hesaplama açısından yasaklayıcıysa ve vekil modeller mevcut değilse, amaçlar bilinen bir ağırlıklı toplam ile bilgi kaybı olmadan meşru olarak toplana biliyorsa veya küçük bir uygun küme kapsamlı listelemeye izin veriyorsa KULLANMAYIN.
Sınırlar ve dikkat edilmesi gerekenler
- Hesaplama maliyeti, popülasyon boyutuna ve fonksiyon değerlendirmelerinin sayısına göre ölçeklenir; karmaşık simülasyonların her bir değerlendirmesi pahalı olabilir.
- Gerçek Pareto cephesine yakınsama garanti edilmez — sonuçlar, hiperparametre seçimlerine (popülasyon boyutu, çaprazlama oranı, mutasyon oranı) duyarlı sezgisel yaklaşımlardır.
- Amaç sayısı üç veya dördün üzerinde büyüdükçe performans düşer (çok amaçlı optimizasyon, NSGA-III veya MOEA/D gibi özel algoritmalar gerektirir).
- Erken yakınsamadan veya zayıf cephe kapsamından kaçınmak için genetik operatörlerin ve çeşitlilik bakımının dikkatli ayarlanmasını gerektirir.
- Tek bir önerilen çözüm sağlamaz — Pareto cephesinden nihai seçim, hala değer yargıları veya ikincil bir karar kuralı gerektirir.
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 çözümler üretir, karar vericilere tek bir cevap yerine açık takas seçenekleri sunar.
- Gradyan veya probleme özgü matematiksel yapı gerektirmeden dışbükey olmayan, süreksiz ve çok modlu amaç manzaralarında çalışır.
- Doğası gereği popülasyon tabanlıdır, bu da çekirdekler veya dağıtılmış sistemler arasında paralelleştirmeyi kolaylaştırır.
- Esnek kodlama, aynı çerçeve içinde sürekli değişkenleri, tamsayıları, ikili dizileri ve permütasyonları sağlar.
- Olgun yazılım kütüphaneleri (DEAP, pymoo, jMetal) ve onlarca yıllık kıyaslama kanıtlarıyla iyi desteklenir.
Uygulama alanları
- Mühendislik tasarım optimizasyonu — yapısal bileşenlerde ağırlık, maliyet ve stresi eş zamanlı olarak en aza indirme.
- Tedarik zinciri ve lojistik — ağ yapılandırmaları boyunca maliyet, teslim süresi ve karbon emisyonlarını dengeleme.
- Çevre ve enerji politikası — maliyet, güvenilirlik ve emisyonlar için yenilenebilir enerji portföylerini optimize etme.
- Farmasötik ve kimyasal proses tasarımı — reaksiyon süresini en aza indirirken verimi ve saflığı en üst düzeye çıkarma.
- Makine öğrenimi hiperparametre ayarı — model doğruluğunu eğitim süresi veya yorumlanabilirliğe karşı takas etme.
- Şehir planlama ve ulaşım — kapsama, seyahat süresi ve altyapı maliyeti için rota ağlarını optimize etme.
Nasıl çalışır?
Nasıl çalışır?
Rastgele veya alan sezgisel yöntemleri kullanarak N aday çözüm (kromozom) başlangıç popülasyonu oluşturun, her çözümü karar değişkenleri vektörü olarak kodlayın. Eş zamanlı olarak en aza indirilecek veya en üst düzeye çıkarılacak k amaç fonksiyonu f1(x), f2(x), ..., fk(x) tanımlayın.
Popülasyondaki her birey için tüm k amaç fonksiyonunu değerlendirin. Uygunluk, hem hedefler arasındaki çözüm kalitesini hem de amaç uzayındaki kapsama çeşitliliğini yansıtır.
Bireyleri baskın olmama durumuna göre sıralayın: bir x çözümü, y çözümünü tüm hedeflerde en azından onun kadar iyi ve en az birinde kesin olarak daha iyi ise baskındır. Baskın olmayan cepheyi (Pareto cephesi adayları) belirleyin ve daha az baskın olan bireylere daha yüksek seçilim önceliği atayın. Kalabalıklaşma mesafesi gibi çeşitlilik metrikleri, cephenin dar bir bölgesinde kümelenmeyi önler.
Daha yüksek sıralı bireyleri tercih etmek için seçilim uygulayın (örneğin, turnuva seçilimi), ardından ebeveyn çiftlerini birleştirmek için çaprazlama ve varyasyon eklemek için mutasyon uygulayın. Elitizm mekanizmaları, nesiller boyunca bulunan en iyi baskın olmayan çözümleri korur.
Önceden belirlenmiş sayıda nesil boyunca veya yakınsama kriterleri karşılanana kadar uygunluk değerlendirmesi, sıralama ve üremeyi tekrarlayın. Nihai baskın olmayan küme, Pareto-optimal cephesini yaklaştırır ve karar vericiye optimal takas çözümlerinin bir spektrumunu sunar.
Sık yapılan hatalar
- Pareto cephesindeki tüm çözümleri, nihai takas seçimini yapmak için alan uzmanlarını dahil etmeden eşit derecede geçerli kabul etmek, keyfi veya kötü gerekçelendirilmiş seçimlere yol açabilir.
- Çok küçük bir popülasyon kullanmak seyrek, temsili olmayan cepheler üretir; çok büyük bir popülasyon orantısız fayda olmaksızın hesaplamayı şişirir.
- Kısıtlama işlemenin göz ardı edilmesi — uygun olmayan çözümler açıkça cezalandırılmalı veya onarılmalıdır; bunu yapmamak, aramayı uygun olmayan bölgelere doğru bozar.
- MOGA'yı dörtten fazla amacı olan problemlere çok amaçlı bir algoritmaya geçmeden uygulamak, neredeyse tüm çözümlerin baskın olmadığı, dağınık, bilgilendirici olmayan cephelere yol açar.
- Nihai Pareto cephesini, yakınsama tanıları (nesiller boyunca hiperhacim) olmadan raporlamak, algoritmanın gerçekten yakınsadığını değerlendirmeyi imkansız hale getirir.
Sık sorulan sorular
MOGA, amaçların ağırlıklı toplamı ile tek amaçlı bir GA çalıştırmaktan nasıl farklıdır?
Ağırlıklı toplam yaklaşımı, önceden atanmış ağırlıklar kullanarak tüm amaçları tek bir skaler değere indirger ve bu ağırlıklara bağlı tek bir çözüm üretir. MOGA, önceden ağırlık belirtmeye gerek kalmadan tüm baskın olmayan çözümlerin bir cephesini eş zamanlı olarak üretir, bu da karar vericinin takasları incelemesine ve sonradan seçim yapmasına olanak tanır.
Pareto cephesi nedir ve neden önemlidir?
Pareto cephesi, herhangi bir tek amacı iyileştirmenin zorunlu olarak en az bir diğerini kötüleştirdiği çözüm kümesidir. Elde edilebilir takasların tam resmini temsil eder. Karar vericiler, bir hedefe ulaşmak için diğerinden ne kadar fedakarlık yapılması gerektiğini anlamak için bu cepheyi inceleyebilirler.
MOGA etkili bir şekilde kaç hedefi işleyebilir?
NSGA-II gibi standart MOGA varyantları iki veya üç hedef için iyi çalışır. Dört hedefin ötesinde, baskın olmayan çözümlerin oranı hızla artar (amaç uzayında boyutluluk laneti), bu da Pareto cephesini büyük ve seçilim baskısını zayıf hale getirir. Dört veya daha fazla hedef için çok amaçlı algoritmalar (NSGA-III, MOEA/D, IBEA) önerilir.
Hangi durdurma kriterini kullanmalıyım?
Yaygın kriterler arasında sabit sayıda fonksiyon değerlendirmesi, maksimum nesil sayısı veya ardışık nesiller boyunca mevcut Pareto cephesi yaklaşımının domine ettiği amaç uzayı hacmi olan hiperhacim göstergesinin yakınsaması bulunur. Hiperhacim büyümesini izlemek en ilkeli yaklaşımdır.
MOGA kısıtlamaları işleyebilir mi?
Evet, kısıtlama işleme teknikleri aracılığıyla: uygun olmayan çözümlerin uygunluğunu düşüren ceza fonksiyonları, uygunluk turnuva seçilimi (uygun çözümler seçilimde her zaman uygun olmayanları yener) veya uygun olmayan çözümleri uygun bölgeye geri yansıtan onarım operatörleri. Seçim, yakınsama davranışını etkiler ve bilinçli yapılmalıdır.
İlgili yöntemler
Kaynaklar
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.
ISBN: 9780201157673Kopyalandı.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ı.