PSO mensimulasikan perilaku
burung berkelompok. Misalkan skenario berikut:
Sekelompok burung
yang secara acak
mencari makanan di suatu
daerah. Hanya ada
satu potong makanan di
daerah yang dicari.
Semua burung tidak tahu di mana
makanan ini. Tapi mereka tahu berapa
banyak makanan di
setiap iterasi. Jadi
apa strategi terbaik untuk
mencari makanan? Efektif adalah mengikuti burung terdekat
dengan makanan. PSO belajar dari
skenario dan menggunakannya untuk memecahkan masalah
optimasi. Dalam PSO, setiap solusi tunggal
merupakan "sebuah burung" dalam ruang
pencarian. Kami menyebutnya "partikel". Semua
partikel memiliki nilai
fitness yang dievaluasi oleh
fungsi fitness harus dioptimalkan dan memiliki kecepatan
penerbangan langsung dari partikel.
Partikel-partikel terbang melalui ruang
masalah dengan mengikuti
partikel optimal saat ini. Algoritma
PSO menggunakan dua variabel
random r1 dan
r2 yang keduanya menghasilkan angka
acak dengan jarak
antara 0 dan 1.
Variabel random tersebut
digunakan untuk memberikan efek
kepada sifat stochastic
dari algoritma PSO. Nilai
dari r1 dan
r2 disesuaikan dengan konstanta
c1 dan c2 yang memiliki rentang nilai
antara 0 <
c1, c2 ≤
2. Konstanta tersebut disebut sebagai
koefisien akselerasi yang mempengaruhi jarak
maksimum yang dapat diambil oleh sebuah partikel
dalam sebuah iterasi. Update
kecepatan dari sebuah
partikel dibedakan untuk setiap
dimensi j € 1…n (n
berdasarkan jumlah parameter yang
dioptimasi), sehingga vi,,j mewakili dimensi ke
j dari vektor kecepatan yang diasosiasikan dengan
partikel ke i.
Sehingga persamaan untuk update
kecepatan oleh van
den Bergh (2001) dapat didefinisikan sebagai berikut :
vi = ὼ v i
+ c 1 r 1
( p b e s t -
x i ) + c 2 r 2
( g b e s t -
x i )
dimana,
vi =
kecepatan partikel saat ini
ὼ
= berat inertia,
c1,
c2 = koefisien akselerasi
r1,
r2 = bilangan random uniform
antara 0 dan 1
pbest
= posisi personal best partikel
saat ini
gbest
= posisi global best partikel saat
ini
xi
= posisi partikel saat ini
Dapat dilihat
dari persamaan update kecepatan bahwa
c2 mengatur jarak
maksimum yang dipengaruhi oleh
partikel global best, dan c1 mengatur
jarak yang dipengaruhi
oleh posisi personal best
dari partikel tersebut.
Nilai dari vi
dapat dibatasi
dengan nilai [-vmax,vmax]
untuk mencegah terjadinya kejadian
dimana partikel meninggalkan daerah
pencarian. Jika daerah pencarian dibatasi
dengan [-xmax,xmax], maka nilai vmax biasanya didefinisikan
sebagai
vmax=k xmax, dimana 0.1≤ k ≤ 1.0
Posisi setiap
partikel di-update menggunakan persamaan (2.2)
sehingga dihasilkan persamaan berikut:
xi
= xi + vi
dimana,
xi
= posisi partikel baru
x
= posisi partikel saat ini
vi
=kecepatan partikel yang baru
Inisialisasi
Membiarkan f
: Rn = R
menjadi fitness atau beban
yang harus diminimalkan. Misalkan diketahui S jumlah partikel
dalam kerumunan itu, masing-masing memiliki
posisi xi € Rn
dalam ruang-pencarian dan kecepatan
sebuah vi € Rn.
Membiarkan
pbest menjadi diketahui posisi terbaik partikel i
dan biarkan gbest
menjadi posisi yang paling
terkenal dari seluruh
mengeriap. Ini merupakan
algoritma PSO dasar :
Ø Untuk
setiap partikel i
= 1, .
. . ., S lakukan:
·
Inisialisasi partikel
posisi: xi ~
U(bb, bt), Dimana bb, bt
adalah batas bawah dan atas ruang-pencarian dan
U(. , .) adalah vektor acak.
·
Menginisialisasi posisi
paling dikenal : pbest = xi
·
Menginisialisasi kecepatan:
v i~ U( -( b t - b b ) ,b t - b b
) )
Ø Menginisialisasi posisi paling terkenal dari gerombolan
:
gbest
= arg min (pbest)
Ø Sampai
suatu kriteria terminasi
terpenuhi (jumlah iterasi dilakukan
misalnya, atau sampai kesesuaian
yang memadai), ulangi :
Ø Untuk
setiap partikel i
= 1, .
. . ., S
lakukan:
·
vektor acak c 1 , c 2 ~ U( 0 ,1 )
·
Update partikel
kecepatan:
vi
= ὼ
vi + c1 r1 ( p best xi ) + c2 rn ( g best - xi ),
Ø Update posisi partikel: xi =
xi + vi,
Perhatikan bahwa hal ini dilakukan tanpa
perbaikan untuk fitness.
Jika
f ( xi). < f (pbest) lakukan:
Ø Update partikel terkenal
posisi:
pbest = xi
Ø Jika f (pbest). < f (gbest) update
posisi
swarm terbaik: gbest
= pbest
Ø Sekarang solusi terbaik ditemukan.
Perancangan
Sistem Aplikasi Mobile
Aplikasi mobile
GIS ini dirancang
sebatas untuk memberikan informasi
berupa jalur terpendek untuk
sampai ke daerah tujuan dan juga untuk memberikan informasi mengenai posisi
suatu desa ataupun fasilitas
umum yang ada di
Kabupaten Bangkalan. Berikut
akan dijelaskan mengenai
perencanaan dan pembuatan sistem yang berhubungan dengan
pengolahan data spasial GIS(Geographic Information
System) sebagai pemetaan gambar
serta J2ME sebagai
bahasa pemrograman berbasis mobile.
 |
Penjelasan
Blok Diagram :
User menginputkan
data berupa lokasi awal
dan tujuan melalui
aplikasi J2me. Kemudian aplikasi j2me
melakukan proses pencarian
jalur berdasarkan data hasil
inputan dari user
dengan mengadopsi algoritma Particle
Swarm Optimization(PSO)
sebagai metode dalam menentukan jalur
terpendek. Dimana proses pencarian jalur berhubungan dengan
database yang berupa data GIS sebagai pemetaan gambar dan data Desa/Fasum
sebagai data lokasi yang akan dipilih.
