Algoritma FA (Firefly 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.
Firefly Algorithm adalah salah satu algoritma optimasi yang terinspirasi dari tingkah laku kunang-kunang yang menyala berkedip. Tujuan utama dari perilaku berkedip kunang-kunang tersebut adalah sebagai sinyal untuk menarik kunang-kunang lain menuju dirinya. Kunang-kunang yang menyala lebih terang akan menarik kunang-kunang lain yang menyala kurang terang menuju dirinya
Diasumsikan ada sebaran titik 3 dimensi, yaitu dimensi x, y, z
Masing-masing dimensi memiliki sebuah konstanta dan batas rentang titik yang dapat digunakan
Contoh data pada masing-masing dimensi adalah sebagai berikut
| Dimensi | konstanta | batas minimal | batas maksimal |
|---|---|---|---|
| x | 3.2 | 10 | 50 |
| y | 3 | 30 | 80 |
| z | 2.5 | 50 | 150 |
Contoh data awal adalah sebagai berikut:
Dim data(2)() As Double
data(0) = New Double() {3.2, 10, 50}
data(1) = New Double() {3, 30, 80}
data(2) = New Double() {2.5, 50, 150}
Nilai fungsi yang diketahui adalah dengan rumus f(x, y, z) = (kx * x^2) + (ky * y^2) + (kz * z^2)
Tentukan posisi dimana fungsi tersebut mengembalikan nilai maksimal
Dengan batasan nilai bahwa x + y + z harus bernilai 200
Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah kunang-kunang yang digunakan
Dalam dunia nyata, dalam sekumpulan kunang-kunang biasanya beranggotakan 15 – 40 ekor kunang-kunang
Diasumsikan dalam kasus ini, akan digunakan 15 kunang-kunang untuk mempercepat perhitungan
Const jumlahFirefly As Integer = 15
* Tentukan dimensi permasalahan
Diasumsikan dalam kasus ini, dimensi bernilai 3 karena ada 3 dimensi yang akan dicari solusinya
Const dimensi As Integer = 3
* Tentukan jumlah perulangan dalam perhitungan
Nantinya setiap kunang-kunang akan melakukan perulangan sebanyak ini untuk mencari posisi terbaik
Diasumsikan dalam kasus ini, jumlah perulangan adalah 1000 kali
Const maksEpoch As Integer = 1000
* Tentukan total posisi yang harus dicapai
Semua solusi yang ditemukan oleh kunang-kunang harus berjumlah sebanyak variabel ini
Diasumsikan dalam kasus ini, total nilai yang harus dicapai adalah 160
Const totalPosisi As Integer = 200
Langkah-langkah penggunaan algoritma ini adalah
Lakukan proses pencarian posisi terbaik sebanyak jumlah perulangan
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 1 – 8)
Dim posisiTerbaik() As Integer = prosesPencarianPosisi(jumlahFirefly, dimensi, maksEpoch, data, totalPosisi)
1. Tentukan B0 (base beta), g (gamma), dan a (alpha)
B0 (base beta), g (gamma), dan a (alpha) adalah variabel untuk menghitung tingkat ketertarikan antar kunang-kunang
Nilai-nilai untuk variabel tersebut adalah nilai-nilai yang direkomendasikan pada jurnal penelitian
Const B0 As Double = 1.0 ' base beta (koefisien ketertarikan awal untuk setiap kunang-kunang) Const g As Double = 1.0 ' gamma (koefisien penarik / pengundang kunang-kunang lain) Const a As Double = 2 'alpha
2. Inisialisasi para kunang-kunang yang digunakan sebanyak parameter jumlahFirefly
Dim daftarFirefly(jumlahFirefly - 1) As Firefly
3. Untuk setiap kunang-kunang, Beri nilai posisi acak pada setiap dimensi
Setiap dimensi memiliki batas minimal dan maksimal sendiri-sendiri, sesuai pada isian parameter data
jumlahPosisi = 0 For k As Integer = 0 To dimensi - 1 daftarFirefly(i).posisi(k) = rnd.Next(data(k)(1), data(k)(2)) jumlahPosisi += daftarFirefly(i).posisi(k) Next k
4. Perlu diingat bahwa jumlah posisi diatas belum tentu sesuai dengan parameter totalPosisi
Oleh karena itu, lakukan penyesuaian posisi agar jumlah posisi selalu bernilai sama dengan parameter totalPosisi
Dim selisih As Integer = totalPosisi - jumlahPosisi Dim idx As Integer = rnd.Next(dimensi) Dim posisiBaru As Integer = daftarFirefly(i).posisi(idx) + selisih If posisiBaru < data(idx)(1) Then Continue Do If posisiBaru > data(idx)(2) Then Continue Do jumlahPosisi = jumlahPosisi - daftarFirefly(i).posisi(idx) + posisiBaru daftarFirefly(i).posisi(idx) = posisiBaru
5. Hitung nilai fungsi untuk kunang-kunang pada posisi tersebut
Karena tujuan permasalahan adalah mencari nilai maksimal, maka semakin tinggi nilai fungsi akan semakin baik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini
daftarFirefly(i).nilaiFungsi = nilaiFungsi(daftarFirefly(i).posisi, data)
* Gunakan fungsi ini untuk menghitung nilai fungsi kunang-kunang tersebut
Rumus yang digunakan adalah sesuai dengan rumus yang sudah ditentukan, yaitu
f(x, y, z) = (kx * x^2) + (ky * y^2) + (kz * z^2)
Private Function nilaiFungsi(ByVal posisi() As Integer, ByVal data()() As Double) As Double Dim hasil As Double = 0.0 For i As Integer = 0 To posisi.Length - 1 hasil += data(i)(0) * posisi(i) * posisi(i) Next i Return hasil End Function
6. Hitung nilai intensitas / kekuatan kunang-kunang tersebut untuk menarik kunang-kunang lainnya
Karena tujuan permasalahan adalah mencari nilai maksimal, jika semakin tinggi nilai fungsi, maka semakin tinggi nilai intensitasnya
Rumus untuk menentukan intensitas adalah bebas tergantung kebutuhan
Diasumsikan dalam kasus ini, intensitas dihitung dengan rumus intensitas = nilai fungsi * 2
daftarFirefly(i).intensitas = daftarFirefly(i).nilaiFungsi * 2
7. Lakukan pengecekan apakah kunang-kunang ini berada pada posisi terbaik
If daftarFirefly(i).nilaiFungsi > nilaiFungsiTerbaik Then nilaiFungsiTerbaik = daftarFirefly(i).nilaiFungsi For k As Integer = 0 To dimensi - 1 posisiTerbaik(k) = daftarFirefly(i).posisi(k) Next k indeksPosisiTerbaik = i End If
8. Lakukan proses pencarian posisi terbaik sebanyak jumlah perulangan (poin 8a – 8h)
Variabel i dan j adalah untuk membandingkan setiap kunang-kunang yang ada
Apabila intensitas kunang-kunang i kurang dari kunang-kunang j, maka kunang-kunang i akan bergerak menuju kunang-kunang j
Dim epoch As Integer = 0 Do While epoch < maksEpoch For i As Integer = 0 To jumlahFirefly - 1 For j As Integer = 0 To jumlahFirefly - 1 If daftarFirefly(i).intensitas < daftarFirefly(j).intensitas Then
Jika kondisi pada poin 8. terpenuhi, maka lakukan perhitungan pada poin 8a. sampai dengan 8g.
8a. Hitung jarak posisi antar firefly
Rumus perhitungan jarak dihitung dengan metode Euclidean
contoh kasusnya adalah, apabila kunang-kunang A berdimensi 2 berada pada posisi (3.0, 4.0) dan kunang-kunang B (5.0, 9.0),
maka jaraknya adalah sqrt((5 – 3)^2 + (9 – 4)^2) = sqrt(4 + 25) = sqrt(29) = 5.4
Dim r As Double = 0.0 For k As Integer = 0 To dimensi - 1 r += (daftarFirefly(i).posisi(k) - daftarFirefly(j).posisi(k)) * (daftarFirefly(i).posisi(k) - daftarFirefly(j).posisi(k)) Next k r = Math.Sqrt(r)
8b. Hitung nilai beta menggunakan konstanta base beta, gamma, dan jarak yang sudah ditentukan sebelumnya
Dim beta As Double = B0 * Math.Exp(-g * r * r)
8c. Pindahkan kunang-kunang ini ke posisi yang baru pada setiap dimensinya
daftarFirefly(i).posisi(k) += beta * (daftarFirefly(j).posisi(k) - daftarFirefly(i).posisi(k)) daftarFirefly(i).posisi(k) += a * (rnd.NextDouble() - 0.5)
8d. Perlu diingat bahwa apabila nilai posisi baru melebihi batas nilai minimal dan maksimal pada masing-masing dimensi,
maka kembalikan nilai posisi nya agar kembali dalam rentang nilai pada dimensi tersebut
If daftarFirefly(i).posisi(k) < data(k)(1) Then daftarFirefly(i).posisi(k) = data(k)(1) ElseIf daftarFirefly(i).posisi(k) > data(k)(2) Then daftarFirefly(i).posisi(k) = data(k)(2) End If
8e. Sama seperti perhitungan sebelumnya, jumlah posisi diatas belum tentu sesuai dengan parameter totalPosisi
Oleh karena itu, lakukan penyesuaian posisi agar jumlah posisi selalu bernilai sama dengan parameter totalPosisi
Do While jumlahPosisi <> totalPosisi Dim selisih As Integer = totalPosisi - jumlahPosisi Dim selisihPerDimensi(dimensi - 1) As Integer Dim idx As Integer = -1 Do While selisih <> 0 idx = rnd.Next(dimensi) If selisih > 0 Then If daftarFirefly(i).posisi(idx) + selisihPerDimensi(idx) < data(idx)(2) Then selisihPerDimensi(idx) += 1 selisih -= 1 End If Else If daftarFirefly(i).posisi(idx) + selisihPerDimensi(idx) > data(idx)(1) Then selisihPerDimensi(idx) -= 1 selisih += 1 End If End If Loop For k As Integer = 0 To dimensi - 1 Dim posisiBaru As Integer = daftarFirefly(i).posisi(k) + selisihPerDimensi(k) If posisiBaru < data(k)(1) Then Continue Do If posisiBaru > data(k)(2) Then Continue Do Next For k As Integer = 0 To dimensi - 1 Dim posisiBaru As Integer = daftarFirefly(i).posisi(k) + selisihPerDimensi(k) jumlahPosisi = jumlahPosisi - daftarFirefly(i).posisi(k) + posisiBaru daftarFirefly(i).posisi(k) = posisiBaru Next Loop
8f. Hitung nilai fungsi dan intensitas untuk kunang-kunang ini pada posisi yang baru
daftarFirefly(i).nilaiFungsi = nilaiFungsi(daftarFirefly(i).posisi, data) daftarFirefly(i).intensitas = daftarFirefly(i).nilaiFungsi * 2
8g. Lakukan pengecekan apakah kunang-kunang ini berada pada posisi terbaik
If daftarFirefly(i).nilaiFungsi > nilaiFungsiTerbaik Then nilaiFungsiTerbaik = daftarFirefly(i).nilaiFungsi For k As Integer = 0 To dimensi - 1 posisiTerbaik(k) = daftarFirefly(i).posisi(k) Next k End If
8h. Setelah menyelesaikan perulangan pada poin 8a. sampai dengan 8g, ada 1 langkah optional / tidak wajib yaitu
Urutkan kunang-kunang dari nilai fungsi tertinggi (terbaik) ke terendah (terburuk)
Langkah ini tidak wajib, karena pengurutan data hanya akan sedikit mempercepat proses perhitungan
Array.Sort(daftarFirefly)
* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Firefly untuk menampung semua data kunang-kunang, seperti posisi, nilaiFungsi, dan intensitas kunang-kunang tersebut. Deklarasi Class Firefly adalah sebagai berikut:
Public Class Firefly
'Hanya untuk fitur pengurutan (sort) pada proses perhitungan diatas
'Jika tidak diperlukan, bisa dihilangkan
Implements IComparable(Of Firefly)
Public posisi() As Integer
Public nilaiFungsi As Double
Public intensitas As Double
Public Sub New(ByVal dimensi As Integer)
Me.posisi = New Integer(dimensi - 1) {}
Me.nilaiFungsi = 0.0
Me.intensitas = 0.0
End Sub
'Hanya untuk fitur pengurutan (sort) pada proses perhitungan diatas
'Jika tidak diperlukan, bisa dihilangkan
Public Function CompareTo(ByVal fireflyLain As Firefly) As Integer Implements IComparable(Of Firefly).CompareTo
If Me.nilaiFungsi > fireflyLain.nilaiFungsi Then
Return -1
ElseIf Me.nilaiFungsi < fireflyLain.nilaiFungsi Then
Return 1
Else
Return 0
End If
End Function
End Class
Hasil akhir adalah: (klik untuk perbesar gambar)
Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:
[sdm_download id=”737″ fancy=”0″]
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.
Leave a Reply