Jurnal
ILMU KOMPUTER Volume 6 Nomor 1 April 2013 Daftar Isi :
HEALTH INFORMATICS : AN INTRODUCTION ................................................................... 1 I Made Agus Setiawan PENERAPAN METODE FORGY PADA PERILAKU LEBAH PENJELAJAH DALAM ARTIFICIAL BEE COLONY .................................................................................................... 10 I Made Widiartha IMPLEMENTASI HIGH-AVAILABILITY VPN CLIENT PADA JARINGAN KOMPUTER FAKULTAS HUKUM UNIVERSITAS UDAYANA................................................................ 17 Putu Topan Pribadi ANALISIS PERBANDINGAN KINERJA ANTARA NETWORK FILE SYSTEM (NFS) DAN PRIMARY DOMAIN CONTROLLER (PDC) SAMBA ........................................................... 25 Gede Wahyudi, Trisna Hanggara ANALISIS IDENTIFIKASI POLA DAUN MENGGUNAKAN METODE CANNY, SOBEL, PREWITT DAN ROBERTS ....................................................................................................... 35 I Ketut Gede Suhartana, Ida Ayu Dhyana Paramitha R.
ANALISIS DAN IMPLEMENTASI PEMERIKSAAN LEMBAR JAWABAN KOMPUTER DENGAN ALGORITMA PERCEPTRON ................................................................................ 47 I Wayan Haris Apriyana, luh gede astuti, I Made Widiartha
JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA DENPASAR
SUSUNAN DEWAN REDAKSI JURNAL ILMU KOMPUTER Jurusan Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Udayana
Ketua Agus Muliantara, S.Kom, M.Kom
Penyunting Drs. Wayan Santiyasa, M.Si Ngurah Agus Sanjaya, S.Kom, M.Kom Cokorda Rai Adi Paramarta, S.T, M.M Ida Bagus Gede Dwidasmara, S.Kom.M.Cs
Penyunting Tamu Imas Sitanggang, S.Si, M.Kom (IPB) Ir. A.A. Gede Raka Dalem, M.Sc (Hons) Prof. Pieter Hartel (Twente University)
Pelaksana I Made Widiartha, S.Si, M.Kom Dra. Luh Gede Astuti, M.Kom Gede Santi Astawa, ST, M.Cs Ida Bagus Mahendra, S.Kom, M.Kom
Alamat Redaksi Jurusan Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Udayana Kampus Bukit Jimbaran – Badung Telpon. 0361 – 701805 Email :
[email protected] Website : www.cs.unud.ac.id
ISSN : 1979-5661
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 :
[email protected]
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. perilaku pengorganisasian diri (self-organize) PENDAHULUAN Dalam
dari koloni serangga sosial [1]. Dua konsep
beberapa
tahun
terakhir,
dasar untuk kinerja kolektif swarm yaitu
penelitian tentang metode kecerdasan yang
organisasi
berbasis pada perilaku kehidupan kelompok
pembagian kerja. Kedua konsep ini diperlukan
hewan
mendapat
sebagai properti untuk mendapatkan perilaku
perhatian oleh para ilmuwan. Dari sudut
kecerdasan swarm, seperti halnya sistem
pandang
swarm
pemecahan masalah terdistribusi (distributed
didefinisikan sebagai suatu pemodelan untuk
problem solving), yang mengatur dirinya
pemecahan masalah terdistribusi (distributed
sendiri dan beradaptasi dengan lingkungan
problem-solving)
tertentu. Salah satu contoh dari swarm adalah
(swarm)
telah
Bonebeau,
ISSN : 1979-5661
banyak
kecerdasan
dengan
menggunakan
-10-
diri
(self-organization)
dan
Jurnal Ilmu Komputer - Volume 6 - No 1 – April 2013
kawanan lebah yang mengerubungi sarang dan
forgy . Performa metode forgy ini telah terbukti
perilakunya dalam mencari sumber makanan
lebih baik daripada teknik randomisasi biasa
(foraging behaviour). Salah satu metode yang
[3]. Hal ini yang menjadi acuan penerapan
mengadopsi perilaku lebah madu adalah
karakteristik forgy ke dalam perilaku lebah
Artificial Bee Colony (ABC). Dalam konsep
penjelajah dalam metode ABC. Uji coba
ABC koloni lebah tiruan dibagi menjadi tiga
performa metode pada penelitian ini dilakukan
kelompok yaitu lebah penjelajah (scout), lebah
pada kasus klasterisasi data yang melibatkan
pekerja (employed bee), dan lebah penunggu
lima buah dataset.
sarang (onlooker bee) [2]. Lebah penjelajah
ARTIFICIAL BEE COLONY
merupakan fase pertama yang dijalankan metode
ABC
dalam
pemecahan
Metode/algoritmaABC ini menggunakan
suatu
perilaku cerdas (intelligent behaviour) dari
permasalahan. Lebah penjelajah ini akan menghasilkan
solusi
awal
yang
sekawanan lebah madu berupa perilaku mencari
akan
makan[5]. Metode ini diperkenalkan
diekplorasi lebih jauh oleh lebah pekerja
Karaboga pada tahun 2005. Separuh bagian
maupun lebah penunggu sarang. Pada saat
pertama dari koloni terdiri dari lebah pekerja
terdapat suatu sumber makanan/solusi yang
dan separuh bagian kedua mencakup lebah
tidak dapat diperbaiki kualitasnya dalam
onlooker. Metode ABC ini dapat digambarkan
beberapa fase tertentu, maka peranan lebah
seperti pada Gambar 1.
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
Gambar 1. Metode ABC
salah satu metode inisialisasi yaitu metode ISSN : 1979-5661
oleh
-11-
Jurnal Ilmu Komputer - Volume 6 - No 1 – April 2013
selection
Metode ABC diawali dengan fase lebah
[6]. Nilai pi ini dihitung melalui
persamaan 2.2.
penjelajah untuk mencari sumber makanan awal (solusi awal) secara random Tiap solusi xi
pi
dimana i = 1, 2, ..., SN (jumlah solusi sumber
fiti
(2.2)
SN
fiti i 1
makanan) merupakan sebuah vektor dimensi D. D adalah jumlah parameter yang dioptimasi.
Dalam menghasilkan kandidat posisi makanan
Setelah tahapan inisialisasi selesai maka
baru, ABC menggunakan persamaan 2.3.
vij xij ij ( xij xk j )
penentuan populasi dari posisi solusi berikutnya didapat melalui siklus yang berulang, C = 1, 2,
(2.3)
Nilai k {1, 2, ..., SN} dengan j {1, 2, .., D}
... , MCN. Pada akhir setiap siklus, lebah pekerja
adalah indeks yang dipilih secara random.
akan melakukan penghitungan nilai fitness
Meskipun k ditentukan secara random, namun k
(nilai nektar) dari solusi yang dihasilkan dan lebah pekerja membagi informasi nektar dan
harus berbeda dari i. ij adalah sebuah bilangan
informasi tentang posisi mereka dengan lebah
random
penunggu di dancing area. Nilai fitness dapat
produksi posisi sumber makanan tetangga di
dicari dengan persamaan 2.1.
sekitar xij
fiti
1 1 fi
[-1,1],
yang
mengontrol
Sumber makanan yang ditinggalkan oleh (2.1)
lebah pekerja, digantikan dengan sumber makanan baru oleh lebah scout. Dalam metode
Variabel fi merupakan nilai cost function
ABC, jika sebuah posisi sumber makanan tidak
dari solusi i. Lebah penunggu mengevaluasi
dapat
informasi yang diambil dari semua lebah
ditingkatkan
lebih
lanjut
melalui
sejumlah siklus (cycle) yang telah ditetapkan
pekerja dan memilih sumber makanan dengan
(limit),
probabilitas yang sesuai jumlah nektarnya.
maka
sumber
makanan
tersebut
diasumsikan untuk ditinggalkan. Hal ini
Seperti kasus lebah pekerja, lebah penunggu
disimulasikan dengan menghasilkan posisi
juga menghasilkan modifikasi pada posisi
sumber makanan baru secara random untuk
sumber makanan (solusi) dalam memorinya dan
menggantikan posisi sumber makanan yang
memeriksa jumlah nektar dari kandidat sumber
ditinggalkan. Misal sumber makanan yang
makanan yang baru. Jika nilai nektar lebih
ditinggalkan adalah xi dan j {1, 2, ..., D}, maka
tinggi dari sebelumnya, lebah akan mengingat
lebah scout akan mencari sumber makanan baru
posisi yang baru tersebut dan melupakan posisi
untuk diganti dengan xi. Operasi ini dilakukan
yang lama. Lebah
antara
penunggu
memilih
dengan menggunakan persamaan 2.4.
sumber
j j j xij xmin rand[0,1]( xmax xmin )
makanan berdasarkan pada nilai probabilitas pi
(2.4)
Setelah masing-masing kandidat posisi
dengan menggunakan metode roulette wheel
sumber makanan vij diproduksi dan dievaluasi ISSN : 1979-5661
-12-
partisi/klaster sedemikian hingga nilai squared error antara titik tengah (mean) dari suatu oleh lebah pekerja, nilai fitnesnya dibandingkan dengan
xij.
Jika
sumber
makanan
klaster ke smua titik data klaster tersebut
baru merupakan nilai minimum. Misalkan
mempunyai nektar yang sama atau lebih baik
k
adalah rata-rata dari klaster ck yang didapat dari
daripada sumber yang lama, maka sumber yang
persamaan 2.5.
lama tersebut akan digantikan dengan yang baru
dipertahankan. Dengan kata lain, rnekanisme
1 xi n k xi ck
greedy selection digunakan sebagai operasi
Dimana nk merupakan jumlah elemen pada
k
dalam memori, jika tidak maka yang lama
(2.5)
k dan seluruh data
seleksi antara sumber makanan saat ini dan
ck.Squared error antara
sumber makanan yang lama.
pada klaster ck didasarkan pada jarak Euclidean antara titik yang ada dengan pusat klasternya,
METODE FORGY PADA LEBAH
squared error tersebut didefinisikan sebagai
PENJELAJAH
berikut:
J (ck ) || xi k || 2
Dalam hal klasterisasi data metode forgy
xi ck
merupakan salah satu metode yang sering kali
Fungsi tujuan (objective function) dari
digunakan untuk inisialisasi titik pusat klaster.
metode forgy dalam permasalahan klasterisasi
Seperti halnya dalam penelitian yang dilakukan
data adalah meminimukan total squared error
Pena, pendekatan forgy diterapkan pada fase
dari seluruh klaster. Fungsi tujuan ini juga
inisialisasi titik pusat klaster pada metode K-
disebut sebagai clustering criterion [3] dan juga
Means [2]. Dalam langkah awal metode forgy,
sebagai cost function [4] dalam penemuan
titik klaster ditentukan dengan memilih K buah
solusi optimal. Adapun formula dari tujuan ini
data sebagai titik pusat awal pada metode forgy.
adalah :
Proses pembaharuan titik pusat di setiap iterasi
K
J (C ) || xi k || 2
dalam metode ini dilakukan dengan mencari
k 1 xi ck
rata-rata dari jarak data dalam klaster pada
Solusi
suatu titik pusat. Iterasi pencarian titik pusat
metode
KM
adalah
terbentuknya klaster-klaster dengan nilai J(C)
akan terhenti ketika nilai fungsi tujuan telah
yang minimum. Apabila metode forgy ini
memenuhi nilai threshold tertentu.
diterapkan pada karakteristik lebah penjelajah
Metode forgy dapat digambarkan sebagai
pada metode ABC maka tahapan pencarian titik
berikut, misal X = {xi|i = 1, ..., n} merupakan
pusat baru oleh lebah penjelajah akan dilakukan
suatau himpunan n titik berdimensi d yang akan
sesuai dengan tahapan pada metode forgy yaitu
diklasterkan kedalam K klaster C = {ck| k = 1,
:
..., K}. Metode forgy menemukan suatu
ISSN : 1979-5661
pada
-13-
Jurnal Ilmu Komputer - Volume 6 - No 1 – April 2013
1. Inisialisasi sejumlah K titik pusat klaster
diujikan. Kesimpulan kinerja dari metode akan
awal dengan memilih salah satu data pada
didapatkan melalui nilai rata-rata (mean) dan
dataset sebagai titik pusat.
standar deviasi dari 10 percobaan tersebut.
2. Klasterkan setiap obyek yang ada sesuai
Tabel 1 merupakan hasil rata-rata dan standar
jarak terdekat ke pusat klaster yang ada.
deviasi dari percobaan yang telah dilakukan,
3. Perbaiki nilai semua pusat klaster
Dari hasil penelitian dengan melibatkan empat
4. Ulangi langkah 2 dan 3 sampai nilai semua
data set didapatkan hasil bahwa metode forgy cukup berperan dalam meningkatkan performa
pusat klaster tidak ada perubahan.
dari metode ABC. Hal ini terlihat dari hasil penelitian yang menunjukkan nilai fungsi
DATA Dataset yang digunakan dalam penelitian
tujuan dari penerapan metode forgy unggul
ini terdiri dari dataset Iris, Wisconsin Breast
dibandingkan dengan metode ABC standar.
Cancer (Cancer),
Contraceptive Method
Dari hasil penelitian ini dapat dilihat bahwa
Choice (CMC), dan Wine. Data dalam
penerapan metode forgy dapat mengoptimalkan
penelitian diambil dari UCI Machine Learning
posisi titik pusat klaster dari metode ABC. Nilai
Repository (ftp://ftp.ics.uci.edu./pub/machine-
fungsi tujuan yang dihasilkan dari penerapan
learning-databases/). Informasi jumlah fitur,
metode forgy ini juga relatif stabil. Hal ini
kelas, dan data dapat dilihat pada Tabel 1.
dibuktikan dengan perolehan nilai standar deviasi yang relatif kecil.
Tabel 1. Pembagian Data Set Jumlah Data Dataset Fitur Kelas Training Testing Iris Cancer CMC Wine
4 9 9 13
3 2 3 3
120 547 1179 143
30 136 294 35
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 ISSN : 1979-5661
-14-
Tabel 2. Rata-rata dan Standar Deviasi Hasil Uji Coba
Fungsi Tujuan Dataset Iris Cancer Cmc Wine
Pengukuran Mean Std. Dev. Mean Std. Dev. Mean Std. Dev. Mean Std. Dev.
Forgy ABC
ABC
187,229 0,106
205,2321 10,9068 47579,5674 7125,8019 1375,7912 65,7988 100,3024 4,6559
30671,334 0
1248,962 8,223 87,103 0,168
Waktu Forgy ABC ABC 6,3087 5,2788 0,1551 0,3053 11,8053 10,5055 0,0783 0,1784 27,0986 23,9018 3,3032 0,2949 13,2478 10,7268 0,4702 0,1843
dihasilkan dari metode ABC. Hal ini dibuktikan Dari sisi pengukuran waktu yang dibutuhkan
dari seluruh hasil ujicoba dataset yang
didapat hasil bahwa metode penerapan metode
menunjukkan nilai fungsi tujuan (objective
forgy pada metode ABC membuat waktu yang
function) dari penerapan metode forgy ini lebih
diperlukan metode ABC menjadi lebih banyak.
kecil dibandingkan dengan hasil yang didapat
Tetapi jika dilihat dari hasil waktu eksekusi
dari metode ABC standar. Nilai fungsi tujuan
untuk forgy ABC terlihat bahwa perbedaan
yang dihasilkan dari penerapan metode forgy
waktunya relatif kecil sehingga dapat dikatakan
ini juga relatif stabil. Hal ini dibuktikan dengan
bahwa penerapan metode forgy masih tetap
perolehan nilai standar deviasi yang relatif
sangat bermanfaat dengan melihat nilai fungsi
kecil.
tujuan (yang merupakan tolak ukur utama) dari
Penerapan metode forgy pada ABC
penerapan forgy yang selalu lebih baik dari
membutuhkan waktu yang lebih lama jika
metode ABC biasa. Meskipun demikian
dibandingkan dengan metode ABC standar,
perbedaan waktu proses ini haruslah mendapat
sehingga hal ini merupakan suatu kelemahan
perhatian untuk dilakukan penelitian lanjutan
dari penerapan ini. Optimasi waktu yang
untuk dapat meningkatkan efisiensi waktu
dibutuhkan dari penerapan metode forgy ini
eksekusi.
akan menjadi fokus penelitian selanjutnya.
KESIMPULAN
REFERENSI
Dalam penelitian ini telah dilakukan
[1] Bonabeau, E., Dorigo, M., dan Theraulaz, G. (1999), Swarm Intelligence: from Natural to Artificial Systems, Oxford Univ. Press, New York.
penerapan metode forgy pada perilaku lebah penjelajah dalam metode Artificial Bee Colony. Penerapan metode forgy ini telah berhasil
[2] Karaboga, D. (2005), "An Idea Based on Honey Bee Swarm for Numerical
mengoptimalkan posisi titik pusat klaster yang
ISSN : 1979-5661
-15-
Jurnal Ilmu Komputer - Volume 6 - No 1 – April 2013
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-
