Skip to content
Kembali ke hasil pencarian

Stochastic NSGA-II — Optimasi Multi-Objektif Evolusioner di Bawah Ketidakpastian

Diperkenalkan oleh
Deb, K. et al. (NSGA-II base); Hughes, E. J. and subsequent researchers for stochastic extensions
Tahun
2001–2002
Jenis
Evolutionary multi-objective optimization under uncertainty
Keluarga
Simulation / optimization

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

Ukuran huruf

Apa fungsinya?

Stochastic NSGA-II memperluas algoritma evolusioner NSGA-II untuk menangani fungsi tujuan yang berisik, tidak pasti, atau probabilistik.

Dengan merata-ratakan atau mengambil sampel tujuan stokastik di berbagai evaluasi, ia mengidentifikasi solusi Pareto-optimal yang kuat terhadap ketidakpastian, membuatnya cocok untuk masalah optimasi desain teknik, rantai pasokan, dan kebijakan di mana variabilitas dunia nyata penting.

Intuisi di balik metode

NSGA-II adalah salah satu algoritma paling efektif untuk menemukan kumpulan solusi trade-off Pareto-optimal yang beragam dalam masalah multi-objektif. Namun, versi standar mengasumsikan evaluasi tujuan yang deterministik. Dalam praktiknya, simulasi, eksperimen, dan sistem nyata sering kali menghasilkan keluaran yang berisik. Stochastic NSGA-II mengatasi hal ini dengan mengambil sampel ulang atau memperkirakan secara statistik kebugaran sejati setiap solusi, kemudian menerapkan pengurutan non-dominasi cepat dan seleksi jarak keramaian NSGA-II untuk menavigasi muka Pareto secara andal meskipun ada kebisingan. Wawasan kuncinya adalah bahwa pemeringkatan solusi berdasarkan kinerja yang diharapkan — atau berdasarkan probabilitas dominasinya — memulihkan struktur Pareto yang benar bahkan ketika evaluasi individu tidak dapat diandalkan.

Sejarah

NSGA-II diperkenalkan oleh Deb et al. pada tahun 2002 sebagai algoritma genetik multi-objektif yang cepat dan elitis dan dengan cepat menjadi standar tolok ukur. Perluasan stokastik muncul tak lama setelahnya, didorong oleh komunitas optimasi teknik yang perlu menangani kebisingan simulasi. Hughes (2001) memformalkan pemeringkatan multi-objektif di bawah ketidakpastian. Sejak pertengahan tahun 2000-an, banyak varian telah muncul yang mencakup pengambilan sampel adaptif, probabilitas dominasi, dan peningkatan hypervolume yang diharapkan di bawah kebisingan.

Kapan digunakan

Gunakan Stochastic NSGA-II ketika Anda menghadapi masalah optimasi multi-objektif di mana tujuan dievaluasi melalui simulasi, eksperimen, atau sensor yang berisik dan Anda memerlukan solusi yang tetap baik di seluruh rentang ketidakpastian — bukan hanya rata-rata. Ini sangat cocok untuk desain teknik di bawah toleransi manufaktur, optimasi rantai pasokan dengan ketidakpastian permintaan, dan model lingkungan atau kebijakan dengan masukan stokastik. JANGAN gunakan ketika tujuan deterministik dan murah untuk dievaluasi (NSGA-II standar sudah cukup), ketika jumlah replikat yang diperlukan untuk perkiraan yang andal membuat anggaran total tidak mungkin, atau ketika masalahnya adalah satu-objektif (gunakan EA satu-objektif stokastik sebagai gantinya). Hindari ketika distribusi kebisingan sangat tidak stasioner atau terstruktur sedemikian rupa yang melanggar asumsi pengambilan sampel i.i.d.

Batasan dan pertimbangan

  • Biaya komputasi berskala dengan jumlah replikat r per evaluasi, dikalikan dengan ukuran populasi dan generasi — dapat menjadi mahal untuk simulasi yang mahal.
  • Memilih jumlah replikat r yang tepat tidak mudah: terlalu sedikit menimbulkan kesalahan peringkat, terlalu banyak membuang anggaran.
  • Tidak ada jaminan konvergensi formal ke muka Pareto stokastik yang sebenarnya; kualitas tergantung pada anggaran dan tingkat kebisingan.
  • Perbandingan dominasi menggunakan rata-rata perkiraan mengabaikan ketidakpastian perkiraan, yang dapat menyebabkan kesalahan peringkat di bawah kebisingan tinggi.

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

