Algoritma SFLA (Shuffled Frog Leaping Algorithm)

Algoritma SFLA (Shuffled Frog Leaping 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 maksimal.
Analogi dari istilah “Frog Leap” juga digunakan dalam permainan tradisional. Orang pertama akan membungkukan diri, kemudian orang kedua yang berada dibelakang orang pertama akan menggunakan punggung orang pertama untuk melompati orang pertama tersebut. Selanjutnya orang kedua akan membungkukan diri, kemudian orang pertama akan menggunakan punggung orang kedua untuk melompati orang kedua tersebut. Demikian seterusnya sampai permainan dihentikan. Dalam kasus ini, anak dari sebuah induk akan melompati induk tersebut menuju solusi terbaik.

Diasumsikan ada sebaran titik 2 dimensi antara -2 sampai dengan 2
Fungsi yang diketahui adalah fungsi Himmelblau, dengan rumus f(x, y) = (x^2+y-11)^2 + (x+y^2-7)^2
Tentukan posisi dimana fungsi tersebut mengembalikan nilai maksimal

Fungsi Himmelblau adalah salah satu fungsi yang dapat digunakan untuk mengoptimasi suatu permasalahan. Fungsi ini memiliki sebuah nilai maksimum pada x = -0.270845, and y = -0.923039 dengan nilai fungsi sebesar f(x,y) = 181.617, dengan asumsi bahwa rentang minimal dan maksimal dari sebaran titik adalah -2 sampai dengan 2

Grafik fungsi Himmelblau yang normal, atau untuk sebaran titik tak terbatas adalah sebagai berikut.

Sedangkan Grafik fungsi Himmelblau untuk sebaran titik dengan rentang minimal -2 dan maksimal 2 adalah sebagai berikut.

Dapat dilihat bahwa pada gambar tersebut, didapatkan area dengan titik tertinggi (berwarna merah) berada pada area x = -0, and y = -1, dimana titik tersebut mengembalikan nilai fungsi tertinggi. Oleh sebab itu digunakan algoritma ini untuk mencari titik di area berwarna merah tersebut.

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* 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
Jika tidak ada batasan posisi, tentu saja posisi yang mendekati tak terhingga akan terpilih karena akan mengembalikan nilai fungsi yang sangat besar
Diasumsikan dalam kasus ini, posisi minimal adalah -2, dan posisi maksimal adalah +2

minPosisi = -2;
maksPosisi = 2;

* Tentukan jumlah kelompok individu yang digunakan
Nantinya nilai ini akan digunakan untuk menghitung ukuran populasi
Diasumsikan dalam kasus ini, jumlah individu adalah 10

jumlahKelompok = 10;

* Tentukan jumlah individu yang digunakan dalam masing-masing kelompok
Nilai minimal yang diperbolehkan adalah sesuai dengan jumlah dimensi yang digunakan, tetapi boleh lebih dari itu
Nantinya nilai ini akan digunakan untuk menghitung ukuran populasi dan jumlah induk dalam kelompok tersebut
Diasumsikan dalam kasus ini, jumlah individu adalah 5

jumlahIndividuPerKelompok = 5;

* Tentukan alpha, yaitu jumlah anak yang dihasilkan dari induk
Diasumsikan dalam kasus ini, nilai alpha adalah 3

alpha = 3;

* Tentukan beta, yaitu jumlah maksimal iterasi dalam sekali proses FLA
Diasumsikan dalam kasus ini, nilai beta adalah 5

beta = 5;

* Tentukan sigma, yaitu nilai step yang dilakukan individu
Diasumsikan dalam kasus ini, nilai sigma adalah 2

sigma = 2;

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses perhitungan dengan metode SFLA (Shuffled Frog Leaping Algorithm)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 2)

[posisiTerbaik,nilaiFungsiTerbaik] = SFLA( ...
    jumlahIterasi, jumlahDimensi, minPosisi, maksPosisi, ...
    jumlahKelompok, jumlahIndividuPerKelompok, alpha, beta, sigma);

Memasuki perhitungan pada fungsi SFLA

* Memasuki proses inisialisasi parameter, matriks, dan variabel yang digunakan (poin 1a – 1g)

