İçeriğe atla
Arama sonuçlarına dön

Agent-Based NSGA-II — Simülasyon Güdümlü Evrimsel Çok Amaçlı Optimizasyon

Ortaya koyan
Deb et al. (NSGA-II, 2002); integrated with agent-based modeling frameworks in the 2000s–2010s
Yıl
2000s–2010s
Tür
Simulation-embedded evolutionary multi-objective optimizer
Aile
Simulation / optimization

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Agent-based NSGA-II, NSGA-II evrimsel algoritmasını bir ajan tabanlı simülasyon döngüsüne gömer, böylece her bir aday çözümün amaç değerleri kapalı form bir fonksiyonu değerlendirmek yerine tam bir ajan simülasyonu çalıştırılarak belirlenir.

Bu eşleştirme, analitik olarak çözülebilir denklemlerden ziyade mikro düzeydeki otonom ajan etkileşimlerinden ortaya çıkan sistemler üzerinde çok amaçlı optimizasyona olanak tanır.

Yöntemin mantığı

Standart NSGA-II, her çözümü birden çok amaç doğrultusunda puanlamak için bir matematiksel formül sorgular. Sistem davranışı bir formül olarak ifade edilemeyecek kadar karmaşık veya ortaya çıkan nitelikte olduğunda — salgınlar, trafik ağları veya uyarlanabilir aktörlere sahip tedarik zincirleri gibi — bu formülü bir ajan tabanlı simülasyonla değiştirirsiniz. Her aday çözüm politika parametrelerini veya ajan kurallarını kodlar; simülasyon ileriye doğru çalıştırılır, toplu sonuçlar amaç değerleri olarak ölçülür ve NSGA-II'nin baskın olmayan sıralaması ve kalabalık mesafesi seçimi daha sonra çeşitli ödünleşme çözümlerinden oluşan bir Pareto cephesi oluşturur. Sonuç, karmaşık uyarlanabilir dinamiklerden kaynaklansa bile, tüm modellenen amaçlar doğrultusunda eş zamanlı olarak Pareto-etkin olan parametre yapılandırmaları kümesidir.

Tarih

NSGA-II, 2002 yılında Kalyanmoy Deb ve meslektaşları tarafından IIT Kanpur'da hızlı, seçkin bir çok amaçlı genetik algoritma olarak tanıtıldı ve hızla evrimsel hesaplamada en çok atıfta bulunulan algoritmalardan biri haline geldi. Ajan tabanlı modelleme, 1990'lar boyunca Swarm, NetLogo ve Repast gibi platformlarla bir hesaplama paradigması olarak büyüdü. NSGA-II'nin ajan tabanlı simülasyonlarla eşleştirilmesi, 2000'ler ve 2010'larda şehir planlama, ekoloji, epidemiyoloji ve tedarik zinciri yönetimi alanlarındaki araştırmacılar analitik formülasyon için fazla karmaşık sistemlerde politikaları optimize etmeye çalıştıkça ortaya çıktı.

Ne zaman kullanılır?

İki veya daha fazla çelişkili amaç eş zamanlı olarak optimize edilmeli ve bu amaçlar kapalı form fonksiyonlardan ziyade ajan etkileşimlerinden kaynaklanıyorsa — örneğin, bir nüfus modelinde salgın kontrol maliyeti ile ekonomik aktiviteyi dengelemek veya uyarlanabilir tedarikçilerin bir ağında tedarik zinciri maliyetini en aza indirirken dayanıklılığı en üst düzeye çıkarmak — ajan tabanlı NSGA-II kullanın. Stokastiklik sistemde doğalsa ve çoğaltmalar üzerinden ortalaması alınması gerekiyorsa uygundur. Hızlı bir analitik amaç fonksiyonu mevcut olduğunda (düz NSGA-II yeterlidir ve çok daha ucuzdur), yalnızca bir amaç ilgili olduğunda, ajan simülasyonu çalıştırma başına çok pahalı olduğundan küçük bir popülasyon bile toplam hesaplama maliyetini karşılanamaz hale getirdiğinde veya üç veya dört amaçtan fazlası gerektiğinde (bunun yerine NSGA-III veya MOEA/D varyantlarını tercih edin) kullanmayın.

