Skip to content
Kembali ke hasil pencarian

Robust NSGA-II — Optimasi Multi-objektif di Bawah Ketidakpastian

Diperkenalkan oleh
Kalyanmoy Deb and Himanshu Gupta
Tahun
2006
Jenis
Robust evolutionary multi-objective optimization algorithm
Keluarga
Simulation / optimization

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

Ukuran huruf

Apa fungsinya?

Robust NSGA-II memperluas algoritma evolusioner klasik NSGA-II untuk memperhitungkan ketidakpastian parametrik, menemukan solusi trade-off Pareto-optimal yang tetap berkinerja tinggi bahkan ketika parameter masukan menyimpang dari nilai nominalnya.

Alih-alih mengoptimalkan nilai objektif pada satu titik, ia mengevaluasi setiap solusi kandidat di berbagai rentang atau distribusi realisasi ketidakpastian dan memilih ketahanan (robustness) bersama dengan dominasi Pareto.

Intuisi di balik metode

Dalam praktiknya, desain rekayasa dan keputusan kebijakan menghadapi kondisi operasi yang tidak pasti: sifat material bervariasi, perkiraan permintaan berbeda dari kenyataan, dan beban lingkungan berfluktuasi. Solusi yang tampak optimal pada nilai parameter nominal dapat berkinerja buruk di bawah penyimpangan yang masuk akal. Robust NSGA-II mengatasi hal ini dengan mengevaluasi setiap solusi kandidat tidak hanya pada titik desainnya tetapi di seluruh lingkungan atau sampel skenario yang tidak pasti, kemudian memperlakukan nilai harapan (expected value) dan varians (atau kinerja kasus terburuk) dari setiap objektif sebagai kriteria seleksi. Algoritma ini dengan demikian menukar sedikit penurunan kinerja nominal untuk peningkatan keandalan yang besar, menghasilkan front Pareto solusi yang kompetitif dan stabil di bawah ketidakpastian.

Sejarah

Robust NSGA-II muncul dari kerangka kerja optimasi multi-objektif tangguh yang diformalkan oleh Deb dan Gupta pada tahun 2006, yang memperkenalkan metrik ketahanan eksplisit ke dalam mekanisme seleksi NSGA-II. Algoritma NSGA-II dasar diterbitkan oleh Deb, Pratap, Agarwal, dan Meyarivan pada tahun 2002. Karya selanjutnya oleh para peneliti dalam desain rekayasa, riset operasi, dan sistem energi memperluas kerangka kerja ke masalah dengan kendala stokastik, jenis ketidakpastian campuran, dan evaluasi ketahanan berbantuan pengganti.

Kapan digunakan

Gunakan Robust NSGA-II ketika masalah multi-objektif melibatkan parameter yang tidak pasti (sifat material, permintaan, biaya, kondisi lingkungan) dan solusi harus tetap dapat diterima di berbagai penyimpangan yang masuk akal dari nilai nominal, bukan hanya pada satu titik desain. Ini sesuai untuk desain rekayasa, perencanaan rantai pasokan di bawah ketidakpastian permintaan, dan optimasi sistem energi dengan generasi stokastik. Hindari jika anggaran komputasi sangat ketat, karena mengevaluasi M sampel ketidakpastian per individu per generasi melipatgandakan biaya evaluasi fungsi sebesar M. Juga hindari jika ketidakpastian dapat diabaikan dibandingkan dengan variasi objektif, atau ketika hanya dua atau tiga evaluasi fungsi per kandidat yang layak — NSGA-II standar atau metode berbantuan pengganti (surrogate-assisted methods) lebih efisien.

Batasan dan pertimbangan

  • Biaya komputasi berskala dengan M (sampel ketidakpastian per evaluasi), membuatnya mahal ketika evaluasi objektif berbasis simulasi atau memakan waktu.
  • Pilihan metrik ketahanan (rata-rata, varians, kasus terburuk) secara signifikan memengaruhi solusi mana yang disukai, dan tidak ada pilihan yang secara universal benar.
  • Kinerja menurun untuk lebih dari tiga objektif karena alasan yang sama seperti NSGA-II standar — jarak keramaian kehilangan kekuatan diskriminatif di ruang objektif berdimensi tinggi.
  • Estimasi ketahanan yang andal membutuhkan M yang cukup besar, tetapi M kecil memperkenalkan noise stokastik yang dapat menyesatkan perkiraan front Pareto.
  • Tidak mudah diterapkan ketika himpunan ketidakpastian bersifat diskontinu atau ketika korelasi antar parameter yang tidak pasti kompleks dan sulit untuk diambil sampelnya.

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