1a. Tentukan dimensi ukuran matriks yang digunakan
Dalam kasus ini, matriks ukuran dimensi akan berisi data dengan jumlah baris 1 dan jumlah kolom sebanyak parameter dimensi

ukuranDimensi = [1 jumlahDimensi];

1b. Hitung ukuran populasi yang digunakan

ukuranPopulasi = jumlahIndividuPerKelompok * jumlahKelompok;

1c. Lakukan pengurutan indeks individu dalam masing-masing kelompok, yang disimpan ke dalam matriks indeks (I)
Jika ukuran populasi adalah 6 dan memiliki 2 kelompok, maka proses ini akan menghasilkan matriks dengan nilai
I = [1 3 5]
[2 4 6]

I = reshape(1:ukuranPopulasi, jumlahKelompok, []);

1d. Hitung parameter q, yaitu jumlah induk dalam masing-masing kelompok

q = max(round(0.3 * jumlahIndividuPerKelompok), 2);

1e. Lakukan inisialisasi posisi dan nilai fungsi pada individu baru sebanyak ukuran populasi
Beri nilai posisi dengan posisi acak, dan hitung nilai fungsi pada posisi acak tersebut

individuBaru.Posisi=[];
individuBaru.NilaiFungsi=[];

populasi=repmat(individuBaru,ukuranPopulasi,1);
for i=1:ukuranPopulasi
    populasi(i).Posisi = unifrnd(minPosisi, maksPosisi, ukuranDimensi);
    populasi(i).NilaiFungsi = HitungNilaiFungsi(populasi(i).Posisi);
end

* Gunakan fungsi ini untuk menghitung fitness dengan rumus:
f(x, y) = (x ^ 2 + y – 11) ^ 2 + (x + y ^ 2 – 7) ^ 2

function z = HitungFitness(u)
z = (u(1)^2 + u(2) - 11) ^ 2 + (u(1) + u(2)^2 - 7) ^ 2;

1f. Urutkan populasi berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

daftarNilaiFungsi = [populasi.NilaiFungsi];
[~, idxTerurut]=sort(daftarNilaiFungsi, 'descend');
populasi = populasi(idxTerurut);

1g. Ambil individu terbaik sebagai posisi terbaik sementara

posisiTerbaik=populasi(1).Posisi;
nilaiFungsiTerbaik=populasi(1).NilaiFungsi;

* Lakukan proses pencarian posisi terbaik (poin 2)

2. Lakukan perhitungan sebanyak jumlah iterasi (poin 2a – 2d)

for i=1:jumlahIterasi    
. . .

2a. Lakukan inisialisasi daftar kelompok yang digunakan sebanyak parameter jumlah kelompok

daftarKelompok = cell(jumlahKelompok, 1);

2b. Lakukan perhitungan sebanyak jumlah kelompok (poin 2b1 – 2b3)

for j = 1:jumlahKelompok
. . .

2b1. Ambil kelompok dalam populasi dengan indeks populasi sesuai dengan urutan dalam matriks indeks (I)

daftarKelompok{j} = populasi(I(j,:));

2b2. Lakukan proses perhitungan dengan metode FLA (Frog Leaping Algorithm)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 2b2a – 2b2b)

daftarKelompok{j} = FLA(daftarKelompok{j}, posisiTerbaik, nilaiFungsiTerbaik, ...
						minPosisi, maksPosisi, q, alpha, beta, sigma);

Memasuki perhitungan pada fungsi FLA

* Memasuki proses inisialisasi parameter, matriks, dan variabel yang digunakan (poin 2b2a)

2b2a1. Hitung ukuran populasi yang digunakan dalam fungsi ini,
yaitu sebanyak ukuran dari parameter populasi

ukuranPopulasi = numel(populasi);

2b2a2. Hitung probabilitas seleksi pada populasi ini

P = 2*(ukuranPopulasi+1-(1:ukuranPopulasi))/(ukuranPopulasi*(ukuranPopulasi+1));

2b2a3. Hitung nilai minimal dan nilai maksimal dari posisi yang terdapat dalam populasi