Sınırlar ve dikkat edilmesi gerekenler

  • Hesaplama açısından çok pahalıdır: her nesil N x R simülasyon çalışması gerektirir, burada birey başına R çoğaltma büyük olabilir; toplam duvar saati süresi engelleyici olabilir.
  • Performans, üç veya dörtten fazla amaçla bozulur, çünkü baskın olmayan sıralama ayırt edici gücünü kaybeder ve kalabalık mesafesi yüksek boyutlu amaç uzayında güvenilmez hale gelir.
  • Sonuçlar simülasyon modeli doğruluğuna bağlıdır; gerçekçi olmayan ajan kuralları veya kötü kalibre edilmiş parametreler, optimizasyon kalitesinden bağımsız olarak yanıltıcı Pareto cepheleri üretir.
  • Simülasyon fitness değerlendirmesindeki stokastiklik, çoğaltma sayısı R çok küçükse baskınlık karşılaştırmalarını bozabilir, bu da yanlış Pareto sıralamasına yol açar.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Analitik olarak ifade edilemeyen ortaya çıkan, yola bağlı ve stokastik amaç manzaralarını işler, bu da onu karmaşık uyarlanabilir sistemlere uygulanabilir kılar.
  • Tek bir optimizasyon çalıştırmasında tam bir Pareto cephesi üretir, karar vericilere önceden tercih ağırlıkları gerektirmeden ödünleşme konusunda açık bir görünürlük sağlar.
  • NSGA-II'nin seçkinlik mekanizması, yüksek kaliteli baskın olmayan çözümlerin nesiller boyunca asla atılmamasını sağlar.
  • Her bir fitness değerlendirmesi içindeki çoğaltma ortalaması, yöntemin stokastik simülasyon gürültüsünü ilkeli bir şekilde işlemesine olanak tanır.
  • Herhangi bir ajan tabanlı simülasyon platformu (NetLogo, Repast, AnyLogic, Mesa) ile standartlaştırılmış bir sarmalayıcı arayüz aracılığıyla uyumludur.

Uygulama alanları

  • Salgın müdahale tasarımı: bir nüfus ajanı modelinde enfeksiyon yükünü ve ekonomik maliyeti ortaklaşa en aza indiren aşılama kapsamı ve hareket kısıtlamalarının Pareto-optimal kombinasyonlarını bulmak.
  • Kentsel arazi kullanımı ve ulaşım planlaması: yerleşik ve araç ajanı etkileşimlerinden ortaya çıkan tıkanıklık, emisyon ve eşitlik sonuçlarını optimize eden imar ve altyapı yatırım parametrelerini optimize etmek.
  • Tedarik zinciri ağı tasarımı: uyarlanabilir tedarikçi ve dağıtıcı ajan ağları arasında maliyet, teslim süresi ve aksama dayanıklılığını dengeleyen politika yapılandırmalarını belirlemek.
  • Ekolojik hasat yönetimi: bir ajan tabanlı ekosistem modelinde ekonomik verimi ortaklaşa en üst düzeye çıkarmak ve biyoçeşitliliği korumak için hasat kurallarını optimize etmek.
  • Enerji mikro şebeke kontrolü: stokastik yenilenebilir üretim altında şebeke maliyetini ve karbon emisyonlarını en aza indirmek için prosumer ajan teklif stratejilerini ortaklaşa optimize etmek.
  • Sosyal eşitsizlik politika analizi: ajan tabanlı ekonomik modellerde gelir eşitliğini ve işgücü piyasası verimliliğini ortaklaşa iyileştiren müdahale parametre kümelerini bulmak.

Nasıl çalışır?

Nasıl çalışır?

1

Karar değişkenlerini (ajan davranış parametreleri, politika kaldıraçları, kaynak tahsisleri) tanımlayın ve optimize edilecek çelişkili amaçları (örneğin, maliyeti en aza indirme ve hizmet oranını en üst düzeye çıkarma) listeleyin. Bir karar değişkeni vektörünü kabul eden ve her simülasyon çalıştırmasının sonunda amaç ölçümlerini döndüren bir ajan tabanlı simülasyon modeli oluşturun veya parametrelendirin. Kısıtlamaları, simülasyon süresini ve her değerlendirme için stokastik çoğaltma sayısını belirtin.

2

Karar alanından düzgün rastgele veya Latin hiperküp örneklemesi yoluyla örnekleyerek N aday çözüm vektöründen oluşan bir popülasyonu başlatın. Her birey, ajan parametrelerinin veya politika ayarlarının bir yapılandırmasını temsil eder. NSGA-II hiperparametrelerini ayarlayın: popülasyon boyutu N, çaprazlama olasılığı, mutasyon oranı ve maksimum nesil sayısı.

3

Mevcut popülasyondaki her birey için, stokastik gürültüyü azaltmak üzere ajan tabanlı simülasyonu R kez (çoğaltma) çalıştırın ve elde edilen amaç değerlerini ortalayın. Her birey için ortalama amaç vektörünü kaydedin. Bu adım hesaplama maliyetine hakimdir: N birey çarpı R çoğaltma çarpı değerlendirme başına T simülasyon zaman adımı.

4

Tüm bireyleri Pareto cepheleri F1, F2, ... şeklinde sıralamak için hızlı baskın olmayan sıralamayı uygulayın. F1 cephesi, başka herhangi bir çözüm tarafından baskın olmayan çözümleri içerir; F2, yalnızca F1 üyeleri tarafından baskın olanları ve bu şekilde devam eder. Her cephe içinde, her çözümün ne kadar izole olduğunu ölçmek ve cephe boyunca çeşitliliği korumak için kalabalık mesafesini — her hedef ekseni boyunca komşu aralıkların toplamını — hesaplayın.

5

