Algoritma FA (Firefly Algorithm) 20

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

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:

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.