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

Eşgüdümlü çok amaçlı optimizasyon — Rekabet eden hedefler arasında dağıtık evrimsel arama

Ortaya koyan
Bonabeau, Dorigo, Theraulaz; Coello Coello et al.
Yıl
1990s–2000s
Tür
Simulation-driven multi-objective search
Aile
Simulation / optimization

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

Yazı boyutu

Ne işe yarar?

Eşgüdümlü çok amaçlı optimizasyon (ABMOO), bir simülasyon ortamına otonom eşgüdümlüler yerleştirerek ve iki veya daha fazla çelişkili hedefi eş zamanlı olarak optimize etmek üzere davranışlarını veya parametrelerini evrimleştirerek, tek bir optimum yerine çözümlerin Pareto-etkin sınırını verir.

Kapalı form denklemlerden ziyade mikro düzeydeki etkileşimlerden ortaya çıkan hedeflere sahip karmaşık uyarlanabilir sistemler için uygundur.

Yöntemin mantığı

Tek bir küresel amaç fonksiyonu yazmak yerine, ABMOO etkileşimli eşgüdümlülerden oluşan bir popülasyonun yerel kurallar ve ortaya çıkan davranışlar yoluyla çözüm uzayını keşfetmesine olanak tanır. Her eşgüdümlü bir aday çözümü veya karar vericiyi temsil eder; sistem simülasyonda ileriye doğru çalıştırılır, her hedeften elde edilen sonuçlar ölçülür ve bir Pareto-seçim mekanizması baskın olmayan çözümleri nesiller boyunca canlı tutar. Amaç fonksiyonu manzarasının simülasyon yoluyla değerlendirilmesi nedeniyle ABMOO, analitik işlemeye meydan okuyan doğrusal olmayan, stokastik ve yola bağlı amaç fonksiyonlarını işleyebilir. Sonuç, rekabet eden hedefler arasındaki tam ödünleşme yapısını gösteren çeşitli bir Pareto cephesidir.

Tarih

ABMOO, 1990'ların sonlarında ve 2000'lerin başlarında, araştırmacıların eşgüdümlü tabanlı modelleme çerçevelerini (NetLogo, Repast, MASON) çok amaçlı evrimsel algoritmalarla birleştirmesiyle ortaya çıktı. Bonabeau, Dorigo ve Theraulaz'ın sürü zekası üzerine ve Coello Coello ve arkadaşlarının evrimsel çok amaçlı optimizasyon üzerine temel çalışmaları, ABMOO'da birleştirilen teorik temelleri oluşturdu. Yaklaşım, 2000'ler ve 2010'lar boyunca karmaşık sistemler bilimi, kentsel planlama ve ekolojik yönetim alanlarında ilgi gördü.

Ne zaman kullanılır?

Sistem davranışının eşgüdümlü etkileşimlerinden kaynaklandığı ve kapalı form denklemlerle yakalanamadığı, iki veya daha fazla hedefin çeliştiği ve karar vericilerin tam ödünleşme sınırına ihtiyaç duyduğu ve stokastiklik veya yola bağımlılığın analitik optimizasyonu imkansız hale getirdiği durumlarda ABMOO'yu kullanın. Sosyal, ekolojik veya tedarik zinciri sistemlerinde politika tasarımı için idealdir. Tek bir hedef yeterli olduğunda, hızlı bir analitik gradyan tabanlı çözücü mevcut olduğunda, hesaplama bütçesi ciddi şekilde kısıtlı olduğunda (simülasyon değerlendirmeleri pahalıdır) veya hedefler içgörü kaybı olmadan skaler bir faydaya birleştirilebildiğinde kullanmayın.

Sınırlar ve dikkat edilmesi gerekenler

  • Hesaplama açısından pahalıdır: her fitness değerlendirmesi tam bir eşgüdümlü tabanlı simülasyon çalıştırmayı gerektirir, bu da maliyeti popülasyon büyüklüğü ve nesil sayısı ile çarpar.
  • Sonuçlar stokastiktir; Pareto cephesi çalıştırmalar arasında kayabilir, bu da birden fazla bağımsız çalıştırma ve istatistiksel toplama gerektirir.
  • Model geçerliliği, eşgüdümlü kurallarının gerçekçiliğine ve simülasyon ortamına büyük ölçüde bağlıdır; yanlış girdi, yanıltıcı Pareto cephelerine yol açar.
  • Popülasyon büyüklüğü, çaprazlama oranı, simülasyon uzunluğu gibi hiperparametre ayarı önemsizdir ve probleme özgüdür.
  • Yüksek boyutlu bir Pareto cephesini yorumlamak ve üzerinde hareket etmek, ek karar destek araçları olmadan bir zorluk olmaya devam etmektedir.

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

