Skip to content
Kembali ke hasil pencarian

NSGA-II Berbasis Agen — Optimisasi Multi-Objektif Evolusioner Berbasis Simulasi

Diperkenalkan oleh
Deb et al. (NSGA-II, 2002); integrated with agent-based modeling frameworks in the 2000s–2010s
Tahun
2000s–2010s
Jenis
Simulation-embedded evolutionary multi-objective optimizer
Keluarga
Simulation / optimization

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

NSGA-II berbasis agen menyematkan algoritma evolusioner NSGA-II di dalam putaran simulasi berbasis agen sehingga nilai objektif untuk setiap solusi kandidat ditentukan dengan menjalankan simulasi agen penuh daripada mengevaluasi fungsi bentuk tertutup.

Penggabungan ini memungkinkan optimisasi multi-objektif pada sistem yang kinerjanya muncul dari interaksi tingkat mikro agen otonom daripada dari persamaan yang dapat ditangani secara analitis.

Intuisi di balik metode

NSGA-II standar menanyakan formula matematika untuk menilai setiap solusi pada berbagai objektif. Ketika perilaku sistem terlalu kompleks atau muncul untuk diekspresikan sebagai formula — pikirkan epidemi, jaringan lalu lintas, atau rantai pasokan dengan aktor adaptif — Anda mengganti formula itu dengan simulasi berbasis agen. Setiap solusi kandidat mengkodekan parameter kebijakan atau aturan agen; simulasi dijalankan ke depan, hasil agregat diukur sebagai nilai objektif, dan pengurutan non-dominasi serta seleksi jarak kerumunan NSGA-II kemudian membangun front Pareto yang beragam dari solusi pertukaran. Hasilnya adalah serangkaian konfigurasi parameter yang secara bersamaan efisien Pareto di semua objektif yang dimodelkan, bahkan ketika objektif tersebut muncul dari dinamika adaptif yang kompleks.

Sejarah

NSGA-II diperkenalkan oleh Kalyanmoy Deb dan rekan-rekannya di IIT Kanpur pada tahun 2002 sebagai algoritma genetik multi-objektif yang cepat dan elitis, dengan cepat menjadi salah satu algoritma yang paling banyak dikutip dalam komputasi evolusioner. Pemodelan berbasis agen sebagai paradigma komputasi tumbuh melalui tahun 1990-an dengan platform seperti Swarm, NetLogo, dan Repast. Penggabungan NSGA-II dengan simulasi berbasis agen muncul pada tahun 2000-an dan 2010-an ketika para peneliti di bidang perencanaan kota, ekologi, epidemiologi, dan manajemen rantai pasokan berusaha untuk mengoptimalkan kebijakan dalam sistem yang terlalu kompleks untuk formulasi analitis.

Kapan digunakan

Gunakan NSGA-II berbasis agen ketika dua atau lebih objektif yang saling bertentangan harus dioptimalkan secara bersamaan dan objektif tersebut muncul dari interaksi agen daripada fungsi bentuk tertutup — misalnya, menyeimbangkan biaya penahanan epidemi dan aktivitas ekonomi dalam model populasi, atau meminimalkan biaya rantai pasokan sambil memaksimalkan ketahanan dalam jaringan pemasok adaptif. Ini sesuai ketika stokastisitas melekat dalam sistem dan harus dirata-ratakan selama replikasi. Jangan gunakan ketika fungsi objektif analitik yang cepat ada (NSGA-II biasa sudah cukup dan jauh lebih murah), ketika hanya satu objektif yang relevan, ketika simulasi agen terlalu mahal per putaran sehingga bahkan populasi kecil membuat total biaya komputasi tidak mungkin, atau ketika lebih dari tiga atau empat objektif diperlukan (gunakan varian NSGA-III atau MOEA/D sebagai gantinya).

