Particle Swarm Optimization

Particle Swarm Optimization (PSO) adalah salah satu teknik optimasi dan termasuk jenis teknik komputasi evolusi. Metode ini memiliki robust yang bagus untuk memecahkan persoalan yang mempunyai karakteristik nonlinear dan nondifferentiability, multiple optima, dimensi besar melalui adaptasi yang diturunkan dari teori psychology-sosial. (Sumber: Alrijadjis, Astrowulan K. 2010. Optimasi Kontroler PID Berbasis Particle Swarm Optimization (PSO) untuk Sistem dengan Waktu Tunda). PSO terinspirasi dari perilaku gerakan kawanan hewan seperti ikan (school of fish), hewan herbivor (herd), dan burung (flock) yang kemudian tiap objek hewan disederhanakan menjadi sebuah partikel. Suatu partikel dalam ruang memiliki posisi yang dikodekan sebagai vektor koordinat. Vektor posisi ini dianggap sebagai keadaan yang sedang ditempati oleh suatu partikel di ruang pencarian. Setiap posisi dalam ruang pencarian merupakan alternatif solusi yang dapat dievaluasi menggunakan fungsi objektif. Setiap partikel bergerak dengan kecepatan v.

Ciri khas dari PSO adalah pengaturan kecepatan partikel secara heuristik dan probabilistik. Jika suatu partikel memiliki kecepatan yang konstan maka jika jejak posisi suatu partikel divisualisasikan akan membentuk garis lurus. Dengan adanya faktor eksternal yang membelokkan garis tersebut yang kemudian menggerakkan partikel dalam ruang pencarian maka diharapkan partikel dapat mengarah, mendekati, dan pada akhirnya mencapai titik optimal. faktor eksternal yang dimaksud antara lain posisi terbaik yang pernah dikunjungi suatu partikel, posisi terbaik seluruh partikel (diasumsikan setiap partikel mengetahui posisi terbaik setiap partikel lainnya), serta faktor kreativitas untuk melakukan eksplorasi. Secara matematis deskripsi di atas ditampilkan sebagai berikut :

v_i(t) = u₁.k₁.v_i(t-1) + u₂.k₂.(xbest_i-x_i) + u₃.k₃.(xbest_g-x_i) + u₄.vacak

xbest di atas merupakan catatan khusus mengenai posisi terbaik yang pernah dikunjungi tiap partikel. Indeks g menyatakan partikel yang posisi terbaiknya merupakan posisi terbaik dibandingkan posisi partikel lainnya. vacak merupakan vektor arah acak yang diinterpretasi sebagai faktor kreativitas untuk melakukan eksplorasi. nilai skalar u1 hingga u4 merupakan variabel acak (random variate) yang terdistribusi merata (uniform distribution) sedangkan a1 hingga a4 merupakan koefisien pengaruh masing-masing suku. (Sumber: http://pebbie.wordpress.com/2010/01/24/bereksperimen-dengan-particle-swarm-optimization/)

Berikut ini adalah contoh implementasi algoritma PSO dalam MATLAB :

%% Particle Swarm Optimization Simulation

% Simulasi pergerakan dari swarm untuk meminimalkan fungsi tujuan

% $$ fungsi rastrigin >> f(x) = sum([x.^2-10*cos(2*pi*x) + 10], 2)$$ 

% Matrix swarm=

% swarm(index, [location, velocity, best position, best value], [x, y

% components or the value component])

%Edited by Aditya Erlangga%

clear

clc

iterations = 100;

inertia = 1.0;

correction_factor = 2.0;

swarm_size = 49;

% Inisialisasi posisi swarm

index = 1;

for i = 1 : 7

for j = 1 : 7

swarm(index, 1, 1) = i;

swarm(index, 1, 2) = j;

index = index + 1;

end

end

swarm(:, 4, 1) = 1000; % sejauh ini, nilai ini yang terbaik

swarm(:, 2, :) = 0; % kelajuan/velocity awal

%% Iterasi

for iter = 1 : iterations

for i = 1 : swarm_size

swarm(i, 1, 1) = swarm(i, 1, 1) + swarm(i, 2, 1)/1.3; %update x position

swarm(i, 1, 2) = swarm(i, 1, 2) + swarm(i, 2, 2)/1.3; %update y position

x = swarm(i, 1, 1);

y = swarm(i, 1, 2);

val = sum([x.^2-10*cos(2*pi*x) + 10], 2); 

if val < swarm(i, 4, 1) % kondisi jika posisi baru lebih baik

swarm(i, 3, 1) = swarm(i, 1, 1); % update best x positions,

swarm(i, 3, 2) = swarm(i, 1, 2); % update best y positions

swarm(i, 4, 1) = val; % dan update best value

end

end

[temp, gbest] = min(swarm(:, 4, 1)); % global best position

for i = 1 : swarm_size

swarm(i, 2, 1) = rand*inertia*swarm(i, 2, 1) + correction_factor*rand*(swarm(i, 3, 1) - swarm(i, 1, 1)) + correction_factor*rand*(swarm(gbest, 3, 1) - swarm(i, 1, 1)); %x velocity component

swarm(i, 2, 2) = rand*inertia*swarm(i, 2, 2) + correction_factor*rand*(swarm(i, 3, 2) - swarm(i, 1, 2)) + correction_factor*rand*(swarm(gbest, 3, 2) - swarm(i, 1, 2)); %y velocity component

end

clf 

plot(swarm(:, 1, 1), swarm(:, 1, 2), 'x') % gambar pergerakan swarm

axis([-30 30 -30 30]);

pause(0.5)

end