Pengenalan Particle Swarm Optimization (PSO) + Studi Kasus: Mencari Nilai Terkecil Drop Wave Function

Particle Swarm Optimization (PSO) adalah salah satu algoritma optimasi Swarm Intelligence (SI). Algoritma dari SI kebanyakan terinspirasi hewan berkelompok yang saling bekerja sama tanpa pemimpin. Selain PSO, ada algoritma SI lainnya seperti Bee Colony, Bat Algorithm, Cuckoo Search dan lainnya yang tidak di bahas di postingan ini.

So, apa yang bisa dipecahkan oleh PSO ini? PSO biasanya digunakan untuk mencari solusi dari suatu persamaan kontinu. Jika kita cukup berpengalaman dan jeli dalam bidang komputasi, sebenarnya banyak masalah yang bisa di transformasi ke suatu bentuk persamaan kontinu untuk dipecahkan.

Sama seperti Neural Network (NN), PSO juga mengandalkan 'luck' dalam memecahkan masalah a.k.a mencari global optima dan tidak tersesat terjebak di local optima. Global optima, local optima...apa itu? Ini sebenarnya konsep yang cukup abstrak, singkatnya algoritma hill climbing seperti NN akan mudah terjebak pada local optima jika starting point bobot yang di inisialisasi secara acak berada pada area search space yang tidak tepat a.k.a tidak hoki. Solusi bagi algoritma NN adalah dengan membagi training datanya menjadi bagian-bagian kecil (mini batch) daripada langsung sekaligus diproses oleh algoritma backpropagation. Dengan begini dalam trainingnnya NN akan memiliki sifat stokastik (a.k.a luck) yang menjadi kunci untuk keluar dari jebakal local optima ini (analoginya, jika lemparan dadu awal kita jelek, supaya bagus yah lempar dadunya sekali lagi ;) ). Pembuktian keunggulan mini batch dibandingkan full batch dalam NN mungkin akan kita bahas lain kali.

Untuk PSO sendiri, 'pergerakannya' dalam mencari solusi dan tidak terjebak dalam local optima cukup unik. PSO mengandalkan 'temannya' untuk keluar dari local optima. Untuk lebih memahaminya, mari kita bahas algoritma PSO ini dari awal. Akan tetapi sebelum itu, terlebih dahulu kita list dulu properti yang ada pada PSO, yaitu:
- X: posisi atau solusi sementara yang dimiliki suatu partikel (vektor).
- P: posisi terbaik atau solusi terbaik yang pernah diraih oleh suatu partikel (vektor).
- Pbest: posisi terbaik atau solusi terbaik yang pernah diraih oleh suatu partikel di antara yang lainnya pada hubungan ketetanggaan.
- V: Arah gerak partikel (vektor).
- X-fitness: nilai fitness suatu partikel sementara.
- P-fitness: nilai fitness terbaik suatu partikel.
- Dbound, Ubound: Batas atas dan batas bawah search space solusi yang ingin dicari.
-vmax: Batas kecepatan gerak partikel.
-learning rate: Kecepatan 'belajar' partikel atau mudahnya kita bisa menganggap ini kecepatan normal gerak partikel karena learning rate di sini berhubungan dengan kecepatan gerak partikel nantinya. Learning rate terbagi menjadi 2, yaitu: Learning rate kognisi (φ1) dan learning rate sosial (φ2).
-kondisi berhenti: Kondisi tanda algoritma PSO harus berhenti. Kondisi ini bisa banyaknya iterasi yang sudah dilakukan atau galat yang diinginkan sudah tercapai.
-r: koefisien kecepatan random dengan rentang nilai mulai dari 0 sampai 1.

Cara kerja algoritma PSO tidak serumit namanya, prinsipnya sebenarnya cukup sederhana. Kita ambil contoh kita ingin mencari parameter drop wave function di bawah agar bisa mendapatkan nilai terkecil dari fungsi tersebut.

Fungsi di atas adalah target yang ingin dicapai oleh PSO (mencari parameter yang mengasilkan nilai minimum). Kenapa saya memilih drop wave function? Fungsi ini punya banyak local optima, di sini kita bisa melihat kehandalan PSO dalam mengatasi local optima tersebut. Kemudian kita tetapkan ingin menginisialisasi berapa partikel a.k.a calon solusi untuk permasalahan tersebut. Calon solusi tersebut masing-masing adalah vektor dengan panjang 2. Nilai awal dari vektor partikel bernilai acak pada rentang nilai (Ubound dan Dbound) yang kita inginkan. Contoh pada kasus ini, nilai Ubound = 2 dan Dbound = -2.

Sebelumnya, kita sudah tahu bahwa nilai terendah yang bisa dihasilkan oleh drop wave function adalah -1 dengan X yaitu (0,0). Berikut contoh ploting ketika kita menginisialisasi 4 partikel dengan nilai acak pada kasus ini.

Semuanya melenceng jauh dari (0,0). Lalu, bagaimana bisa partikel-partikel ini maju mendekati nilai (0,0)? Inilah core dari algoritma PSO, jadi perpindahan posisi partikel pada PSO dirumuskan menjadi

