PENERAPAN METODE FORGY PADA PERILAKU LEBAH PENJELAJAH DALAM ARTIFICIAL BEE COLONY

I Made Widiartha

Program Studi Teknik Informatika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Udayana email : imadewidiartha@cs.unud.ac.id

Abstrak

Metode Artificial Bee Colony (ABC) merupakan salah satu metode swarm yang mengadopsi karakteristik dari koloni lebah madu dalam proses pencarian sumber makanan/solusi. Yang dimaksud suatu sumber makanan dalam metode ABC merupakan suatu solusi yang dihasilkan oleh kelompok lebah. Dalam metode ABC koloni lebah tiruan dibagi menjadi tiga kelompok yaitu lebah penjelajah (scout), lebah pekerja (employed bee), dan lebah penunggu sarang (onlooker bee).

Lebah penjelajah memiliki peranan penting dalam menentukan sumber makanan awal dari koloni lebah pekerja. Disamping berperan dalam fase awal pada metode ABC, kelompok lebah ini juga berperan penting dalam menentukan sumber makanan baru ketika performa dari sumber makanan tidak mengalami peningkatan dalam jumlah fase tertentu. Dalam metode ABC perilaku lebah penjelajah dalam penentuan sumber makanan dilakukan dengan cara randomisasi solusi pada ruang pencarian sehingga hal ini seringkali menyebabkan hasil dari pencarian lebah penjelajah jauh dari posisi. Metode forgy merupakan salah satu metode yang dapat digunakan dalam penentuan titik solusi awal yang telah terbukti lebih baik jika dibandingkan dengan randomisasi.

Dalam penelitian ini dilakukan penerapan metode forgy untuk merubah karakteristik lebah penjelajah dalam melakukan pencarian sumber makanan baru. Uji coba penelitian ini dilakukan pada permasalahan klasterisasi data dengan memanfaatkan lima buah dataset. Kinerja metode ABC dengan penerapan metode forgy ini telah dibandingkan dengan metode ABC. Dari hasil penelitian didapatkan hasil dimana metode ABC dengan penerapan metode forgy ini telah berhasil mengoptimalkan posisi titik pusat klaster ABC. Nilai fungsi tujuan yang dihasilkan dari penerapan metode forgy ini juga relatif stabil. Hal ini dibuktikan dengan perolehan nilai standar deviasi yang relatif kecil.

Kata kunci: Metode Forgy, Artificial Bee Colony, Klasterisasi Data.

PENDAHULUAN

Dalam beberapa tahun terakhir, penelitian tentang metode kecerdasan yang berbasis pada perilaku kehidupan kelompok hewan (swarm) telah banyak mendapat perhatian oleh para ilmuwan. Dari sudut pandang Bonebeau, kecerdasan swarm didefinisikan sebagai suatu pemodelan untuk pemecahan masalah terdistribusi (distributed problem-solving) dengan menggunakan

perilaku pengorganisasian diri (self-organize) dari koloni serangga sosial [1]. Dua konsep dasar untuk kinerja kolektif swarm yaitu organisasi diri (self-organization) dan pembagian kerja. Kedua konsep ini diperlukan sebagai properti untuk mendapatkan perilaku kecerdasan swarm, seperti halnya sistem pemecahan masalah terdistribusi (distributed problem solving), yang mengatur dirinya sendiri dan beradaptasi dengan lingkungan tertentu. Salah satu contoh dari swarm adalah

kawanan lebah yang mengerubungi sarang dan perilakunya dalam mencari sumber makanan (foraging behaviour). Salah satu metode yang mengadopsi perilaku lebah madu adalah Artificial Bee Colony (ABC). Dalam konsep ABC koloni lebah tiruan dibagi menjadi tiga kelompok yaitu lebah penjelajah (scout), lebah pekerja (employed bee), dan lebah penunggu sarang (onlooker bee) [2]. Lebah penjelajah merupakan fase pertama yang dijalankan metode ABC dalam pemecahan suatu permasalahan. Lebah penjelajah ini akan menghasilkan solusi awal yang akan diekplorasi lebih jauh oleh lebah pekerja maupun lebah penunggu sarang. Pada saat terdapat suatu sumber makanan/solusi yang tidak dapat diperbaiki kualitasnya dalam beberapa fase tertentu, maka peranan lebah penjelajah akan dimulai kembali. Kelompok lebah ini akan mencari solusi baru ke seluruh ruang pencarian secara acak.

