Jumat, 15 Maret 2019

Matlab-FireFly Algorithm

Penulis mencoba untuk menulis code Algoritma Kunang-Kunang menggunakan Octave (sintaks mirip dengan matlab) agar code nya lebih mudah dipelajari dan lebih sedikit. 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.



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 :

Inisialisasi parameter Firefly Algorithm.

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


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

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

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.

Melakukan  movement  dengan  persamaan 



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

Melakukan proses diatas sampai batas iterasi dipenuhi. 

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



Tidak ada komentar: