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

Dimensikonstantabatas minimalbatas maksimal
x3.21050
y33080
z2.550150

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)

cmd38

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.


Tinggalkan Balasan ke pip Batalkan balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

20 pemikiran di “Algoritma FA (Firefly Algorithm)

  • Handoko

    Min… ane bingung teorinya, jadi si kunang2 terbanyak yg menang? terus ga paham juga soalnya ngitung 3 dimensi, klo contoh kasus yang sistem informasi apa min? ane cuma disuruh dosen cek algoritma ini buat tugas akhir, tapi ga dijelasin mau dibuat apa. kalau buat toko atau pabrik diterapkan dalam sistem apanya?

    tq.

    • pip Penulis

      Algoritma ini adalah algoritma optimasi dimana tujuannya adalah mencari obyektif dengan nilai yang paling optimum, bisa minimal atau maksimal. Kunang-kunang yang menang adalah kunang-kunang yang memiliki nilai paling optimum. Bisa digunakan untuk dimensi sebanyak apapun, tetapi harus dilakukan penyesuaian rumus nilai obyektif yang melibatkan semua variabel dimensi.

      Jika diterapkan dalam pabrik atau toko, bisa digunakan untuk menghitung stok mana saja yang harus dibeli dalam sebuah periode, agar biaya yang dikeluarkan seminimal mungkin, atau hasil keuntungannya adalah semaksimal mungkin, atau keduanya. Jika toko tersebut memiliki 100 barang, maka semua barang tersebut akan masuk dalam algoritma (100 dimensi), kemudian tinggal menyusun rumus nilai obyektif yang melibatkan ke 100 dimensi tersebut.

      • Indra

        Terima kasih atas jawabannya admin. Maksud saya adalah algoritma serupa (Firefly Algorithm) tetapi menggunakan bahasa Matlab. Saya sangat terbantu dengan penjelasan per-point pada post ini, namun saya tidak memahami bahasa VB yang digunakan. Kalau boleh, mungkin admin bisa membuat post baru yang berisi program serupa (FA) menggunakan bahasa Matlab

        • pip Penulis

          Untuk studi kasus pabrik, FA bisa diterapkan sebagai optimasi penjadwalan produksi. Jadi penjadwalan dari bahan mentah sampai menjadi barang jadi, dan biasanya digunakan untuk mengoptimasi penjadwalan yang sudah ada di pabrik tersebut.

    • pip Penulis

      Apakah maksud anda algoritma lain yang sejenis untuk permasalahan yang mirip dengan pos ini?
      Algoritma ini saya masukkan ke dalam kategori Algoritma Optimasi, yang dapat anda pilih pada sidebar di sebelah kanan. Silahkan klik link tersebut untuk menemukan algoritma sejenis, kemudian cari algoritma yang menggunakan bahasa Matlab sebagai bahasa pemrogramannya.

  • Bani

    Salam. Min.., mau nanya dong, kebetulan saya sedang buat project TA Game. Untuk FA sendiri apakah relevan jika diterapkan ke Game dengan bahasa C# ?
    Thanks

    • pip Penulis

      Algoritma ini dapat diterapkan pada kasus optimasi apapun, termasuk dalam kasus permainan / game. Boleh tahu fitur apakah yang ingin anda lakukan optimasi di game tersebut?

        • pip Penulis

          Permasalahan pathfinding / pencarian jalur termasuk dalam salah satu kasus optimasi. Jadi tentu saja FA (dan algoritma optimasi lainnya) bisa diterapkan pada dalam kasus tersebut.
          Sebagai catatan bahwa permasalahan pencarian jalur sendiri bisa diselesaikan dengan algoritma pada kategori Algoritma Pencarian Jalur yang dapat anda pilih pada sidebar di sebelah kanan.

  • Karan

    min, berarti algoritam FA bisa digunakan untuk optimasi penyusunan barang dalam mobil box dong ? karena di algoritama ini kan bertujuan menentukan maksimum atau minimum suatu nilai atau barang yaa kan… kira2 bisa kasih masukan gak min ttg ini ?
    Thanks

    • pip Penulis

      Tentu saja algoritma ini dapat digunakan untuk mengoptimasi penyusunan barang. Jika demikian maka nilai fungsi dihitung dengan banyaknya ruang yang ditempati dari susunan barang tersebut, atau bisa jadi dihitung dengan banyaknya ruang yang tersisa dari susunan barang tersebut.

      • Tiya

        sebelumnya terimakasih untuk info detailnya tentang algoritma ini, yang mau saya tanyakan adalah berapa nilai parameter alfa dan gamma terbaik agar dapat solusi yang terbaik juga? mohon balasannya, karena untuk kelanjutan TA saya :”)

        • pip Penulis

          Sebenarnya tidak ada patokan nilai parameter yang terbaik, karena implementasi algoritma ini bergantung pada studi kasus optimasi yang sedang terjadi. Nilai tersebut hanya dapat diketahui setelah trial dan error. Tetapi pada umumnya nilai rekomendasi yang sebaiknya digunakan sudah tercatat pada referensi jurnal yang anda gunakan.

  • Rahel

    Sebagaimana pada poin 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. Bagaimana cara mengembalikan nilai posisinya, apakah tetap pada nilai awal, atau nilai bari dengan di random lagi sesuai batasan?

    • pip Penulis

      Dalam contoh implementasi yang saya lakukan diatas, saya mengembalikan nilai yang melebihi batas menjadi nilai batas yang diperbolehkan, tetapi hal ini dapat disesuaikan bergantung dari referensi jurnal yang dipakai; jika nilai yang melebihi batas harus dikembalikan dengan sistem acak nilai pada rentang tertentu maka skrip pada poin 8d dapat diubah demikian.