Tutorial Cara Kerja Particle Swarm Optimization

Particle swarm optimization, disingkat sebagai PSO, didasarkan pada perilaku sebuah kawanan serangga, seperti semut, rayap, lebah atau burung. Algoritma PSO meniru perilaku sosial organisme ini. Perilaku sosial terdiri dari tindakan individu dan pengaruh dari individu-individu lain dalam suatu kelompok. Kata partikel menunjukkan, misalnya, seekor burung dalam kawanan burung. Setiap individu atau partikel berperilaku secara terdistribusi dengan cara menggunakan kecerdasannya (intelligence) sendiri dan juga dipengaruhi perilaku kelompok kolektifnya. Dengan demikian, jika satu partikel atau seekor burung menemukan jalan yang tepat atau pendek menuju ke sumber makanan, sisa kelompok yang lain juga akan dapat segera mengikuti jalan tersebut meskipun lokasi mereka jauh di kelompok tersebut Misalkan kita mempunyai fungsi berikut

Kita mempunyai persamaan partikel matematika berikut

F(x) = 2*x^2+4*x+5

Dengan posisi awal partikel berikut

 

Kemudian nilai awal kecepatan / velocity nya

Kemudian Pbest dan Gbest berikut

Akan dilakukan iterasi sebanyak 5 kali, sehingga didapatkan rho(i) untuk masing-masing iterasi sebagai berikut

Tiap iterasi akan dilakukan update berupa V dan Posisi dengan aturan berikut

V_[partikel,i] = rho_[i]*V_[i-1]+c1*r1*(Pbest_[partikel,i]-posisi_[partikel])+c2*r2(Best-posisi_[partikel])

Dengan update posisi berikut

Posisi[partikel_baru,i] = Posisi[partikel_lama,i-1] + V[partikel,i]

# Misalkan pada iterasi ke i=1

Hitung kecepatan/velocity baru

V[1,1] = rho_[1]*V_[0]+c1*r1*(Pbest_[1]-posisi_[1])+c2*r2(Best-posisi_[1])

0.74 * 0.0 +  ( 1.0 * 0.1 *  ( -4.0 - -4.0 )) +  ( 1.0 * 0.2 *  ( -3.0 - -4.0 ) ) = 0.2

 V[2,1] = rho_[1]*V_[0]+c1*r1*(Pbest_[2]-posisi_[2])+c2*r2(Best-posisi_[2])

0.74 * 0.0 +  ( 1.0 * 0.1 *  ( -3.0 - -3.0 )) +  ( 1.0 * 0.2 *  ( -3.0 - -3.0 ) ) = 0

V[3,1] = rho_[1]*V_[0]+c1*r1*(Pbest_[3]-posisi_[3])+c2*r2(Best-posisi_[3])

0.74 * 0.0 +  ( 1.0 * 0.1 *  ( 2.0 - 2.0 )) +  ( 1.0 * 0.2 *  ( -3.0 - 2.0 ) )  = -1

Dan seterus nya…

V[4,1]  = 0.74 * 0.0 +  ( 1.0 * 0.1 *  ( 5.0 - 5.0 )) +  ( 1.0 * 0.2 *  ( -3.0 - 5.0 ) ) = -1.6

Kemudian update Posisi Baru

Posisi[1,1] = Posisi[1,0] + V[1,1] = -4.0 + 0.2 = -3.8

Posisi[2,1] = Posisi[2,0] + V[2,1] = -3.0 + 0.0 = -3.0

Posisi[3,1] = Posisi[3,0] + V[3,1] = 2.0 + -1.0 = 1.0

Posisi[4,1] = Posisi[4,0] + V[4,1] = 5.0 + -1.6 = 3.4

Kemudian kita akan mencari nilai Pbest dengan cara compare partikel lama dan partikel baru

Ingat yang dibandingkan BUKAN POSISI tapi NILAI partikel nya

 

Sehingga menjadi berikut

Sedangkan untuk mencari Gbest sebagai berikut yaitu NILAI partikel terkecil dari Pbest, BUKAN POSISI

Hal yang penting dari Pbest dan Gbest adalah POSISI, sedangkan NILAI hanya untuk PEMBANDING SAJA

# Misalkan pada iterasi ke i=2

Hitung kecepatan/velocity baru

V[1,2] = 0.58 * 0.2 +  ( 1.0 * 0.1 *  ( -3.8 - -3.8 )) +  ( 1.0 * 0.2 *  ( -3.0 - -3.8 ) ) =  0.276

V[2,2] = 0.58 * 0.0 +  ( 1.0 * 0.1 *  ( -3.0 - -3.0 )) +  ( 1.0 * 0.2 *  ( -3.0 - -3.0 ) ) =  0.0

V[3,2] = 0.58 * -1.0 +  ( 1.0 * 0.1 *  ( 1.0 - 1.0 )) +  ( 1.0 * 0.2 *  ( -3.0 - 1.0 ) ) =  -1.38

V[4,2] = 0.58  * -1.6 +  ( 1.0 * 0.1 *  ( 3.4 - 3.4 )) +  ( 1.0 * 0.2 *  ( -3.0 - 3.4 ) ) =  -2.208

Kemudian update Posisi Baru

Posisi[1,2] = Posisi[1,1] + V[1,2] = -3.8 + 0.276 = -3.524

Posisi[2,2] = Posisi[2,1] + V[2,2] = -3.0 + 0.0 = -3.0

Posisi[3,2] = Posisi[3,1] + V[3,2] = 1.0 + -1.38 = -0.38

Posisi[4,2] = Posisi[4,1] + V[4,2] = 3.4 + -2.208 = 1.192

 

# Misalkan pada iterasi ke i=3

Hitung kecepatan/velocity baru

V[1,3] = 0.42 * 0.276 +  ( 1.0 * 0.1 *  ( -3.524 - -3.524 )) +  ( 1.0 * 0.2 *  ( -0.38 - -3.524 ) ) =  0.744

V[2,3] = 0.42 * 0.0 +  ( 1.0 * 0.1 *  ( -3.0 - -3.0 )) +  ( 1.0 * 0.2 *  ( -0.38 - -3.0 ) ) =  0.524

V[3,3] = 0.42 * -1.38 +  ( 1.0 * 0.1 *  ( -0.38 - -0.38)) +  ( 1.0 * 0.2 *  ( -0.38 - -0.38 ) ) =  -0.579

V[4,3] = 0.42 * -2.208 +  ( 1.0 * 0.1 *  ( 1.192 - 1.192 )) +  ( 1.0 * 0.2 *  ( -0.38 - 1.192 ) ) =  -1.241

Kemudian update Posisi Baru

Posisi[1,3] = Posisi[1,2] + V[1,3] = -3.524 + 0.744 = -2.78

Posisi[2,3] = Posisi[2,2] + V[2,3] = -3.0 + 0.524 = -2.476

Posisi[3,3] = Posisi[3,2] + V[3,3] = -0.38 + -0.579= -0.959

Posisi[4,3] = Posisi[4,2] + V[4,3] = 1.192 + -1.241 = -0.049

Berikut jika kita menggunakan jumlah iterasi maksimal = 50, akan menghasilkan berikut

dicapai pada epoch ke 24


kita akan melihat secara grafikpersamaan y(x) = 2*x^2+4*x+5 yaitu

referensi:

Budi Santosa, Teknik Industri, ITS,Kampus ITS, Sukolilo Surabaya