3 April 2008

Paticle Swarm Optimisation


Particle Swarm Optimisation (PSO) merupakan sebuah teknik optimasi yang dibangun oleh Dr. Eberhart dan Dr. Kennedy pada tahun 1995, yang terinspirasi dari perilaku sosial sekawanan burung atau ikan. Misalkan terdapat sekawanan ikan yang secara acak mencari makanan pada suatu wilayah dan hanya terdapat satu makanan disana. Semua burung tidak tahu dimana letak makanan tersebut, tetapi mereka tahu seberapa jauh mereka dari makanan dalam setiap iterasi. Jadi strategi yang paling efektif adalah mengikuti ikan yang paling dekat dengan makanan.

PSO diinisialisasi dengan sebuah populasi dari solusi-solusi acak dan mencari solusi yang paling optimal dengan membaharui anggota populasi. Setiap solusi acak tersebut disebut particle. Setiap particle bergerak dalam ruang masalah dan memiliki nilai terbaik yang telah dicapai, nilai ini disebut pbest. Nilai “terbaik” lainnya adalah nilai terbaik yang dicapai oleh particle manapun dalam populasi, nilai ini disebut gbest. PSO memiliki velocity yang akan mengubah posisi dari particle-particle pada setiap iterasi. Pada tiap iterasi nilai velocity dan posisi dibaharui.

Selain digunakan untuk optimasi fungsi, beberapa studi juga menggunakan PSO untuk hal lainnya. Misalnya menggunakan PSO untuk menggantikan algoritma back-propagation learning dalam Artificial Neural Network, dan hasilnya cukup menjanjikan.

Pseudo-code
For each particle
Initialize particle
END

Do
For each particle
Calculate fitness value
If the fitness value is better than the best fitness value (pBest) in history set current value as the new pBest
End

Choose the particle with the best fitness value of all the particles as the gBest
For each particle
Calculate particle velocity according velocity equation
Update particle position according position equation
End
While maximum iterations or minimum error criteria is not attained

Persamaan

Persamaan algoritma PSO terdiri dari velocity dan posisi, yang paling mendasar adalah sebagai berikut, velocity:

vi( k+1 ) = vi( k ) + L1i * R1i * ( pi-xi( k ) ) + L2i * R2i * ( G-xi( k ) )
dan posisi:

xi( k+1 ) = xi( k ) + vi( k+1 )

dimana :

i = index particle
k = iterasi
v = velocity dari particle ke-i
x = posisi dari particle ke-i
p = posisi terbaik dari partikel ke-i (pbest)
G = posisi terbaik dari swarm (gbest, terbaik dari semua particle)
L1,2 = Learning rates
R1,2 = bilangan acak dengan interval [0,1]

Studi lebih lanjut mengenai PSO di tahun 1999 (a modified particle swarm optimizer) menambahkan inertia (w) dalam persamaan update velocity. Persamaan ini kemudian menjadi algortima PSO yang paling umum digunakan:

vi( k+1 ) = w * vi( k ) + L1i * R1i * ( pi-xi( k ) ) + L2i * R2i * ( G-xi( k ) )
namun sistem ini bisa menbuat particle menjadi tidak stabil, disebabkan kecepatan nya yang tidak terkontrol. Teknik standard yang digunakan untuk menangani hal ini adalah membatasi velocity, vi є [-Vmax, +Vmax]. studi yang dilakukan Clerc dan Kennedy di tahun 2002 (The particle swarm-explosion, stability, and convergence in a multidimensional complex space), memberikan update rule yang dimodifikasi menjadi:

vi( k+1 ) =  * { vi( k ) + L1i * R1i * ( pi-xi( k ) ) + L2i * R2i * ( G-xi( k ) ) }

dimana (koefisien constriction) merupakan sebuah konstanta, yang jika dipilih dengan benar akan menjanjikan kestabilan dari PSO tanpa perlu membatasi velocity.

informasi lebih lanjut bisa dibaca di www.swarmintelligence.org
Matlab juga sudah menyediakan toolbox untuk PSO, jadi bisa mempermudah siapa saja yang berminat belajar PSO di matlab. Untuk Matlab versi 6.5, belum menyediakan toolbox PSO. Matlab versi 7 pun yang saya tahu juga belum menyediakan toolbox PSO. Jadi untuk toolbox ini, bisa di download langsung dari situs resmi Matlab, www.mathworks.com

5 komentar:

  1. Misalnya menggunakan PSO untuk menggantikan algoritma back-propagation learning dalam Artificial Neural Network, dan hasilnya cukup menjanjikan.

    kata siapa bu?..

    haha...

    BalasHapus
  2. silahkan di googling aja... :D
    ada banyak orang cerdas yg sudah tahu ini, cerita lama lah istilahnya

    singkat cerita nih ya, update error dan bias pada ANN itu bisa dilakukan oleh PSO. supaya optimal gitu deh...

    gmn, tertarik mengkombinasikan PSO dgn boxcox-rbf? hehehehehe!

    BalasHapus
  3. saya sedang mencari-cari PSO toolbox di matlab.
    toolbox untuk PSO nya berbayar ya ?
    makasih jawabannya...

    BalasHapus
  4. @Anonymous
    bisa free download kok, langsung dr web ny MATLAB.
    coba aja liat disini. good luck :)

    BalasHapus
  5. radian adi nugraha13 Mei 2009 05.41

    kalau kita akan mengoptimisasi suatu problem, bagaimana membuat masalah tersebut menjadi multi object jika inputnya berasal dari fuzzy (kan cuma single)?? mohon bantuannya..
    terima kasih.. kalau boleh saya minta emailnya..
    email saya : radiannugraha@gmail.com

    BalasHapus