Sabtu, 12 April 2014

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

Posting Komentar