Algoritma FireFly untuk Optimasi

By | January 15, 2021
Print Friendly, PDF & Email
3,010 Views

Sinopsis

Algoritma Metaheuristik untuk kebutuhan optimasi yaitu Algoritma Kunang-Kunang / FireFly. Kalian bisa pelajari algoritma dibawah ini, OK Langsung saja, sebuah persamaan berikut dengan fungsi objektif

Berapa nilai global minimal nya?

Titik bulat yang berwarna-warni adalah movement dari firefly dalam ruang pencarian.

Penerapan FireFly Algorithm atau Algoritma Kunang-Kunang

FireFly Algorithm atau Algoritma Kunang-Kunang merupakan salah satu dari algoritma untuk mencari optimal dari sebuah fungsi objektif. Algoritma  kunang-kunang  direpresentasikan  sebagai  seekor  kunang-kunang.  Kunang-kunang  dengan  intensitas  cahaya  yang  lebih  rendah  akan  bergerak  menuju  kunang-kunang yang  lebih  terang sehingga mampu didapatkan solusi optimal (global maksimum/minimum) lebih baik.

Maaf, hanya copy paste dari referensi, daripada menulis ulang

Judul: Pendekatan Firefly Algorithm (FA) Untuk Menyelesaikan Masalah Pengepakan Persegi Tiga Dimensi

Nama: Dessy Piton’s Bunga Pertiwi

Program Studi S-1 Matematika Departemen Matematika Fakultas Sains Dan Teknologi Universitas Airlangga 2016

Algoritma  Firefly  (FA)  pertama  kali  dikembangkan  oleh  Xin-She  Yang  pada akhir  tahun 2007 dan 2008 di Cambridge University, yang didasarkan pada pola  berkedip  dan    perilaku  kunang-kunang.  Menurut  Xin  Yang  (2010),  FA menggunakan tiga aturan yang dianggap ideal, yakni :

  1. Kunang  bersifat  unisex,  sehingga  satu  kunang-kunang  dapat  tertarik dengan kunang-kunang lain tanpa melihat jenis kelamin.
  2. Ketertarikan  antar  kunang  kunang  akan  sebanding  dengan  tingkat kecerahan  kunang-kunang  tersebut. Dengan  ketentuan  bahwa  semakin jauh  jarak  antar  kunang-kunang,  maka  tingkat  kecerahan  kunang-kunang akan menurun atau menghilang. Jadi untuk setiap dua kunang-kunang  yang  berkedipan,  kunang-kunang  yang  kurang  terang  (redup) akan  mendekati  kunang-kunang  yang  lebih  terang.  Jika  dari  kedua kunang-kunang  tidak ada yang  lebih  terang maka kunang-kunang akan bergerak secara acak.
  3. Kecerahan pada kunang-kunang akan ditentukan oleh fungsi tujuan dari masalah yang diberikan.

Istilah dalam FireFly

Berikut ini beberapa istilah yang digunakan dalam Firefly Algorithm (FA) dan definisinya menurut Yang (2010) :

  •  Populasi  adalah  sebuah  kumpulan  solusi  yang direprentasikan dengan kunang-kunang (firefly)
  •  Firefly  adalah  individu  dalam  populasi  yang  terdiri  dari kumpulan  kode  yang  merepresentasikan  solusi  dari permasalahan.
  •  Intensitas  cahaya  adalah  nilai  atau  ukuran  untuk mengevaluasi firefly.
  •  Atractiveness  adalah  daya  tarik  seekor  kunang-kunang yang  dinilai  oleh  kunang-kunang  lainnya  berdasarkan intensitas cahayanya.
  •  Distance adalah jarak antar dua firefly.
  •  Movement  adalah  pergerakan  yang  dlakukan  masing-masing firefly menuju firefly lain yang intensitas cahayanya lebih terang.

Intensitas cahaya

