Algoritma BFO (Bacterial Foraging Optimization) 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.
Bacterial Foraging Optimization adalah teknik probabiltas yang meniru tingkah laku cara pencarian makanan dan reproduksi dari bakteri. Algoritma ini dapat digunakan untuk menyelesaikan permasalahan matematika yang sangat rumit ketika tidak ada pendekatan tertentu yang efektif
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.
* 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
Const minPosisi As Double = -2 Const maksPosisi As Double = 2
* Tentukan ukuran koloni dari bakteri
Ukuran koloni harus genap, karena nantinya akan ada perhitungan bakteri yang bereproduksi menjadi 2
Diasumsikan dalam kasus ini, ukuran koloni adalah 100 bakteri
Const ukuranKoloni As Integer = 100
* Tentukan umur dari masing-masing bakteri
Nantinya akan ada perulangan untuk menjalankan perhitungan tertentu sebanyak umur bakteri
Diasumsikan dalam kasus ini, umur bakteri adalah 20
Const umurBakteri As Integer = 20
* Tentukan jumlah maksimal pergerakan bakteri
Dalam sekali proses pergerakan bakteri, tiap-tiap bakteri dapat berenang untuk berpindah tempat ke arah solusi yang lebih baik
Diasumsikan dalam kasus ini, jumlah maksimal pergerakan bakteri adalah 5 kali,
dan jumlah maksimal jarak pergerakan dalam sekali tempuh adalah 0.05
Const prosesPergerakan As Integer = 5 Const maksPergerakan As Double = 0.05
* Tentukan jumlah proses reproduksi
Dalam sekali proses reproduksi, bakteri akan melakukan reproduksi setelah bergerak dari posisi semula
Bakteri dengan nilai fungsi rendah akan digantikan oleh bakteri dengan nilai fungsi tinggi
Diasumsikan dalam kasus ini, jumlah reproduksi adalah 8 kali
Const prosesReproduksi As Integer = 8
* Tentukan jumlah proses penyebaran
Dalam sekali proses penyebaran bakteri, tiap-tiap bakteri akan memiliki kemungkinan untuk berpindah ke posisi acak
Diasumsikan dalam kasus ini, jumlah proses penyebaran bakteri adalah 4 kali,
dan kemungkinan bakteri untuk berpindah ke posisi acak adalah 25%
Const prosesPenyebaran As Integer = 4 Const kemungkinanPenyebaranPosisiAcak As Double = 0.25
Langkah-langkah penggunaan algoritma ini adalah
1. Inisialisasi nilai awal untuk semua bakteri
Beri posisi acak untuk tiap-tiap bakteri
Kemudian hitung nilai fungsi untuk posisi acak tersebut
Dim koloni As New koloni(ukuranKoloni, dimensi, minPosisi, maksPosisi) For i = 0 To ukuranKoloni - 1 Dim nilai As Double = hitungFungsi(koloni.bakteri(i).posisi) koloni.bakteri(i).nilai = nilai koloni.bakteri(i).nilaiSebelumnya = nilai Next i
* Gunakan fungsi ini untuk menghitung nilai fungsi yang diinginkan
Fungsi yang diketahui adalah fungsi Himmelblau, dengan rumus f(x, y) = (x^2+y-11)^2 + (x+y^2-7)^2
Private Function hitungFungsi(ByVal posisi() As Double) As Double Dim result As Double = Math.Pow(posisi(0) * posisi(0) + posisi(1) - 11, 2) + Math.Pow(posisi(0) + posisi(1) * posisi(1) - 7, 2) Return result End Function
2. Cari posisi bakteri dengan nilai fungsi terbaik
Dim nilaiTerbaik As Double = koloni.bakteri(0).nilai Dim indeksTerbaik As Integer = 0 For i = 0 To ukuranKoloni - 1 If koloni.bakteri(i).nilai > nilaiTerbaik Then nilaiTerbaik = koloni.bakteri(i).nilai indeksTerbaik = i End If Next i Dim posisiTerbaik(dimensi - 1) As Double koloni.bakteri(indeksTerbaik).posisi.CopyTo(posisiTerbaik, 0)
3. Lakukan proses pergerakan bakteri
Tentukan kemungkinan arah bakteri akan jatuh pada masing-masing nilai x dan y
Dim arahJatuh(dimensi - 1) As Double For p = 0 To dimensi - 1 arahJatuh(p) = 2.0 * random.NextDouble - 1.0 Next p Dim jumlahKuadratarahJatuh As Double = 0.0 For p = 0 To dimensi - 1 jumlahKuadratarahJatuh += (arahJatuh(p) * arahJatuh(p)) Next p
4. Lakukan pergerakan ke arah bakteri jatuh sepanjang nilai random pergerakan * nilai maksimal pergerakan
For p = 0 To dimensi - 1 koloni.bakteri(i).posisi(p) += (maksPergerakan * arahJatuh(p)) / jumlahKuadratarahJatuh If koloni.bakteri(i).posisi(p) < minPosisi Then koloni.bakteri(i).posisi(p) = minPosisi ElseIf koloni.bakteri(i).posisi(p) > maksPosisi Then koloni.bakteri(i).posisi(p) = maksPosisi End If Next p
5. Cari nilai fungsi dari posisi yang baru
Jika nilai fungsi dari posisi yang baru lebih dari nilai terbaik, maka ambil posisi ini sebagai posisi terbaik
koloni.bakteri(i).nilaiSebelumnya = koloni.bakteri(i).nilai
koloni.bakteri(i).nilai = hitungFungsi(koloni.bakteri(i).posisi)
koloni.bakteri(i).totalNilai += koloni.bakteri(i).nilai
If koloni.bakteri(i).nilai > nilaiTerbaik Then
s = ""
For x As Integer = 0 To dimensi - 1
s &= IIf(s <> "", " ", "") & koloni.bakteri(i).posisi(x).ToString("F4")
Next
Console.WriteLine("Perulangan #" & counterWaktu & ", bakteri #" & i & " [" & s & "] dengan nilai fungsi = " & koloni.bakteri(i).nilai.ToString("F4"))
nilaiTerbaik = koloni.bakteri(i).nilai
koloni.bakteri(i).posisi.CopyTo(posisiTerbaik, 0)
End If
6. Lakukan pergerakan ke arah jatuh yang sama jika belum melewati batas jumlah pergerakan dan nilai posisi baru masih lebih dari nilai posisi sebelumnya
Kemudian hitung nilai fungsi yang baru untuk setiap kali bergerak ke posisi yang baru
Jika nilai fungsi dari posisi yang baru lebih dari nilai terbaik, maka ambil posisi ini sebagai posisi terbaik
Dim iPergerakan As Integer = 0
Do While iPergerakan < prosesPergerakan AndAlso koloni.bakteri(i).nilai > koloni.bakteri(i).nilaiSebelumnya
iPergerakan += 1
For p = 0 To dimensi - 1
koloni.bakteri(i).posisi(p) += (maksPergerakan * arahJatuh(p)) / jumlahKuadratarahJatuh
If koloni.bakteri(i).posisi(p) < minPosisi Then
koloni.bakteri(i).posisi(p) = minPosisi
ElseIf koloni.bakteri(i).posisi(p) > maksPosisi Then
koloni.bakteri(i).posisi(p) = maksPosisi
End If
Next p
koloni.bakteri(i).nilaiSebelumnya = koloni.bakteri(i).nilai
koloni.bakteri(i).nilai = hitungFungsi(koloni.bakteri(i).posisi)
If koloni.bakteri(i).nilai > nilaiTerbaik Then
s = ""
For x As Integer = 0 To dimensi - 1
s &= IIf(s <> "", " ", "") & koloni.bakteri(i).posisi(x).ToString("F4")
Next
Console.WriteLine("Perulangan #" & counterWaktu & ", bakteri #" & i & " [" & s & "] dengan nilai fungsi = " & koloni.bakteri(i).nilai.ToString("F4"))
nilaiTerbaik = koloni.bakteri(i).nilai
koloni.bakteri(i).posisi.CopyTo(posisiTerbaik, 0)
End If
Loop
7. Lakukan proses pergerakan (poin 3 sampai dengan 6) sebanyak jumlah umur bakteri
8. Lakukan proses reproduksi bakteri
Urutkan bakteri dari nilai terendah ke nilai tertinggi
Buang setengah dari total bakteri dengan nilai terendah, kemudian lakukan proses reproduksi, yaitu gandakan semua bakteri dengan nilai tertinggi
Array.Sort(koloni.bakteri) For left As Integer = 0 To ukuranKoloni \ 2 - 1 Dim right = left + ukuranKoloni \ 2 koloni.bakteri(right).posisi.CopyTo(koloni.bakteri(left).posisi, 0) koloni.bakteri(left).nilai = koloni.bakteri(right).nilai koloni.bakteri(left).nilaiSebelumnya = koloni.bakteri(right).nilaiSebelumnya koloni.bakteri(left).totalNilai = koloni.bakteri(right).totalNilai Next left
9. Lakukan proses pergerakan dan reproduksi bakteri (poin 3 sampai dengan 8) sebanyak jumlah proses reproduksi
10. Lakukan proses penyebaran bakteri ke posisi acak
Ambil sebuah nilai acak
Jika nilai acak ini kurang dari nilai kemungkinan penyebaran bakteri (<= 25%), maka lakukan proses penyebaran bakteri ke posisi acak
Kemudian hitung nilai fungsi yang baru untuk posisi yang baru
Jika nilai fungsi dari posisi yang baru lebih dari nilai terbaik, maka ambil posisi ini sebagai posisi terbaik
Dim prob As Double = random.NextDouble If prob < kemungkinanPenyebaranPosisiAcak Then For p = 0 To dimensi - 1 Dim x As Double = (maksPosisi - minPosisi) * random.NextDouble + minPosisi koloni.bakteri(i).posisi(p) = x Next p Dim nilai As Double = hitungFungsi(koloni.bakteri(i).posisi) koloni.bakteri(i).nilai = nilai koloni.bakteri(i).nilaiSebelumnya = nilai koloni.bakteri(i).totalNilai = 0.0 If koloni.bakteri(i).nilai > nilaiTerbaik Then s = “” For x As Integer = 0 To dimensi – 1 s &= IIf(s <> “”, ” “, “”) & koloni.bakteri(i).posisi(x).ToString(“F4”) Next Console.WriteLine(“Perulangan #” & counterWaktu & “, bakteri #” & i & ” [” & s & “] dengan nilai fungsi = ” & koloni.bakteri(i).nilai.ToString(“F4”)) nilaiTerbaik = koloni.bakteri(i).nilai koloni.bakteri(i).posisi.CopyTo(posisiTerbaik, 0) End If End If
11. Lakukan proses pergerakan, reproduksi, dan penyebaran bakteri (poin 3 sampai dengan 10) sebanyak jumlah proses penyebaran
Hasil akhir adalah: (klik untuk perbesar gambar)
Dapat dilihat bahwa hasil akhir perhitungan tidak sama dengan x = -0.270845, and y = -0.923039, tetapi sangat mendekati posisi tersebut. Jika ingin mendapatkan jawaban yang lebih mirip lagi, maka silahkan lakukan penambahan jumlah iterasi, dengan resiko bahwa perhitungan yang dilakukan akan semakin lama.
Contoh modul / source code dalam bahasa VB (Visual Basic) 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.