Kelebihan

  • Menghasilkan solusi Pareto-optimal yang secara eksplisit diverifikasi berkinerja baik di bawah ketidakpastian, mengurangi risiko solusi yang menurun buruk dalam praktik.
  • Mewarisi pengurutan non-dominasi cepat dan elitisme NSGA-II, memastikan bahwa solusi yang secara tangguh tidak didominasi tidak pernah dibuang antar generasi.
  • Fleksibilitas dalam metrik ketahanan: nilai harapan, penalti varians, kasus terburuk, atau kendala probabilistik dapat diganti tergantung pada preferensi risiko.
  • Bekerja untuk ruang keputusan kontinu dan diskrit tanpa modifikasi pada mekanisme seleksi inti.
  • Memberikan pengambil keputusan serangkaian pilihan trade-off yang berbeda dalam keseimbangan multi-objektif dan tingkat ketahanan, mendukung artikulasi preferensi yang terinformasi.

Penerapan

  • Desain aerodinamis tangguh yang mengoptimalkan trade-off drag dan lift di bawah kondisi atmosfer yang bervariasi
  • Desain jaringan rantai pasokan yang menyeimbangkan biaya dan tingkat layanan di bawah permintaan pelanggan stokastik
  • Perencanaan sistem energi tangguh dengan generasi terbarukan dan profil beban yang tidak pasti
  • Optimasi struktural multi-objektif yang memperhitungkan toleransi manufaktur dan variabilitas beban
  • Optimasi portofolio di bawah ketidakpastian pasar dengan trade-off antara imbal hasil yang diharapkan dan varians
  • Manajemen sumber daya air yang mengoptimalkan alokasi dan keandalan di bawah skenario aliran masuk yang tidak pasti iklim

Cara kerjanya

Cara kerjanya

1

Hasilkan populasi awal P yang terdiri dari N solusi kandidat yang mengkodekan vektor variabel keputusan. Tentukan model ketidakpastian: tentukan parameter mana yang tidak pasti, distribusi probabilitas atau himpunan perturbasinya, dan metrik ketahanan yang akan digunakan (nilai harapan, varians, kasus terburuk, atau kombinasi berbobot). Evaluasi semua solusi dalam kondisi nominal untuk menetapkan kebugaran dasar.

2

Untuk setiap solusi kandidat x dalam populasi, ambil M realisasi ketidakpastian dari distribusi parameter yang ditentukan (atau urutkan lingkungan terstruktur). Evaluasi semua fungsi objektif di bawah setiap realisasi dan agregasikan hasil menjadi estimasi objektif yang tangguh. Agregasi umum: gunakan rata-rata sebagai estimasi ketahanan untuk kinerja yang diharapkan dan tambahkan penalti yang sebanding dengan standar deviasi untuk memperhitungkan varians, sehingga objektif tangguh menjadi f_robust(x) = mean[f(x, xi)] + lambda * std[f(x, xi)].

3

Terapkan pengurutan non-dominasi cepat (fast non-dominated sorting) pada populasi menggunakan estimasi objektif tangguh daripada nilai nominal. Tetapkan setiap solusi ke front non-dominasi F1, F2, dll. berdasarkan dominasi Pareto dari objektif tangguh. Solusi di F1 secara tangguh tidak didominasi: tidak ada solusi lain yang lebih baik pada semua objektif tangguh secara bersamaan.

4

Dalam setiap front non-dominasi, hitung jarak keramaian (crowding distance) untuk setiap solusi di sepanjang setiap sumbu objektif tangguh. Jarak keramaian mengukur seberapa terisolasi solusi dalam ruang objektif tangguh, mempromosikan penyebaran di seluruh front Pareto tangguh. Solusi dengan jarak keramaian yang besar menempati wilayah yang jarang penduduknya dan lebih disukai selama seleksi untuk menjaga keragaman.

5

Terapkan seleksi turnamen biner menggunakan operator perbandingan keramaian (crowded-comparison operator) pada front tangguh dan jarak keramaian. Hasilkan populasi anakan (offspring) Q berukuran N melalui operator persilangan (simulated binary crossover) dan mutasi (polynomial mutation). Evaluasi ulang solusi anakan menggunakan evaluasi ketahanan dengan M sampel ketidakpastian per individu. Langkah ini mendominasi waktu berjalan ketika M besar.

6

Gabungkan populasi induk P dan anakan Q ke dalam kumpulan gabungan 2N solusi. Urutkan ulang berdasarkan non-dominasi tangguh dan jarak keramaian. Pilih N individu terbaik untuk membentuk generasi berikutnya, mempertahankan elitisme. Hentikan ketika batas generasi maksimum tercapai, hypervolume stagnan, atau anggaran komputasi habis. Kembalikan front Pareto tangguh F1 terakhir.