Güçlü yönleri

  • Kapalı form formülasyonuna direnen doğrusal olmayan, ortaya çıkan ve yola bağlı amaç manzaralarını işler.
  • Tek bir noktadan ziyade karar vericilere ödünleşmelerin açık görünürlüğünü veren tam bir Pareto cephesi üretir.
  • Fitness değerlendirmesi içindeki simülasyon tekrarlarını ortalayarak stokastikliği doğal olarak barındırır.
  • Çeşitli davranış kuralları ve etkileşim topolojilerine sahip heterojen eşgüdümlü popülasyonlara ölçeklenir.
  • Yerleşik çok amaçlı algoritmalara (NSGA-II, MOEA/D, MOPSO) optimizasyon sürücüsü olarak uyumludur.

Uygulama alanları

  • Altyapı yatırım ödünleşmelerinin (maliyet vs. tıkanıklık vs. emisyonlar) yerleşik eşgüdümlü kararlarından kaynaklandığı kentsel trafik ve arazi kullanımı planlaması.
  • Ağ tedarikçi eşgüdümlüleri arasında maliyet, teslim süresi ve aksama riskini dengeleyen tedarik zinciri dayanıklılık optimizasyonu.
  • Ekonomik verim ve biyoçeşitlilik hedeflerini dengeleyen Pareto-optimal hasat veya koruma politikaları bulan ekolojik yönetim.
  • Halk sağlığı eşgüdümlü simülasyonları aracılığıyla aşılama kapsamı ve ekonomik aktivite ödünleşmelerini optimize eden salgın müdahale tasarımı.
  • Maliyeti, karbon emisyonlarını ve şebeke istikrarsızlığını eş zamanlı olarak en aza indirmek için prosumer eşgüdümlülerini koordine eden enerji şebekesi yönetimi.
  • Eşgüdümlü tabanlı sosyal modellerde eşitlik ve verimlilik sonuçlarını ortaklaşa iyileştiren politika parametre kümelerini belirleyen sosyal politika değerlendirmesi.

Nasıl çalışır?

Nasıl çalışır?

1

En aza indirilecek veya en üst düzeye çıkarılacak m hedef f_1, ..., f_m ve her eşgüdümlünün genomunda veya kural setinde kodlanmış karar değişkenlerini listeleyin. Kısıtlamaları ve eşgüdümlü kararları gözlemlenebilir sonuçlara dönüştüren simülasyon ortamını tanımlayın.

2

Rastgele veya sezgisel olarak başlatılmış genomlara sahip N eşgüdümlüden oluşan bir popülasyonu başlatın. Her eşgüdümlünün genomu, optimizasyonun nesiller boyunca ayarlayacağı parametreleri veya davranış kurallarını kodlar.

3

Eşgüdümlü tabanlı simülasyonu T zaman adımı boyunca ileriye doğru çalıştırın. Her çalıştırmanın sonunda, her eşgüdümlü veya kolektif sistem için amaç değerlerini f_1(x), ..., f_m(x) okuyun. Stokastik gürültüyü yönetmek için birden fazla tekrarlama ortalaması alınabilir.

4

Baskın olmayan sıralama uygulayın: eşgüdümlüleri Pareto baskınlığına göre sıralayın. Bir x eşgüdümlüsü, tüm hedeflerde y'den daha kötü değilse ve en az birinde kesin olarak daha iyiyse y'yi baskılar. Baskın olmayan cepheyi (Pareto cephesi) tutun ve çeşitliliği korumak için kalabalık mesafesini veya hiperhacim katkısını kullanın.

5

Hayatta kalan popülasyona genetik operatörler (çaprazlama, mutasyon) veya sürü tarzı hız güncellemeleri uygulayın. Yeni aday eşgüdümlüler, Pareto cephesi üyelerinin genomlarını miras alır, birleştirir veya bozar, ardından değerlendirme için simülasyona yeniden girerler.