nilaiPosisiMinimal = populasi(1).Posisi;
nilaiPosisiMaksimal = populasi(1).Posisi;
for i = 2:ukuranPopulasi
    nilaiPosisiMinimal = min(nilaiPosisiMinimal, populasi(i).Posisi);
    nilaiPosisiMaksimal = max(nilaiPosisiMaksimal, populasi(i).Posisi);
end

* Memasuki perhitungan utama dari fungsi FLA (poin 2b2b)

2b2b. Lakukan perhitungan sebanyak parameter beta, yaitu jumlah maksimal iterasi pada fungsi ini (poin 2b2b1 – 2b2b3)

for i = 1:beta
. . .

2b2b1. Lakukan pemilihan induk sebanyak parameter q, yaitu jumlah induk dalam populasi
Pemilihan induk dilakukan secara acak
Probabilitas masing-masing individu sesuai dengan parameter probabilitas seleksi yang telah ditentukan sebelumnya
dan pastikan tidak ada induk dengan indeks yang sama

daftarIdxInduk = zeros(q,1);
tmpP = P;
for j=1:q
	daftarIdxInduk(j) = randsample(numel(tmpP), 1, true, tmpP);
	tmpP(daftarIdxInduk(j)) = 0;
end
daftarInduk = populasi(daftarIdxInduk);

* Berikut adalah proses untuk menghasilkan anak dari induk yang sudah terpilih (poin 2b2b2)

2b2b2. Lakukan perhitungan sebanyak parameter alpha, yaitu jumlah anak yang dihasilkan dari induk (poin 2b2b2a – 2b2b2d)

for k=1:alpha
. . .

2b2b2a. Urutkan daftar induk berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)

daftarNilaiFungsi = [daftarInduk.NilaiFungsi];
[~, idxTerurut]=sort(daftarNilaiFungsi, 'descend');
daftarIdxInduk = daftarIdxInduk(idxTerurut);

* Memasuki proses perbaikan tahap pertama (poin 2b2b2b)

2b2b2b1. Gunakan posisi terburuk sebagai posisi awal solusi baru

SolusiBaru1 = daftarInduk(end);

2b2b2b2. Hitung nilai step dengan rumus:
step = sigma * nilai acak * (posisi induk terbaik – posisi induk terburuk)

Step = sigma*rand(jumlahDimensi).*(daftarInduk(1).Posisi-daftarInduk(end).Posisi);

2b2b2b3. Hitung posisi yang baru dengan menjumlahkan posisi lama dengan nilai step

SolusiBaru1.Posisi = daftarInduk(end).Posisi + Step;

2b2b2b4. Jika posisi baru ternyata diluar batas yang diperbolehkan, maka lanjutkan ke langkah perbaikan tahap kedua
Selain itu, lakukan perhitungan nilai fungsi pada posisi tersebut
Jika nilai fungsi yang baru masih belum lebih baik dari nilai fungsi induk terburuk, maka lanjutkan ke langkah perbaikan tahap kedua
Jika tidak, maka ambil solusi baru ini menggantikan induk pada posisi terburuk

if all(SolusiBaru1.Posisi>=minPosisi) & all(SolusiBaru1.Posisi<=maksPosisi)
	SolusiBaru1.NilaiFungsi = HitungNilaiFungsi(SolusiBaru1.Posisi);
	if SolusiBaru1.NilaiFungsi

* Lakukan proses perbaikan tahap kedua apabila salah satu kondisi sebelumnya terpenuhi (poin 2b2b2c)
if Perbaikan2
. . .

2b2b2c1. Gunakan posisi terburuk sebagai posisi awal solusi baru
SolusiBaru2 = daftarInduk(end);

2b2b2c2. Hitung nilai step dengan rumus:

step = sigma * nilai acak * (posisi terbaik - posisi induk terburuk)
Step = sigma*rand(jumlahDimensi).*(posisiTerbaik-daftarInduk(end).Posisi);

2b2b2c3. Hitung posisi yang baru dengan menjumlahkan posisi lama dengan nilai step
SolusiBaru2.Posisi = daftarInduk(end).Posisi + Step;

2b2b2c4. Jika posisi baru ternyata diluar batas yang diperbolehkan, maka lanjutkan ke langkah perbaikan tahap kedua

