Algoritma MOBA (Multi-Objective Bat Algorithm) 2

Algoritma MOBA (Multi-Objective Bat Algorithm) adalah salah satu algoritma optimasi yang dapat digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah mengenai pencarian posisi dengan pengembalian nilai fungsi minimal.
Algoritma ini merupakan pengembangan dari Algoritma BA (Bat Algorithm) yang sudah dijelaskan sebelumnya. Arti dari Multi-Objective itu sendiri adalah fungsi yang digunakan dalam perhitungan nilai ada lebih dari satu, dan biasanya memiliki batasan-batasan wilayah tersendiri agar posisi yang dicari tidak melebar kemana-mana. Analogi yang paling mudah adalah bagaimana caranya membeli barang sebanyak mungkin dengan harga seminimal mungkin, atau bisa juga seperti Permasalahan Knapsack.

Diasumsikan ada sebaran titik 2 dimensi antara -20 sampai dengan 20
Fungsi yang diketahui adalah fungsi Chakong dan Haimes, dimana ada 2 fungsi yang harus dicari nilai minimalnya, yaitu:
F1(x, y) = 2 + (x-2)^2 + (y-1)^2
F2(x, y) = 9x – (y-1)^2;
dan fungsi ini memiliki batasan inputan dimana:
G1(x, y) = x^2 + y^2 <= 225
G2(x, y) = x – 3y + 10 <= 0
Tentukan posisi dimana fungsi tersebut mengembalikan nilai minimal

Grafik fungsi Chakong dan Haimes adalah sebagai berikut.

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah pareto / optimasi yang dilakukan
Jumlah pareto akan mempengaruhi bobot yang digunakan dalam setiap kali perulangan pareto
Diasumsikan dalam kasus ini, jumlah pareto adalah 20

jumlahPareto = 20;

* Tentukan jumlah kelelawar / bat yang digunakan
Nilai yang direkomendasikan adalah 10 sampai dengan 40
Diasumsikan dalam kasus ini, bat yang digunakan adalah 20 ekor

jumlahBat = 20;

* Tentukan jumlah maksimal iterasi yang digunakan
Diasumsikan dalam kasus ini, jumlah maksimal iterasi adalah 500 kali

jumlahIterasi = 500;

* Tentukan jumlah dimensi yang digunakan
Diasumsikan dalam kasus ini, jumlah dimensi adalah 2 karena posisi bunga hanya ditentukan dari 2 sumbu yaitu sumbu x dan y

jumlahDimensi = 2;

* Tentukan posisi minimal dan maksimal dari fungsi yang akan dihitung
Diasumsikan dalam kasus ini, posisi minimal adalah -20, dan posisi maksimal adalah +20

minPosisi = -20;
maksPosisi = 20;

* Tentukan matriks batas bawah dan batas atas posisi pada masing-masing dimensi yang sudah ditentukan sebelumnya
Matriks ini akan digunakan untuk mengecek apakah posisi serangga yang baru masih berada dalam batas yang diperbolehkan

Lb = minPosisi * ones(1,jumlahDimensi);
Ub = maksPosisi * ones(1,jumlahDimensi);

* Tentukan batas minimal dan maksimal frekuensi yang digunakan untuk menghitung kecepatan kelelawar
Diasumsikan dalam kasus ini, frekuensi minimal adalah 0, dan frekuensi maksimal adalah 2

minFrekuensi = 0;
maksFrekuensi = 2;

* Tentukan batas minimal rasio pemancaran getaran kelelawar
Jika sebuah kelelawar terkena pantulan getaran setelah memancarkan getaran, maka posisinya akan sedikit bergeser dari posisi semula
Diasumsikan dalam kasus ini, batas minimal rasio pemancaran getaran adalah 0.5

rasioPemancaranGetaran = 0.5;

* Tentukan batas maksimal Amplitudo / tingkat kebisingan pada saat kelelawar memancarkan getaran
Jika ada solusi yang lebih baik, tetapi posisi tersebut terlalu bising, maka kelelawar tidak akan menuju tempat tersebut
Diasumsikan dalam kasus ini, batas maksimal tingkat kebisingan adalah 0.5

tingkatKebisingan = 0.5;

Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan urutan nilai bobot yang digunakan dalam perhitungan pareto
Nilai urutan adalah secara acak antara 1 sampai dengan jumlahPareto

urutanBobot = randperm(jumlahPareto);

2. Lakukan perhitungan pada masing-masing pareto (poin 2a – 2c)

for i = 1:jumlahPareto,
. . .

2a. Tentukan bobot yang digunakan dalam perulangan ini, yaitu sesuai urutan yang sudah didapatkan sebelumnya

bobot = urutanBobot(i) / jumlahPareto;

2b. Lakukan proses perhitungan dengan metode BA (Bat Algorithm)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 2b1 – 2b3)

[posisiBatTerbaik,nilaiFungsiTerbaik] = BA( ...
    bobot, jumlahBat, jumlahIterasi, jumlahDimensi, Lb, Ub, ...
    minFrekuensi, maksFrekuensi, rasioPemancaranGetaran, tingkatKebisingan);