Kesalahan umum

  • Menggunakan terlalu sedikit sampel ketidakpastian per evaluasi (M kurang dari 20-30) memperkenalkan noise evaluasi yang mendistorsi peringkat non-dominasi dan menghasilkan front Pareto tangguh yang tidak dapat diandalkan.
  • Menggabungkan ketahanan nilai objektif dengan ketahanan solusi optimal: solusi yang tangguh dalam ruang objektif mungkin masih memerlukan nilai variabel keputusan yang tepat yang sulit diimplementasikan.
  • Menerapkan jarak keramaian default NSGA-II dalam ruang objektif tangguh tanpa memeriksa apakah objektif tangguh berada pada skala yang sebanding; normalisasi objektif sebelum menghitung jarak.
  • Menjalankan satu replikasi dan memperlakukan hasilnya sebagai definitif; selalu jalankan beberapa replikasi independen dan laporkan statistik hypervolume untuk memperhitungkan variasi stokastik.
  • Memilih lambda (bobot penalti varians) secara ad hoc tanpa analisis sensitivitas; lambda yang dipilih secara implisit mengkodekan sikap risiko yang harus dibuat eksplisit dan dibenarkan.

Pertanyaan yang sering diajukan

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

NSGA-II standar mengevaluasi setiap solusi kandidat pada nilai parameter nominalnya dan menggunakan nilai objektif tersebut untuk dominasi Pareto. Robust NSGA-II mengevaluasi setiap solusi di M realisasi parameter yang tidak pasti, mengagregasikan hasil menjadi estimasi objektif tangguh (misalnya, rata-rata dan varians), dan menggunakan estimasi tersebut untuk peringkat dominasi. Ini meningkatkan biaya komputasi sebesar faktor M tetapi menghasilkan solusi yang tetap kompetitif ketika parameter menyimpang dari nilai nominal.

Berapa banyak sampel ketidakpastian M yang harus saya gunakan per individu?

Tidak ada aturan universal. Titik awal yang umum adalah M = 30 hingga 50 sampel Monte Carlo jika evaluasi objektif murah. Untuk evaluasi yang mahal, M = 5 hingga 10 mungkin diperlukan. Lakukan studi sensitivitas: tingkatkan M hingga estimasi objektif tangguh stabil. Pengambilan sampel kuasi-acak (Latin hypercube atau Sobol) mencapai cakupan yang lebih baik daripada pengambilan sampel acak murni untuk M yang sama.

Bisakah saya menggunakan Robust NSGA-II dengan lebih dari tiga objektif?

Algoritma dapat diterapkan, tetapi kinerjanya menurun karena alasan yang sama seperti NSGA-II standar: jarak keramaian kehilangan kekuatan diskriminatif di ruang objektif berdimensi tinggi, dan sebagian besar solusi berakhir di front non-dominasi pertama. Untuk empat objektif atau lebih, pertimbangkan varian tangguh dari NSGA-III, yang menggunakan seleksi berbasis titik referensi alih-alih jarak keramaian.

Metrik ketahanan apa yang harus saya pilih?

Pilihan tergantung pada sikap risiko. Optimasi hanya rata-rata menargetkan kinerja yang diharapkan tanpa menghukum variabilitas — cocok untuk keputusan berulang. Rata-rata ditambah varians menghukum ketidakstabilan dan cocok untuk konteks yang menghindari risiko. Optimasi kasus terburuk (minimax) sangat konservatif dan hanya sesuai jika satu realisasi katastropik tidak dapat diterima. Dokumentasikan dan benarkan pilihan, karena secara material memengaruhi solusi mana yang muncul di front Pareto tangguh.

Bagaimana cara memvalidasi bahwa solusi yang dikembalikan benar-benar tangguh?

Setelah algoritma berakhir, evaluasi ulang setiap solusi front Pareto dengan set sampel ketidakpastian baru yang besar (misalnya, M = 1000) yang independen dari sampel yang digunakan selama optimasi. Periksa apakah rata-rata dan varians objektif cocok dengan estimasi dari proses evolusioner. Perbedaan besar menunjukkan bahwa M terlalu kecil selama optimasi, atau bahwa model ketidakpastian salah ditentukan.

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. Deb, K., & Gupta, H. (2006). Introducing robustness in multi-objective optimization. Evolutionary Computation, 14(4), 463-494.

    Buka referensi DOI
    Disalin.