Senin, 03 Februari 2020
Particle Swarm Optimization
1.
Pendahuluan
Particle
swarm optimization, disingkat sebagai PSO merupakan ,
merupakan algoritma optimasi yang meniru proses yang terjadi dalam kehidupan
populasi dalam bertahan hidup. Algoritma PSO adalah sebuah populasi yang
didasarkan penelusuran inisialisasi partikel secara random dan adanya interaksi
diantara partikel dalam populasi. Di dalam PSO setiap partikel bergerak melalui
ruang solusi dan mempunyai kemampuan untuk mengingat posisi terbaik sebelumnya
dan dapat bertahan dari generasi ke generasi.
PSO didasarkan
pada perilaku sebuah kawanan 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.
Setiap partikel
bergerak dalam ruang/space tertentu dan mengingat posisi terbaik yang pernah
dilalui atau ditemukan terhadap sumber makanan atau nilai fungsi objektif.
Setiap partikel menyampaikan informasi atau posisi bagusnya kepada partikel
yang lain dan menyesuaikan posisi dan kecepatan masing-masing berdasarkan
informasi yang diterima mengenai posisi yang bagus tersebut.
Meskipun setiap
burung mempunyai keterbatasan dalam hal kecerdasan, biasanya ia akan mengikuti
kebiasaan (rule) seperti berikut :
a. Seekor
burung tidak berada terlalu dekat dengan burung yang lain
b. Burung
tersebut akan mengarahkan terbangnya ke arah rata-rata keseluruhan burung
c. Akan
memposisikan diri dengan rata-rata posisi burung yang lain dengan menjaga
sehingga jarak antar burung dalam kawanan itu tidak terlalu jauh
Dengan demikian
perilaku kawanan burung akan didasarkan pada kombinasi dari 3 faktor simpel
berikut, Kohesi - terbang bersama, separasi - jangan terlalu dekat, dan
penyesuaian (alignment) mengikuti arah bersama.
Pada algoritma PSO ini, pencarian solusi dilakukan oleh
suatu populasi yang terdiri dari beberapa partikel. Populasi dibangkitkan
secara randomdengan batasan nilai terkecil dan terbesar. Setiap partikel
merepresentasikan posisi atau solusi dari permasalahan yang
dihadapi. Setiap partikel
melakukan pencarian solusi
yang optimal dengan melintasi ruang pencarian (search space). Hal ini
dilakukan dengan cara setiap partikel
melakukan penyesuaian terhadap
posisi terbaik dari
partikel tersebut (local best)
dan penyesuaian terhadap
posisi partikel terbaik
dari seluruh kawanan (global
best) selama melintasi
ruang pencarian. Jadi,
penyebaran pengalaman atau informasi
terjadi di dalam
partikel itu sendiri
dan antara suatu partikel dengan
partikel terbaik dari
seluruh kawanan selama
proses pencarian solusi. Setelah
itu, dilakukan proses
pencarian untuk mencari
posisi terbaik setiap partikel dalam
sejumlah iterasi tertentu
sampai didapatkan posisi
yang relative steady atau
mencapai batas iterasi yang telah ditetapkan. Pada setiap iterasi, setiap
solusi yang direpresentasikan oleh
posisi partikel, dievaluasi
performansinya dengan cara memasukkan solusi tersebut kedalam fitness
function.
Setiap partikel diperlakukan
seperti sebuah titik
pada suatu dimensi
ruang tertentu. Kemudian terdapat dua faktor yang memberikan karakter
terhadap status partikel pada ruang pencarian yaitu posisi partikel dan
kecepatan partikel.
2.
Implementasi
PSO
Berikut adalah kode Matlab untuk
implementasi PSO dalam minimasi fungsi.
a. Program
PSO
Pertama dengan memilih secara acak
suatu populasi awal, dalam hal ini kawanan burung dalam ruangan pencarian.
Diketahui bahwa iterations dari populasi ini adalah 100, inertia dari populasi tersebut
0,5 dan jumlah kawanan atau kelompok burung adalah 100. Inertia ini untuk
meredam kecepatan selama iterasi, yang memungkinkan kawanan burung menuju
(converge) titik target secara lebih akurat dan efisien.
Selanjutnya evaluasi Evaluasi nilai
fungsi tujuan untuk setiap partikelnya posisi, fungsi ini memperkirakan apakah
populasi dapat merubah posisi. Disini dibandingkan dengan jumlah kawanan dan
hasil yang di dapat.
Setelah
itu kita dapat mengupdate vector kecepatan
kawanan dan perencanaan pergerakan awanan burung.
b. Hasil
Gambar
·
Seekor burung tidak berada terlalu dekat
dengan burung yang lain, Ketika seekor burung mendekati target atau makanan
(atau bisa mnimum atau maximum suatu fungsi tujuan) secara cepat mengirim
informasi kepada burungburung yang lain dalam kawanan tertentu.
·
Burung yang lain akan mengikuti arah
menuju ke makanan tetapi tidak secara langsung
·
Ada komponen yang tergantung pada
pikiran setiap burung, yaitu memorinya tentang apa yang sudah dilewati pada
waktu sebelumnya.
·
Semua kawanan burung bergerak menuju
titik optimal dengan suatu kecepatan tertentu,
·
Pergerakan
kawanan burung menuju titik (10, 3) dengan PSO
3.
Kesimpulan
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.
Meskipun setiap
burung mempunyai keterbatasan dalam hal kecerdasan, biasanya ia akan mengikuti
kebiasaan (rule) seperti berikut :
d. Seekor
burung tidak berada terlalu dekat dengan burung yang lain
e. Burung
tersebut akan mengarahkan terbangnya ke arah rata-rata keseluruhan burung
f. Akan
memposisikan diri dengan rata-rata posisi burung yang lain dengan menjaga
sehingga jarak antar burung dalam kawanan itu tidak terlalu jauh
Dengan demikian
perilaku kawanan burung akan didasarkan pada kombinasi dari 3 faktor simpel
berikut, Kohesi - terbang bersama, separasi - jangan terlalu dekat, dan
penyesuaian (alignment) mengikuti arah bersama.
0 Comments:
Subscribe to:
Posting Komentar (Atom)
