Algoritma Particle Swarm Optimization (PSO) dengan JAVA
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
No comments