I. Pendahuluan
Hidup ini tidak ada yang ideal begitulah pepatah
hidup yang selama ini sering kita dengar. Di dalam hidup, kita hanya bisa
melakukan yang terbaik untuk hari ini dengan segala keterbatasan yang kita
miliki. Dengan kata lain, sebagai manusia kita hanya bisa melakukan optimasi
dengan harapan hari ini akan lebih baik dari hari kemarin dan hari esok akan
lebih baik dari hari ini. Sama halnya dengan Particle Swarm Optimization yang
nanti akan kita bahas.
Particle Swarm Optimization adalah salah satu
metode optimasi yang 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.
Particle Swarm Optimization atau yang kita kenal
dengan PSO menerapkan sifat masing-masing individu dalam satu kelompok besar.
Kemudian menggabungkan sifat-sifat tersebut untuk menyelesaikan permasalahan.
Particle Swarm Optimization pertama kali dimunculkan pada tahun 1995, sejak
saat itulah para peneliti banyak menurunkan dan mengembangkan metode PSO.
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.
Particle Swarm Optimization memiliki kesamaan sifat
dengan teknik komputasi seperti Algoritma Genetika (Genetic Algorithm). Sistem
PSO diinisialisasi oleh sebuah populasi solusi secara acak dan selanjutnya
mencari titik optimum dengan cara meng-update tiap hasil pembangkitan. Metode
optimasi yang didasarkan pada swarm intelligence ini disebut algoritma
behaviorally inspired sebagai alternatif dari algoritma genetika, yang sering
disebut evolution-based procedures. Dalam konteks optimasi multivariabel,
kawanan diasumsikan mempunyai ukuran tertentu atau tetap dengan setiap partikel
posisi awalnya terletak di suatu lokasi yang acak dalam ruang multidimensi.
Setiap partikel diasumsikan memiliki dua karakteristik: posisi dan kecepatan.
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.
Sebagai contoh, misalnya perilaku burung-burung
dalam dalam kawanan burung. Meskipun setiap burung mempunyai keterbatasan dalam
hal kecerdasan, biasanya ia akan mengikuti kebiasaan (rule) seperti berikut :
1. Seekor burung tidak berada terlalu dekat dengan
burung yang lain
2. Burung tersebut akan mengarahkan terbangnya ke
arah rata-rata keseluruhan burung
3. 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:
1. Kohesi - terbang bersama
2. Separasi - jangan terlalu dekat
3. Penyesuaian(alignment) - mengikuti arah bersama
Jadi PSO dikembangkan dengan berdasarkan pada model
berikut:
1. Ketika seekor burung mendekati target atau
makanan (atau bisa mnimum atau maximum suatu fungsi tujuan) secara cepat
mengirim informasi kepada burung-burung yang lain dalam kawanan tertentu
2. Burung yang lain akan mengikuti arah menuju ke
makanan tetapi tidak secara langsung
3. Ada komponen yang tergantung pada pikiran setiap
burung, yaitu memorinya tentang apa yang sudah dilewati pada waktu sebelumnya.
Model ini akan disimulasikan dalam ruang dengan
dimensi tertentu dengan sejumlah iterasi sehingga di setiap iterasi, posisi
partikel akan semakin mengarah ke target yang dituju (minimasi atau maksimasi
fungsi). Ini dilakukan hingga maksimum iterasi dicapai atau bisa juga digunakan
kriteria penghentian yang lain.
II. Implementasi
Berikut ini adalah contoh implementasi algoritma PSO dalam JAVA :
Misal fungsi yang harus diminimalkan adalah sebagai berikut:
$ latex f (x, y) = (2,8125-x + xy ^ 4) ^ 2 + (2,25-x + xy ^ 2) ^ 2 +
(1,5-x + xy) ^ 2 $
Dengan kendala berikut: $ latex
1 <= x <= 4; -1 <= y <= 1 $
Untuk mengatasi masalah tersebut dengan menggunakan PSO, kita akan
membutuhkan kelas-kelas:
Posisi : untuk
mewakili bagian Posisi partikel
Kecepatan : untuk
mewakili bagian Kecepatan partikel
Partikel :
partikel itu sendiri
SimplePSO : kontrol utama
dari program ini
PSOConstants : sebuah antarmuka
untuk menentukan parameter yang digunakan dalam PSO
Kita harus menyediakan dua-dimensi posisi dan kecepatan.
>> Untuk Posisi (Position):
public class Position {
private double x;
private double y;
public Position(double x, double y) {
this.x = x;
this.y = y;
}
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}
}
>> Untuk Kecepatan (Velocity)
public class Velocity {
private double x;
private double y;
public Velocity(double x, double y) {
this.x = x;
this.y = y;
}
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}
}
>> Untuk Partikel
public class Particle {
private Position location;
private Velocity velocity;
private double fitness;
public double getFitness() {
calculateFitness();
return fitness;
}
public void calculateFitness() {
double x = this.location.getX();
double y = this.location.getY();
fitness = Math.pow((2.8125 - x + x * Math.pow(y, 4)), 2) +
Math.pow((2.25 - x + x * Math.pow(y, 2)), 2) +
Math.pow((1.5 - x + x * y), 2);
}
public Position getLocation() {
return location;
}
public void setLocation(Position location) {
this.location = location;
}
public Velocity getVelocity() {
return velocity;
}
public void setVelocity(Velocity velocity) {
this.velocity = velocity;
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////
Perhatikan metode calculateFitness (), itu adalah tempat untuk menaruh
evaluasi fungsi. Di kelas ini, kita akan membutuhkan beberapa metode:
- initializeSwarm () = untuk
menginisialisasi kawanan digunakan dalam metode
- mengeksekusi () = bagian utama dari proses
>> Untuk Parsial
private void initializeSwarm() {
Particle p;
Random generator = new Random();
for (int i = 0; i < SWARM_SIZE; i++) {
p = new Particle();
double posX = generator.nextDouble() * 3.0 + 1.0;
double posY = generator.nextDouble() * 2.0 - 1.0;
p.setLocation(new Position(posX, posY));
double velX = generator.nextDouble() * 2.0 - 1.0;
double velY = generator.nextDouble() * 2.0 - 1.0;
p.setVelocity(new Velocity(velX, velY));
swarm.add(p);
}
}
public void execute() {
Random generator = new Random();
initializeSwarm();
evolutionaryStateEstimation();
int t = 0;
double w;
while (t < MAX_ITERATION) {
// calculate corresponding f(i,t) corresponding to location x(i,t)
calculateAllFitness();
// update pBest
if (t == 0) {
for (int i = 0; i < SWARM_SIZE; i++) {
pBest[i] = fitnessList[i];
pBestLoc.add(swarm.get(i).getLocation());
}
} else {
for (int i = 0; i < SWARM_SIZE; i++) {
if (fitnessList[i] < pBest[i]) {
pBest[i] = fitnessList[i];
pBestLoc.set(i, swarm.get(i).getLocation());
}
}
}
int bestIndex = getBestParticle();
// update gBest
if (t == 0 || fitnessList[bestIndex] < gBest) {
gBest = fitnessList[bestIndex];
gBestLoc = swarm.get(bestIndex).getLocation();
}
w = W_UP - (((double) t) / MAX_ITERATION) * (W_UP - W_LO);
for (int i = 0; i < SWARM_SIZE; i++) {
// update particle Velocity
double r1 = generator.nextDouble();
double r2 = generator.nextDouble();
double lx = swarm.get(i).getLocation().getX();
double ly = swarm.get(i).getLocation().getY();
double vx = swarm.get(i).getVelocity().getX();
double vy = swarm.get(i).getVelocity().getY();
double pBestX = pBestLoc.get(i).getX();
double pBestY = pBestLoc.get(i).getY();
double gBestX = gBestLoc.getX();
double gBestY = gBestLoc.getY();
double newVelX = (w * vx) + (r1 * C1) * (pBestX - lx) + (r2 * C2) *
(gBestX - lx);
double newVelY = (w * vy) + (r1 * C1) * (pBestY - ly) + (r2 * C2) *
(gBestY - ly);
swarm.get(i).setVelocity(new Velocity(newVelX, newVelY));
// update particle Location
double newPosX = lx + newVelX;
double newPosY = ly + newVelY;
swarm.get(i).setLocation(new Position(newPosX, newPosY));
}
t++;
}
}
}
>> Antarmuka untuk menyimpan konstanta
public interface PSOConstans {
int SWARM_SIZE = 30;
int DIMENSION = 2;
int MAX_ITERATION = 300;
double C1 = 2.0;
double C2 = 2.0;
double W_UP = 1.0;
double W_LO = 0.0;
}
>>
Hasil setelah program dijalankan
Seperti
yang bisa kita lihat dari hasilnya, program menemukan solusi dari masalah untuk
(x = 3.0 dan y = 0,5) pada iterasi ke 244.Sumber : Dari berbagai sumber :p
 dengan JAVA){kind=link}