Particle Swarm Optimization

Particle Swarm Optimization (PSO) adalah sebuah teknik stochastic optimization berdasarkan populasi yang terinspirasi oleh perilaku sosial dari pergerakan burung atau ikan (bird flocking or fish schooling). Teknik PSO dikemukakan oleh Russell C. Eberhart dan James Kennedy di tahun 1995.

pso

Bersama dengan Ant Colony Optimization (ACO), PSO digolongkan ke dalam teknik metaheuristik optimasi swarm intelligence (SI) di mana prinsip sosio-psikologi yang mempengaruhi perilaku sosial makhluk hidup, diadopsi. Secara sederhana, sebuah sistem SI, yang diperkenalkan oleh Gerardo Beni dan Jing Wang di tahun 1989, terbentuk dari sebuah populasi yang terdiri dari individu-individu yang berinteraksi baik secara lokal satu sama lain maupun dengan lingkungan mereka dengan mengikuti aturan yang sangat sederhana [wikipedia]. Akibatnya, pengetahuan setiap individu berkembang optimal melalui interaksi sosial yang terjadi. Kemampuan berpikir bukan lagi menjadi sesuatu yang hanya bersifat pribadi melainkan juga interpersonal.

Karena itulah, orang melihat PSO, demikian pula ACO, bukan hanya sekedar sebuah alat optimasi tapi juga sebuah alat yang melambangkan sosiokognisi (sociocognition) dari makhluk hidup dan lingkungannya (artificial agents), yang berdasarkan pada prinsip sosio-psikologi.

Sebagai sebuah alat optimasi, PSO menawarkan suatu prosedur pencarian (search procedure) berdasarkan populasi yang di dalamnya individu-individu, yang disebut particles, mengubah posisi, atau state, mereka terhadap waktu. Mereka ‘terbang’ mengitari suatu ruang pencarian multi dimensi (multidimensional search space). Selama ‘penerbangan’ setiap individu menyesuaikan posisinya menurut pengalaman pribadinya, dan menurut pengalaman individu di sebelahnya, sehingga membentuk posisi terbaik yang sesuai untuk dirinya dan untuk individu di sebelahnya. Jadi, algoritma PSO menggabungkan metode-metode local search dengan metode-metode global search, yang menyeimbangkan antara eksplorasi dan eksploitasi.

PSO telah sukses diterapkan di dalam pelbagai bidang penelitian dan aplikasi, termasuk ‘pelatihan’ Artificial Neural Networks (ANN) dan permainan sudoku. Hal ini disebabkan karena PSO memberi hasil yang lebih baik melalui cara yang lebih cepat dan sederhana bila dibandingan dengan metode lain. Selain itu, PSO memiliki sedikit parameter untuk disesuaikan. Sehingga sebuah versi, dengan sedikit variasi, dapat bekerja dengan baik dalam banyak bentuk aplikasi, termasuk aplikasi yang spesifik dengan kebutuhan yang spesifik pula.

PSO vs GA

PSO memiliki banyak kemiripan dengan Genetic Algorithms (GA), di mana sistem diawali dengan suatu populasi yang terbentuk dari solusi-solusi acak (random solutions) kemudian sistem mencari optimalitas melalui pembaharuan generasi secara acak.

Namun demikian, PSO tidak memiliki evolution operators, seperti mutasi dan crossover (persilangan). Sebaliknya, potential solutions, yakni individu-individu, atau yang disebut sebagai particles, ‘terbang’ mengikuti individu-individu yang optimum saat ini (current optimum particles).

Setiap individu menyimpan jejak-jejak posisinya dalam problem space. Jejak-jejak posisi tersebut diartikan sebagai best solution, atau fitness dalam GA, yang diperolehnya sejauh ini. Nilainya, yakni fitness value, yang disebut pbest, juga turut disimpan. Selain pbest yang merupakan milik individu yang bersangkutan, turut disimpan pula nilai terbaik milik individu di sekitarnya (local best), yang disebut lbest. Jika suatu individu memperhitungkan semua individu di dalam populasi di mana dia berada sebagai individu di sekitarnya, maka nilai terbaik yang dimaksud adalah nilai terbaik umum (global best) dan disebut gbest. Selanjutnya, terjadi akselerasi antara lokasi pbest dan lokasi lbest dari setiap individu. Akselerasi ini diberi bobot berupa bilangan acak.

