Skip to content
Kembali ke hasil pencarian

Particle Swarm Optimization (PSO)

Tahun
1995
Jenis
Population-based metaheuristic / swarm intelligence

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

Ukuran huruf

Apa fungsinya?

Particle Swarm Optimization (PSO) adalah algoritma metaheuristik berbasis populasi yang diperkenalkan oleh Kennedy dan Eberhart pada tahun 1995, terinspirasi oleh pergerakan kolektif kawanan burung dan gerombolan ikan.

Setiap solusi kandidat — yang disebut partikel — bergerak melalui ruang pencarian dengan memperbarui kecepatan dan posisinya berdasarkan pengalaman terbaiknya sendiri dan pengalaman terbaik seluruh kawanan, memungkinkan konvergensi cepat pada masalah optimasi kontinu.

Intuisi di balik metode

Bayangkan sekawanan burung mencari sumber makanan terkaya di lapangan yang luas. Tidak ada burung tunggal yang memiliki peta, tetapi masing-masing mengingat tempat terbaik yang pernah dikunjunginya secara pribadi dan menyadari tempat terbaik yang ditemukan oleh burung terdekat mana pun. Setiap burung mengarahkan penerbangannya sebagian menuju lokasi terbaik yang diingatnya sendiri dan sebagian menuju yang terbaik dari seluruh kawanan, menyesuaikan kecepatan sesuai kebutuhan. Melalui banyak penyesuaian semacam itu, seluruh kawanan akan konvergen ke area terkaya. PSO bekerja persis seperti ini: setiap partikel adalah solusi kandidat, posisinya adalah solusi itu sendiri, dan kawanan secara kolektif menuju ke optimum dengan menggabungkan memori individu dan sosial.

Sejarah

PSO diperkenalkan oleh James Kennedy dan Russell Eberhart pada Konferensi Internasional IEEE tentang Jaringan Saraf Tiruan tahun 1995, mengambil inspirasi langsung dari model simulasi perilaku sosial pada kawanan burung dan gerombolan ikan. Makalah dasar tahun 1995 menetapkan persamaan pembaruan kecepatan dan posisi yang tetap menjadi inti algoritma. Pada tahun 1998, Shi dan Eberhart memperkenalkan parameter bobot inersia ke dalam pembaruan kecepatan, secara signifikan meningkatkan kontrol konvergensi dan menjadi modifikasi standar yang diadopsi oleh penelitian selanjutnya. PSO dengan cepat mendapatkan daya tarik sebagai alternatif praktis untuk algoritma genetik untuk optimasi kontinu, karena kesederhanaan dan kecepatan konvergensinya yang kompetitif, dan sejak itu telah diterapkan di berbagai bidang teknik, penyetelan hyperparameter machine learning, pemrosesan sinyal, dan pemodelan ilmiah.

Kapan digunakan

PSO cocok untuk masalah optimasi kontinu di mana fungsi kebugaran dapat dievaluasi di titik mana pun dalam ruang pencarian tetapi mungkin non-diferensiabel, multimodal, atau mahal untuk dihitung secara analitis. Metode ini tidak memerlukan asumsi normalitas dan tidak memerlukan ukuran sampel minimum, membuatnya dapat diterapkan di berbagai domain. Metode ini bekerja paling baik ketika batas ruang pencarian diketahui sebelumnya, ketika bobot inersia dan koefisien percepatan disetel dengan hati-hati, dan ketika jumlah iterasi yang cukup dialokasikan. Jika jumlah iterasi terlalu rendah (kurang dari beberapa ratus pada masalah non-trivial), konvergensi dini kemungkinan terjadi dan optimasi Bayesian mungkin merupakan alternatif yang lebih aman.

Batasan dan pertimbangan

  • Dirancang untuk ruang pencarian kontinu; tidak secara langsung berlaku untuk masalah diskrit atau kombinatorial tanpa modifikasi.
  • Konvergensi dini adalah risiko yang diketahui: kawanan dapat mengelompok di sekitar optimum lokal jika bobot inersia dan koefisien dipilih dengan buruk.
  • Kecepatan konvergensi dan kualitas solusi sensitif terhadap pilihan bobot inersia dan koefisien percepatan.
  • Tidak ada jaminan teoretis untuk menemukan optimum global dalam jumlah iterasi yang terbatas.

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

