Optimasi Kawanan Partikel Multi-Objektif (MOPSO)
- Diperkenalkan oleh
- Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S.
- Tahun
- 2004
- Jenis
- Population-based swarm metaheuristic
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Optimasi Kawanan Partikel Multi-Objektif (MOPSO) adalah metaheuristik kecerdasan kawanan yang memperluas Optimasi Kawanan Partikel (PSO) asli untuk menangani beberapa fungsi tujuan yang saling bertentangan secara bersamaan.
Algoritma ini mempertahankan arsip Pareto eksternal dan menggunakan seleksi berbasis dominasi untuk memandu populasi solusi kandidat menuju front Pareto yang sebenarnya tanpa memerlukan informasi preferensi a priori.
Intuisi di balik metode
Bayangkan sekawanan burung secara kolektif mencari makanan di lanskap dengan beberapa bukit dengan ketinggian berbeda yang tidak semuanya dapat didaki sekaligus — mendapatkan ketinggian di satu bukit sering kali berarti kehilangan pijakan di bukit lain. MOPSO meluncurkan kawanan partikel melintasi ruang *trade-off* multidimensi ini. Setiap partikel mengingat posisi non-dominasi terbaiknya sendiri dan belajar dari arsip eksternal solusi non-dominasi terbaik global yang ditemukan sejauh ini. Dengan memadukan memori pribadi, pembelajaran sosial, dan keacakan yang terkontrol, kawanan secara progresif memetakan seluruh front Pareto, mengungkapkan spektrum penuh dari *trade-off* yang efisien daripada satu kompromi tunggal.
Sejarah
Optimasi Kawanan Partikel diperkenalkan oleh Kennedy dan Eberhart pada tahun 1995, terinspirasi oleh perilaku sosial kawanan burung. Perluasan multi-objektif pertama yang diadopsi secara luas, MOPSO, diusulkan oleh Coello Coello, Pulido, dan Lechuga pada tahun 2004, memperkenalkan arsip Pareto eksternal dan pemilihan pemimpin berbasis hiperkubus. Varian selanjutnya — termasuk OMOPSO, dMOPSO, dan SMPSO — menyempurnakan manajemen arsip, parameter adaptif, dan penanganan kendala, menjadikan MOPSO sebagai algoritma aproksimasi front Pareto arus utama bersama dengan NSGA-II.
Kapan digunakan
Gunakan MOPSO ketika Anda menghadapi masalah optimasi kontinu dengan dua atau lebih tujuan yang saling bertentangan dan perlu mengaproksimasi seluruh front Pareto daripada satu solusi tunggal. Algoritma ini unggul dalam desain teknik, rantai pasokan, sistem energi, dan penyetelan *hyperparameter* di mana evaluasi tujuan berbiaya sedang dan ruang keputusan bersifat kontinu. Pilih NSGA-II atau NSGA-III untuk masalah kombinatorial atau campuran-bilangan bulat, dan pilih metode multi-objektif berbasis gradien ketika tujuan mulus dan dapat diturunkan. Jangan gunakan MOPSO ketika jumlah tujuan melebihi lima hingga tujuh — masalah banyak-tujuan memerlukan algoritma khusus banyak-tujuan (misalnya, NSGA-III, MOEA/D). Hindari juga ketika setiap evaluasi fungsi sangat mahal (tersedia kurang dari 100 evaluasi) — metode berbantuan *surrogate* lebih disukai dalam rezim tersebut.
Batasan dan pertimbangan
- Kinerja sensitif terhadap bobot inersia (w) dan koefisien percepatan (c1, c2); parameter yang disetel dengan buruk menyebabkan konvergensi prematur atau penyimpangan yang berlebihan.
- Manajemen arsip dan pemilihan pemimpin memperkenalkan *hyperparameter* tambahan (ukuran arsip, metrik kepadatan) yang bergantung pada masalah.
- Jaminan konvergensi dan keragaman bersifat heuristik, bukan matematis — front Pareto yang diaproksimasi mungkin melewatkan wilayah front yang sebenarnya.
- Kesulitan menangani lebih dari lima hingga tujuh tujuan karena kutukan dimensi dalam seleksi berbasis dominasi.
- Tidak secara langsung berlaku untuk ruang pencarian diskrit atau kombinatorial tanpa adaptasi pengkodean dan pembatasan kecepatan spesifik masalah.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Secara alami mengaproksimasi seluruh front Pareto dalam satu kali jalan, memberikan pembuat keputusan serangkaian solusi *trade-off* yang efisien.
- Tidak memerlukan informasi gradien, membuatnya dapat diterapkan pada fungsi tujuan yang tidak dapat diturunkan, berisik, atau *black-box*.
- Mekanisme pembaruan kecepatan-posisi yang sederhana secara komputasi ringan dan mudah diimplementasikan secara paralel.
- Arsip Pareto eksternal mempertahankan solusi terbaik yang ditemukan sepanjang pencarian, mencegah hilangnya titik non-dominasi berkualitas tinggi.
- Kerangka kerja yang fleksibel mengakomodasi penanganan kendala, kontrol parameter adaptif, dan hibridisasi dengan pencarian lokal.
Penerapan
- Desain teknik multi-objektif: minimisasi simultan berat, biaya, dan tegangan pada komponen struktural dan mekanis.
- Sistem energi: *trade-off* Pareto-optimal antara biaya, keandalan, dan emisi dalam penjadwalan jaringan listrik dan perencanaan energi terbarukan.
- Manajemen rantai pasokan: optimasi gabungan tingkat layanan, biaya inventaris, dan waktu tunggu di seluruh jaringan multi-tingkat.
- Penyetelan *hyperparameter* pembelajaran mesin: menyeimbangkan akurasi model terhadap waktu inferensi atau jejak memori.
- Manajemen sumber daya air: mengoptimalkan kebijakan pelepasan waduk untuk tujuan bersaing pembangkit listrik, pengendalian banjir, dan aliran ekologis.
- Optimasi portofolio: mengaproksimasi *efficient frontier* dari imbal hasil yang diharapkan versus risiko untuk alokasi aset keuangan.
Cara kerjanya
Cara kerjanya
Hasilkan populasi N partikel dengan posisi dan kecepatan acak di ruang keputusan. Evaluasi semua fungsi tujuan untuk setiap partikel dan isi arsip Pareto eksternal dengan semua solusi awal non-dominasi. Tetapkan setiap partikel *personal best* (pbest) yang sama dengan posisi awalnya.
Hitung semua nilai fungsi tujuan untuk setiap partikel dalam kawanan saat ini. Terapkan perbandingan dominasi: solusi x mendominasi y jika x tidak lebih buruk pada semua tujuan dan secara ketat lebih baik pada setidaknya satu. Perbarui pbest setiap partikel jika posisi baru mendominasi *personal best* yang tersimpan, atau non-dominasi terhadapnya.
Masukkan semua solusi non-dominasi yang baru ke dalam arsip eksternal. Hapus anggota arsip yang sekarang didominasi oleh pendatang baru. Jika arsip melebihi batas kapasitasnya, terapkan strategi pemangkasan berbasis kepadatan (misalnya, *crowding* hiperkubus atau jarak tetangga terdekat) untuk mempertahankan keragaman di seluruh aproksimasi front Pareto.
Untuk setiap partikel, pilih pemimpin terbaik global (gbest) dari arsip eksternal. Pemimpin biasanya dipilih dari wilayah arsip yang kurang padat menggunakan mekanisme turnamen atau *roulette* berdasarkan jarak kepadatan (*crowding distance*), memastikan kawanan tertarik ke segmen front Pareto yang kurang dieksplorasi daripada konvergen secara prematur ke satu wilayah.
Perbarui kecepatan dan posisi untuk setiap partikel menggunakan aturan pembaruan PSO: v = w*v + c1*r1*(pbest - x) + c2*r2*(gbest - x), di mana w adalah bobot inersia yang mengontrol keseimbangan eksplorasi/eksploitasi, c1 dan c2 adalah koefisien percepatan kognitif dan sosial, dan r1, r2 adalah angka acak seragam. Terapkan penanganan batas untuk menjaga partikel tetap berada di ruang keputusan yang layak.
Rumus
v_{id}^{t+1} = w v_{id}^t + c_1 r_1 (pbest_{id} - x_{id}^t) + c_2 r_2 (gbest_d - x_{id}^t)Ulangi evaluasi–pembaruan-arsip–pemilihan-pemimpin–pergerakan-partikel hingga kriteria penghentian terpenuhi (iterasi maksimum, evaluasi fungsi maksimum, atau stagnasi front Pareto). Kembalikan arsip eksternal akhir sebagai himpunan Pareto-optimal yang diaproksimasi, yang kemudian diperiksa oleh pengambil keputusan untuk memilih solusi *trade-off* yang disukai.
Kesalahan umum
- Menetapkan kapasitas arsip terlalu kecil menyebabkan pemangkasan agresif yang menghancurkan keragaman front Pareto; terlalu besar memperlambat pemilihan pemimpin dan meningkatkan biaya memori.
- Menggunakan satu pemimpin global terbaik untuk seluruh kawanan menyebabkan konvergensi prematur; selalu gunakan mekanisme pemilihan pemimpin yang sadar keragaman (misalnya, turnamen jarak kepadatan).
- Mengabaikan penanganan batas memungkinkan partikel keluar dari wilayah yang layak, menghasilkan solusi yang tidak layak yang mencemari arsip.
- Melaporkan hanya arsip akhir tanpa metrik konvergensi dan keragaman (misalnya, indikator *hypervolume*, jarak generasi) membuat perbandingan hasil antar jalan atau metode menjadi tidak mungkin.
- Memperlakukan MOPSO sebagai pengoptimal *black-box* tanpa memvalidasi bahwa tujuan masalah tersebut benar-benar bertentangan — jika tujuan selaras, PSO tujuan tunggal standar atau penurunan gradien sudah cukup.
Pertanyaan yang sering diajukan
Bagaimana MOPSO berbeda dari NSGA-II?
Keduanya mengaproksimasi front Pareto menggunakan populasi solusi dan seleksi berbasis dominasi, tetapi berbeda dalam mekanismenya. NSGA-II menggunakan operator persilangan dan mutasi pada populasi induk-keturunan gabungan dengan pengurutan jarak kepadatan (*crowding distance*). MOPSO menggunakan pergerakan partikel berbasis kecepatan yang dipandu oleh pemimpin pribadi dan berbasis arsip. MOPSO biasanya lebih cepat per iterasi untuk ruang kontinu; NSGA-II lebih cocok secara alami untuk masalah permutasi dan kombinatorial.
Ukuran arsip berapa yang harus saya gunakan?
Ukuran umum adalah 100–200 solusi untuk masalah dua atau tiga tujuan. Arsip yang lebih besar meningkatkan cakupan front Pareto tetapi memperlambat pemilihan pemimpin. Untuk masalah dengan empat atau lebih tujuan, ukuran arsip harus diskalakan dengan kompleksitas yang diharapkan dari front Pareto; skema manajemen arsip adaptif dapat membantu.
Bisakah MOPSO menangani kendala?
Ya, melalui fungsi penalti, aturan kelayakan (lebih memilih solusi layak daripada yang tidak layak dalam perbandingan dominasi), atau operator perbaikan. Formulasi asli Coello Coello mencakup mekanisme penanganan kendala sederhana berdasarkan turnamen kelayakan.
Berapa banyak fungsi tujuan yang dapat ditangani MOPSO secara efektif?
MOPSO bekerja dengan baik untuk dua hingga empat tujuan. Di atas lima hingga tujuh tujuan, tekanan dominasi melemah secara drastis — hampir semua solusi menjadi saling non-dominasi — dan pengoptimal khusus banyak-tujuan (NSGA-III, MOEA/D, atau metode berbasis dekomposisi) mengungguli MOPSO standar.
Metrik apa yang harus saya gunakan untuk mengevaluasi hasil MOPSO?
Laporkan indikator *hypervolume* (mengukur volume ruang tujuan yang didominasi oleh front yang diaproksimasi — semakin tinggi semakin baik), jarak generasi (kedekatan dengan front Pareto referensi), dan metrik sebaran atau delta (keseragaman distribusi). Beberapa kali jalan independen dengan perbandingan statistik diperlukan untuk *benchmarking* yang kredibel.
Metode terkait
Sumber
Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8(3), 256–279.
Buka referensi DOIDisalin.Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks (ICNN), Perth, Australia, 4, 1942–1948.
Buka referensi DOIDisalin.