Selain itu, lakukan perhitungan nilai fungsi pada posisi tersebut

Jika nilai fungsi yang baru masih belum lebih baik dari nilai fungsi induk terburuk, maka lanjutkan ke langkah perbaikan tahap kedua

Jika tidak, maka ambil solusi baru ini menggantikan induk pada posisi terburuk
if all(SolusiBaru2.Posisi>=minPosisi) & all(SolusiBaru2.Posisi<=maksPosisi)
	SolusiBaru2.NilaiFungsi = HitungNilaiFungsi(SolusiBaru2.Posisi);
	if SolusiBaru2.NilaiFungsi

* Lakukan proses penghapusan apabila salah satu kondisi sebelumnya terpenuhi (poin 2b2b2d)
if Penghapusan
. . .

2b2b2d. Beri nilai posisi acak pada posisi induk terburuk

Kemudian hitung nilai fungsi pada posisi tersebut

Jika nilai fungsi pada posisi acak tidak lebih baik dari nilai fungsi induk terburuk,

maka tidak perlu menggunakan posisi acak ini
tmpPosisi = unifrnd(minPosisi, maksPosisi, jumlahDimensi);
tmpNilaiFungsi = HitungNilaiFungsi(tmpPosisi);

if tmpNilaiFungsi > daftarInduk(end).NilaiFungsi
	daftarInduk(end).Posisi = tmpPosisi;
	daftarInduk(end).NilaiFungsi = tmpNilaiFungsi;
end

2b2b3. Lakukan update posisi dan nilai fungsi dari populasi dengan indeks induk yang telah ditentukan sebelumnya
populasi(daftarIdxInduk) = daftarInduk;

2b3. Lakukan update kelompok populasi dengan nilai kelompok yang sudah dihitung sebelumnya
populasi(I(j,:)) = daftarKelompok{j};

2c. Urutkan populasi berdasarkan nilai fungsi terbaik (tertinggi) ke nilai fungsi terburuk (terendah)
daftarNilaiFungsi = [populasi.NilaiFungsi];
[~, idxTerurut]=sort(daftarNilaiFungsi, 'descend');
populasi = populasi(idxTerurut);

2d. Jika nilai fungsi pada populasi yang sedang dihitung lebih baik dari nilai fungsi terbaik

maka ambil posisinya sebagai posisi terbaik
if populasi(1).NilaiFungsi > nilaiFungsiTerbaik
	nilaiFungsiTerbaik = populasi(1).NilaiFungsi;
	posisiTerbaik = populasi(1).Posisi;
end

Hasil akhir adalah:
Algoritma SFLA (Shuffled Frog Leaping Algorithm)
Contoh: Mencari posisi dengan pengembalian nilai fungsi maksimal
Diasumsikan ada sebaran titik 2 dimensi antara -2 sampai dengan 2
Fungsi yang diketahui adalah fungsi Himmelblau, dengan rumus f(x, y) = (x^2+y-11)^2 + (x+y^2-7)^2
Tentukan posisi dimana fungsi tersebut mengembalikan nilai maksimal


Jumlah maksimal iterasi      = 500
Jumlah dimensi               = 2
Batas minimal posisi         = -2
Batas maksimal posisi        = 2
Jumlah Kelompok              = 10
Jumlah individu per kelompok = 5
alpha                        = 3
beta                         = 5
sigma                        = 2


Iterasi: 2, Posisi terbaik: -0.20908    -0.88167, Nilai Fungsi terbaik: 181.5044
Iterasi: 37, Posisi terbaik: -0.29931     -1.0194, Nilai Fungsi terbaik: 181.5097
Iterasi: 76, Posisi terbaik: -0.21728    -0.88377, Nilai Fungsi terbaik: 181.5292
Iterasi: 95, Posisi terbaik: -0.26848     -0.8829, Nilai Fungsi terbaik: 181.6021
Iterasi: 220, Posisi terbaik: -0.28622    -0.89438, Nilai Fungsi terbaik: 181.6063
Iterasi: 230, Posisi terbaik: -0.2817    -0.90887, Nilai Fungsi terbaik: 181.6129


Posisi Terbaik: -0.2817    -0.90887
Nilai Fungsi Terbaik =181.6129

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