Dalam  algoritma  FA,  terdapat  dua masalah  penting  yaitu  variasi intensitas  cahaya  dan  perumusan  atractiveness. Kecerahan  pada  kunang-kunang  akan  ditentukan  oleh  fungsi  tujuan  dan  atractiveness  sebanding dengan kecerahan, dengan demikian untuk setiap dua kunang-kunang yang berkedip,  kunang-kunang  dengan  cahaya  yang  kurang  terang  akan bergerak ke arah kunang-kunang yang cahanya lebih cerah. Intensitas  cahaya  pada  kunang-kunang  dipengaruhi  oleh  fungsi tujuan. Tingkat  intensitas  cahaya  untuk masalah meminimumkan  sebuah  kunang-kunang x dapat dilihat sebagai.

Nilai I(x) merupakan tingkat  intensitas cahaya pada kunang-kunang x yang berbanding  terbalik terhadap solusi fungsi tujuan permasalahan yang akan dicari f(x). Atractiveness  β bernilai  relatif,  karena  intensitas  cahaya  harus dilihat  dan  dinilai  oleh  kunang-kunang  lain.  Dengan  demikian,  hasil penilaian  akan  berbeda  tergatung  dari  jarak  antara  kunang-kunang  yang satu dengan  yang  lainnya  rij. Selain  itu,  intensitas cahaya akan menurun dari  sumbernya  dikarenakan  terserap  oleh  media,  misalnya  udara. Sehingga  dapat  ditentukan  atractiveness  β  dengan  jarak  r    sebagai berikut :

Dengan β 0 adalah daya tarik di saat tidak ada jarak antar kunang-kunang (r = 0) dan γ ∈ [0,∞) adalah koefisien penyerapan cahaya.

Distance

Distance atau  jarak antara dua kunang-kunang  i dan  j pada posisi xi dan xj masing-masing adalah jarak kartesian yang dirumuskan sebagai berikut:

Movement

Movement  adalah  pergerakan  yang  dilakukan  firefly i karena ketertarikan  terhadap  firefly lain  j,  yang  intensitas  cahanya  lebih  terang. Dengan  adanya  movement,  maka  posisi  firefly  atau  solusi  dari  firefly tersebut akan berubah sesuai rumus berikut :

dengan suku pertama merupakan posisi lama dari firefly, suku kedua terjadi karena ketertarikan, suku ketiga adalah pergerakan random firefly dengan α adalah koefisien parameter random dan rand adalah bilangan real random pada interval [0,1]. Pada sebagian besar implementasi Firefly Algorithm menggunakan β 0 = 1, α ∈ [0,1] dan γ ∈ [0,∞)

Proses Firefly Algorithm

Menurut  Yang  (2014),  Firefly  Algorithm  dijalankan  dengan  cara sebagai berikut :

[1] Inisialisasi parameter Firefly Algorithm.

[2] Membangkitkan  secara  random  populasi  awal  sebanyak N firefly. Hitung  intensitas  cahaya  tiap  firefly  I(y) berdasarkan  nilai  fungsi tujuan f(x).

[3] Membandingkan  intensitas  cahaya  tiap  firefly  dengan    firefly lainnya.  Apabila  terdapat  firefly  yang  intensitas  cahayanya  lebih besar,  akan  dilakukan  update  pergeraka  firefly  menggunakan persamaan.

[4] Menentukan G-best. Untuk iterasi pertama, firefly terbaik (firefly dengan intensitas cahaya terbesar) adalah G-best.

[5] Membandingkan firefly terbaik tiap iterasi denngan G-best yang diperoleh. Apabila intensitas cahaya firefly terbaik saat itu lebih besar daripada G-best maka firefly tersebut menjadi G-best.

[6] Melakukan movement dengan persamaan

kepada  firefly  terbaik  dan menggabungkannya  dengan  firefly  yang lain untuk menjadi populasi awal pada iterasi selanjutnya.

[7] Melakukan proses diatas sampai batas iterasi dipenuhi.

Bagi kalian yang tertarik dengan penerapan firefly dalam kode Matlab, cukup Subcribe dan Follow blog ini dan kirim email kesini

Ref:

Yang, X. S. 2010, Engineering Optmization : An Introduction with Metaheuristic Applications. John Wiley & Sons, Inc., US.

Leave a Reply