Stochastic Particle Swarm Optimization — Pencarian Global Berbasis Kawanan Stokastik
- Diperkenalkan oleh
- Kennedy, J. and Eberhart, R. (base PSO); stochastic extensions by Clerc, Kennedy and community
- Tahun
- 1995–2002
- Jenis
- Metaheuristic optimization — stochastic swarm intelligence
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Stochastic Particle Swarm Optimization (Stochastic PSO) adalah metaheuristik kecerdasan kawanan yang memperluas kerangka PSO standar dengan memasukkan elemen stokastik eksplisit — bobot inersia acak, reset kecepatan probabilistik, atau injeksi derau — untuk keluar dari optimum lokal dan mempertahankan keragaman populasi sepanjang pencarian.
Metode ini banyak diterapkan pada masalah optimasi kontinu, campuran, dan berderau dalam bidang teknik, riset operasi, dan desain berbasis simulasi.
Intuisi di balik metode
Bayangkan sekawanan burung mencari makanan di mana setiap burung mengingat lokasi terbaik pribadinya dan juga mengikuti tempat terbaik yang diketahui oleh kelompok. Dalam PSO standar, koefisien acak r1 dan r2 sudah menyuntikkan stokastisitas, tetapi Stochastic PSO secara sengaja memperkuat atau menstrukturkan keacakan ini — memvariasikan bobot inersia secara acak setiap iterasi, menambahkan derau Gaussian ke posisi, atau secara probabilistik mengatur ulang partikel yang stagnan — sehingga kawanan terus menjelajahi secara luas daripada konvergen prematur ke wilayah suboptimal.
Sejarah
Particle Swarm Optimization diperkenalkan oleh Kennedy dan Eberhart pada tahun 1995, terinspirasi oleh perilaku sosial kawanan burung dan gerombolan ikan. Clerc dan Kennedy (2002) memformalkan varian koefisien konstriksi dan menganalisis stabilitas, meletakkan dasar teoretis. Perluasan stokastik — bobot inersia acak, kecepatan yang diperkaya derau, reset probabilistik — muncul sepanjang akhir 1990-an dan 2000-an ketika para peneliti mengidentifikasi konvergensi prematur sebagai kelemahan praktis utama dari algoritma asli.
Kapan digunakan
Gunakan Stochastic PSO ketika lanskap pencarian bersifat multimodal, berderau, atau berdimensi tinggi dan PSO standar cenderung konvergen prematur. Metode ini sangat cocok untuk optimasi berbasis simulasi di mana fungsi objektif bersifat stokastik atau mahal untuk dievaluasi, dan untuk masalah desain teknik dengan banyak minimum lokal. Pilih metode ini daripada varian deterministik ketika pemeliharaan keragaman sangat penting. JANGAN gunakan jika masalah memiliki objektif cembung, unimodal dengan evaluasi yang murah — metode berbasis gradien atau eksak akan lebih cepat dan lebih presisi. Hindari juga jika reproduktibilitas setiap jalankan sangat penting tanpa kebijakan benih acak yang tetap, karena derau stokastik mempersulit replikasi yang tepat.
Batasan dan pertimbangan
- Sensitivitas hiperparameter: parameter derau dan distribusi bobot inersia sangat memengaruhi kecepatan konvergensi dan kualitas solusi.
- Tidak ada jaminan teoretis untuk menemukan optimum global dalam waktu terbatas untuk masalah non-cembung arbitrer.
- Inisialisasi ulang stokastik dapat membuang partikel yang menjanjikan, sesekali membuang evaluasi kebugaran.
- Kinerja menurun di ruang berdimensi sangat tinggi (kutukan dimensi) relatif terhadap metode spesifik masalah.
- Beberapa jalankan mungkin diperlukan untuk membangun kepercayaan pada kualitas solusi, meningkatkan total biaya komputasi.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Mempertahankan keragaman populasi melalui keacakan yang terkontrol, secara substansial mengurangi konvergensi prematur dibandingkan dengan PSO standar.
- Tidak memerlukan informasi gradien dan menangani fungsi objektif yang tidak mulus, diskontinu, atau kotak hitam.
- Mudah diparalelkan: setiap evaluasi partikel independen dalam satu iterasi.
- Fleksibel: tingkat stokastisitas (tingkat derau, distribusi inersia) dapat disesuaikan untuk menyeimbangkan eksplorasi dan eksploitasi.
- Secara alami menangani fungsi kebugaran stokastik atau berbasis simulasi di mana evaluasi membawa derau inheren.
- Konsepnya sederhana dengan beberapa hiperparameter (ukuran kawanan N, koefisien kognitif c1, sosial c2, dan parameter derau).
Penerapan
- Optimasi desain teknik: penyetelan bentuk aerodinamis, desain susunan antena, optimasi struktural di bawah ketidakpastian.
- Pelatihan jaringan saraf: optimasi bobot untuk jaringan feedforward dan rekuren pada kumpulan data berderau.
- Rantai pasokan dan penjadwalan: penjadwalan job-shop stokastik, optimasi inventaris di bawah ketidakpastian permintaan.
- Optimasi portofolio keuangan: memaksimalkan pengembalian yang disesuaikan risiko dengan model pasar stokastik.
- Optimasi berbasis simulasi: mengkalibrasi model berbasis agen atau dinamika sistem ke data empiris.
- Penyetelan hiperparameter untuk pipeline pembelajaran mesin di mana permukaan kerugian validasi berderau.
Cara kerjanya
Cara kerjanya
Inisialisasi kawanan N partikel dengan posisi x_i dan kecepatan v_i yang diambil secara acak seragam dalam ruang pencarian yang layak. Evaluasi fungsi objektif f(x_i) untuk setiap partikel dan tetapkan terbaik pribadi p_i = x_i dan terbaik global g = argmin f(x_i).
Perbarui kecepatan setiap partikel menggunakan aturan stokastik: v_i(t+1) = omega * v_i(t) + c1*r1*(p_i - x_i) + c2*r2*(g - x_i), di mana r1, r2 ~ Uniform(0,1) adalah pengambilan acak baru setiap iterasi. Dalam Stochastic PSO, omega itu sendiri dapat diambil dari distribusi (misalnya, Uniform(0.4, 0.9)) atau suku derau Gaussian epsilon ~ N(0, sigma^2) ditambahkan untuk mempertahankan keragaman.
Rumus
v_i(t+1) = \omega v_i(t) + c_1 r_1 (p_i - x_i(t)) + c_2 r_2 (g - x_i(t))
Pindahkan setiap partikel ke posisi kandidat barunya: x_i(t+1) = x_i(t) + v_i(t+1). Terapkan penanganan batas (refleksi, penjepitan, atau pembungkusan toroida) untuk menjaga partikel tetap dalam domain yang layak.
Rumus
x_i(t+1) = x_i(t) + v_i(t+1)
Terapkan mekanisme stokastik tambahan tergantung pada varian: (a) bobot inersia acak yang diambil setiap iterasi, (b) perturbasi Gaussian dari terbaik pribadi untuk keluar dari cekungan atraksi lokal, atau (c) inisialisasi ulang acak partikel yang laju peningkatannya jatuh di bawah ambang batas, memulihkan kapasitas eksplorasi.
Evaluasi f(x_i(t+1)) untuk semua partikel; perbarui terbaik pribadi dan terbaik global. Ulangi pembaruan kecepatan melalui pemeriksaan konvergensi untuk T iterasi atau sampai kriteria penghentian terpenuhi (misalnya, peningkatan kebugaran < epsilon selama K iterasi berturut-turut). Kembalikan terbaik global g sebagai solusi.
Kesalahan umum
- Menetapkan varians derau terlalu tinggi mengubah algoritma menjadi pencarian yang hampir acak; terlalu rendah tidak memberikan manfaat dibandingkan PSO standar — kalibrasi terlebih dahulu pada masalah validasi.
- Mengabaikan penanganan batas dalam langkah perturbasi stokastik dapat mendorong partikel keluar dari wilayah yang layak, menghasilkan solusi yang tidak valid atau tidak berarti.
- Membandingkan Stochastic PSO dengan baseline deterministik pada satu jalankan menyesatkan; selalu laporkan statistik (rata-rata, standar deviasi) dari beberapa jalankan independen.
- Menggunakan benih acak yang tetap di semua partikel menghilangkan manfaat keragaman — pastikan setiap partikel menggunakan aliran acak independen.
Pertanyaan yang sering diajukan
Bagaimana Stochastic PSO berbeda dari PSO standar?
PSO standar sudah menggunakan koefisien acak r1 dan r2 yang diambil secara seragam setiap iterasi. Stochastic PSO secara sengaja menstrukturkan atau memperkuat keacakan ini — misalnya dengan mengambil bobot inersia omega dari distribusi probabilitas setiap iterasi, menambahkan derau Gaussian ke posisi partikel, atau secara probabilistik menginisialisasi ulang partikel yang stagnan — untuk memberikan pemeliharaan keragaman yang lebih kuat.
Berapa banyak partikel yang harus saya gunakan?
Titik awal yang umum adalah 20–50 partikel untuk masalah hingga ~30 dimensi. Kawanan yang lebih besar (50–200) meningkatkan cakupan di ruang berdimensi tinggi atau sangat multimodal dengan biaya evaluasi fungsi yang lebih banyak per iterasi.
Bagaimana cara memilih varians derau untuk perturbasi stokastik?
Kalibrasi pada contoh representatif dari kelas masalah Anda. Heuristik praktis adalah menetapkan standar deviasi derau aditif sekitar 1–5% dari lebar ruang pencarian per dimensi, kemudian menyetel berdasarkan diagnostik konvergensi — metrik keragaman seharusnya tidak runtuh menjadi hampir nol sebelum anggaran habis.
Kapan saya harus memilih Stochastic PSO daripada Differential Evolution atau Algoritma Genetik?
Stochastic PSO cenderung konvergen lebih cepat pada masalah kontinu berdimensi rendah hingga menengah dan sangat mudah diimplementasikan. Differential Evolution dan Algoritma Genetik biasanya menangani struktur kombinatorial atau diskrit dengan lebih baik. Jika masalah Anda murni kontinu dan multimodal, Stochastic PSO adalah pilihan pertama yang kuat.
Apakah Stochastic PSO cocok untuk masalah multi-objektif?
Varian tujuan tunggal yang dijelaskan di sini tidak dirancang langsung untuk masalah multi-objektif. Untuk itu, gunakan Multi-Objective PSO (MOPSO) atau NSGA-II, yang mempertahankan arsip eksplisit solusi Pareto-non-dominan.
Metode terkait
Sumber
Kennedy, J., Eberhart, R. (1995). Particle swarm optimization. Proceedings of ICNN'95 - International Conference on Neural Networks, Vol. 4, pp. 1942-1948. IEEE.
Buka referensi DOIDisalin.Clerc, M., Kennedy, J. (2002). The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), 58-73.
Buka referensi DOIDisalin.