Skip to content
Kembali ke hasil pencarian

NSGA-II — Algoritma Genetika Penyortiran Non-dominasi II

Tahun
2002
Jenis
Evolutionary multi-objective optimisation algorithm

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

Ukuran huruf

Apa fungsinya?

NSGA-II (Algoritma Genetika Penyortiran Non-dominasi II) adalah algoritma referensi standar untuk optimasi evolusioner multi-objektif, yang diperkenalkan oleh Deb, Pratap, Agarwal, dan Meyarivan pada tahun 2002.

Alih-alih meruntuhkan berbagai objektif yang saling bertentangan menjadi satu skor tunggal, algoritma ini mengembangkan populasi solusi kandidat lintas generasi dan mengembalikan satu set solusi trade-off Pareto-optimal — front Pareto — menggunakan penyortiran non-dominasi cepat dan metrik jarak kerumunan untuk mempertahankan keragaman.

Intuisi di balik metode

Bayangkan Anda ingin merancang produk yang secara bersamaan semurah dan sedurable mungkin. Lebih murah biasanya berarti kurang tahan lama, jadi tidak ada satu jawaban sempurna — ada keluarga kompromi yang masuk akal. NSGA-II bekerja seperti populasi desain yang bersaing: setiap generasi, desain yang lebih lemah yang didominasi oleh yang lain pada setiap objektif dieliminasi, dan yang bertahan disebar sehingga mereka mencakup seluruh rentang trade-off daripada mengelompok di sekitar satu sudut. Setelah cukup generasi, Anda akan ditinggalkan dengan berbagai pilihan — front Pareto — dari mana Anda memilih keseimbangan yang sesuai dengan prioritas Anda.

Sejarah

NSGA-II diterbitkan oleh Kalyanmoy Deb dan rekan-rekannya di Indian Institute of Technology Kanpur pada tahun 2002 sebagai penerus yang diperbaiki dan ditingkatkan secara substansial dari NSGA asli (Srinivas & Deb, 1994). Inovasi utamanya adalah prosedur penyortiran non-dominasi cepat dengan kompleksitas O(MN²), operator jarak kerumunan eksplisit untuk mempertahankan keragaman solusi tanpa parameter berbagi, dan mekanisme seleksi elitis. Makalah IEEE Transactions on Evolutionary Computation tahun 2002 telah menjadi salah satu karya yang paling banyak dikutip dalam komputasi evolusioner dan menjadikan NSGA-II sebagai tolok ukur de facto untuk algoritma evolusioner multi-objektif. Varian selanjutnya — NSGA-III (2014) dan lainnya — memperluas kerangka kerja ke masalah multi-objektif.

Kapan digunakan

NSGA-II berlaku kapan pun sebuah masalah memiliki dua atau lebih fungsi objektif yang saling bertentangan yang tidak dapat digabungkan menjadi satu kriteria tanpa kehilangan informasi. Variabel keputusan dapat berupa kontinu, biner, atau kategorikal, dan tidak ada asumsi distribusi pada lanskap objektif yang diperlukan. Algoritma ini cocok untuk desain teknik, alokasi sumber daya, penjadwalan, dan masalah portofolio di mana spektrum solusi trade-off lebih berguna daripada satu optimum. Jumlah generasi yang cukup (biasanya beberapa ratus atau lebih) diperlukan untuk mencapai cakupan front yang baik; menjalankan terlalu sedikit generasi adalah mode kegagalan utama.

Batasan dan pertimbangan

  • Kinerja menurun seiring bertambahnya jumlah objektif melebihi tiga atau empat — jarak kerumunan menjadi ukuran keragaman yang buruk dalam dimensi tinggi.
  • Memerlukan penyesuaian hati-hati terhadap ukuran populasi dan jumlah generasi; terlalu sedikit generasi mencegah cakupan front yang memadai.
  • Mengevaluasi fungsi objektif yang melibatkan simulasi mahal membuat algoritma menjadi mahal secara komputasi.
  • Hasilnya stokastik: benih acak yang berbeda dapat menghasilkan front Pareto yang berbeda, sehingga disarankan beberapa kali jalan dan perbandingan statistik (misalnya, hypervolume).

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

Kelebihan

  • Menghasilkan set solusi trade-off Pareto-optimal yang beragam dalam satu kali jalan, menghindari kebutuhan untuk mengulang optimasi dengan bobot yang berbeda.
  • Penyortiran non-dominasi cepat berjalan dalam waktu O(MN²) (M objektif, N ukuran populasi), membuatnya dapat ditangani untuk ukuran masalah sedang.
  • Seleksi elitis memastikan bahwa solusi bagus yang ditemukan lebih awal tidak pernah dibuang.
  • Dapat diterapkan pada variabel keputusan kontinu, biner, dan kategorikal tanpa asumsi distribusi.
  • Divalidasi secara luas di domain teknik, riset operasi, dan ilmu komputasi.