Memasuki perhitungan pada fungsi BA

2b1. Lakukan inisialisasi kelelawar pada posisi acak,
Kemudian lakukan pengecekan batasan apakah posisi acak tersebut adalah posisi yang valid
Kemudian hitung nilai fungsi pada posisi tersebut
Penjelasan tentang masing-masing fungsi akan dijelaskan pada perhitungan dibawah ini

for i=1:jumlahBat,
    isValid = 0;
    while isValid == 0
        daftarBat(i,:) = Lb + (Ub-Lb) .* rand(1,jumlahDimensi);
        isValid = HitungBatasan(daftarBat(i,:));
    end
        
    nilaiFungsi(i) = HitungNilaiFungsi(bobot, daftarBat(i,:));        
end

* Gunakan fungsi ini untuk menghitung nilai fungsi multi-obyektif
Rumus perhitungan masing-masing fungsi adalah:
F1(x, y) = 2 + (x-2)^2 + (y-1)^2
F2(x, y) = 9x – (y-1)^2;
Nilai akhir diperoleh dengan rumus bobot * f1 + (1 – bobot) * f2

function z = HitungNilaiFungsi(bobot, u)
fx1 = 2 + (u(1) - 2) ^ 2 + (u(2) - 1) ^ 2;
fx2 = 9 * u(1) - (u(2) - 1) ^ 2;
z = bobot * fx1 + (1 - bobot) * fx2;

* Gunakan fungsi ini untuk menghitung batasan inputan apakah masih valid atau tidak
Jika memenuhi batasan-batssan ini, maka inputan tersebut dianggap valid
Rumus batasan yang digunakan adalah
G1(x, y) = x^2 + y^2 <= 225
G2(x, y) = x – 3y + 10 <= 0

function [isValid]=HitungBatasan(u)
isValid = 1;

if u(1) ^ 2 + u(2) ^ 2 > 225, 
    isValid = 0; 
    return;
end;

if u(1) + 3 * u(2) + 10 > 0, 
    isValid = 0; 
    return;
end;

2b2. Catat posisi terbaik dengan nilai fungsi tertinggi sementara

[nilaiFungsiTerbaik,I] = max(nilaiFungsi);
posisiBatTerbaik = daftarBat(I,:);

2b3. Lakukan perhitungan sebanyak jumlah iterasi
Kemudian pada masing-masing iterasi, lakukan perhitungan pada masing-masing kelelawar yang ada (poin 2b3a – 2b3i)

for iterasi = 1:jumlahIterasi, 
	for i = 1:jumlahBat,
	. . .

2b3a. Tentukan nilai acak frekuensi yang digunakan sesuai dengan batas frekuensi yang tersedia

frekuensi(i) = minFrekuensi + (minFrekuensi-maksFrekuensi) * rand;

2b3b. Hitung kecepatan perpindahan kelelawar ke posisi yang baru

kecepatan(i,:) = kecepatan(i,:) + (daftarBat(i,:) - posisiBatTerbaik) * frekuensi(i);

2b3c. Hitung posisi yang baru dari kelelawar tersebut

posisiBatBaru(i,:) = daftarBat(i,:) + kecepatan(i,:);

2b3d. Lakukan pengecekan apakah posisi bat yang baru masih berada dalam batas yang diperbolehkan
Jika posisi yang baru ternyata diluar batas yang diperbolehkan,
maka kembalikan posisinya agar masuk dalam batas tersebut

tmpPosisi=posisiBatBaru(i,:);

I=tmpPosisiUb;
tmpPosisi(J)=Ub(J);

posisiBatBaru(i,:)=tmpPosisi;

2b3e. Tentukan nilai acak untuk dibandingkan dengan parameter rasio pemancaran getaran
Jika nilai acak tersebut lebih dari batas minimal rasio pemancaran getaran,
maka lakukan sedikit pergeseran pada posisi kelelawar tersebut

if rand > rasioPemancaranGetaran
	posisiBatBaru(i,:) = posisiBatTerbaik + 0.001 * randn(1,jumlahDimensi);
end

2b3f. Lakukan pengecekan batasan pada posisi yang baru dihitung
Jika posisi nya dianggap tidak valid,
maka lanjutkan perhitungan ke kelelawar berikutnya
Penjelasan mengenai fungsi HitungBatasan sudah dijelaskan pada perhitungan diatas

[isValid]=HitungBatasan(posisiBatBaru(i,:));
if isValid == 0,
	continue;
end

2b3g. Hitung nilai fungsi pada posisi yang baru

nilaiFungsiBaru = HitungNilaiFungsi(posisiBatBaru(i,:));

2b3h. Tentukan nilai acak untuk dibandingkan dengan parameter tingkat kebisingan
Jika nilai fungsi baru lebih baik dari nilai fungsi terbaik kelelawar tersebut,
dan nilai acak tersebut kurang dari batas maksimal tingkat kebisingan,
maka ambil posisi yang baru sebagai posisi terbaik kelelawar tersebut

