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.
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.
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.
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
Algoritma ini tentu saja bisa anda tulis ulang dalam bahasa Matlab jika anda sudah memahami penjelasan pada masing-masing poin pada pos ini, dan saya bisa bantu untuk menulis ulang skrip ini ke dalam bahasa Matlab. Jika ada pertanyaan lebih lanjut, komunikasi selanjutnya bisa dilakukan secara pribadi, dengan nomor kontak yang tertera pada halaman http://piptools.net/hubungi-kami/
Saya sudah kirimkan email ke [email protected] mohon bantuannya, terima kasih
Baik, komunikasi selanjutnya akan dilanjutkan secara pribadi. Terima kasih
mau tanya ada contoh FA jika di terapkan di dalam toko/pabrik
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.
Dear admin, apa boleh minta list program dengan permasalahan yang sama menggunakan MATLAB? terima kasih
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.
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
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?
Maksudnya fitur sprti apa nih min?
Soalnya game saya menggunakan Algoritma firefly sebagai Pathfinding pada NPC.
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.
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
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.
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 :”)
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.
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?
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.