Karakteristik lebah penjelajah dalam pencarian solusi ini seringkali menghasilkan solusi yang jauh dari optimal sehingga membutuhkan jumlah iterasi yang relatif lama untuk mencari konvergensi ke arah solusi optimal. Hal ini membutuhkan modifikasi karakteristik lebah ini agar mampu menghasilkan solusi awal dalam metode ABC yang dapat mempercepat proses penemuan solusi optimal dari permasalahan yang ada.

Dalam penelitian ini akan dilakukan modifikasi perilaku lebah penjelajah pada metode ABC dengan mengadopsi karakteristik salah satu metode inisialisasi yaitu metode

forgy . Performa metode forgy ini telah terbukti lebih baik daripada teknik randomisasi biasa [3]. Hal ini yang menjadi acuan penerapan karakteristik forgy ke dalam perilaku lebah penjelajah dalam metode ABC. Uji coba performa metode pada penelitian ini dilakukan pada kasus klasterisasi data yang melibatkan lima buah dataset.

ARTIFICIAL BEE COLONY

Metode/algoritmaABC ini menggunakan perilaku cerdas (intelligent behaviour) dari sekawanan lebah madu berupa perilaku mencari makan[5]. Metode ini diperkenalkan oleh Karaboga pada tahun 2005. Separuh bagian pertama dari koloni terdiri dari lebah pekerja dan separuh bagian kedua mencakup lebah onlooker. Metode ABC ini dapat digambarkan seperti pada Gambar 1.

Gambar 1. Metode ABC

Metode ABC diawali dengan fase lebah penjelajah untuk mencari sumber makanan awal (solusi awal) secara random Tiap solusi xi dimana i = 1, 2, ..., SN (jumlah solusi sumber makanan) merupakan sebuah vektor dimensi D. D adalah jumlah parameter yang dioptimasi. Setelah tahapan inisialisasi selesai maka penentuan populasi dari posisi solusi berikutnya didapat melalui siklus yang berulang, C = 1, 2, ... , MCN. Pada akhir setiap siklus, lebah pekerja akan melakukan penghitungan nilai fitness (nilai nektar) dari solusi yang dihasilkan dan lebah pekerja membagi informasi nektar dan informasi tentang posisi mereka dengan lebah penunggu di dancing area. Nilai fitness dapat dicari dengan persamaan 2.1.

fiti = —^— i 1 + f

(2.1)


Variabel fi merupakan nilai cost function dari solusi i. Lebah penunggu mengevaluasi informasi yang diambil dari semua lebah pekerja dan memilih sumber makanan dengan probabilitas yang sesuai jumlah nektarnya. Seperti kasus lebah pekerja, lebah penunggu juga menghasilkan modifikasi pada posisi sumber makanan (solusi) dalam memorinya dan memeriksa jumlah nektar dari kandidat sumber makanan yang baru. Jika nilai nektar lebih tinggi dari sebelumnya, lebah akan mengingat posisi yang baru tersebut dan melupakan posisi yang lama.

Lebah penunggu memilih sumber makanan berdasarkan pada nilai probabilitas pi dengan menggunakan metode roulette wheel

selection [6]. Nilai pi ini dihitung melalui persamaan 2.2.

Pi =


fiti

SN

∑ fit1

i=1

(2.2)


Dalam menghasilkan kandidat posisi makanan baru, ABC menggunakan persamaan 2.3.

vjj = Xj + φj (-X - xkj)       (2.3)

Nilai k ∈ {1, 2, ..., SN} dengan j ∈ {1, 2, .., D} adalah indeks yang dipilih secara random. Meskipun k ditentukan secara random, namun k harus berbeda dari i. φj adalah sebuah bilangan random antara [-1,1], yang mengontrol produksi posisi sumber makanan tetangga di sekitar xij

Sumber makanan yang ditinggalkan oleh lebah pekerja, digantikan dengan sumber makanan baru oleh lebah scout. Dalam metode ABC, jika sebuah posisi sumber makanan tidak dapat ditingkatkan lebih lanjut melalui sejumlah siklus (cycle) yang telah ditetapkan (limit), maka sumber makanan tersebut diasumsikan untuk ditinggalkan. Hal ini disimulasikan dengan menghasilkan posisi sumber makanan baru secara random untuk menggantikan posisi sumber makanan yang ditinggalkan. Misal sumber makanan yang ditinggalkan adalah xi dan j ∈{1, 2, ..., D}, maka lebah scout akan mencari sumber makanan baru untuk diganti dengan xi. Operasi ini dilakukan dengan menggunakan persamaan 2.4.

xj = xmn + rand[0,1](x mx - xmin)   (2.4)

Setelah masing-masing kandidat posisi sumber makanan vij diproduksi dan dievaluasi