if (nilaiFungsiBaru > nilaiFungsi(i)) && (rand

2b3i. Kemudian lakukan perbandingan dengan nilai fungsi terbaik

Jika nilai fungsi baru lebih baik dari nilai fungsi terbaik secara umum,

maka ambil posisi yang baru sebagai posisi yang terbaik
if nilaiFungsiBaru > nilaiFungsiTerbaik,
	posisiBatTerbaik = posisiBatBaru(i,:);
	nilaiFungsiTerbaik = nilaiFungsiBaru;
end

2c. Jika nilai fungsi dari metode BA diatas lebih baik dari nilai fungsi pareto terbaik,

maka ambil bobot dan posisi yang baru sebagai nilai terbaik
if nilaiFungsiTerbaik <= nilaiFungsiParetoTerbaik,
	bobotParetoTerbaik = bobot;
	posisiBatParetoTerbaik = posisiBatTerbaik;
	nilaiFungsiParetoTerbaik = nilaiFungsiTerbaik;
end

Hasil akhir adalah:
Algoritma MOBA (Multi-Objective Bat Algorithm)
Contoh: Mencari posisi dengan pengembalian nilai fungsi minimal
Diasumsikan ada sebaran titik 2 dimensi antara -20 sampai dengan 20
Fungsi yang diketahui adalah fungsi Chakong dan Haimes, dimana ada 2 fungsi yang harus dicari nilai minimalnya, yaitu:
F1(x, y) = 2 + (x-2)^2 + (y-1)^2
F2(x, y) = 9x - (y-1)^2;
dan fungsi ini memiliki batasan inputan dimana: 
G1(x, y) = x^2 + y^2 <= 225
G2(x, y) = x - 3y + 10 <= 0
Tentukan posisi dimana fungsi tersebut mengembalikan nilai minimal


Jumlah Pareto / Optimasi        = 20
Jumlah Kelelawar                = 20
Jumlah maksimal iterasi         = 500
Jumlah dimensi                  = 2
Batas minimal posisi kelelawar  = -20
Batas maksimal posisi kelelawar = 20
Batas minimal frekuensi         = 0
Batas maksimal frekuensi        = 2
Rasio pemancaran getaran        = 0.5
Tingkat kebisingan              = 0.5


Bobot: 0.3, Posisi terbaik: -2.10487     -14.7555, Nilai Fungsi terbaik: -106.8995
Bobot: 0.15, Posisi terbaik: -6.04268     -13.7289, Nilai Fungsi terbaik: -188.0819
Bobot: 0.8, Posisi terbaik: -1.2681     -2.9106, Nilai Fungsi terbaik: 17.0379
Bobot: 0.55, Posisi terbaik: -1.6834     -2.7722, Nilai Fungsi terbaik: 3.1673
Bobot: 0.35, Posisi terbaik: -3.06243     -14.6841, Nilai Fungsi terbaik: -82.0422
Bobot: 0.85, Posisi terbaik: 3.4831     -4.4945, Nilai Fungsi terbaik: 29.4047
Bobot: 0.7, Posisi terbaik: -1.7084     -2.7647, Nilai Fungsi terbaik: 12.083
Bobot: 0.4, Posisi terbaik: -3.81351      -14.507, Nilai Fungsi terbaik: -54.3678
Bobot: 0.25, Posisi terbaik: -3.22116       -14.65, Nilai Fungsi terbaik: -136.8893
Bobot: 0.95, Posisi terbaik: 0.83339     -3.6691, Nilai Fungsi terbaik: 23.1884
Bobot: 0.75, Posisi terbaik: -0.34375     -3.2188, Nilai Fungsi terbaik: 13.7454
Bobot: 0.05, Posisi terbaik: -10.455      -10.756, Nilai Fungsi terbaik: -205.9163
Bobot: 0.1, Posisi terbaik: -3.09172     -14.6779, Nilai Fungsi terbaik: -218.8865
Bobot: 0.2, Posisi terbaik: -7.89501     -12.7541, Nilai Fungsi terbaik: -150.3671
Bobot: 0.9, Posisi terbaik: 1.7962     -3.9332, Nilai Fungsi terbaik: 22.9233
Bobot: 0.65, Posisi terbaik: -0.95543     -3.0149, Nilai Fungsi terbaik: 8.8036
Bobot: 0.45, Posisi terbaik: -3.90997     -14.4814, Nilai Fungsi terbaik: -26.7041
Bobot: 1, Posisi terbaik: -0.3078     -3.2309, Nilai Fungsi terbaik: 25.2265
Bobot: 0.5, Posisi terbaik: -2.5     -7.1277, Nilai Fungsi terbaik: -0.125
Bobot: 0.6, Posisi terbaik: -0.83713     -3.0544, Nilai Fungsi terbaik: 6.3036


Bobot Pareto terbaik: 0.1, Posisi Pareto terbaik: -3.09172     -14.6779, Nilai Fungsi Pareto terbaik: -218.8865

Contoh modul / source code menggunakan Matlab dapat didownload disini:
Download Now!



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga

Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.

Selamat mencoba.
Bagikan ini:
Facebook
Twitter
WhatsApp
Surat elektronik