Batasan dan pertimbangan

  • Sangat mahal secara komputasi: setiap generasi membutuhkan N x R putaran simulasi, di mana R replikasi per individu mungkin besar; total waktu dinding dapat menghalangi.
  • Kinerja menurun dengan lebih dari tiga atau empat objektif, karena pengurutan non-dominasi kehilangan kekuatan diskriminatif dan jarak kerumunan menjadi tidak dapat diandalkan dalam ruang objektif berdimensi tinggi.
  • Hasil bergantung pada kesetiaan model simulasi; aturan agen yang tidak realistis atau parameter yang dikalibrasi dengan buruk menghasilkan front Pareto yang menyesatkan terlepas dari kualitas optimisasi.
  • Stokastisitas dalam evaluasi kebugaran simulasi dapat merusak perbandingan dominasi jika jumlah replikasi R terlalu kecil, yang mengarah pada peringkat Pareto yang salah.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Menangani lanskap objektif yang muncul, bergantung pada jalur, dan stokastik yang tidak dapat diekspresikan secara analitis, membuatnya dapat diterapkan pada sistem adaptif yang kompleks.
  • Menghasilkan front Pareto penuh dalam satu putaran optimisasi, memberikan pembuat keputusan visibilitas eksplisit tentang pertukaran tanpa memerlukan bobot preferensi sebelumnya.
  • Mekanisme elitisme NSGA-II memastikan bahwa solusi non-dominasi berkualitas tinggi tidak pernah dibuang antar generasi.
  • Rata-rata replikasi dalam setiap evaluasi kebugaran memungkinkan metode untuk menangani noise simulasi stokastik secara terprinsip.
  • Kompatibel dengan platform simulasi berbasis agen apa pun (NetLogo, Repast, AnyLogic, Mesa) melalui antarmuka wrapper standar.

Penerapan

  • Desain intervensi epidemi: menemukan kombinasi optimal Pareto dari cakupan vaksinasi dan pembatasan pergerakan yang secara bersamaan meminimalkan beban infeksi dan biaya ekonomi dalam model agen populasi.
  • Perencanaan penggunaan lahan dan transportasi perkotaan: mengoptimalkan parameter zonasi dan investasi infrastruktur yang muncul sebagai hasil kemacetan, emisi, dan kesetaraan dari interaksi agen penghuni dan kendaraan.
  • Desain jaringan rantai pasokan: mengidentifikasi konfigurasi kebijakan yang menyeimbangkan biaya, waktu tunggu, dan ketahanan terhadap gangguan di seluruh jaringan agen pemasok dan distributor adaptif.
  • Manajemen panen ekologis: mengoptimalkan aturan panen untuk secara bersamaan memaksimalkan hasil ekonomi dan mempertahankan keanekaragaman hayati dalam model ekosistem berbasis agen.
  • Kontrol microgrid energi: mengoptimalkan strategi penawaran agen prosumer untuk meminimalkan biaya grid dan emisi karbon di bawah generasi terbarukan stokastik.
  • Analisis kebijakan kesenjangan sosial: menemukan set parameter intervensi yang secara bersamaan meningkatkan kesetaraan pendapatan dan efisiensi pasar tenaga kerja dalam model ekonomi berbasis agen.

Cara kerjanya

Cara kerjanya

1

Definisikan variabel keputusan (parameter perilaku agen, tuas kebijakan, alokasi sumber daya) dan uraikan objektif yang saling bertentangan untuk dioptimalkan (misalnya, minimalkan biaya dan maksimalkan tingkat layanan). Bangun atau parametrisasi model simulasi berbasis agen yang menerima vektor variabel keputusan dan mengembalikan pengukuran objektif di akhir setiap putaran simulasi. Tentukan batasan, durasi simulasi, dan jumlah replikasi stokastik per evaluasi.

2

Inisialisasi populasi N vektor solusi kandidat dengan mengambil sampel ruang keputusan secara acak seragam atau melalui pengambilan sampel Latin hypercube. Setiap individu mewakili satu konfigurasi parameter agen atau pengaturan kebijakan. Tetapkan hiperparameter NSGA-II: ukuran populasi N, probabilitas persilangan, laju mutasi, dan jumlah generasi maksimum.

3

Untuk setiap individu dalam populasi saat ini, jalankan simulasi berbasis agen R kali (replikasi) dan rata-ratakan nilai objektif yang dihasilkan untuk mengurangi noise stokastik. Catat vektor objektif rata-rata untuk setiap individu. Langkah ini mendominasi biaya komputasi: N individu dikalikan R replikasi dikalikan T langkah waktu simulasi per evaluasi.

4

Terapkan pengurutan non-dominasi cepat untuk memberi peringkat semua individu ke dalam front Pareto F1, F2, .... Front F1 berisi solusi yang tidak didominasi oleh yang lain; F2 berisi yang hanya didominasi oleh anggota F1, dan seterusnya. Di dalam setiap front, hitung jarak kerumunan — jumlah celah antar-tetangga yang dinormalisasi di sepanjang setiap sumbu objektif — untuk mengukur seberapa terisolasi setiap solusi dan mempertahankan keragaman di seluruh front.

5

