PSO particle swarm optimization ppt.ppsx

particle swarm optimization

1. Departemen Teknik Informatika

2. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Particle Swarm Optimization

3. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Capaian Pembelajaran
Mahasiswa mampu menjelaskan metode optimasi dan penggunaannya pada
permasalahan klasifikasi dan clustering.

4. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Pengenalan
•Konsep kali pertama diperkenalkan oleh Kennedy dan Eberhart
(1995)
•Ide awal adalah mengembangkan simulasi visual pada perilaku
kawanan burung
•Simulasi kemudian dimodifikasi untuk memasukkan sebuah titik di
lingkungan yang menarik agen burung virtual
•Potensi untuk aplikasi pengoptimalan kemudian menjadi jelas

5. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Contoh Konsep Kerjasama

6. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Ide Dasar
•Setiap partikel mencari yang optimal;
•Setiap partikel bergerak, dan karena itu memiliki kecepatan;
•Setiap partikel mengingat posisinya di mana ia mendapatkan hasil
terbaik sejauh ini (terbaik pribadinya)
Tidak akan terlalu bagus dengan sendirinya; partikel membutuhkan bantuan dalam
mencari tahu di mana harus mencari.

7. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Ide Dasar
•Partikel dalam gerombolan bekerja sama
Bertukar informasi tentang apa yang mereka temukan di tempat-tempat yang pernah
mereka kunjungi.
•Kerjasamanya sangat sederhana
Dalam PSO dasar:
Sebuah partikel memiliki lingkungan yang terkait dengannya. Sebuah partikel
mengetahui kebugaran orang-orang di lingkungannya, dan menggunakan posisi partikel
yang paling fit. Posisi ini hanya digunakan untuk mengatur kecepatan partikel.

8. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Inisialisasi, Posisi, dan Kecepatan

9. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Neighbourhoods
geografis
sosial

10. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Neighbourhoods
global

11. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Circular neighbourhood
virtual circle
1
5
7
6
4
3
8
2
3-neighbourhood
dari partikel 1

12. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Posisi Partikel
Saya di sini!
Performa terbaik
para tetangga
Performa terbaikku
x
p
g
p
i
v


Partikel menyesuaikan posisi mereka sesuai dengan ``kompromi psikososial” antara apa yang
membuat seseorang merasa nyaman, dan apa yang dianggap oleh masyarakat.

13. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Pseudocode (http://www.swarmintelligence.org/tutorials.php)
Equation (a)
v[] = c0 *v[]
+ c1 * rand() * (pbest[] - present[])
+ c2 * rand() * (gbest[] - present[])
(in the original method, c0=1, but many
researchers now play with this parameter)
Equation (b)
present[] = present[] + v[]
For each particle
 
   Initialize particle
END

14. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Pseudocode (http://www.swarmintelligence.org/tutorials.php)
Do
For each particle
Calculate fitness value
 
    If the fitness value is better than
its peronal best
 
   
set current value as the new pBest
 
   End
 
   Choose the particle with the best fitness value of all as
gBest
 
   For each particle
 
    Calculate particle velocity according equation (a)
 
     Update particle position according equation (b)
 
   End
While maximum iterations or minimum error criteria is not attained

15. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Parameter
•Jumlah partikel (swarmsize)
•C
1 (pentingnya personal best)
•C
2
(pentingnya tetangga terbaik)
•v
max
(batas kecepatan)

16. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Parameter
•Jumlah partikel (swarmsize)
(10-50) dilaporkan biasanya cukup
•C
1
(pentingnya personal best)
•C
2 (pentingnya tetangga terbaik)
Biasanya C
1 + C
2 = 4 – Tidak ada alasan yang baik selain empirisme
•v
max
(batas kecepatan)
terlalu rendah, terlalu lambat; terlalu tinggi, terlalu tidak stabil

17. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Adaptive Swarm Size
Sudah cukup banyak peningkatan
meskipun saya yang terburuk
Saya yang terbaik tapi belum
ada peningkatan yang cukup
Saya ingin bunuh diri!
Saya mencoba membuat
partikel baru

18. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Koefisien Adaptif
Semakin baik saya,
semakin saya
mengikuti cara saya
sendiri
Semakin baik tetangga terbaik saya,
semakin saya cenderung mendekatinya
av
rand(0…b)(p-x)

19. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Rangkuman
•Konsep particle swarm
•Konsep particle swarm optimization
•Algoritma particle swarm optimization
•Posisi
•Velocity
•Neighborhood

20. www.its.ac.id INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
- TERIMA KASIH -