PSO

Particle Swarm Optimization

Particle Swarm Optimization (PSO) adalah sebuah teknik stochastic optimization berdasarkan populasi yang terinspirasi oleh perilaku sosial dari pergerakan burung atau ikan (bird flocking or fish schooling). Teknik PSO dikemukakan oleh Russell C. Eberhartdan James Kennedy di tahun 1995.

Bersama dengan Ant Colony Optimization (ACO), PSO digolongkan ke dalam teknik metaheuristik optimasi swarm intelligence (SI) di mana prinsip sosio-psikologi yang mempengaruhi perilaku sosial makhluk hidup, diadopsi. Secara sederhana, sebuah sistem SI, yang diperkenalkan oleh Gerardo Benidan Jing Wang di tahun 1989, terbentuk dari sebuah populasi yang terdiri dari individu-individu yang berinteraksi baik secara lokal satu sama lain maupun dengan lingkungan mereka dengan mengikuti aturan yang sangat sederhana [wikipedia]. Akibatnya, pengetahuan setiap individu berkembang optimal melalui interaksi sosial yang terjadi. Kemampuan berpikir bukan lagi menjadi sesuatu yang hanya bersifat pribadi melainkan juga interpersonal.

Karena itulah, orang melihat PSO, demikian pula ACO, bukan hanya sekedar sebuah alat optimasi tapi juga sebuah alat yang melambangkan sosiokognisi (sociocognition) dari makhluk hidup dan lingkungannya (artificial agents), yang berdasarkan pada prinsip sosio-psikologi.

Sebagai sebuah alat optimasi, PSO menawarkan suatu prosedur pencarian (search procedure) berdasarkan populasi yang di dalamnya individu-individu, yang disebut particles, mengubah posisi, ataustate, mereka terhadap waktu. Mereka ‘terbang’ mengitari suatu ruang pencarian multi dimensi (multidimensional search space). Selama ‘penerbangan’ setiap individu menyesuaikan posisinya menurut pengalaman pribadinya, dan menurut pengalaman individu di sebelahnya, sehingga membentuk posisi terbaik yang sesuai untuk dirinya dan untuk individu di sebelahnya. Jadi, algoritma PSO menggabungkan metode-metode local search dengan metode-metode global search, yang menyeimbangkan antara eksplorasi dan eksploitasi.

PSO telah sukses diterapkan di dalam pelbagai bidang penelitian dan aplikasi, termasuk ‘pelatihan’ Artificial Neural Networks (ANN) dan permainan sudoku. Hal ini disebabkan karena PSO memberi hasil yang lebih baik melalui cara yang lebih cepat dan sederhana bila dibandingan dengan metode lain. Selain itu, PSO memiliki sedikit parameter untuk disesuaikan. Sehingga sebuah versi, dengan sedikit variasi, dapat bekerja dengan baik dalam banyak bentuk aplikasi, termasuk aplikasi yang spesifik dengan kebutuhan yang spesifik pula.

PSO vs GA

PSO memiliki banyak kemiripan dengan Genetic Algorithms (GA), di mana sistem diawali dengan suatu populasi yang terbentuk dari solusi-solusi acak (random solutions) kemudian sistem mencari optimalitas melalui pembaharuan generasi secara acak.

Namun demikian, PSO tidak memiliki evolution operators, seperti mutasi dan crossover (persilangan). Sebaliknya, potential solutions, yakni individu-individu, atau yang disebut sebagai particles, ‘terbang’ mengikuti individu-individu yang optimum saat ini (current optimum particles).

Setiap individu menyimpan jejak-jejak posisinya dalam problem space. Jejak-jejak posisi tersebut diartikan sebagai best solution, atau fitness dalam GA, yang diperolehnya sejauh ini. Nilainya, yaknifitness value, yang disebut pbest, juga turut disimpan. Selain pbest yang merupakan milik individu yang bersangkutan, turut disimpan pula nilai terbaik milik individu di sekitarnya (local best), yang disebut lbest. Jika suatu individu memperhitungkan semua individu di dalam populasi di mana dia berada sebagai individu di sekitarnya, maka nilai terbaik yang dimaksud adalah nilai terbaik umum (global best) dan disebut gbest. Selanjutnya, terjadi akselerasi antara lokasi pbest dan lokasi lbest dari setiap individu. Akselerasi ini diberi bobot berupa bilangan acak.

Dengan demikian, mekanisme berbagi informasi (information sharing mechanism) yang dimiliki PSO berbeda secara signifikan dengan yang dimiliki GA. Dalam GA, setiap individu, yang disebutchromosome, berbagi informasi satu sama lain, sehingga keseluruhan populasi bergerak sebagai sebuah kesatuan menuju optimalitas. Dalam PSO, hanya gbest, atau lbest, yang memberi informasi kepada yang lain. Ini adalah sebuah mekanisme berbagi informasi satu arah. Proses evolusi hanya mencari solusi yang terbaik. Dengan demikian, seluruh individu, yang disebut particle, bergerak konvergen secara cepat ke solusi terbaik.

PSO dan ANN

Sebagaimana diutarakan di atas, PSO dapat dipergunakan untuk ‘melatih’ suatu Artificial Neural Network (ANN), menggantikan teknik back-propagation learning yang umum dipakai, di mana ANN dilatih melalui kesalahan yang dihasilkan (back-propagation of errors). Teknik pelatihan ‘belajar dari kesalahan’ ini pertama kali dinyatakan oleh Paul Werbos di tahun 1974, kemudian disempurnakan oleh David E. Rumelhart, Geoffrey E. Hinton dan Ronald J. Williams, 12 tahun kemudian [wikipedia]. 

Dengan menggunakan PSO, ANN dapat ‘dilatih’ lebih cepat dengan hasil yang lebih baik pada sebagian besar kasus. PSO juga mampu menghindari beberapa problem yang dihadapi oleh GA dalam ‘melatih’ ANN.