Pilih induk melalui turnamen biner menggunakan operator perbandingan kerumunan: utamakan individu di front bernomor lebih rendah, pecahkan seri yang menguntungkan jarak kerumunan yang lebih besar. Terapkan persilangan biner simulasi (SBX) dan mutasi polinomial untuk menghasilkan N anakan. Gabungkan induk dan anakan ke dalam kumpulan 2N individu, urutkan ulang, dan pertahankan N individu terbaik untuk generasi berikutnya menggunakan peringkat front dan jarak kerumunan sebagai pemecah seri.

6

Setelah kriteria penghentian tercapai (anggaran generasi habis atau konvergensi hypervolume terkonfirmasi), kembalikan front F1 dari populasi akhir sebagai himpunan optimal Pareto perkiraan. Visualisasikan permukaan pertukaran dalam ruang objektif dan laporkan hypervolume atau inverted generational distance (IGD) sebagai metrik kualitas yang diagregasi dari beberapa putaran independen.

Kesalahan umum

  • Menggunakan terlalu sedikit replikasi per individu (R = 1 atau 2) ketika simulasi bersifat stokastik — perkiraan kebugaran yang berisik menyebabkan langkah pengurutan dominasi salah mengklasifikasikan solusi dan merusak front Pareto.
  • Menetapkan ukuran populasi N lebih kecil dari kompleksitas front Pareto yang diharapkan, yang memaksa algoritma untuk membuang seluruh wilayah ruang pertukaran dan mengembalikan front yang terfragmentasi.
  • Menerapkan metode ini ke empat atau lebih objektif tanpa beralih ke NSGA-III atau MOEA/D, menyebabkan sebagian besar individu mengelompok di front F1 dan membuat seleksi hampir acak.
  • Mencampuradukkan kalibrasi model agen dan optimisasi: simulasi harus dikalibrasi pada data yang diamati sebelum optimisasi dimulai — mengoptimalkan model yang tidak terkalibrasi menghasilkan front Pareto tanpa validitas dunia nyata.
  • Mengabaikan komputasi paralel: karena setiap putaran simulasi independen, NSGA-II berbasis agen dapat diparalelkan dengan mudah; menjalankannya secara single-threaded menyia-nyiakan perangkat keras yang tersedia dan membuat waktu berjalan menjadi tidak perlu lama.

Pertanyaan yang sering diajukan

Bagaimana agent-based NSGA-II berbeda dari NSGA-II biasa?

NSGA-II biasa mengevaluasi setiap solusi dengan memanggil fungsi analitik, yang cepat. Agent-based NSGA-II mengganti panggilan fungsi tersebut dengan menjalankan simulasi berbasis agen penuh, memungkinkan optimisasi atas objektif yang muncul dan bergantung pada jalur, tetapi dengan biaya komputasi yang jauh lebih tinggi per evaluasi.

Berapa banyak replikasi yang harus saya jalankan per evaluasi individu?

Cukup sehingga koefisien variasi setiap objektif di seluruh replikasi turun di bawah sekitar 5-10%. Mulai dengan R = 10 dan tingkatkan sampai perkiraan objektif stabil. Untuk model yang sangat stokastik, R = 30 hingga 50 mungkin diperlukan, yang secara proporsional meningkatkan biaya.

Bagaimana saya bisa membuat agent-based NSGA-II layak secara komputasi?

Paralelkan di seluruh inti CPU atau kluster — setiap jalannya simulasi individu independen dan dapat diparalelkan dengan mudah. Gunakan model pengganti (Gaussian processes atau neural networks) untuk memperkirakan kebugaran untuk penyaringan awal yang murah, menyisakan evaluasi simulasi penuh untuk kandidat yang menjanjikan.

Bagaimana jika saya memiliki empat atau lebih objektif?

Beralih ke varian berbasis agen dari NSGA-III atau MOEA/D. NSGA-III menggunakan seleksi berbasis titik referensi alih-alih jarak kerumunan, secara efektif mempertahankan keragaman dalam empat atau lebih objektif. MOEA/D menguraikan masalah menjadi submasalah skalar dan diskalakan lebih baik ke pengaturan multi-objektif.

Bagaimana cara memvalidasi bahwa front Pareto andal?

Jalankan setidaknya 10 putaran optimisasi independen dengan seed acak yang berbeda dan hitung hypervolume atau IGD untuk masing-masing. Laporkan median dan rentang interkuartil di seluruh putaran. Hypervolume yang konsisten di seluruh putaran menunjukkan bahwa optimizer telah secara andal konvergen ke front Pareto perkiraan yang sama.

Metode terkait

Sumber

  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.

    Buka referensi DOI
    Disalin.
  2. Macal, C. M., & North, M. J. (2010). Tutorial on agent-based modelling and simulation. Journal of Simulation, 4(3), 151-162.

    Buka referensi DOI
    Disalin.