Kelebihan

  • Mewarisi penemuan muka Pareto yang kuat dan pelestarian keragaman NSGA-II melalui pengurutan non-dominasi dan jarak keramaian.
  • Secara eksplisit memperhitungkan kebisingan fungsi tujuan, menghasilkan solusi yang kuat dan andal dalam penerapan dunia nyata.
  • Kerangka kerja yang fleksibel — perkiraan stokastik dapat menggunakan perataan, ketahanan berbasis kuantil, atau probabilitas dominasi tanpa mengubah algoritma inti.
  • Dapat diterapkan pada model simulasi kotak hitam di mana informasi gradien tidak tersedia.
  • Menghasilkan muka Pareto penuh daripada satu solusi, memberikan pilihan trade-off eksplisit kepada pengambil keputusan.

Penerapan

  • Desain teknik yang kuat: mengoptimalkan komponen struktural atau mekanis di bawah toleransi manufaktur dan variabilitas beban.
  • Desain jaringan rantai pasokan: meminimalkan biaya dan waktu tunggu ketika kuantitas permintaan dan pasokan bersifat stokastik.
  • Pemodelan kebijakan lingkungan: menemukan strategi pengurangan emisi Pareto-optimal ketika model dampak iklim memiliki parameter yang tidak pasti.
  • Optimasi portofolio: menyeimbangkan pengembalian yang diharapkan dan risiko ketika pengembalian aset mengikuti proses stokastik.
  • Alokasi sumber daya perawatan kesehatan: mengoptimalkan biaya dan hasil pasien di bawah tingkat kedatangan pasien yang tidak pasti dan kemanjuran pengobatan.
  • Perencanaan sistem energi: menentukan ukuran instalasi energi terbarukan di bawah profil generasi angin dan surya yang stokastik.

Cara kerjanya

Cara kerjanya

1

Definisikan masalah optimasi multi-objektif dengan k fungsi tujuan stokastik f_1(x,xi), ..., f_k(x,xi), di mana xi mewakili parameter acak yang ditarik dari distribusi yang diketahui atau diperkirakan. Tentukan batas variabel keputusan, kendala, dan jumlah evaluasi berulang (replikat) r yang digunakan untuk memperkirakan nilai rata-rata setiap tujuan.

2

Inisialisasi populasi N solusi kandidat secara acak dalam ruang keputusan yang layak. Untuk setiap individu, alokasikan vektor perkiraan kebugaran sepanjang k, diinisialisasi ke nol. Atur penghitung generasi g = 0 dan tentukan kriteria penghentian (generasi maksimum G_max atau toleransi konvergensi).

3

Untuk setiap individu x_i dalam populasi, evaluasi setiap tujuan f_j(x_i, xi) tepat r kali dengan mengambil sampel xi dari distribusinya (atau menjalankan r replikat simulasi). Perkirakan tujuan sebenarnya sebagai rata-rata sampel: f_j_hat(x_i) = (1/r) * sum_{l=1}^{r} f_j(x_i, xi_l). Secara opsional hitung kesalahan standar untuk menginformasikan strategi pengambilan sampel adaptif.

4

Terapkan pengurutan non-dominasi cepat ke vektor tujuan yang diperkirakan. Solusi x_a mendominasi x_b jika f_j_hat(x_a) <= f_j_hat(x_b) untuk semua j dan secara ketat kurang untuk setidaknya satu j. Tetapkan setiap solusi ke peringkat muka Pareto F_1, F_2, ... di mana F_1 berisi solusi yang tidak didominasi oleh yang lain.

5

Pilih induk menggunakan seleksi turnamen biner berdasarkan peringkat Pareto dan jarak keramaian (untuk melestarikan keragaman). Terapkan operator genetik — persilangan biner simulasi (SBX) dan mutasi polinomial — untuk menghasilkan populasi keturunan Q berukuran N. Gabungkan populasi induk dan keturunan (ukuran 2N), evaluasi ulang tujuan stokastik, urutkan ulang, dan pilih N solusi teratas berdasarkan peringkat lalu jarak keramaian.

