Algoritma BCO (Bee Colony Optimization) 16


Algoritma BCO (Bee Colony Optimization) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik tujuan dengan jarak paling rendah.
Bee Colony Optimization adalah algoritma optimasi yang berdasarkan pada tingkah laku kumpulan lebah madu dalam sebuah koloni untuk menemukan sumber makanan. Kemungkinan solusi dilambangkan dengan posisi sumber makanan, sedangkan nilainya dilambangkan dengan jumlah nektar yang terdapat dalam sumber makanan tersebut.



Diasumsikan ada sebaran titik yang harus dilalui semuanya
semua titik terhubung secara langsung dengan titik-titik lainnya, dan semua jalurnya dapat dilalui 2 arah
Jarak antar titik pada semua titik akan diambil secara acak antara angka 1 sampai 10
Tentukan Jalur yang harus diambil untuk mengelilingi semua titik dengan jarak terpendek



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah lebah yang digunakan dalam perhitungan
Dalam dunia nyata, dalam 1 sarang lebah, biasanya terdapat 5.000 – 20.000 lebah
Diasumsikan dalam kasus ini, jumlah lebah hanya ada 100, karena semakin besar angkanya, semakin lama perhitungannya

* Tentukan jumlah lebah aktif, lebah nonaktif, dan lebah pencari
Jumlah ketiga jenis lebah ini harus sama dengan variabel jumlah lebah diatas
Dalam dunia nyata, perbandingan lebah aktif : lebah nonaktif : lebah pencari adalah kira-kira 75% : 10% : 15%
Diasumsikan dalam kasus ini, perbandingan tersebut akan digunakan untuk mendeklarasikan jumlah masing-masing jenis lebah

* Tentukan jumlah maksimal perjalanan yang dapat dilakukan lebah sebelum harus kembali ke sarangnya
Ini mencegah seekor lebah keluar terlalu lama karena tidak mendapatkan perjalanan yang lebih baik dari perjalanan yang sudah ditempuhnya.
Diasumsikan dalam kasus ini, jumlah maksimal perjalanan adalah 100

* Tentukan jumlah iterasi yang dilakukan untuk masing-masing lebah
Semakin besar angkanya, semakin optimal hasil perhitungannya, tetapi semakin lama perhitungannya
Diasumsikan dalam kasus ini, jumlah iterasi adalah 1000


Langkah-langkah penggunaan algoritma ini adalah

1. Inisialisasi sarang lebah beserta semua obyek yang ada di dalamnya
Buat lebah sebanyak parameter total Lebah
Beri status pada masing-masing lebah sesuai dengan parameter total lebah aktif, total lebah nonaktif, total lebah pencari
Tentukan jalur acak pada masing-masing lebah, kemudian cari jejak terpendek sementara yang diperoleh secara acak
Simpan jalur terbaik sementara berdasarkan jalur dengan jarak terpendek
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class sarangLebah untuk menampung data seperti daftar lebah, data titik, jalur terbaik, dan nilai jalur terbaik. Deklarasi Class sarangLebah adalah sebagai berikut:

2. Lakukan proses perhitungan sebanyak jumlah perulangan
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 3 – 5)

Memasuki perhitungan pada proses prosesPerhitungan

* Lakukan proses perulangan sebanyak jumlah iterasi untuk semua lebah yang berada pada daftar lebah
Lakukan proses perhitungan sesuai dengan status lebah yang sedang diproses

3. Jika lebah ini lebah aktif, maka lakukan proses perhitungan untuk lebah aktif

3a. Tentukan jalur baru untuk lebah ini

3b. Hitung nilai jalur untuk jalur yang baru ditemukan

3c. Jika jalur yang baru ternyata lebih baik dari jalur lebah tersebut

3c1. Tentukan apakah nilai acak kurang dari nilai probabilitas kesalahan
Jika benar maka Lebah melakukan kesalahan, sehingga menolak solusi yang lebih baik

3c2. Jika tidak maka lebah tidak melakukan kesalahan, sehingga menerima solusi yang baru

3d. Jika jalur yang baru ternyata tidak lebih baik dari jalur lebah tersebut

3d1. Tentukan apakah nilai acak kurang dari nilai probabilitas kesalahan
Jika benar maka lebah melakukan kesalahan, sehingga menerima solusi yang lebih buruk

3d2. Jika tidak maka lebah tidak melakukan kesalahan, sehingga menolak solusi yang baru

3e. Setelah perhitungan tersebut, maka lebah akan kembali ke sarang
ada 3 kemungkinan keadaan pada saat lebah sudah berada di sarang:

3e1. Jika jumlah perjalanan lebah tersebut sudah melebihi maksimum perjalanan, maka lebah ini akan berubah menjadi lebah nonaktif

3e2. Jika jalur baru diterima oleh lebah tersebut, maka lakukan pengecekan apakah jalur baru ini lebih baik dari solusi umum. Kemudian lakukan tarian waggle

3e3. Tidak terjadi apa-apa (lebah hanya kembali ke sarang)

* Lakukan fungsi ini jika jalur baru telah diterima oleh lebah
Dalam dunia nyata, tarian waggle dilakukan oleh lebah untuk mengirimkan informasi kepada teman lebahnya mengenai sumber makanan yang lebih baik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

4. Lakukan fungsi ini jika status lebah adalah lebah pencari

4a. Tentukan jalur acak untuk lebah ini

4b. Hitung nilai jalur untuk jalur acak tersebut

4c. jika nilai jalur acak ternyata lebih rendah dari nilai jalur terpendek lebah tersebut
maka lebah pencari menemukan solusi yang lebih baik dari solusi yang pernah ditemukan sebelumnya

4c1. ambil jalur ini sebagai jalur terbaik lebah tersebut

4c2. Apabila jalur acak ternyata lebih baik dari solusi umum
maka Ambil jalur ini sebagai solusi umum

4c3. Lakukan Tarian Waggle

5. Lakukan fungsi ini jika status lebah adalah lebah nonaktif

* Untuk menyimpan data titik dan jarak antar titik, diperlukan sebuah class tersendiri yang tidak berhubungan dengan class sarang lebah, yaitu class daftarTitik. Deklarasi class daftarTitik adalah sebagai berikut:


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd24b


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 *

16 pemikiran di “Algoritma BCO (Bee Colony Optimization)