Kalabalık karşılaştırma operatörünü kullanarak ikili turnuva yoluyla ebeveynleri seçin: daha düşük numaralı cephedeki bireyi tercih edin, beraberlikleri daha büyük kalabalık mesafesi lehine bozun. N yavru üretmek için simüle edilmiş ikili çaprazlamayı (SBX) ve polinom mutasyonunu uygulayın. Ebeveynleri ve yavruları 2N bireylik bir havuzda birleştirin, yeniden sıralayın ve cephe sıralaması ve kalabalık mesafesini beraberlik bozucu olarak kullanarak bir sonraki nesil için en iyi N bireyi saklayın.

6

Durdurma kriterine ulaşıldıktan sonra (nesil bütçesi tükendi veya hiperhacim yakınsaması doğrulandı), yaklaşık Pareto-optimal küme olarak son popülasyonun F1 cephesini döndürün. Amaç uzayında ödünleşme yüzeyini görselleştirin ve birden çok bağımsız çalıştırma üzerinden toplanan kalite metrikleri olarak hiperhacmi veya ters üretken mesafeyi (IGD) raporlayın.

Sık yapılan hatalar

  • Simülasyon stokastik olduğunda birey başına çok az çoğaltma kullanmak (R = 1 veya 2) — gürültülü bir fitness tahmini, baskın sıralama adımının çözümleri yanlış sınıflandırmasına ve Pareto cephesini bozmasına neden olur.
  • Popülasyon boyutunu N, beklenen Pareto cephesi karmaşıklığından daha küçük ayarlamak, algoritmayı ödünleşme uzayının tüm bölgelerini atmaya zorlar ve parçalı bir cephe döndürür.
  • Bu yöntemi dört veya daha fazla amaç için NSGA-III veya MOEA/D'ye geçmeden uygulamak, çoğu bireyin F1 cephesinde kümelenmesine neden olur ve seçimi neredeyse rastgele hale getirir.
  • Ajan modeli kalibrasyonunu ve optimizasyonunu karıştırmak: simülasyon, optimizasyon başlamadan önce gözlemlenen verilere göre kalibre edilmelidir — kalibre edilmemiş bir modelin optimize edilmesi, gerçek dünya geçerliliği olmayan Pareto cepheleri üretir.
  • Paralel hesaplamayı ihmal etmek: her simülasyon çalışması bağımsız olduğundan, ajan tabanlı NSGA-II'nin kendiliğinden paralelleştirilebilir olması; tek iş parçacıklı çalıştırmak mevcut donanımı boşa harcar ve çalışma sürelerini gereksiz yere uzatır.

Sık sorulan sorular

Ajan tabanlı NSGA-II, düz NSGA-II'den nasıl farklıdır?

Düz NSGA-II, her çözümü hızlı olan analitik bir fonksiyon çağırarak değerlendirir. Ajan tabanlı NSGA-II, bu fonksiyon çağrısını tam bir ajan tabanlı simülasyon çalışmasıyla değiştirir, bu da ortaya çıkan ve yola bağlı amaçlar üzerinde optimizasyona olanak tanır, ancak değerlendirme başına önemli ölçüde daha yüksek hesaplama maliyetiyle.

Birey değerlendirmesi başına kaç çoğaltma çalıştırmalıyım?

Çoğaltmalar arasındaki her bir amacın değişim katsayısının kabaca %5-10'un altına düşecek kadar. R = 10 ile başlayın ve amaç tahminleri kararlı hale gelene kadar artırın. Yüksek derecede stokastik modeller için R = 30 ila 50 gerekebilir, bu da maliyeti buna göre katlar.

Ajan tabanlı NSGA-II'yi hesaplama açısından nasıl fizibil hale getirebilirim?

CPU çekirdekleri veya bir küme üzerinde paralelleştirin — her bireyin simülasyon çalışmaları bağımsızdır ve önemsiz derecede paralelleştirilebilir. Ucuz ön tarama için fitness'ı tahmin etmek üzere vekil modeller (Gauss süreçleri veya sinir ağları) kullanın, umut vadeden adaylar için tam simülasyon değerlendirmelerini saklayın.

Dört veya daha fazla amacım varsa ne olur?

NSGA-III veya MOEA/D'nin ajan tabanlı bir varyantına geçin. NSGA-III, kalabalık mesafesi yerine referans noktası tabanlı seçimi kullanır, dört veya daha fazla amaçta çeşitliliği etkili bir şekilde korur. MOEA/D, problemi skaler alt problemlere ayırır ve çok amaçlı ayarlara daha iyi ölçeklenir.

Pareto cephesinin güvenilir olduğunu nasıl doğrularım?

Farklı rastgele tohumlarla en az 10 bağımsız optimizasyon çalıştırması yapın ve her biri için hiperhacmi veya IGD'yi hesaplayın. Çalıştırmalar arasındaki ortancayı ve çeyrekler arası aralığı raporlayın. Çalıştırmalar boyunca tutarlı hiperhacim, optimize edicinin aynı yaklaşık Pareto cephesine güvenilir bir şekilde yakınsadığını gösterir.

İlgili yöntemler

Kaynaklar

  1. 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ı.
  2. Macal, C. M., & North, M. J. (2010). Tutorial on agent-based modelling and simulation. Journal of Simulation, 4(3), 151-162.

    DOI kaynağını aç
    Kopyalandı.