oleh lebah pekerja, nilai fitnesnya dibandingkan dengan xij. Jika sumber makanan baru mempunyai nektar yang sama atau lebih baik daripada sumber yang lama, maka sumber yang lama tersebut akan digantikan dengan yang baru dalam memori, jika tidak maka yang lama dipertahankan. Dengan kata lain, rnekanisme greedy selection digunakan sebagai operasi seleksi antara sumber makanan saat ini dan sumber makanan yang lama.

METODE FORGY PADA LEBAH PENJELAJAH

Dalam hal klasterisasi data metode forgy merupakan salah satu metode yang sering kali digunakan untuk inisialisasi titik pusat klaster. Seperti halnya dalam penelitian yang dilakukan Pena, pendekatan forgy diterapkan pada fase inisialisasi titik pusat klaster pada metode K-Means [2]. Dalam langkah awal metode forgy, titik klaster ditentukan dengan memilih K buah data sebagai titik pusat awal pada metode forgy. Proses pembaharuan titik pusat di setiap iterasi dalam metode ini dilakukan dengan mencari rata-rata dari jarak data dalam klaster pada suatu titik pusat. Iterasi pencarian titik pusat akan terhenti ketika nilai fungsi tujuan telah memenuhi nilai threshold tertentu.

Metode forgy dapat digambarkan sebagai berikut, misal X = {xi|i = 1, ..., n} merupakan suatau himpunan n titik berdimensi d yang akan diklasterkan kedalam K klaster C = {ck| k = 1, ..., K}. Metode forgy menemukan suatu

partisi/klaster sedemikian hingga nilai squared error antara titik tengah (mean) dari suatu klaster ke smua titik data klaster tersebut merupakan nilai minimum. Misalkan µk adalah rata-rata dari klaster ck yang didapat dari persamaan 2.5.

1

µk =    ∑xi          (2.5)

nk xi∈ck

Dimana nk merupakan jumlah elemen pada ck.Squared error antara µk dan seluruh data pada klaster ck didasarkan pada jarak Euclidean antara titik yang ada dengan pusat klasternya, squared error tersebut didefinisikan sebagai berikut:

J(ck)= ∑|| xi-µk ||2 xi∈ck

Fungsi tujuan (objective function) dari metode forgy dalam permasalahan klasterisasi data adalah meminimukan total squared error dari seluruh klaster. Fungsi tujuan ini juga disebut sebagai clustering criterion [3] dan juga sebagai cost function [4] dalam penemuan solusi optimal. Adapun formula dari tujuan ini adalah :

K

J(C)=∑ ∑|| xi -µk ||2 k=1 xi ∈ck

Solusi pada metode KM adalah terbentuknya klaster-klaster dengan nilai J(C) yang minimum. Apabila metode forgy ini diterapkan pada karakteristik lebah penjelajah pada metode ABC maka tahapan pencarian titik pusat baru oleh lebah penjelajah akan dilakukan sesuai dengan tahapan pada metode forgy yaitu

  • 1.    Inisialisasi sejumlah K titik pusat klaster awal dengan memilih salah satu data pada dataset sebagai titik pusat.

  • 2.    Klasterkan setiap obyek yang ada sesuai jarak terdekat ke pusat klaster yang ada.

  • 3.    Perbaiki nilai semua pusat klaster

  • 4.    Ulangi langkah 2 dan 3 sampai nilai semua pusat klaster tidak ada perubahan.

DATA

