Artificial Bee Colony

Algoritma Artificial Bee Colony (ABC) adalah algoritma metaheuristic yang meniru perilaku koloni lebah dalam mencari makanan (nektar) (Karaboga & Basturk, 2007). Dalam algoritma ABC, koloni lebah dibagi menjadi 3 jenis yaitu:

1. Lebah Employee bertugas untuk mengeksploitasi sumber makanan (solusi).
2. Lebah Onlooker, menunggu di sarang dan kemudian ikut mengeksploitasi sumber makanan berdasarkan informasi tentang sumber makanan yang disampaikan oleh lebah employee melalui waggle dance.
3. Lebah Scout, bertugas mencari sumber makanan baru jika terdapat sumber makanan yang ditinggalkan oleh lebah employee atau lebah onlooker.

Pada algoritma ABC, solusi atas permasalahan yang optimisasi digambarkan sebagai sumber makanan (nektar) (Akay & Karaboga, 2012).  Dan kualitas dari nektar menggambarkan nilai objective function dari suatu solusi. Jumlah sumber makanan sama dengan jumlah lebah employee, sedangkan jumlah lebah employee sama dengan jumlah lebah onlooker. Perilaku lebah dalam mencari makan dapat digambarkan sebagai berikut (Akay & Karaboga, 2012):

1. Pada tahapan awal mencari sumber makanan, lebah mulai menjelajah wilayah sekitar sarang secara acak untuk mendapatkan sumber makanan.
2. Setelah menemukan sumber makanan, lebah mulai menjadi lebah employee dan mulai mengeksploitasi sumber makanan yang ditemukan. Setelah itu lebah employee akan kembali ke dalam sarang dengan membawa nektar dan menurunkan nektar. Setelah menurunkan nektar, lebah employee tersebut dapat langsung kembali ke sumber makanan yang dia temukan atau lebah tersebut dapat membagikan informasi tentang sumber makanan yang dia temukan ke lebah lainnya dengan melakukan waggle dance. Banyaknya gerakan dalam tarian menunjukkan kualitas dari nektar. Apabila nektar telah habis, maka lebah employee akan menjadi lebah scout dan mulai mencari sumber makanan lain secara acak.
3. Lebah onlooker yang menunggu di dalam sarang dapat memilih sumber makan setelah melihat waggle dance yang dilakukan oleh lebah employee

Berdasarkan perilaku lebah dalam mencari makan tersebut, tahapan algoritma Artificial Bee Colony dapat dijabarkan sebagai berikut (Karaboga & Basturk, 2007) :

1. Inisialisasi kumpulan solusi menggunakan persamaan 1.  Tiap solusi merupakan vector dengan D

x_ij= x_j^min+rand(0,1)(x_j^max- x_j^min)                                                              (1)

Dimana i = 1 . . . SN, j = 1 . . . D. SN adalah jumlah sumber makanan (solusi) dan D adalah jumlah parameter yang dioptimasi.

2. Evaluasi nilai objective function seluruh solusi awal
3. Siklus = 1. Proses pencarian parameter yang optimal berada dalam siklus, C = 1, 2, . . ., MCN.
4. Ulangi langkah nomor 5 sampai 12 hingga siklus = Maximum Cycle Number (MCN)
5. Buat solusi baru untuk tiap lebah employee dari solusi  dengan menggunakan persamaan 2 dan evaluasi hasilnya. Solusi baru ini merupakan modifikasi dari solusi sebelumnya.

v_ij= x_ij+∅_ij (x_ij- x_kj)                                                                                                                    (2)

Dimana k ∈{1,2,…,SN)  dan j ∈{1,2,…,D) merupakan indeks yang dipilih secara acak.

6. Lakukan proses seleksi. Jika nilai objective function dari solusi baru lebih kecil dari solusi sebelumnya maka solusi akan diupdate menjadi solusi baru tersebut. Lebah employee kemudian akan mengingat solusi baru yang lebih baik tersebut.
7. Hitung nilai probabilitas untuk solusi  dengan menggunakan persamaan 3 dan 4.

fitness_i= (1/(1+f_i )) if f_i ≥0                                                                 (3)

fitness_i =1+abs(f_i) if f_i<0                                                                 (3)

Dimana fi  adalah nilai objective function solusi  i.

p_i= fitness_i / (∑_(i=1)^SN {fitness}_i )                                              (4)

Dimana  fitness i adalah  fitness value dari nilai objective function solusi  i. Dan SN adalah jumlah solusi.

8. Lebah onlooker mengevaluasi solusi berdasarkan informasi yang telah diberikan oleh lebah employee kemudian memilih solusi mana yang akan diikuti berdasarkan probabilitas yang dihitung menggunakan persamaan 4.  Buat solusi baru  untuk tiap lebah onlooker dari solusi  yang terpilih berdasarkan probabilitas  dengan menggunakan persamaan 1 dan evaluasi nilai objective value-nya. Seperti halnya pada lebah employee, solusi ini merupakan modifikasi dari solusi  yang terpilih.
9. Lakukan proses seleksi. Jika nilai objective function dari solusi baru lebih kecil dari solusi sebelumnya maka solusi akan diupdate menjadi solusi baru tersebut. Lebah employee kemudian akan mengingat solusi baru yang lebih baik tersebut.
10. Jika terdapat lebah ketika memodifikasi suatu solusi tidak mendapatkan solusi baru yang lebih baik dari solusi sebelumnya sampai dengan batas tertentu yang telah ditentukan, maka solusi tersebut akan ditinggalkan, lalu lebah tersebut menjadi lebah scout dan mencari sumber makanan baru secara acak dengan menggunakan persamaan 1. Solusi baru tersebut akan menggantikan solusi lama yang ditinggalkan.
11. Simpan solusi terbaik sampai dengan saat ini
12. Siklus = siklus + 1

References

Karaboga, D., & Basturk, B. (2007). A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of global optimization, 39(3), 459-471.

Akay, B., & Karaboga, D. (2012). A modified artificial bee colony algorithm for real-parameter optimization. Information sciences, 192, 120-142.

Karaboga, D., Akay, B., & Ozturk, C. (2007, August). Artificial bee colony (ABC) optimization algorithm for training feed-forward neural networks. In International conference on modeling decisions for artificial intelligence (pp. 318-329). Springer, Berlin, Heidelberg.