Kelebihan

  • Konvergensi cepat di ruang pencarian kontinu dibandingkan dengan banyak metode berbasis populasi.
  • Sangat sedikit parameter yang perlu disetel — terutama bobot inersia dan dua koefisien percepatan.
  • Tidak memerlukan informasi gradien atau turunan, membuatnya dapat diterapkan pada fungsi kebugaran non-diferensiabel dan kotak hitam.
  • Secara alami diskalakan ke masalah kontinu berdimensi tinggi.
  • Konsep sederhana dan mudah diimplementasikan.

Penerapan

  • Penyetelan hyperparameter untuk model machine learning pada ruang parameter kontinu.
  • Optimasi desain teknik — desain sistem struktural, aerodinamis, dan kelistrikan.
  • Pelatihan bobot jaringan saraf dan pencarian arsitektur.
  • Pemrosesan sinyal dan desain antena.
  • Economic dispatch (penyaluran beban secara ekonomis) dan optimasi sistem tenaga.
  • Estimasi parameter dalam model ilmiah dan simulasi.

Cara kerjanya

Cara kerjanya

1

Sebuah kawanan partikel ditempatkan pada posisi acak dalam ruang pencarian yang ditentukan, dan setiap partikel diberi kecepatan awal acak. Setiap partikel juga mencatat posisi terbaik pribadinya — solusi terbaik yang telah ditemuinya sejauh ini — dan kawanan melacak posisi terbaik global yang ditemukan oleh partikel mana pun. Bobot inersia, koefisien kognitif, dan koefisien sosial ditetapkan sebelum dijalankan, karena keseimbangan mereka secara langsung mengatur apakah kawanan menjelajahi secara luas atau mengeksploitasi wilayah yang sudah diketahui baik.

2

Fungsi kebugaran (fitness) dihitung untuk setiap partikel pada posisinya saat ini. Ini adalah satu-satunya langkah spesifik masalah: PSO tidak memberlakukan batasan pada bentuk fungsi kebugaran selain persyaratan bahwa fungsi tersebut dapat dievaluasi di titik mana pun dalam ruang pencarian kontinu. Posisi terbaik pribadi setiap partikel dan posisi terbaik global kawanan diperbarui setiap kali posisi baru menghasilkan nilai kebugaran yang lebih baik.

3

Kecepatan setiap partikel diperbarui menggunakan tiga komponen: suku inersia (kecepatan sebelumnya yang diskalakan, mempromosikan momentum), suku kognitif (daya tarik menuju posisi terbaik pribadi partikel itu sendiri), dan suku sosial (daya tarik menuju posisi terbaik global kawanan). Posisi baru kemudian dihitung dengan menambahkan kecepatan yang diperbarui ke posisi saat ini. Bobot inersia mengontrol keseimbangan antara eksplorasi dan eksploitasi: nilai yang lebih tinggi mendukung eksplorasi luas sementara nilai yang lebih rendah mempromosikan eksploitasi terperinci dari wilayah yang diketahui baik.

4

Langkah evaluasi dan pembaruan diulang untuk jumlah iterasi yang ditentukan. Kawanan secara progresif mempersempit pencariannya di sekitar wilayah yang paling menjanjikan. Eksekusi berakhir ketika batas iterasi tercapai, pada saat itu posisi terbaik global dilaporkan sebagai solusi. Jumlah iterasi yang cukup — biasanya setidaknya beberapa ratus hingga seribu untuk masalah non-trivial — diperlukan untuk memungkinkan kawanan konvergen; berhenti terlalu dini berisiko mengembalikan hasil suboptimal.