6

Bir durdurma kriteri (nesil bütçesi, hiperhacim yakınsaması veya saat sınırı) karşılandığında, son Pareto cephesini çözüm kümesi olarak döndürün. Karar verici yorumlaması için hedef uzay dağılım grafikleri veya paralel koordinat diyagramları kullanarak ödünleşmeleri görselleştirin.

Sık yapılan hatalar

  • Her eşgüdümlü değerlendirmesi başına çok az sayıda simülasyon tekrarı çalıştırmak gürültüyü artırır ve Pareto sıralamasını bozar — her zaman önce tekrarlama yeterliliğini test edin.
  • Yetersiz çeşitlilik mekanizmaları nedeniyle Pareto cephesinin ince bir bölgesine erken yakınsama; açıkça kalabalık mesafesi veya hiperhacim tabanlı seçimi kullanın.
  • Optimizasyon amacını simülasyon modelinin kendisiyle karıştırmak; eşgüdümlü kurallarının gerçek sistemi, istenen sonucu değil, temsil ettiğinden emin olun.
  • Hesaplama bütçesi kısıtlamalarını göz ardı etmek ve simülasyon çalışma süresi için karşılanamayan popülasyon büyüklükleri veya nesil sayıları belirlemek.
  • Karar vericilere, analiz felcine yol açan karar destek filtrelemesi veya görselleştirmesi olmadan ham Pareto cephesini sunmak.

Sık sorulan sorular

ABMOO, standart bir çok amaçlı genetik algoritmadan nasıl farklıdır?

Standart bir MOEA'da, fitness analitik olarak veya hızlı bir fonksiyon aracılığıyla hesaplanır. ABMOO'da, fitness tam bir eşgüdümlü tabanlı simülasyon çalıştırılarak hesaplanır, bu da her değerlendirmeyi çok daha pahalı hale getirir ancak ortaya çıkan, etkileşimli ve stokastik dinamiklere bağlı amaç manzaralarını etkinleştirir.

ABMOO'da hangi çok amaçlı algoritma optimize edici olarak en iyi çalışır?

NSGA-II, baskın olmayan sıralaması ve kalabalık mesafesi nedeniyle en yaygın kullanılanıdır. MOEA/D ve MOPSO da yaygındır. Seçim, Pareto cephesinin şekline ve boyutuna bağlıdır; evrensel olarak en iyi seçim yoktur — önce küçük bir çalıştırmada kıyaslayın.

Her eşgüdümlü değerlendirmesi için kaç simülasyon tekrarı çalıştırmalıyım?

Gürültüyü azaltacak kadar, böylece Pareto baskınlığı karşılaştırmaları güvenilir olur. Yaygın bir sezgisel yöntem, her hedefin değişim katsayısı %5-10'un altına düşene kadar çalıştırmaktır. Bu, sistem stokastikliğine bağlı olarak 10-50 tekrar gerektirebilir.

ABMOO ikiden fazla hedefi işleyebilir mi?

Evet, ancak performans hedef sayısı arttıkça düşer (Pareto baskınlığında boyutluluk laneti). Üçten fazla hedef için NSGA-III veya MOEA/D gibi çoklu hedef algoritmalarını düşünün ve ortaya çıkan cephe için boyut azaltma görselleştirme tekniklerini kullanın.

Standart ABMOO yerine ne zaman sağlam optimizasyonu tercih etmeliyim?

Simülasyon ortamının kendisi belirsiz olduğunda (parametre belirsizliği, yapısal belirsizlik), birden fazla çevresel senaryo altında eşgüdümlüleri değerlendiren ve tek bir deterministik cephe yerine en kötü durum veya beklenen Pareto performansını optimize eden sağlam varyantları kullanın.

İlgili yöntemler

Kaynaklar

  1. Bonabeau, E., Dorigo, M., & Theraulaz, G. (2002). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press.

    ISBN: 9780195131598
    Kopyalandı.
  2. Coello Coello, C. A., Lamont, G. B., & Van Veldhuizen, D. A. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems (2nd ed.). Springer.

    ISBN: 9780387332543
    Kopyalandı.