Saturday, April 12, 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

12 comments:

  1. siang gan, gan ane mau tanya soal perhitungan manual untuk contoh kasus sentimen analisis tweet dari twitter itu seperti apa ya untuk menentukan insialisasi awal partikel nya ?
    Terima kasih

    ReplyDelete
  2. belum tahu sih, karena saya menggunakan PSO belum pernah nangani analisis sentimen

    ReplyDelete
  3. saya mau tanya untuk menentukan rhomax dan rhomin itu dari mana ya ? saya stuck disitu karena tidak tahu detail kasus nya seperti apa

    ReplyDelete
  4. lalu untuk menentukan posisi awal dari partikel saya minta tolong bisa dijelaskan didapat darimana untuk perhitungan rand[0,1], xmax, dan xmin nya

    ReplyDelete
  5. rho max dan rho min, kita yang nentukan sendiri yaitu 0.1 sampai dengan 0.9

    ReplyDelete
  6. saya ada kodenya sekitar 300 line menggunakan bahasa java sesuai dengan kasus diatas yang saya tulis sendiri, coba blog ini di follow ntar saya kirim kodenya

    ReplyDelete
  7. dalam kasus ini jumlah partikel nya ada 4 ya ? Baik saya sudah follow

    ReplyDelete
  8. halo min hitungan lengkap by excel boleh di share dong , surikenand@gmail.com . terimakasih

    ReplyDelete
    Replies
    1. Saya nggak punya
      Itu hanya ilustrasi saja low
      Yg ada hanya kode di Java yg saya buat sendiri

      Delete