6

Tingkatkan g. Jika g < G_max dan muka Pareto belum stabil, ulangi dari langkah evaluasi stokastik. Jika tidak, kembalikan muka Pareto F_1 akhir sebagai kumpulan solusi kuat yang tidak didominasi. Laporkan muka Pareto perkiraan dalam ruang tujuan untuk pemilihan pengambil keputusan.

Kesalahan umum

  • Menggunakan satu replikat (r=1) per individu memperlakukan kebisingan sebagai sinyal, yang mengarah ke muka Pareto yang sangat tidak stabil di berbagai jalankan — selalu gunakan r >= 3 sebagai minimum dan validasi konvergensi.
  • Mengabaikan varians tujuan stokastik dapat memilih solusi yang terlihat bagus rata-rata tetapi berkinerja buruk dalam skenario ekor — pertimbangkan formulasi tujuan berbasis kuantil atau kasus terburuk ketika risiko ekor penting.
  • Menerapkan metode tanpa memeriksa apakah kebisingan stasioner: jika sifat kebisingan berubah dengan nilai variabel keputusan, pengambilan sampel adaptif atau model heteroskedastik diperlukan.
  • Memperlakukan muka Pareto keluaran sebagai keputusan akhir tanpa menilai ketahanan di luar sampel — selalu validasi solusi yang direkomendasikan dengan menjalankan simulasi yang ditahan.

Pertanyaan yang sering diajukan

Berapa banyak replikat r yang harus saya gunakan per evaluasi individu?

Titik awal yang umum adalah r = 5–30, tergantung pada koefisien variasi tujuan. Strategi adaptif yang mengalokasikan lebih banyak replikat ke solusi elit atau menggunakan pengambilan sampel sekuensial sampai kriteria kepercayaan terpenuhi lebih efisien. Untuk simulasi yang mahal, r = 3–5 dengan populasi besar sering kali merupakan kompromi praktis.

Bagaimana Stochastic NSGA-II berbeda dari NSGA-II standar?

Satu-satunya perbedaan struktural adalah dalam evaluasi tujuan: NSGA-II standar mengevaluasi f(x) sekali dan mengasumsikan hasilnya tepat, sedangkan Stochastic NSGA-II mengevaluasi f(x, xi) r kali dan menggunakan rata-rata sampel (atau statistik ketahanan lainnya) sebagai tujuan efektif. Semua mekanisme pengurutan, seleksi, dan operator genetik tetap identik.

Bisakah saya menggunakan Stochastic NSGA-II dengan probabilitas dominasi alih-alih rata-rata tujuan?

Ya. Pendekatan probabilitas dominasi menggantikan perbandingan dominasi deterministik dengan probabilitas dominasi stokastik, yang lebih prinsipil di bawah kebisingan tinggi. Ini membutuhkan lebih banyak sampel per perbandingan tetapi menghasilkan peringkat yang lebih andal ketika kebisingan besar relatif terhadap perbedaan tujuan.

Bagaimana jika simulasi saya terlalu mahal untuk beberapa replikat?

Pertimbangkan pendekatan berbantuan pengganti (surrogate-assisted): bangun metamodel proses Gaussian atau jaringan saraf dari fungsi tujuan, gunakan untuk memperkirakan rata-rata dan varians secara murah, dan terapkan kriteria peningkatan yang diharapkan atau probabilitas peningkatan sebagai pengganti evaluasi langsung berulang.

Apakah Stochastic NSGA-II dijamin menemukan muka Pareto stokastik yang sebenarnya?

Tidak. Seperti semua algoritma evolusioner, ini adalah heuristik tanpa jaminan konvergensi waktu terbatas ke muka yang sebenarnya. Panduan praktis: jalankan beberapa uji coba independen, bandingkan muka yang dihasilkan menggunakan indikator hypervolume, dan tingkatkan ukuran populasi atau generasi jika muka berbeda secara substansial antar jalankan.

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. Hughes, E. J. (2001). Evolutionary multi-objective ranking with uncertainty and noise. In Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization (EMO 2001), Lecture Notes in Computer Science, vol. 1993, pp. 329–343. Springer.

    Buka referensi DOI
    Disalin.