Optimasi Multi-Objektif Berbasis Agen — Pencarian evolusioner terdesentralisasi melintasi objektif yang bersaing
- Diperkenalkan oleh
- Bonabeau, Dorigo, Theraulaz; Coello Coello et al.
- Tahun
- 1990s–2000s
- Jenis
- Simulation-driven multi-objective search
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Optimasi multi-objektif berbasis agen (ABMOO) menanamkan agen otonom di dalam lingkungan simulasi dan mengembangkan perilaku atau parameternya untuk secara simultan mengoptimalkan dua atau lebih objektif yang saling bertentangan, menghasilkan kurva Pareto-efisien dari solusi daripada satu optimum.
Pendekatan ini cocok untuk sistem adaptif kompleks di mana objektif muncul dari interaksi tingkat mikro daripada persamaan bentuk tertutup.
Intuisi di balik metode
Alih-alih menulis satu fungsi objektif global, ABMOO membiarkan populasi agen yang berinteraksi menjelajahi ruang solusi melalui aturan lokal dan perilaku yang muncul. Setiap agen mewakili solusi kandidat atau pengambil keputusan; sistem dijalankan maju dalam simulasi, hasil diukur pada setiap objektif, dan mekanisme seleksi Pareto menjaga solusi yang tidak didominasi tetap hidup lintas generasi. Karena lanskap kebugaran dievaluasi melalui simulasi, ABMOO dapat menangani fungsi objektif non-linear, stokastik, dan bergantung lintasan yang menolak perlakuan analitis. Hasilnya adalah muka Pareto yang beragam yang menunjukkan struktur perdagangan penuh di antara tujuan yang bersaing.
Sejarah
Optimasi multi-objektif berbasis agen muncul pada akhir 1990-an dan awal 2000-an ketika para peneliti menggabungkan kerangka kerja pemodelan berbasis agen (NetLogo, Repast, MASON) dengan algoritma evolusioner multi-objektif. Karya fundamental oleh Bonabeau, Dorigo, dan Theraulaz tentang kecerdasan kawanan dan oleh Coello Coello et al. tentang optimasi evolusioner multi-objektif menetapkan dasar-dasar teoretis yang digabungkan dalam ABMOO. Pendekatan ini mendapatkan daya tarik dalam ilmu sistem kompleks, perencanaan perkotaan, dan manajemen ekologi sepanjang tahun 2000-an dan 2010-an.
Kapan digunakan
Gunakan ABMOO ketika perilaku sistem muncul dari interaksi agen dan tidak dapat ditangkap oleh persamaan bentuk tertutup, ketika dua atau lebih objektif bertentangan dan pengambil keputusan membutuhkan kurva perdagangan penuh, dan ketika stokastisitas atau ketergantungan lintasan membuat optimasi analitis tidak dapat dipecahkan. Ideal untuk desain kebijakan dalam sistem sosial, ekologis, atau rantai pasokan. Jangan gunakan ketika satu objektif sudah cukup, ketika pemecah berbasis gradien analitis yang cepat ada, ketika anggaran komputasi sangat terbatas (evaluasi simulasi mahal), atau ketika objektif dapat digabungkan menjadi utilitas skalar tanpa kehilangan wawasan.
Batasan dan pertimbangan
- Mahal secara komputasi: setiap evaluasi kebugaran memerlukan menjalankan simulasi berbasis agen penuh, mengalikan biaya dengan ukuran populasi dan jumlah generasi.
- Hasilnya stokastik; muka Pareto dapat bergeser antar putaran, memerlukan beberapa putaran independen dan agregasi statistik.
- Validitas model sangat bergantung pada realisme aturan agen dan lingkungan simulasi; masukan sampah menghasilkan muka Pareto yang menyesatkan.
- Penyetelan hyperparameter (ukuran populasi, tingkat persilangan, panjang simulasi) tidak sepele dan spesifik masalah.
- Menginterpretasikan dan bertindak berdasarkan muka Pareto berdimensi tinggi tetap menjadi tantangan tanpa alat pendukung keputusan tambahan.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menangani lanskap objektif non-linear, yang muncul, dan bergantung lintasan yang menolak formulasi bentuk tertutup.
- Menghasilkan muka Pareto penuh, memberikan pembuat keputusan visibilitas eksplisit tentang perdagangan daripada satu titik.
- Secara alami mengakomodasi stokastisitas dengan merata-ratakan replikasi simulasi dalam evaluasi kebugaran.
- Menskalakan ke populasi agen heterogen dengan aturan perilaku dan topologi interaksi yang beragam.
- Kompatibel dengan algoritma multi-objektif yang mapan (NSGA-II, MOEA/D, MOPSO) sebagai penggerak optimasi.
Penerapan
- Perencanaan lalu lintas perkotaan dan penggunaan lahan di mana perdagangan investasi infrastruktur (biaya vs. kemacetan vs. emisi) muncul dari keputusan agen penduduk.
- Optimasi ketahanan rantai pasokan menyeimbangkan biaya, waktu tunggu, dan risiko gangguan di antara agen pemasok yang terhubung jaringan.
- Manajemen ekologi menemukan kebijakan panen atau konservasi Pareto-optimal yang menyeimbangkan tujuan hasil ekonomi dan keanekaragaman hayati.
- Desain intervensi epidemi mengoptimalkan cakupan vaksinasi versus perdagangan aktivitas ekonomi melalui simulasi agen populasi.
- Manajemen jaringan energi mengoordinasikan agen prosumer untuk secara bersamaan meminimalkan biaya, emisi karbon, dan ketidakstabilan jaringan.
- Evaluasi kebijakan sosial mengidentifikasi kumpulan parameter kebijakan yang bersama-sama meningkatkan hasil ekuitas dan efisiensi dalam model sosial berbasis agen.
Cara kerjanya
Cara kerjanya
Uraikan m objektif f_1, ..., f_m (semuanya untuk diminimalkan atau dimaksimalkan) dan variabel keputusan yang dikodekan dalam genom atau kumpulan aturan setiap agen. Definisikan kendala dan lingkungan simulasi yang mengubah keputusan agen menjadi hasil yang dapat diamati.
Inisialisasi populasi N agen dengan genom acak atau yang diberi benih heuristik. Genom setiap agen mengkodekan parameter atau aturan perilaku yang akan disetel oleh optimasi lintas generasi.
Jalankan simulasi berbasis agen maju untuk T langkah waktu. Di akhir setiap putaran, baca nilai objektif f_1(x), ..., f_m(x) untuk setiap agen atau untuk sistem kolektif. Beberapa replikasi dapat dirata-ratakan untuk mengelola kebisingan stokastik.
Terapkan pengurutan non-dominasi: beri peringkat agen berdasarkan dominasi Pareto. Agen x mendominasi y jika x tidak lebih buruk pada semua objektif dan secara ketat lebih baik pada setidaknya satu. Pertahankan muka yang tidak didominasi (muka Pareto) dan gunakan jarak kerumunan atau kontribusi volume hiper untuk mempertahankan keragaman.
Terapkan operator genetik (persilangan, mutasi) atau pembaruan kecepatan gaya kawanan ke populasi yang bertahan. Agen kandidat baru mewarisi, menggabungkan, atau mengganggu genom anggota muka Pareto, kemudian masuk kembali ke simulasi untuk evaluasi.
Setelah kriteria penghentian (anggaran generasi, konvergensi volume hiper, atau batas waktu dinding) terpenuhi, kembalikan muka Pareto akhir sebagai kumpulan solusi. Visualisasikan perdagangan menggunakan plot sebar ruang objektif atau diagram koordinat paralel untuk interpretasi pengambil keputusan.
Kesalahan umum
- Menjalankan replikasi simulasi yang terlalu sedikit per evaluasi agen meningkatkan kebisingan dan merusak peringkat Pareto — selalu uji kecukupan replikasi terlebih dahulu.
- Konvergensi prematur ke wilayah muka Pareto yang tipis karena mekanisme keragaman yang tidak mencukupi; gunakan jarak kerumunan atau seleksi berbasis volume hiper secara eksplisit.
- Mencampur objektif optimasi dengan model simulasi itu sendiri; pastikan aturan agen mewakili sistem nyata, bukan hasil yang diinginkan.
- Mengabaikan batasan anggaran komputasi dan menentukan ukuran populasi atau jumlah generasi yang tidak layak untuk waktu berjalan simulasi.
- Menyajikan muka Pareto mentah kepada pengambil keputusan tanpa pemfilteran atau visualisasi pendukung keputusan, yang menyebabkan kelumpuhan analisis.
Pertanyaan yang sering diajukan
Bagaimana ABMOO berbeda dari algoritma genetik multi-objektif standar?
Dalam MOEA standar, kebugaran dihitung secara analitis atau melalui fungsi cepat. Dalam ABMOO, kebugaran dihitung dengan menjalankan simulasi berbasis agen penuh, membuat setiap evaluasi jauh lebih mahal tetapi memungkinkan lanskap objektif yang bergantung pada dinamika yang muncul, interaktif, dan stokastik.
Algoritma multi-objektif mana yang paling baik berfungsi sebagai pengoptimal dalam ABMOO?
NSGA-II adalah yang paling banyak digunakan karena pengurutan non-dominasi dan jarak kerumunannya. MOEA/D dan MOPSO juga umum. Pilihan tergantung pada bentuk dan dimensi muka Pareto; tidak ada pilihan terbaik universal — uji coba pada putaran kecil terlebih dahulu.
Berapa banyak replikasi simulasi yang harus saya jalankan per evaluasi agen?
Cukup untuk mengurangi kebisingan sehingga perbandingan dominasi Pareto andal. Heuristik umum adalah menjalankan sampai koefisien variasi setiap objektif turun di bawah 5–10%. Ini mungkin memerlukan 10–50 replikasi tergantung pada stokastisitas sistem.
Bisakah ABMOO menangani lebih dari dua objektif?
Ya, tetapi kinerja menurun seiring bertambahnya jumlah objektif (kutukan dimensi dalam dominasi Pareto). Di atas tiga objektif, pertimbangkan algoritma multi-objektif seperti NSGA-III atau MOEA/D, dan gunakan teknik visualisasi pengurangan dimensi untuk muka yang dihasilkan.
Kapan saya harus memilih optimasi kuat daripada ABMOO standar?
Ketika lingkungan simulasi itu sendiri tidak pasti (ketidakpastian parameter, ketidakpastian struktural), gunakan varian kuat yang mengevaluasi agen di bawah berbagai skenario lingkungan dan mengoptimalkan kinerja Pareto kasus terburuk atau yang diharapkan daripada muka deterministik tunggal.
Metode terkait
Sumber
Bonabeau, E., Dorigo, M., & Theraulaz, G. (2002). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press.
ISBN: 9780195131598Disalin.Coello Coello, C. A., Lamont, G. B., & Van Veldhuizen, D. A. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems (2nd ed.). Springer.
ISBN: 9780387332543Disalin.