Kesalahan umum

  • Menjalankan terlalu sedikit iterasi — pada masalah non-trivial, iterasi yang tidak mencukupi mencegah kawanan konvergen; lebih memilih optimasi Bayesian ketika anggaran komputasi sangat ketat.
  • Memilih bobot inersia yang terlalu tinggi membuat partikel terus menjelajah dan menunda konvergensi; terlalu rendah menyebabkan pengelompokan dini di sekitar optimum lokal.
  • Mengabaikan batas ruang pencarian — partikel yang melayang di luar batas yang dimaksud menjelajahi wilayah yang tidak relevan dan mendistorsi optimum global.
  • Memperlakukan PSO sebagai cocok untuk masalah diskrit atau kombinatorial tanpa adaptasi — persamaan pembaruan kecepatan dan posisi standar mengasumsikan ruang bernilai riil.
  • Konvergensi dini tidak terdeteksi jika kemajuan kebugaran tidak dipantau di seluruh iterasi; selalu lacak kebugaran terbaik global versus jumlah iterasi.

Pertanyaan yang sering diajukan

Bagaimana PSO berbeda dari algoritma genetik?

Keduanya adalah metaheuristik berbasis populasi untuk optimasi, tetapi mereka berbeda dalam mekanisme. Algoritma genetik mengembangkan populasi melalui operator seleksi, persilangan, dan mutasi yang terinspirasi oleh evolusi biologis. Sebaliknya, PSO memindahkan partikel melalui ruang kontinu dengan memperbarui kecepatan berdasarkan memori pribadi dan sosial — tidak ada persilangan atau mutasi. PSO biasanya memiliki lebih sedikit parameter untuk disetel dan sering kali konvergen lebih cepat pada masalah kontinu, sementara algoritma genetik dapat diadaptasi lebih alami ke ruang diskrit atau kombinatorial.

Apa saja parameter kuncinya dan bagaimana cara menyetelnya?

Tiga parameter inti adalah bobot inersia (w), yang mengontrol berapa banyak kecepatan sebelumnya yang dipertahankan; koefisien kognitif (c1), yang menskalakan daya tarik menuju posisi terbaik pribadi partikel; dan koefisien sosial (c2), yang menskalakan daya tarik menuju posisi terbaik global. Titik awal yang umum dari literatur adalah w sekitar 0,7–0,9, c1 dan c2 sekitar 1,5–2,0. Bobot inersia sering kali diturunkan secara linier selama iterasi untuk menggeser kawanan dari eksplorasi di awal menuju eksploitasi di kemudian hari.

Bisakah PSO menangani masalah diskrit atau kombinatorial?

PSO standar didefinisikan untuk ruang pencarian kontinu dan menerapkan pembaruan kecepatan dan posisi yang mengasumsikan koordinat bernilai riil. Varian diskrit atau kombinatorial ada — seperti PSO biner — tetapi ini memerlukan modifikasi non-trivial pada persamaan pembaruan. Untuk masalah kombinatorial murni seperti routing atau penjadwalan, Optimasi Koloni Semut sering kali merupakan pilihan yang lebih alami.

Bagaimana saya tahu jika kawanan telah konvergen secara prematur?

Lacak nilai kebugaran terbaik global di seluruh iterasi. Jika kurva mendatar jauh sebelum anggaran iterasi habis dan solusi yang dilaporkan tidak memuaskan, konvergensi dini kemungkinan telah terjadi. Solusi umum termasuk meningkatkan bobot inersia, memulai ulang kawanan dari posisi acak baru, atau meningkatkan ukuran kawanan. Jika anggaran komputasi tidak memungkinkan lebih banyak iterasi, optimasi Bayesian mungkin merupakan alternatif yang lebih efisien.

Metode terkait

Sumber

  1. Kennedy, J. & Eberhart, R. (1995). Particle Swarm Optimization. IEEE International Conference on Neural Networks (ICNN), 1942-1948.

    Buka referensi DOI
    Disalin.
  2. Shi, Y. & Eberhart, R. (1998). A Modified Particle Swarm Optimizer. IEEE Congress on Evolutionary Computation (CEC).

    Buka referensi publikasi
    Disalin.