Particle Swarm Optimization (PSO)

PSO jika diterjemahkan berarti optimasi segerombolan partikel. Partikel di sini adalah makhluk hidup seperti burung, ikan, atau lebah yang sedang mencari makanan. Mengapa mengikuti prinsip pergerakan segerombolah makhluk-makhluk tersebut? Jawabannya sederhana, karena makhluk-makhluk tersebut berhasil menemukan makanannya. PSO pertama kali dicetuskan oleh kennedy dan Eberhart pada tahun 1995 yang membahas mengenai perilaku kerumunan makhluk hidup.

Menurut beberapa paper, misalnya Sathya, yang melakukan optimasi terhadap segmentasi gambar, PSO memiliki beberapa kelebihan di antaranya:

  • Mudah diimplementasikan dan hanya sedikit parameter yang dibutuhkan.
  • Tidak ada evolusi pada operatornya, misalnya mutasi dan crossover pada Genetic Algorithms (GAs).
  • Di GAs kromosom membagi informasi sehingga pergerakan mengikuti group-nya sendiri, berbeda dengan PSO yang berkelompak, dan menurut Sathya PSO lebih robust. Sepertinya saya kurang setuju dengan pendapat yang ini, apa boleh buat kita rujuk saja.
  • PSO lebih efisien karena membutuhkan sedikit komputasi.
  • Dibanding GAs dan metode heuristik lainnya, PSO lebih fleksibel dalam menjaga keseimbangan antara pencarian global dan lokal terhadap search space-nya.

Salah satu point menarik yang dibahas oleh kennedi et al. adalah masalah collision karena jika setiap partikel menganggap ada partikel lain yang lebih “optimum” tentu saja dia akan mengarah ke sana dan terjadi tuburukan/collision. Tetapi kenyataannya tidak ada tabrakan saat burung terbang, ikan berenang, lebah menari-nari dan sebagainya.

Untuk menerapkan algoritma PSO, di sini kita coba dengan menggunakan matlab atau octave. Kita coba terlebih dahulu dengan matlab. Sebagai referensi, Anda dapat mendownload materi budi santoso dari ITS di link berikut, kemudian coba jalankan kode yang ada di dalamnya. Di sana dijelaskan dua jenis PSO dengan dan tanpa inersia. Agar lebih mudah memahami alur instruksi programnya, di bawah instruksi yang akan saya selidiki biasanya saya sisipkan instruksi pause dan titik kemo di belakang kode yang dibuat saya hilangkan titik koma-nya agar muncul di layar command window. Saya coba jalankan dengan jumlah partikel 3 dan iterasi maksimum 4.

Variabel v,x,f yang menyatakan nilai awal kecepatan, swarm, dan nilai fitness-nya dimunculkan dalam variabel yang saya lingkari di atas. Untuk menampilkan nilai minimum minftot saya hapus titik komanya agar muncul di command window ketika berhenti sejenak di tiap iterasi karena instruksi pause yang saya sisipkan. Hasilnya tampak di bawah ini dimana fitness yang terbaik adalah pada swarm ketiga (34.8627) dengan swarm 105.9045. Ini tentu saja masih belum optimal karena masih iterasi pertama.

Setelah iterasi keempat dijalankan dengan menekan sembarang tombol untuk melanjutkan akibat instruksi pause tersebut diperoleh grafik dan hasil akhir. Kita coba dengan octave, di tulisan selanjutnya

Iklan

7 respons untuk ‘Particle Swarm Optimization (PSO)

  1. Pak, apakah bapak punya referensi perhitungan manual PSO untuk feature selection? Karena saya masih bingung PSO untuk feature selection. Terima kasih.

    • kasusnya harus yg bervariabel banyak, trus dipilih variabel-variabel yg paling mencirikan suatu fitur. Maksudnya supaya variabel sesedikit mungkin tapi tidak membuat fitur melenceng jauh dari yang sesungguhnya. Dengan variabel yg sedikit diharapkan proses learning lebih cepat. Nah peran PSO untuk mencari variabel2 itu sambil dihitung performanya (kecocokan dengan yang asli /semirip mungkin)

      • Pak, saya masih bingung menentukan fungsi fitness nya bagaimana ya? Kalo pada case seleksi fitur untuk klasifikasi citra fungsi fitness nya kira-kira apa ya pak ?

      • inti dari optimasi ya meramu fitnes. minimumkan variabel fitur, dan maksimumkan similarity dengan citra real-nya (bisa dengan euclidean)

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s