Skip to content
Kembali ke hasil pencarian

Algoritma Genetika Multi-Objektif (MOGA) — Pencarian Evolusioner untuk Solusi Pareto-Optimal

Diperkenalkan oleh
Schaffer, J. D. (early MOGA); Goldberg, D. E. (GA foundations)
Tahun
1984
Jenis
Population-based evolutionary optimizer
Keluarga
Simulation / optimization

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

Ukuran huruf

Apa fungsinya?

Algoritma Genetika Multi-Objektif (MOGA) adalah metode komputasi evolusioner yang mengembangkan populasi kandidat solusi menuju front Pareto-optimal, secara simultan mengoptimalkan dua atau lebih fungsi tujuan yang saling bertentangan.

Metode ini menghindari keruntuhan trade-off menjadi satu skor tunggal, melainkan menghasilkan serangkaian solusi non-dominan untuk dipilih oleh pengambil keputusan.

Intuisi di balik metode

Bayangkan membiakkan generasi berturut-turut dari desain kandidat, di mana hanya solusi yang tidak kalah secara jelas pada semua tujuan yang bertahan dan bereproduksi. Selama banyak generasi, populasi akan konvergen menuju batas trade-off terbaik yang mungkin — tidak ada solusi pada front Pareto ini yang dapat meningkatkan satu tujuan tanpa memperburuk tujuan lain. MOGA memanfaatkan operasi genetik — seleksi, persilangan (crossover), dan mutasi — untuk menjelajahi batas ini secara efisien, bahkan dalam ruang pencarian berdimensi tinggi, non-konveks, atau diskontinu di mana metode gradien klasik gagal.

Sejarah

Algoritma genetika multi-objektif muncul dari Vector Evaluated Genetic Algorithm (VEGA) Schaffer pada tahun 1984, GA pertama yang secara eksplisit menangani banyak tujuan. Buku teks Goldberg tahun 1989 memformalkan pemeringkatan berbasis Pareto sebagai strategi penetapan kebugaran yang berprinsip. Bidang ini matang dengan cepat dengan MOGA Fonseca dan Fleming (1993), NSGA Srinivas dan Deb (1994), dan NSGA-II yang monumental (Deb dkk., 2002), yang menjadi benchmark standar di bidang ini dan tetap menjadi algoritma multi-objektif evolusioner yang paling banyak dikutip.

Kapan digunakan

Gunakan MOGA ketika suatu masalah memiliki dua atau lebih tujuan yang saling bertentangan dan tidak ada solusi optimal tunggal — desain teknik, konfigurasi rantai pasokan, optimasi portofolio, dan perencanaan lingkungan adalah domain tipikal. Metode ini cocok untuk lanskap tujuan non-konveks, multimodal, atau kotak hitam (black-box) di mana metode berbasis gradien tidak dapat diterapkan. JANGAN gunakan jika tujuan tunggal yang terdefinisi dengan baik sudah cukup (gunakan GA standar atau pemrograman matematis sebagai gantinya), ketika evaluasi populasi secara komputasi memberatkan dan pengganti (surrogate) tidak tersedia, ketika tujuan dapat diagregasi secara sah oleh jumlah tertimbang (weighted sum) yang diketahui tanpa kehilangan informasi, atau ketika kumpulan layak yang kecil memungkinkan enumerasi menyeluruh.

Batasan dan pertimbangan

  • Biaya komputasi berskala dengan ukuran populasi dan jumlah evaluasi fungsi; setiap evaluasi simulasi kompleks bisa mahal.
  • Konvergensi ke front Pareto yang sebenarnya tidak dijamin — hasil adalah aproksimasi heuristik yang sensitif terhadap pilihan hyperparameter (ukuran populasi, laju persilangan, laju mutasi).
  • Kinerja menurun seiring bertambahnya jumlah tujuan melebihi tiga atau empat (optimasi banyak tujuan memerlukan algoritma khusus seperti NSGA-III atau MOEA/D).
  • Memerlukan penyesuaian operator genetik dan pemeliharaan keragaman yang cermat untuk menghindari konvergensi prematur atau cakupan front yang buruk.
  • Tidak menyediakan satu solusi yang direkomendasikan — pemilihan akhir dari front Pareto masih memerlukan penilaian nilai atau aturan keputusan sekunder.

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

Kelebihan

  • Menghasilkan serangkaian solusi Pareto-optimal yang beragam dalam satu kali jalan, memberikan pilihan trade-off eksplisit kepada pengambil keputusan daripada satu jawaban.
  • Bekerja pada lanskap tujuan non-konveks, diskontinu, dan multimodal tanpa memerlukan gradien atau struktur matematis spesifik masalah.
  • Secara inheren berbasis populasi, membuatnya mudah untuk diparalelkan di seluruh inti atau sistem terdistribusi.
  • Pengkodean yang fleksibel memungkinkan variabel kontinu, integer, string biner, dan permutasi dalam kerangka kerja yang sama.
  • Didukung dengan baik oleh pustaka perangkat lunak matang (DEAP, pymoo, jMetal) dan bukti benchmark selama puluhan tahun.

Penerapan

  • Optimasi desain teknik — secara simultan meminimalkan berat, biaya, dan tegangan pada komponen struktural.
  • Rantai pasokan dan logistik — menyeimbangkan biaya, waktu tunggu, dan emisi karbon di seluruh konfigurasi jaringan.
  • Kebijakan lingkungan dan energi — mengoptimalkan portofolio energi terbarukan untuk biaya, keandalan, dan emisi.
  • Desain proses farmasi dan kimia — memaksimalkan hasil dan kemurnian sambil meminimalkan waktu reaksi.
  • Penyetelan hyperparameter machine learning — menukar akurasi model dengan waktu pelatihan atau interpretasi.
  • Perencanaan kota dan transportasi — mengoptimalkan jaringan rute untuk cakupan, waktu tempuh, dan biaya infrastruktur.

