Algoritma BSA (Backtracking Search Algorithm)

Algoritma BSA (Backtracking Search 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.
Backtracking adalah istilah untuk mencari solusi dengan cara membuat calon solusi baru secara terus menerus, dan calon solusi yang lebih baik akan menggantikan solusi yang sudah dianggap tidak dapat menghasilkan solusi yang lebih baik.

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 ukuran populasi yang digunakan
Diasumsikan dalam kasus ini, ukuran populasi adalah 20

ukuranPopulasi = 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
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;

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses perhitungan dengan metode BSA (Backtracking Search Algorithm)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 4)

[posisiTerbaik,nilaiFungsiTerbaik] = BSA( ...
    ukuranPopulasi, jumlahIterasi, jumlahDimensi, Lb, Ub);

Memasuki perhitungan pada fungsi BSA

1. Lakukan inisialisasi individu populasi pada posisi acak,
Kemudian hitung nilai fungsi pada posisi tersebut
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini

for i = 1:ukuranPopulasi,
    posisi(i,:) = Lb + (Ub-Lb).* rand(1,jumlahDimensi);
    nilaiFungsi(i) = HitungNilaiFungsi(posisi(i,:));
end

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

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

2. Catat posisi terbaik dengan nilai fungsi tertinggi sementara

[nilaiFungsiTerbaik,I] = max(nilaiFungsi);
posisiTerbaik = posisi(I,:);

3. Lakukan inisialisasi posisi acak pada populasi dummy
Populasi ini akan digunakan untuk menghitung populasi anak pada setiap perulangan

for i = 1:ukuranPopulasi,
    posisiDummy(i,:) = Lb + (Ub-Lb).* rand(1,jumlahDimensi);
end

4. Lakukan perhitungan sebanyak jumlah iterasi (poin 4a – 4i)

for iterasi = 1:jumlahIterasi,
. . .

4a. Tentukan nilai acak antara 0 sampai dengan 1
Jika nilai acak ini kurang dari 0.5,
%maka posisi populasi sebenarnya akan menggantikan nilai posisi populasi dummy

if rand < 0.5, posisiDummy = posisi; end;

4b. Lakukan pengacakan urutan posisi individu dalam populasi dummy

posisiDummy=posisiDummy(randperm(ukuranPopulasi),:);

4c. Tentukan faktor skala untuk digunakan dalam perhitungan posisi anak
faktor skala dapat dihitung menggunakan metode Brownian, invers distribusi gamma, atau distribusi Levy
Dalam kasus ini akan digunakan metode Brownian yang paling standar

faktorSkala = 3 * randn;        % STANDARD brownian

4d. Lakukan pemetaaan posisi dimensi yang akan digunakan untuk menghitung posisi anak
Posisi pada dimensi acak tertentu akan bernilai 1,
dan nantinya posisi tersebut akan dikalikan dengan faktor skala untuk mendapatkan nilai sebenarnya

map=zeros(ukuranPopulasi,jumlahDimensi);
if rand < 0.5,
	for i=1:ukuranPopulasi,  
		u=randperm(jumlahDimensi); 
		map(i,u(1:ceil(rand*jumlahDimensi)))=1; 
	end
else
	for i=1:ukuranPopulasi,  
		map(i,randi(jumlahDimensi))=1; 
	end
end

4e. Hitung posisi anak dengan rumus:
posisi anak = pop + (map * F) * (selisih populasi dummy dan populasi sebenarnya)

posisiAnak = posisi + (map.*faktorSkala) .* (posisiDummy-posisi);

4f. Jika posisi anak tersebut ternyata diluar batas yang diperbolehkan,
maka kembalikan posisinya agar masuk dalam batas tersebut
Kemudian hitung nilai fungsi pada posisi yang baru

for i=1:ukuranPopulasi
	tmpPosisi=posisiAnak(i,:);

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

	posisiAnak(i,:)=tmpPosisi;

	nilaiFungsiAnak(i) = HitungNilaiFungsi(posisiAnak(i,:));
end

4g. Bandingkan nilai fungsi antara populasi anak dengan populasi sebenarnya
Cari indeks dimana populasi anak memiliki nilai fungsi lebih tinggi dari nilai fungsi populasi sebenarnya
Ganti semua posisi dan nilai fungsi dari populasi sebenarnya pada indeks tersebut sesuai dengan posisi dan nilai fungsi pada populasi anak

idxLebihBaik = nilaiFungsiAnak>nilaiFungsi;
nilaiFungsi(idxLebihBaik) = nilaiFungsiAnak(idxLebihBaik);    
posisi(idxLebihBaik,:) = posisiAnak(idxLebihBaik,:);