Dataset yang digunakan dalam penelitian ini terdiri dari dataset Iris, Wisconsin Breast Cancer (Cancer), Contraceptive Method Choice (CMC), dan Wine. Data dalam penelitian diambil dari UCI Machine Learning Repository (ftp://ftp.ics.uci.edu./pub/machine-learning-databases/). Informasi jumlah fitur, kelas, dan data dapat dilihat pada Tabel 1.

Tabel 1. Pembagian Data Set

Dataset

Fitur

Kelas

Jumlah Data

Training

Testing

Iris

4

3

120

30

Cancer

9

2

547

136

CMC

9

3

1179

294

Wine

13

3

143

35

diujikan. Kesimpulan kinerja dari metode akan didapatkan melalui nilai rata-rata (mean) dan standar deviasi dari 10 percobaan tersebut. Tabel 1 merupakan hasil rata-rata dan standar deviasi dari percobaan yang telah dilakukan, Dari hasil penelitian dengan melibatkan empat data set didapatkan hasil bahwa metode forgy cukup berperan dalam meningkatkan performa dari metode ABC. Hal ini terlihat dari hasil penelitian yang menunjukkan nilai fungsi tujuan dari penerapan metode forgy unggul dibandingkan dengan metode ABC standar. Dari hasil penelitian ini dapat dilihat bahwa penerapan metode forgy dapat mengoptimalkan posisi titik pusat klaster dari metode ABC. Nilai fungsi tujuan yang dihasilkan dari penerapan metode forgy ini juga relatif stabil. Hal ini dibuktikan dengan perolehan nilai standar deviasi yang relatif kecil.

HASIL

Pada penelitian ini, untuk mendapatkan nilai performa dari penerapan metode forgy pada karakteristik lebah penjelajah dari metode ABC ini digunakan dua tolak ukur yaitu nilai fungsi tujuan dari permasalahan klasterisasi data dan waktu yang dibutuhkan.

Untuk mendapatkan kesimpulan akhir hasil klasterisasi menggunakan metode-metode yang ada, maka uji coba klasterisasi dilakukan sebanyak 10 kali untuk tiap dataset yang


Tabel 2. Rata-rata dan Standar Deviasi Hasil Uji Coba

Dataset

Pengukuran

Fungsi Tujuan

Waktu

Forgy ABC

ABC

Forgy ABC

ABC

Iris

Mean

187,229

205,2321

6,3087

5,2788

Std. Dev.

0,106

10,9068

0,1551

0,3053

Cancer

Mean

30671,334

47579,5674

11,8053

10,5055

Std. Dev.

0

7125,8019

0,0783

0,1784

Cmc

Mean

1248,962

1375,7912

27,0986

23,9018

Std. Dev.

8,223

65,7988

3,3032

0,2949

Wine

Mean

87,103

100,3024

13,2478

10,7268

Std. Dev.

0,168

4,6559

0,4702

0,1843


Dari sisi pengukuran waktu yang dibutuhkan didapat hasil bahwa metode penerapan metode forgy pada metode ABC membuat waktu yang diperlukan metode ABC menjadi lebih banyak. Tetapi jika dilihat dari hasil waktu eksekusi untuk forgy ABC terlihat bahwa perbedaan waktunya relatif kecil sehingga dapat dikatakan bahwa penerapan metode forgy masih tetap sangat bermanfaat dengan melihat nilai fungsi tujuan (yang merupakan tolak ukur utama) dari penerapan forgy yang selalu lebih baik dari metode ABC biasa. Meskipun demikian perbedaan waktu proses ini haruslah mendapat perhatian untuk dilakukan penelitian lanjutan untuk dapat meningkatkan efisiensi waktu eksekusi.

dihasilkan dari metode ABC. Hal ini dibuktikan dari seluruh hasil ujicoba dataset yang menunjukkan nilai fungsi tujuan (objective function) dari penerapan metode forgy ini lebih kecil dibandingkan dengan hasil yang didapat dari metode ABC standar. Nilai fungsi tujuan yang dihasilkan dari penerapan metode forgy ini juga relatif stabil. Hal ini dibuktikan dengan perolehan nilai standar deviasi yang relatif kecil.

Penerapan metode forgy pada ABC membutuhkan waktu yang lebih lama jika dibandingkan dengan metode ABC standar, sehingga hal ini merupakan suatu kelemahan dari penerapan ini. Optimasi waktu yang dibutuhkan dari penerapan metode forgy ini akan menjadi fokus penelitian selanjutnya.

KESIMPULAN

Dalam penelitian ini telah dilakukan penerapan metode forgy pada perilaku lebah penjelajah dalam metode Artificial Bee Colony. Penerapan metode forgy ini telah berhasil mengoptimalkan posisi titik pusat klaster yang

REFERENSI

  • [1]    Bonabeau, E., Dorigo, M., dan Theraulaz, G. (1999), Swarm Intelligence: from Natural to Artificial Systems, Oxford Univ. Press, New York.

  • [2]    Karaboga, D. (2005), "An Idea Based on Honey Bee Swarm for Numerical

Optimization", Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department.

  • [3]    Pena, J.M, Lozano, J.A, dan Larranaga, P (1999), "An Empirical Comparison of

Four Initialization methods for K-Means Algorithm", Pattern Recognition Letters, Vol 20, hal. 1027-1040.

  • [4]    Khan, S.S. dan Ahmad, A. (2004), “Cluster Center Initialization Algorithm for K-Means   Clustering”,   Pattern

Recognition Letters, Vol. 25, hal. 1293– 1302..

  • [5]    Karaboga, D. (2005), "An Idea Based on Honey Bee Swarm for Numerical Optimization", Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department.

  • [6]    Karaboga, D. dan Basturk (2008), B., "On The Performance of Artificial Bee Colony ABC Algorithm", Applied Soft Computing, Vol. 8, hal. 687–697.

ISSN : 1979-5661

-16-