Cara kerjanya

Cara kerjanya

1

Hasilkan populasi awal N kandidat solusi (kromosom) secara acak atau menggunakan heuristik domain, dengan mengkodekan setiap solusi sebagai vektor variabel keputusan. Definisikan k fungsi tujuan f1(x), f2(x), ..., fk(x) untuk diminimalkan atau dimaksimalkan secara simultan.

2

Evaluasi semua k fungsi tujuan untuk setiap individu dalam populasi. Kebugaran (fitness) mencerminkan kualitas solusi di seluruh tujuan dan keragaman cakupan di seluruh ruang tujuan.

3

Peringkat individu berdasarkan non-dominasi: solusi x mendominasi y jika setidaknya sama baiknya pada semua tujuan dan secara ketat lebih baik pada setidaknya satu tujuan. Identifikasi front non-dominan (kandidat front Pareto) dan berikan prioritas seleksi yang lebih tinggi kepada individu yang kurang dominan. Metrik keragaman seperti jarak kerumunan (crowding distance) mencegah pengelompokan di wilayah sempit pada front.

4

Terapkan seleksi (misalnya, seleksi turnamen) untuk mendukung individu berperingkat lebih tinggi, kemudian terapkan persilangan untuk menggabungkan pasangan induk dan mutasi untuk memperkenalkan variasi. Mekanisme elitisme mempertahankan solusi non-dominan terbaik yang ditemukan di seluruh generasi.

5

Ulangi evaluasi kebugaran, pemeringkatan, dan reproduksi untuk jumlah generasi yang telah ditentukan sebelumnya atau hingga kriteria konvergensi terpenuhi. Kumpulan non-dominan akhir mengaproksimasi front Pareto-optimal, menyajikan spektrum solusi trade-off optimal kepada pengambil keputusan.

Kesalahan umum

  • Memperlakukan semua solusi pada front Pareto sebagai sama validnya tanpa melibatkan pakar domain untuk membuat pemilihan trade-off akhir dapat menyebabkan pilihan yang sewenang-wenang atau kurang beralasan.
  • Menggunakan populasi yang terlalu kecil menghasilkan front yang jarang dan tidak representatif; populasi yang terlalu besar meningkatkan komputasi tanpa manfaat proporsional.
  • Mengabaikan penanganan kendala — solusi yang tidak layak harus dihukum atau diperbaiki secara eksplisit; kegagalan melakukannya mendistorsi pencarian ke arah wilayah yang tidak layak.
  • Menerapkan MOGA pada masalah dengan lebih dari empat tujuan tanpa beralih ke algoritma banyak tujuan menghasilkan front yang berantakan dan tidak informatif di mana hampir semua solusi adalah non-dominan.
  • Melaporkan hanya front Pareto akhir tanpa diagnostik konvergensi (hypervolume selama generasi) membuatnya tidak mungkin untuk menilai apakah algoritma benar-benar telah konvergen.

Pertanyaan yang sering diajukan

Bagaimana MOGA berbeda dari menjalankan GA satu tujuan dengan jumlah tertimbang dari tujuan?

Pendekatan jumlah tertimbang menggabungkan semua tujuan menjadi satu skalar menggunakan bobot yang telah ditentukan sebelumnya, menghasilkan satu solusi yang bergantung pada bobot tersebut. MOGA secara simultan menghasilkan seluruh front solusi non-dominan tanpa memerlukan spesifikasi bobot di muka, memungkinkan pengambil keputusan untuk memeriksa trade-off dan memilih setelahnya.

Apa itu front Pareto dan mengapa itu penting?

Front Pareto adalah himpunan solusi di mana peningkatan satu tujuan tunggal secara inheren memperburuk setidaknya satu tujuan lainnya. Ini mewakili gambaran lengkap dari trade-off yang dapat dicapai. Pengambil keputusan dapat memeriksa front ini untuk memahami berapa banyak satu tujuan harus dikorbankan untuk mendapatkan keuntungan pada tujuan lain.

Berapa banyak tujuan yang dapat ditangani MOGA secara efektif?

Varian MOGA standar seperti NSGA-II bekerja dengan baik untuk dua atau tiga tujuan. Di atas empat tujuan, proporsi solusi non-dominan tumbuh pesat (kutukan dimensionalitas dalam ruang tujuan), membuat front Pareto besar dan tekanan seleksi lemah. Algoritma banyak tujuan (NSGA-III, MOEA/D, IBEA) direkomendasikan untuk empat atau lebih tujuan.

Kriteria penghentian apa yang harus saya gunakan?

Kriteria umum meliputi jumlah evaluasi fungsi yang tetap, jumlah generasi maksimum, atau konvergensi indikator hypervolume — volume ruang tujuan yang didominasi oleh aproksimasi front Pareto saat ini — selama generasi berturut-turut. Memantau pertumbuhan hypervolume adalah pendekatan yang paling berprinsip.

Bisakah MOGA menangani kendala?

Ya, melalui teknik penanganan kendala: fungsi penalti yang menurunkan kebugaran solusi yang tidak layak, seleksi turnamen kelayakan (solusi yang layak selalu mengalahkan yang tidak layak dalam seleksi), atau operator perbaikan yang memproyeksikan solusi yang tidak layak kembali ke wilayah yang layak. Pilihan ini memengaruhi perilaku konvergensi dan harus dilakukan secara sengaja.

Metode terkait

Sumber

  1. Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.

    ISBN: 9780201157673
    Disalin.
  2. 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.