Algoritma kunang-kunang

Dalam kasus optimasi matematika, algoritma kunang-kunang atau firefly algorithm adalah salah satu algoritma metaheuristik yang pertama kali dikemukakan oleh Xin-She Yang. Algoritma ini terinspirasi oleh perilaku berkedip yang dilakukan oleh kunang-kunang.

Algoritma

Dalam bentuk pseudocode, algoritma ini dapat dinyatakan sebagai:

Begin
  1) Fungsi objektif: $f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},...,x_{d})$;
  2) Inisialisasi populasi awal kunang-kunang $\mathbf {x} _{i}\quad (i=1,2,\dots ,n)$;.
  3) Tentukan intensitas cahaya I sehingga berhubungan dengan $f(\mathbf {x} )$
    (misalnya, untuk masalah maksimalisasi, $I\propto f(\mathbf {x} )$ atau $I=f(\mathbf {x} )$;)
  4) Definisikan koefisien light absorption γ

  while (t < MaksGenerasi) atau (KriteriaBerhenti = true)
    for i = 1 : n (semua n kunang-kunang)
      for j = 1 : i (n kunang-kunang)
        if ($I_{j}>I_{i}$),
          Variasikan daya tarik (attractiveness) dengan jarak r melalui $\exp(-\gamma \;r)$;
          Gerakkan kunang-kunang i menuju j untuk semua dimensi d;        
          Evaluasi solusi baru dan perbarui intensitas cahaya (light intensity);
        end if 
      end for j
    end for i
    Buat peringkat kunang-kunang dan cari yang terbaik saat ini (current best);
  end while
end

Perhatikan bahwa jumlah evaluasi terhadap fungsi objektif pada setiap iterasi adalah satu evaluasi untuk setiap kunang-kunang, meskipun pseudocode di atas menunjukkan sebesar n × n. (Berdasarkan kode MATLAB oleh Yang). Jadi, banyaknya evaluasi terhadap fungsi objektif adalah sebesar (jumlah generasi) × (jumlah kunang-kunang).

Rumus pembaruan utama untuk sepasang kunang-kunang $\mathbf {x} _{i}$ dan $\mathbf {x} _{j}$ adalah

$\mathbf {x} _{i}^{t+1}=\mathbf {x} _{i}^{t}+\beta \exp[-\gamma r_{ij}^{2}](\mathbf {x} _{j}^{t}-\mathbf {x} _{i}^{t})+\alpha _{t}{\boldsymbol {\epsilon }}_{t}$

Di mana $\alpha _{t}$ adalah suatu parameter yang mengatur besar langkah atau ukuran langkah. Parameter ini menentukan sejauh mana firefly bergerak untuk setiap iterasi. Dengan nilai $\alpha _{t}$​ yang lebih besar, firefly akan bergerak lebih jauh dalam ruang pencarian solusi. Jika $\alpha _{t}$​ lebih kecil, pergerakan firefly akan lebih terbatas. Sedangkan ${\boldsymbol {\epsilon }}_{t}$ adalah sebuah vektor yang diambil dari distribusi Gaussian atau distribusi lainnya, parameter ini digunakan untuk memberikan komponen acak pada pergerakan firefly. Hal ini dapat memberikan variasi pada posisi firefly dan membantu mencegah terjebaknya proses pencarian pada minimum lokal.

Hal ini dapat ditunjukkan bahwa dengan kasus pembatas $\gamma \rightarrow 0$, firefly algorithm mendekati standar Particle Swarm Optimization (PSO). Faktanya, jika iterasi looping bagian dalam (for j) dihilangkan dan kecerahan $I_{j}$ digantikan dengan $g^{*}$, global terbaik saat ini, maka FA pada dasarnya menjadi PSO standar. Artinya, FA dan PSO memiliki keterkaitan yang mendalam, dan ketika suatu parameter pada FA didekati nol, FA akan berkembang menjadi PSO.

Kritik

Metaheuristik yang terinspirasi dari alam secara umum telah menuai kritik dari komunitas riset karena menyembunyikan kurangnya kebaruan di balik metafora yang digunakan. Firefly algorithm telah dikritik karena perbedaan dari optimasi kawanan partikel (PSO) yang sudah ada hanya dalam hal yang dapat diabaikan atau sederhana (kurang signifikan).

Lihat juga

• Kecerdasan gerombolan

Tautan eksternal

• [1] File program Matlab yang terdapat dalam buku: Xin-She Yang, Algoritma Metaheuristik Terinspirasi Alam, Edisi Kedua, Luniver Press, (2010).