dimana i adalah banyaknya iterasi. Kecepatan perpindahan partikel dirumuskan sebagai

Jadi, dari rumus kecepatan yang ada 3 suku ini, kecepatan partikel disebabkan oleh 3 hal, yaitu:
1.) Kecepatan inersia

2.) Kecepatan kognisi

3.) Kecepatan sosial

Kecepatan sosial cukup krusial dalam algoritma PSO karena akan sangat menentukan nilai Pbest. Pbest ada nilai P yang terbaik pada hubungan ketetanggaan. Hubungan ketetanggaan yang umum digunakan pada PSO adalah hubungan ketetanggaan topologi cincin, global, dan bintang. Selain itu, kecepatan sosial juga menjadi kunci partikel dalam PSO bisa keluar dari jebakan local optima.

Gambar topologi cincin, global, dan bintang secara berurutan.

Misal pada topologi global, tentu nilai Pbest hanya akan ada 1 dan itu diakui untuk semua partikel sementara untuk topologi cincin nilai Pbest akan ada banyak dan hanya 3 partikel yang akan mengakui Pbest tersebut (1 partikel terhubung dengan 2 partikel lainnya). Untuk topologi selain global, versi Pbest akan ada sebanyak dengan banyaknya jumlah partikel.

Posisi terbaik ditentukan oleh nilai fitness (X-fitness, P-fitness). Pada kasus ini, jika keluaran dari drop wave function semakin rendah maka fitness dari posisi partikel tersebut akan dianggap semakin baik. Proses perubahan posisi partikel ini akan terjadi terus menerus sampai kondisi tanda berhentinya terjadi. Setelah berhenti, dari semua partikel yang diinisialisasi, dipilih yang nilai fitnessnya terbaik dan didapatkanlah solusi terbaiknya, dimana dalam kasus ini nilai x1 dan x2 yang mendekati nilai (0,0).

Untuk prakteknya, di Python sendiri sebenarnya kalau mau usaha googling sedikit sudah ada yang meneyediakan library siap pakai untuk algoritma PSO. Hanya saja, menurut saya untuk bisa memahami lebih detil tentang suatu algoritma, bagusnya kita coding dari 0, dengan modal utama  library numpy. Script yang sudah saya buat untuk mencari nilai terkecil drop wave function menggunakan PSO sudah saya buat dan tinggal mendownloadnya di sini.

Sepengetahuan saya sekarang ketika membuat post ini, belum ada rule of thumb tentang nilai-nilai properti yang harus ditetapkan dalam PSO. Untuk mendapat hasil yang optimal, butuh pengalaman dan trial and error pada suatu kasus yang ingin dipecahkan tersebut. Pertimbangan dalam menentukan properti PSO antara lain seperti pada learning rate. Jika learning ratenya terlalu besar, maka pergerak partikel akan menjadi terlalu cepat sehingga kesulitan untuk bisa berhenti tepat di area solusi yang tepat sementara itu learning rate yang terlalu lambat membuat iterasi yang dibutuhkan untuk memecahkan masalah menjadi harus banyak. Untuk gerak partikel yang potensial melenceng dari Ubound maupun Dbound juga harus dipikirkan, apakah kecepatannya harus di 0 kan atau dibuat berpindah saja sampai menyamai nilai Dbound maupun Ubound tergantung arah geraknya. Banyaknya partikel juga sangat mempengaruhi ditemukannya solusi. Semakin banyak partikel tentu semakin cepat (iterasi yang dibutuhkan sedikit) solusi paling optimal ditemukan tapi akan semakin berat juga komputasi yang harus dilakukan.

Silahkan bereksperimen dengan script yang telah diberikan. Salah satu kunci untuk memahami algoritma suatu script adalah dengan mencobanya sendiri dan mengubahnya sedikit demi sedikit. Script yang dibagikan tersebut akan menghasilkan solusi optimal yang berbeda-beda untuk setiap kali running yang berbeda (sama seperti NN yang sering dibahas pada blog ini) dan ini wajar saja jika kita memahami cara kerja dari PSO.

Berikut pergerakan dari 4 partikel yang tadi mencari solusi untuk kasus ini dengan iterasi sebanyak 30x.

Bisa dilihat pada akhir iterasi, semua partikel bergerak menuju ketengah ke nilai (0,0) yang merupakan solusi paling optimal pada kasus drop wave function. Sekian pembahasan kali ini.

referensi:

Swarm Intelligence Komputasi Modern untuk Optimasi dan Big Data Mining karangan Dr. Suyanto, S.T., M.Sc.

http://al-roomi.org/benchmarks/unconstrained/2-dimensions/54-drop-wave-function, diakses pada 16 April 2018.

http://slideplayer.com/slide/7698916/, diakses pada 17 April 2018

https://www.sfu.ca/~ssurjano/drop.html, diakses pada 17 April 2018

https://www.researchgate.net/figure/Ring-Global-and-Star-topologies-of-PSO_fig1_279999821, diakses pada 17 Februari 2018