4h. Hitung nilai fungsi terbaik yang terdapat pada populasi sebenarnya

[nilaiFungsiPopulasiTerbaik,idxTerbaik]=max(nilaiFungsi);

4i. Jika nilai fungsi tersebut ternyata lebih baik dari nilai fungsi terbaik secara umum,
maka ambil posisi yang baru sebagai posisi yang terbaik

if nilaiFungsiPopulasiTerbaik > nilaiFungsiTerbaik,
	posisiTerbaik = posisi(idxTerbaik,:);
	nilaiFungsiTerbaik = nilaiFungsiPopulasiTerbaik;
end

Hasil akhir adalah:

Algoritma BSA (Backtracking Search 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


Ukuran populasi         = 20
Jumlah maksimal iterasi = 500
Jumlah dimensi          = 2
Batas minimal posisi    = -2
Batas maksimal posisi   = 2


Iterasi: 2, Posisi terbaik: -0.21662     -0.5898, Nilai Fungsi terbaik: 180.4178
Iterasi: 4, Posisi terbaik: -0.21662     -1.3312, Nilai Fungsi terbaik: 180.5463
Iterasi: 6, Posisi terbaik: -0.12234      -1.221, Nilai Fungsi terbaik: 180.7011
Iterasi: 8, Posisi terbaik: -0.21662     -1.1838, Nilai Fungsi terbaik: 181.1208
Iterasi: 11, Posisi terbaik: -0.36035    -0.72799, Nilai Fungsi terbaik: 181.1709
Iterasi: 13, Posisi terbaik: -0.36035    -0.91613, Nilai Fungsi terbaik: 181.4405
Iterasi: 21, Posisi terbaik: -0.34273    -0.88817, Nilai Fungsi terbaik: 181.5029
Iterasi: 22, Posisi terbaik: -0.23846     -0.9018, Nilai Fungsi terbaik: 181.5859
Iterasi: 25, Posisi terbaik: -0.29795     -0.9018, Nilai Fungsi terbaik: 181.599
Iterasi: 29, Posisi terbaik: -0.29783     -0.9018, Nilai Fungsi terbaik: 181.5991
Iterasi: 30, Posisi terbaik: -0.2531     -0.9018, Nilai Fungsi terbaik: 181.6039
Iterasi: 33, Posisi terbaik: -0.27458    -0.90931, Nilai Fungsi terbaik: 181.6149
Iterasi: 42, Posisi terbaik: -0.26827      -0.927, Nilai Fungsi terbaik: 181.6163
Iterasi: 45, Posisi terbaik: -0.27043      -0.927, Nilai Fungsi terbaik: 181.6164
Iterasi: 64, Posisi terbaik: -0.26909    -0.92391, Nilai Fungsi terbaik: 181.6165
Iterasi: 71, Posisi terbaik: -0.27043     -0.9227, Nilai Fungsi terbaik: 181.6165
Iterasi: 102, Posisi terbaik: -0.27083    -0.92298, Nilai Fungsi terbaik: 181.6165
Iterasi: 112, Posisi terbaik: -0.27083     -0.9231, Nilai Fungsi terbaik: 181.6165
Iterasi: 134, Posisi terbaik: -0.27083    -0.92302, Nilai Fungsi terbaik: 181.6165
Iterasi: 139, Posisi terbaik: -0.27083    -0.92306, Nilai Fungsi terbaik: 181.6165
Iterasi: 144, Posisi terbaik: -0.27083    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 148, Posisi terbaik: -0.27084    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 155, Posisi terbaik: -0.27085    -0.92303, Nilai Fungsi terbaik: 181.6165
Iterasi: 168, Posisi terbaik: -0.27085    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 181, Posisi terbaik: -0.27085    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 183, Posisi terbaik: -0.27084    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 190, Posisi terbaik: -0.27085    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 200, Posisi terbaik: -0.27084    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 201, Posisi terbaik: -0.27084    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 206, Posisi terbaik: -0.27084    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 210, Posisi terbaik: -0.27084    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 216, Posisi terbaik: -0.27084    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 219, Posisi terbaik: -0.27084    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 224, Posisi terbaik: -0.27084    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 239, Posisi terbaik: -0.27084    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 255, Posisi terbaik: -0.27084    -0.92304, Nilai Fungsi terbaik: 181.6165
Iterasi: 264, Posisi terbaik: -0.27084    -0.92304, Nilai Fungsi terbaik: 181.6165


Posisi Terbaik: -0.27084    -0.92304
Nilai Fungsi Terbaik =181.6165

Contoh modul / source code menggunakan Matlab dapat didownload disini:

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.