Penerapan

  • Desain teknik: secara bersamaan meminimalkan berat dan memaksimalkan kekuatan struktural dalam komponen mekanis.
  • Sistem lingkungan dan energi: menyeimbangkan biaya, emisi, dan keandalan dalam perencanaan jaringan listrik atau energi terbarukan.
  • Layanan kesehatan dan riset operasi: penjadwalan yang mengoptimalkan waktu tunggu pasien, utilisasi sumber daya, dan biaya secara bersamaan.
  • Optimasi portofolio dalam keuangan dan pemilihan proyek dalam bisnis: menyeimbangkan imbal hasil, risiko, dan likuiditas.
  • Penyetelan hyperparameter dalam pembelajaran mesin: mengoptimalkan akurasi terhadap kompleksitas model atau waktu inferensi.

Cara kerjanya

Cara kerjanya

1

Sebuah populasi solusi kandidat dibuat dengan mengambil variabel keputusan secara acak (atau berdasarkan desain) dalam batas-batasnya. Ukuran populasi diatur cukup besar untuk memastikan keragaman di seluruh ruang objektif sejak awal.

2

Setiap solusi kandidat didekode menjadi nilai variabel keputusan dan setiap fungsi objektif dievaluasi. Hasilnya adalah vektor skor objektif per individu. Langkah ini seringkali menjadi hambatan komputasi ketika objektif melibatkan simulasi atau model yang mahal.

3

Solusi diurutkan berdasarkan penyortiran non-dominasi: front pertama berisi semua solusi yang tidak didominasi oleh solusi lain pada setiap objektif; front kedua berisi solusi yang hanya didominasi oleh yang ada di front pertama; dan seterusnya. Di dalam setiap front, skor jarak kerumunan dihitung untuk mengukur seberapa terisolasi sebuah solusi dari tetangganya — jarak kerumunan yang lebih tinggi berarti solusi menempati wilayah front yang kurang ramai.

4

Strategi seleksi elitis menggabungkan populasi saat ini dengan keturunan dan mempertahankan N individu terbaik, mengisi front secara berurutan dan menggunakan jarak kerumunan untuk memecah seri di dalam front terakhir yang diizinkan. Ini menjamin bahwa solusi bagus yang ditemukan di generasi sebelumnya tidak pernah hilang.

5

Individu yang dipilih bereproduksi melalui operator genetik — seleksi turnamen biner, persilangan biner simulasi (SBX), dan mutasi polinomial — menghasilkan populasi keturunan baru. Operator-operator ini mempertahankan variasi yang bermakna sambil menjelajahi lingkungan solusi yang menjanjikan.

6

Langkah-langkah dievaluasi melalui evolusi berulang untuk jumlah generasi yang ditentukan. Konvergensi dinilai dengan inspeksi visual front Pareto atau dengan pelacakan indikator hypervolume. Keluaran akhir adalah set solusi non-dominasi yang mendekati front Pareto yang sebenarnya.

Kesalahan umum

  • Menjalankan kurang dari beberapa ratus generasi biasanya menghasilkan front Pareto yang tidak lengkap; jika anggaran komputasi terbatas, pertimbangkan optimasi satu-objektif berbobot sebagai gantinya.
  • Memperlakukan masalah dengan satu objektif sebagai multi-objektif tidak perlu — gunakan pengoptimal satu-objektif.
  • Mengabaikan penetapan batas variabel yang masuk akal menyebabkan populasi yang tidak pernah mencapai wilayah ruang pencarian yang layak atau bermakna.
  • Melaporkan hanya satu solusi dari front Pareto tanpa mengungkapkan front lengkap menyembunyikan struktur trade-off yang dirancang NSGA-II untuk diungkap.

Pertanyaan yang sering diajukan

Berapa banyak generasi yang dibutuhkan NSGA-II?

Tidak ada aturan universal, tetapi menjalankan kurang dari beberapa ratus generasi biasanya menghasilkan front Pareto yang tidak lengkap. Pendekatan praktis adalah memplot indikator hypervolume di seluruh generasi dan berhenti ketika stabil. Jika anggaran komputasi mencegah hal ini, pengoptimal satu-objektif berbobot adalah alternatif yang lebih aman.

Apa itu front Pareto?

Front Pareto adalah himpunan solusi di mana tidak ada peningkatan pada satu objektif yang mungkin terjadi tanpa memperburuk setidaknya satu objektif lainnya. NSGA-II mendekati front ini, memberi Anda seluruh pilihan kompromi yang seimbang daripada satu jawaban.

Bisakah NSGA-II menangani lebih dari dua objektif?

Ya, tetapi jarak kerumunan — mekanisme keragaman — menjadi kurang efektif seiring bertambahnya jumlah objektif melebihi tiga atau empat (rezim 'multi-objektif'). Untuk masalah dengan lima atau lebih objektif, NSGA-III atau algoritma berbasis dekomposisi seperti MOEA/D umumnya lebih disukai.

Apakah NSGA-II deterministik?

Tidak. Operator genetik dan populasi awal melibatkan keacakan, sehingga jalan yang berbeda dengan benih acak yang berbeda dapat menghasilkan perkiraan front Pareto yang berbeda. Praktik terbaik adalah menjalankan algoritma beberapa kali dan membandingkan kualitas front menggunakan indikator hypervolume.

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. Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.

    Buka referensi DOI
    Disalin.