Dengan demikian, mekanisme berbagi informasi (information sharing mechanism) yang dimiliki PSO berbeda secara signifikan dengan yang dimiliki GA. Dalam GA, setiap individu, yang disebut chromosome, berbagi informasi satu sama lain, sehingga keseluruhan populasi bergerak sebagai sebuah kesatuan menuju optimalitas. Dalam PSO, hanya gbest, atau lbest, yang memberi informasi kepada yang lain. Ini adalah sebuah mekanisme berbagi informasi satu arah. Proses evolusi hanya mencari solusi yang terbaik. Dengan demikian, seluruh individu, yang disebut particle, bergerak konvergen secara cepat ke solusi terbaik.

PSO dan ANN

Sebagaimana diutarakan di atas, PSO dapat dipergunakan untuk ‘melatih’ suatu Artificial Neural Network (ANN), menggantikan teknik back-propagation learning yang umum dipakai, di mana ANN dilatih melalui kesalahan yang dihasilkan (back-propagation of errors). Teknik pelatihan ‘belajar dari kesalahan’ ini pertama kali dinyatakan oleh Paul Werbos di tahun 1974, kemudian disempurnakan oleh David E. RumelhartGeoffrey E. Hinton dan Ronald J. Williams, 12 tahun kemudian [wikipedia]. 

Dengan menggunakan PSO, ANN dapat ‘dilatih’ lebih cepat dengan hasil yang lebih baik pada sebagian besar kasus. PSO juga mampu menghindari beberapa problem yang dihadapi oleh GA dalam ‘melatih’ ANN.

 

Sumber :

http://www.cis.syr.edu/~mohan/pso/
http://www.swarmintelligence.org/
http://en.wikipedia.org/wiki/Particle_swarm_optimization/
 

10 comments on “Particle Swarm Optimization

  1. Ping-balik: Sudoku « Riset Operasi

  2. wah…thanks bgt atas pembahasannya… ini merupakan suatu metode yang lebih baik dari palmer, gupta, cds, ra ataupun neh.

    klu boleh tolong dengan penjelasan rumus-rumusnya. terutama bagian transposition…. velocity dan new position.
    bagaimana dengan discrete particle swarm optimization for permutation flowshop…

    thanks..

  3. @gangsal:
    Sama-sama. Senang rasanya bila tulisan yang dibuat dapat berguna bagi yang lain.
    Mengenai apakah suatu metode lebih baik dari metode yang lain, sangatlah subyektif sifatnya, karena sangat tergantung pada persoalan yang dihadapi. Itulah sifat yang berlaku di dunia Optimasi.
    Mengenai penjelasan yang diminta, akan segera dibuat tulisan mengenai hal itu. Hanya saja, mohon kesabaran yang amat sangat, karena semuanya terkendala pada waktu yang tersedia. Tapi akan diusahakan seoptimal (baca: secepat) mungkin.
    Kalau mau cepat, dan dapat berdiskusi dengan leluasa, silahkan bergabung ke grup diskusi OR-Opt. Cukup klik menu di sebelah kanan paling bawah. Semoga bermanfaat.

  4. apakah ada situs yang membahas pso secara basic dan detail? kalau ada mohon bantuannya mas karena saya tertarik dengan artikel pso

  5. wah artikel yang sangat mencerahkan …
    mo nyanya nih, klo menjalankan pso di matlab gmana ya…
    saya pernah mencoba mngunduh toolboxpso dr slah website referensi sodara
    namun saya bigung menggunakannya, gmana y biar bisa mengintegrasikan toolbox tsb dengan matlab..

    mungkin ada tutorial yang bisa di pelajari??

    terima kasih

  6. Ping-balik: Optimasi Lebah « Riset Operasi

  7. Ping-balik: Optimasi Lebah

  8. bagus bngt pembahasannya,makasi…boleh nanya gk.ada pembahasan detail tentang algoritma bee colony gk…mohon pencerahanny dong?

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 )

Gambar Twitter

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

Foto Facebook

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

Foto Google+

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

Connecting to %s