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

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:

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

* Tentukan dimensi permasalahan
Diasumsikan dalam kasus ini, dimensi bernilai 3 karena ada 3 dimensi yang akan dicari solusinya

* 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

* 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


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)

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

2. Inisialisasi para kunang-kunang yang digunakan sebanyak parameter jumlahFirefly

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

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

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

* 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)

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

7. Lakukan pengecekan apakah kunang-kunang ini berada pada posisi terbaik

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

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

8b. Hitung nilai beta menggunakan konstanta base beta, gamma, dan jarak yang sudah ditentukan sebelumnya

8c. Pindahkan kunang-kunang ini ke posisi yang baru pada setiap dimensinya

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

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

8f. Hitung nilai fungsi dan intensitas untuk kunang-kunang ini pada posisi yang baru

8g. Lakukan pengecekan apakah kunang-kunang ini berada pada posisi terbaik

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

* 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:


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 sebuah komentar

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.