Transmisi, Vol. 11, No. 1, Juni 2006 : 22 – 27
APLIKASI KRIPTOGRAFI DENGAN ALGORITMA
MESSAGE DIGEST 5 (MD5)
Aghus Sofwan, Agung Budi P, Toni Susanto
aghus@elektro.ft.undip.ac.id, agungbp@elektro.ft.undip.ac.id
Jurusan Teknik Elektro Fakultas Teknik Universitas Diponegoro
Abstrak
Sewaktu kita menerima atau mengirim pesan pada
jaringan, terdapat tiga buah persoalan yang sangat
penting, kerahasian, autentikasi, keutuhan dan tak
berbantahkan (non-repudiation). Message Digest 5
(MD5) adalah salah satu alat untuk memberi garansi
bahwa pesan yang dikirim akan sama dengan pesan
yang diterima, hal ini dengan membandingkan ‘sidik
jari’ atau ‘intisari pesan’ kedua pesan tersebut. MD5
merupakan pengembangan dari MD4 dimana terjadi
penambahan satu ronde. MD5 memproses teks
masukan ke dalam blok-blok bit sebanyak 512 bit,
kemudian dibagi ke dalam 32 bit sub blok sebanyak 16
buah. Keluaran dari MD5 berupa 4 buah blok yang
masing-masing 32 bit yang mana akan menjadi 128 bit
yang biasa disebut nilai hash. Makalah ini mempunyai
tujuan untuk merencanakan dan merancang suatu
aplikasi untuk menganalisa proses keutuhan atau
perubahan pesan dengan menggunakan MD5 dan juga
dapat menganalisa hasil keluaran dari MD-5 yang
berupa kecepatan dari proses aplikasi yang dibuat.
Kata Kunci : MD5, Kriptografi, hash
1. Latar Belakang
Sewaktu seseorang menerima atau mengirim
pesan pada jaringan, terdapat empat buah persoalan
yang sangat penting, yaitu kerahasian, autentikasi,
keutuhan dan non repudiation[1,2,3]. Kerahasian adalah
bahwa data kita tidak dapat dibaca oleh orang yang
tidak berkepentingan. Autentikasi memberi garansi
tentang keaslian data serta dengan siapa kita
berhubungan. Keutuhan memberi garansi bahwa data
tidak mengalami perubahan sewaktu perjalanan,
dengan kata lain data yang dikirim adalah data yang
diterima[1,2,3]. Dan non repudiation yang berarti si
pengirim tidak dapat menyangkal bahwa pesan yang
dikirim bukan darinya[2,3].
Salah satu dari bagian kriptografi adalah fungsi
hash satu arah. Fungsi hash satu arah adalah dimana
kita dengan mudah melakukan enkripsi untuk
mendapatkan cipher-nya tetapi sangat sulit untuk
mendapatkan plaintext-nya [1,3,12]. Salah satu fungsi
hash yang paling banyak digunakan adalah Message
Digest 5 (MD-5).
MD-5 merupakan fungsi hash satu arah yang
diciptakan oleh Ron Rivest. MD-5 adalah salah satu
aplikasi yang digunakan untuk mengetahui bahwa
pesan yang dikirim tidak ada perubahan sewaktu
berada di jaringan.
Algoritma MD-5 secara garis besar adalah
mengambil pesan yang mempunyai panjang variabel
diubah menjadi ‘sidik jari’ atau ‘intisari pesan’ yang
mempunyai panjang tetap yaitu 128 bit. ‘Sidik jari’
ini tidak dapat dibalik untuk mendapatkan pesan,
dengan kata lain tidak ada orang yang dapat melihat
pesan dari ‘sidik jari’ MD-5[10].
Message digest atau intisari pesan harus
mempunyai tiga sifat penting, yaitu[3,4]:
1. Bila P diketahui, maka MD(P) akan dengan
mudah dapat dihitung.
2. Bila MD(P) diketahui, maka tidak mungkin
menghitung P.
3. Tidak seorang pun dapat memberi dua pesan
yang mempunyai intisari pesan yang sama.
H(M) ≠ H(M’).
1.2 Tujuan dan Manfaat
Tujuan yang hendak dicapai adalah
merencanakan dan merancang suatu aplikasi untuk
menganalisa proses keutuhan atau pun perubahan
pesan dengan menggunakan Message Digest 5
(MD5) dan juga dapat menganalisa hasil keluaran
dari MD5 yang berupa kecepatan dari proses aplikasi
yang dibuat.
1.3 Batasan Masalah
Untuk tidak memperluas area pembahasan
yang terdapat pada proses autentikasi, perlu
adanya batasan-batasan untuk menye derhanakan
permasalahan, yaitu:
1. Aplikasi hanya memakai MD5, tidak
menggunakan enkripsi data.
22
Transmisi, Vol. 11, No. 1, Juni 2006 : 22 – 27
2. Aplikasi dilakukan pada semua file untuk
diubah menjadi ‘intisari pesan’ dengan
panjang 128 bit.
3. Contoh Aplikasi hanya simulasi dari
fungsi MD5 dalam perubahan pesan
2. Kriptografi dan Fungsi Hash Satu Arah Secara
Umum
Bagian ini menerangkan tentang kriptografi secara
umum yaitu tentang enkripsi dan dekripsi,
penggunaan kunci simetrik dan asimetrik, juga tujuan
dari kriptografi.
2.1 Prinsip Dasar Kriptografi
Ilmu kriptografi adalah ilmu yang mempelajari
tentang penyembunyian huruf atau tulisan sehingga
membuat tulisan tersebut tidak dapat dibaca oleh
orang yang tidak berkepentingan[2]. Kriptografi sudah
dipakai sejak jaman Julius Caesar dimana akan
mengirimkan pesan kepada panglimanya tetapi tidak
mempercayai kurir pembawa pesan tersebut.
Kriptografi mempunyai 2 (dua) bagian yang
penting, yaitu enkripsi dan dekripsi. Enkripsi adalah
proses dari penyandian pesan asli menjadi pesan
yang tidak dapat diartikan seperti aslinya. Dekripsi
sendiri berarti merubah pesan yang sudah disandikan
menjadi pesan aslinya. Pesan asli biasanya disebut
plaintext, sedangkan pesan yang sudah disandikan
disebut ciphertext[3].
Pada Gambar 2.1 dapat dilihat bahwa masukan
berupa plaintext akan masuk ke dalam blok enkripsi
dan keluarannya akan berupa ciphertext, kemudian
ciphertext akan masuk ke dalam blok dekripsi dan
keluarannya akan kembali menjadi plaintext semula.
Gambar 2.1 Proses Enkripsi dan Dekripsi
Ada 2 (dua) model algoritma enkripsi yang
menggunakan kunci, yaitu kunci simetrik dan kunci
asimetrik[2, 3, 12].
Enkripsi kunci simetrik yang biasanya disebut
enkripsi konvensional adalah enkripsi yang
menggunakan kunci yang sama untuk enkripsi
maupun dekripsi, dari Gambar 2.2 terlihat bahwa
untuk mengenkripsi maupun mendekripsi pesan
hanya menggunakan satu buah kunci (K) saja.
Gambar 2.2 Enkripsi-dekripsi Kunci Simetrik
Penggunaan metode ini membutuhkan
persetujuan antara pengirim dan penerima tentang
kunci sebelum mereka saling mengirim pesan.
Keamanan dari kunci simetrik tergantung pada
kerahasiaan kunci, apabila seorang penyusup dapat
menemukan kunci maka dengan mudah dapat
membaca pesan yang sudah dienkripsi.
Enkripsi kunci simetrik dapat dibagi kedalam 2
(dua) kelompok yaitu metode stream cipher dan
metode block cipher[3,12].
Enkripsi kunci asimetrik (biasa disebut enkripsi
kunci publik) dibuat sedemikian rupa sehingga kunci
yang dipakai untuk enkripsi berbeda dengan kunci
yang dipakai untuk dekripsi. Enkripsi kunci publik
disebut demikian karena kunci untuk enkripsi boleh
disebarluaskan kepada umum sedangkan kunci untuk
mendekripsi hanya disimpan oleh orang yang
bersangkutan[2,3,12]. Enkripsi asimetrik dapat ditulis
seperti berikut:
Ek (P) = C
Dk (C) = P
Contohnya seperti pada Gambar 2.3 bila
seseorang ingin mengirim pesan kepada orang lain
maka orang tersebut menggunakan kunci publik
orang tersebut untuk mengenkripsi pesan yang kita
kirim kepadanya lalu orang tersebut akan
mendekripsi pesan tersebut dengan kunci privat
miliknya.
Gambar 2.3 Enkripsi Kunci Asimetrik
2.2 Tujuan Dari Kriptografi
23
Aplikasi Kriptografi dengan MD5 (Aghus Sofwan, Agung BP, Tony Susanto)
Seperti juga perkembangan ilmu kriptografi,
tujuan-tujuan dari kriptografi teruslah berkembang.
Bila pertama kali dibuat hanya untuk keamanan data
saja, tetapi sekarang semakin banyak tujuan-tujuan
yang ingin dicapai[12], yaitu:
1. Privasi, Musuh tidak dapat membongkar
tulisan yang kita kirim.
2. Autentikasi, Penerima pesan dapat
meyakinkan dirinya bahwa pesan yang
diterima tidak terjadi perubahan dan berasal
dari orang yang diinginkan.
3. Tanda tangan, penerima pesan dapat
meyakinkan pihak ketiga bahwa pesan yang
yang diterima berasal dari orang yang
diinginkan.
4. Minimal, Tidak ada yang dapat
berkomunikasi dengan pihak lain kecuali
berkomunikasi dengan pihak yang
diinginkan.
5. Pertukaran bersama, suatu nilai (misalnya
tanda tangan sebuah kontrak) tidak akan
dikeluarkan sebelum nilai lainnya (misalnya
tanda tangan pihak lain) diterima.
6. Koordinasi, di dalam komunikasi dengan
banyak pihak, setiap pihak dapat
berkoordinasi untuk tujuan yang sama
walaupun terdapat kehadiran musuh.
2.3 Prinsip Dasar Fungsi Hash Satu Arah
Fungsi hash satu arah memiliki banyak
nama: fungsi pembanding, fungsi penyusutan, intisari
pesan, sidik jari, message integrity check (MIC) atau
pemeriksa keutuhan pesan dan manipulation
detection code (MDC) atau pendektesi
penyelewengan kode[3].
Fungsi hash satu arah dibuat berdasarkan ide
tentang fungsi pemampatan. Fungsi hash adalah
sebuah fungsi atau persamaan matematika yang
mengambil input dengan panjang variabel (preimage)
dan merubahnya menjadi panjang yang tetap
(biasanya lebih pendek), keluarannya biasa disebut
nilai hash[3,10].
Fungsi hash satu arah adalah sebuah fungsi
hash yang berjalan hanya satu arah. Adalah mudah
untuk menghitung nilai hash dari pre-image, tetapi
sangat sulit untuk membangkitkan pre-image dari
nilai hash-nya[3].
Metode fungsi hash satu arah adalah
berfungsi melindungi data dari modifikasi. Apabila
ingin melindungi data dari modifikasi yang tidak
terdeteksi, dapat dihitung hasil fungsi hash dari data
tersebut, selanjutnya dapat menghitung hasil fungsi
hash lagi dan membandingkannya dengan hasil yang
pertama apabila berbeda maka terjadi perubahan
selama pengiriman.
Sebagai contohnya adalah bila si pengirim
(A) akan mengirim pesan kepada temannya (B).
Sebelum mengirim, A melakukan hash dari pesannya
untuk mendapatkan nilai hash kemudian dia
mengirim pesan itu beserta nilai hashnya, Lalu B
melakukan hash untuk mencari nilai hash dari pesan
itu bila terjadi perbedaan maka sewaktu pengiriman
telah terjadi perubahan dari pesan tersebut.
Masukan dari fungsi hash satu arah adalah
blok pesan dan keluaran dari blok text atau nilai hash
sebelumnya ini dapat dilihat pada Gambar 2.4
sehingga secara garis besar, hash dari blok Mi adalah:
hi = f(Mi,hi - 1)
Nilai hash ini bersama blok pesan berikutnya
menjadi masukan berikutnya bagi fungsi
pemampatan. Nilai hash keseluruhan adalah nilai
hash dari blok paling akhir. Pre-image sedapatnya
mengandung beberapa binari yang menggambarkan
panjang dari masukan pesan. Teknik ini digunakan
untuk mengatasi masalah yang dapat terjadi bila
pesan yang mempunyai pesan yang tidak sama
mempunyai nilai hash yang sama. Metode ini biasa
disebut MD-strengthening atau penguatan MD[3].
Gambar 2.4 Fungsi Hash Satu Arah
2.4. Sistem Kriptografi MD5
Pada bagian ini dijelaskan mengenai sistem
kriptografi MD-5 secara spesifik, yaitu sistem
kriptografi algoritma MD5 yang menjelaskan dari
awal masukan hingga keluarannya.
2.4.1 Prinsip Dasar MD5
Message Digest 5 (MD-5) adalah salah satu
penggunaan fungsi hash satu arah yang paling
banyak digunakan. MD-5 merupakan fungsi hash
kelima yang dirancang oleh Ron Rivest dan
didefinisikan pada RFC 1321[10]. MD-5 merupakan
pengembangan dari MD-4 dimana terjadi
penambahan satu ronde[1,3,10]. MD-5 memproses teks
masukan ke dalam blok-blok bit sebanyak 512 bit,
kemudian dibagi ke dalam 32 bit sub blok sebanyak
24
Transmisi, Vol. 11, No. 1, Juni 2006 : 22 – 27
16 buah. Keluaran dari MD-5 berupa 4 buah blok
yang masing-masing 32 bit yang mana akan menjadi
128 bit yang biasa disebut nilai hash[3,10].
Pada Gambar 3.1 terlihat simpul utama dari MD-
5. Simpul utama MD5 mempunyai blok pesan
dengan panjang 512 bit yang masuk ke dalam 4 buah
ronde. Hasil keluaran dari MD-5 adalah berupa 128
bit dari byte terendah A dan tertinggi byte D.
B lo k P e s a n
( 5 1 2 b i t )
R o n d e 1 R o n d e 2 R o n d e 3 R o n d e 4
A
B
D
Gambar 3.1 simpul utama MD-5
2.4.2 Penjelasan Algoritma MD-5
Setiap pesan yang akan dienkripsi, terlebih
dahulu dicari berapa banyak bit yang terdapat pada
pesan. Kita anggap sebanyak b bit. Di sini b adalah
bit non negatif integer, b bisa saja nol dan tidak
harus selalu kelipatan delapan[10]. Pesan dengan
panjang b bit dapat digambarkan seperti berikut :
m_0 m_1 …..m_(b-1)
Terdapat 5 langkah yang dibutuhkan
untuk untuk menghitung intisari pesan. Adapun
langkah–langkah tersebut dijelaskan pada
subbab-subbab berikut.
2.4.2.1 Menambahkan bit
Pesan akan ditambahkan bit-bit tambahan
sehingga panjang bit akan kongruen dengan 448,
mod 512. Hal ini berarti pesan akan mempunyai
panjang yang hanya kurang 64 bit dari kelipatan 512
bit. Penambahan bit selalu dilakukan walaupun
panjang dari pesan sudah kongruen dengan 448, mod
512 bit.[3,10] . Penambahan bit dilakukan dengan
menambahkan “1” di awal dan diikuti “0” sebanyak
yang diperlukan sehingga panjang pesan akan
kongruen dengan 448, mod 512.
2.4.2.2 Penambahan Panjang Pesan
Setelah penambahan bit, pesan masih
membutuhkan 64 bit agar kongruen dengan kelipatan
512 bit. 64 bit tersebut merupakan perwakilan dari b
(panjang pesan sebelum penambahan bit dilakukan).
Bit-bit ini ditambahkan ke dalam dua word (32 bit)
dan ditambahkan dengan low-order terlebih dahulu.
Penambahan pesan ini biasa disebut juga MD
Strengthening atau Penguatan MD[3].
2.4.2.3 Inisialisasi MD-5
Pada MD-5 terdapat empat buah word 32 bit
register yang berguna untuk menginisialisasi
message digest pertama kali. Register-register ini
di inisialisasikan dengan bilangan hexadesimal.
word A: 01 23 45 67
word B: 89 AB CD EF
word C: FE DC BA 98
word D: 76 54 32 10
Register-register ini biasa disebut dengan
nama Chain variabel atau variabel rantai.
2.4.2.4 Proses Pesan di dalam Blok 16 Word
Pada MD-5 juga terdapat 4 (empat) buah
fungsi nonlinear yang masing-masing digunakan
pada tiap operasinya (satu fungsi untuk satu blok),
yaitu:
F(X,Y,Z) = (X Ù Y) Ú ((Ø X) Ù Z)
G(X,Y,Z) = (X Ù Z) Ú (Y Ù (Ø Z))
H(X,Y,Z) = X Å Y Å Z
I (X,Y,Z) = Y Å (X Ú (Ø Z))
(Å untuk XOR, Ù untuk AND, Ú untuk OR dan Ø
untuk NOT).
Pada Gambar 3.2 dapat dilihat satu buah
operasi dari MD-5 dengan operasi yang dipakai
sebagai contoh adalah FF(a,b,c,d,Mj,s,ti) menunjukan
a = b + ((a + F(b,c,d) + Mj + ti) <<< s)
Bila Mj menggambarkan pesan ke-j dari sub
blok (dari 0 sampai 15) dan <<<s menggambarkan
bit akan digeser ke kiri sebanyak s bit, maka keempat
operasi dari masing-masing ronde adalah:
25
Aplikasi Kriptografi dengan MD5 (Aghus Sofwan, Agung BP, Tony Susanto)
FF(a,b,c,d,Mj,s,ti) menunjukan a = b + ((a +
F(b,c,d) + Mj + ti) <<< s)
GG(a,b,c,d,Mj,s,ti) menunjukan a = b + ((a +
G(b,c,d) + Mj + ti) <<< s)
HH(a,b,c,d,Mj,s,ti) menunjukan a = b + ((a +
H(b,c,d) + Mj + ti) <<< s)
II(a,b,c,d,Mj,s,ti) menunjukan a = b + ((a +
I(b,c,d) + Mj + ti) <<< s)
A
B
C
D
F u n g s i F
< < <
S
M j t i
Gambar 3.2 Satu buah operasi MD-5
Konstanta ti didapat dari integer 232. abs(sin(i)),
dimana i dalam radian.
2.4.2.5 Keluaran MD-5
Keluaran dari MD-5 adalah 128 bit dari word
terendah A dan tertinggi word D masing-masing
32 bit.
3. Perancangan Aplikasi
· Spesifikasi:
Aplikasi yang digunakan adalah aplikasi
32-bit yang berjalan pada sistem operasi
Windows 98 ke atas.
Aplikasi berbentuk sebuah file
executable dengan nama md5_test.exe
Aplikasi md5_string ® mencari
nilai hash dari masukan berupa karakterkarakter
yang dimasukkan oleh pemakai
melalui keyboard.
Aplikasi md5_file ® mencari nilai
hash dari masukan berupa file yang
dipilih oleh pemakai.
Aplikasi test suite untuk memeriksa
bahwa program yang sudah dibuat sudah
sesuai RFC 1321.
Aplikasi ini juga terdapat contoh
penggunaan dari MD5.
3.1 Proses MD-5 Dengan Masukan Berupa String
Proses MD5 dengan masukan berupa string
adalah proses yang masukan nya berupa
karakter-karakter yang dimasukan melalui
keyboard. Hal ini dapat dilihat pada gambar 3.1
M u la i
P r o s e s
M D 5
L a k u k a n
P a d d in g
L a k u k a n
I n is ia lis a s i
M a s u k k a n
K a r a k t e r
C e t a k H a s il
P a d a L a y a r
Gambar 3.1 Proses MD5 dengan masukan string
3.2 Proses MD5 Dengan Masukan Berupa File
Proses MD5 dengan masukan berupa file
adalah proses MD5 yang masukannya memanggil
file yang kemudian dihitung berapa panjang bitnya,
dalam keadaan ini file diperlakukan sebagai bit
memori sehingga masukannya tidak terpengaruh
pada ekstensinya. Kemudian dilakukan proses MD5.
Hal ini dapat dilihat pada Gambar 3.2.
M u la i
M e m a n g g il
F ile
M e n g h it u n g
P a n j a n g F ile
L a k u k a n
P a d d in g
L a k u k a n
In is ia lis a s i
M u la i P r o s e s
M D 5
C e t a k H a s il
P a d a L a y a r
Gambar 3.2 Proses MD5 dengan Masukan File
3.3 Proses MD5 Sebagai Test Suite
Test suite dilakukan untuk mengetahui
apakah program yang dibuat ini sudah benar atau
tidak. Sebagai perbandingannya digunakan hasil
yang sudah dibuat oleh Ron Rivest yang sudah
didefinisikan pada RFC 1321. Pada Gambar 3.3
dapat dilihat bahwa masukan dari MD5 sudah
ditentukan sehingga hanya membandingkan hasil
pada layar dengan yang tercantum pada RFC 1321.
M u la i
C e t a k H a s il
P a d a L a y a r
M e la k u k a n
P r o s e s M D 5
Gambar 3.3 Proses MD5 Sebagai Test Suite
3.4 Contoh Aplikasi
Pada Contoh Aplikasi ini terdapat dua buah
aplikasi yang dipakai yaitu Simpan dan Tampil.
Simpan akan menyimpan data yaitu berupa Nama,
nilai ujian dan nilai hash-nya. Akhir akan melakukan
perhitungan MD5 dari data yang disimpan untuk
mendapatkan nilai hash-nya yang kemudian
membandingkan nilai hash-nya dengan nilai hash
dari data semula, apabila nilai hash yang di dapat
sama maka data akan ditampilkan. Tetapi bila nilai
hash yang di dapat berbeda maka pada form Akhir
akan ditampilkan pesan bahwa data terdapat
kesalahan atau perubahan
26
Transmisi, Vol. 11, No. 1, Juni 2006 : 22 – 27
3.5 Pengukuran Kecepatan Aplikasi
Pengukuran kecepatan aplikasi merupakan
sebuah analisa yang akan dipakai untuk mengukur
tingkat kecepatan dari proses mencari nilai hash dari
file dengan menggunakan aplikasi MD5
Adapun rumus yang dipakai dalam aplikasi
untuk menghitung kecepatan mencari nilai hash
tersebut adalah:
Besar Ukuran File
Kecepatan =
Lama waktu proses
Satuan dari kecepatan enkripsi ini adalah
Mbytes/detik
Dalam analisa kecepatan ini, akan dilakukan
sebanyak 5 (lima) kali pengambilan waktu terbaik
yang diperlukan untuk enkripsi untuk setiap filenya
kemudian dicari waktu rata-ratanya.
besar file dan tabel perbandingan kecepatan
maksimum dengan kecepatan rerata terhadap besar
file
4. Analisis Kecepatan MD5
Analisis kecepatan disini adalah analisis
tentang kecepatan aplikasi dalam mengenkrip file
untuk mencari nilai hash. Analisis dilakukan untuk
mencari kecepatan aplikasi dengan masukan file yang
mempunyai besar berbeda-beda
Pengujian dilakukan dengan cara mengenkrip
file sebanyak 31 (tigapuluh satu) buah file dengan
besar file yang berbeda-beda. Setiap file dilakukan
pengambilan waktu eksekusi sebanyak 5 kali
kemudian mencari waktu reratanya.
4.1 Hasil Pengujian
Hasil pengujian digambarkan dengan tabel
hasil pengujian, yang kemudian dijabarkan dengan
grafik hasil uji coba terhadap file yaitu Grafik
kecepatan aplikasi terhadap besar file, Grafik rerata
waktu eksekusi terhadap besar file dan Tabel
perbandingan kecepatan maksimum dengan
kecepatan rerata terhadap besar file.
5 Kesimpulan
Beberapa kesimpulan yang dapat diperoleh dari
makalah ini adalah:
1. Message Digest 5 (MD5) adalah sebuah
fungsi hash satu arah yang mengubah
masukan dengan panjang variabel menjadi
keluaran dengan panjang tetap yaitu 128 bit.
2. Rerata kecepatan dari program aplikasi MD-
5 adalah 7,1633 Mbytes/detik
3. Aplikasi yang dibuat hanya efektif digunakan
untuk ukuran file kurang dari 40 Mbytes.
4. Sumber daya komputer berpengaruh terhadap
kecepatan enkripsi.
6. Saran
Adapun saran-saran dari penulis tentang aplikasi ini
adalah:
1. Aplikasi MD5 dapat digabungkan dengan
algoritma kriptografi lainnya sehingga
didapat aplikasi kriptografi yang lebih
handal.
2. Untuk pengembangan selanjutnya, contoh
aplikasi dapat mempergunakan 2 (dua)
komputer atau lebih.
7. DAFTAR PUSTAKA
1. A.Menezes, P. Van Oorschot, S. Vanstone.
Handbook of applied Cryptography. CRC
Press 1996.
2. Pfleeger, Charles P, Security in Computing
Second Edition. Prentice-Hall International,
Inc, New Jersey, 1997
3. B. Schneier, Applied Cryptography, John
Wiley & Sons, New York, 1994
4. Tanenbaum, Andrew S, Jaringan Komputer
Edisi Indonesia Dari Computer Network
Edisi III, Prenhallindo, Jakarta, 1997
5. ---, http:// www.counterpane.com/
6. ---, http:// www.cryptography.com.
7. ---, http:// www.cryptography.org
8. ---,http://www.eskino.com/~weidai
/benchrarks.html.
9. ---, http:// www.cwi.nl/~kik/persb-UK.html.
10. ---, http://www.faqs.org/ftp/rfc/ rfc1321.txt
11. ---, http://www.spitzner.net/pubs.html
12. ---, http://www.secure-hash-algorithm-md5-
sha-1.co.uk/index.htm
27
Sabtu, 26 November 2011
FUNGSI ALGORITMA
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
1
PENGGUNAAN ALGORITMA GENETIKA DALAM
PENINGKATAN KINERJA FUZZY CLUSTERING UNTUK
PENGENALAN POLA
(Application of Genetic Algorithm to Enhance the Performance of Clustering
Fuzzy in Pattern Recognition)
Naniek Widyastuti1, Amir Hamzah1
1Fakultas Teknologi Industri, Institut Sains & Teknologi AKPRIND Yogyakarta
ABSTRAK
Algoritma genetika (AG) adalah metode untuk menyelesaikan persoalan optimasi berbasis
teori evolusi dalam biologi. Algoritma ini bekerja pada populasi calon penyelesaian yang
disebut kromosom yang awalnya dibangkitkan secara random dari ruang penyelesaian
fungsi tujuan. Dengan menggunakan mekanisme opearator genetik yaitu persilangan dan
mutasi populasi dievolusikan melalui fungsi fitness yang diarahkan pada kondisi
konvergensi. Algoritma ini dapat diterapkan dalam banyak area fungsi-fungsi optimasi,
salah satu penerapannya adalah fungsi objektif berbasis fuzzy clustering.
Fuzzy clustering bertujuan mengelompokkan n objek yang disajikan dengan vektor
kedalam C-cluster berdasarkan kesamaannya dengan pusat cluster yang diukur melalui
fungsi jarak. Fungsi tujuan Jm didefinisikan sebagai fungsi V (matriks sifat prototipe)
dan U ( fungsi keanggotaan Fuzzy dari objek i: 1, 2, . . . .,n menjadi anggota cluster j: 1, 2,
. . . . , c) yang diminimumkan melalui iterasi. Karena sensitivitas inisiasi random terjebak
dalam minimum lokal, pendekatan genetik biasanya dapat diterapkan untuk
menghilangkan masalah diatas.
Penelitian ini ditujukan untuk mempelajari unjuk kerja AG pada masalah fuzzy
clustering, khususnya fuzzy C Mean (FCM). Guided GA (GGA) sebagai alternatif FCM
diperkenalkan melalui kode MATLAB, kedua algoritma ini dibandingkan melalui tiga
kasus numerik. Unjuk kerja FCM dan GGA-FCM diuji melalui beberapa parameter
seperti kesahihan cluster, kompleksitas, laju klasifikasi komputasi. Hasilnya
menunjukkan bahwa GGA-FCM mempunyai unjuk kerja yang lebih baik dibandingkan
FCM dalam bentuk Jm, kesahihan cluster dan laju klasifikasi, meskipun dalam
kompleksitas komputasi lebih rumit dan memerlukan waktu lebih banyak.
Kata kunci : fuzzy cluctering, Algoritma Genetika, GGA-FCM, FCM.
ABSTRACT
Genetic Algorithm(GA) is a method for solving optimization problem that based on
evolutionary theory in biology. This algorithm work with a population of candidate
solutions named as chromosom that initially generated randomly from the area of the
solution space of objective function. By using a mechanism of genetic operator i.e. crossover
and mutation the population is evoluted controlled by fitness function that directed to
konvergence condition. This algorithms can be applied in many area of function
optimizations, one of those is applications on objective function based fuzzy clustering.
Fuzzy clustering aims to cluster n objects represented by feature vectors into c cluster
based on similarity to the cluster center measured by a distance function. Objective
function Jm was defined as function of V (matrix of feature prototype) and U(fuzzy
Berkala MIPA, 17(2), Mei 2007
2
membership function of object i:1,2,..,n become member of cluster j:1,2,…,c) to be
minimized through iteration. Because of sensitivity to random initialization to be trapped
in local minima, genetic approach generally can be applied to reduce this problem.
This research was aimed to study the performance of GA approach to the problem of
fuzzy clustering, mainly fuzzy-c-mean (FCM). The Guided Genetic Algorithm as an
alternative to FCM, called GGA-FCM was introduced to be coded in MATLAB script.
The two algorithms was compared through the tests of those algorithms with three
numerical cases. The performance of both FCM and GGA-FCM was examined by some
parameters such as cluster validity, complexity of computation classification rate. The
results showed that GGA-FCM has better performance than FCM in terms of Jm, cluster
validity and classification rate, although in term of computational complexity is more
complex and time consuming.
Keywords: fuzzy clustering, genetic algorithm, GGA-FCM, FCM
Makalah diterima tanggal 3 April 2007
1. PENDAHULUAN
Pengenalan pola (pattern recognition)
merupakan konsep yang sangat luas
aplikasinya dalam banyak bidang antara lain
: biomedical (EEG,ECG,Röntgen, Nuclear,
Tomography,Tissue,Cells,Chromosomes,
meteorolgy (remote sensing), industrial
inspection (robotic vision) dan digital
microscopy. Beberapa aplikasi dalam bidang
komputer dan informatika diantaranya :
Speech recognition, speaker identification,
character recognition, signature verification,
image segmentation dan artifcial
intelligence.
Belanche and Nebot (2002)
menggambarkan pengenalan pola secara
garis besar sebagai serangkaian kegiatan
yang mencakup: kegiatan pengukuran dunia
nyata dengan alat ukur yang
menggambarkan fenomena yang akan
diukur diikuti serangkaian kegiatan:
preprosesor, ekstrak feature, klasifikasi atau
diskrips i pola (lihat Gambar 1). Kegiatan
yang fital dalam pengenalan pola adalah
kegiata klasifikasi dari ruang feature yang
diperoleh dari kegiatan seleksi dan ekstrak
feature.
Metode yang lebih baik dari metode
clustering secara tegas adalah aplikasi teori
fuzzy dalam proses kluster (fuzzy
clustering). Hamzah (2001) menunjukkan
bahwa proses kluster secara fuzzy (fuzzy
clustering) menunjukkan hasil yang lebih
baik dan lebih alami dibandingkan dengan
proses kluster dengan pendekatan tegas.
Sejak dikembangkan pertama kali oleh
Holland tahun 1975, algoritma genetika
(Genetic Algoritms=GA) terus mengalami
perkembangan dalam banyak aplikasi (Gen
and Cheng 2000). Pesatnya perkembangan
applikasi GA pada berbagai problem
optimasi dipacu oleh perkembangan
teknologi komputer dan mikro prosesor.
Salah satu minat dalam aplikasi
genetic -fuzzy system adalah genetic -fuzzy
clustering. Pada fuzzy clustering berbasis
fungsi tujuan persoalan mencari kluster
terbaik akan identik dengan persoalan
optimasi fungsi tujuan. Penggunaan
algoritma genetika untuk fuzzy clustering
dimungkinkan dapat meningkatkan unjuk
kerja fuzzy clustering. Penerapan GFS pada
Gambar 1. Skema Kegiatan dalam Pengenalan Pola(Belanche
and Nebot, 2002)
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
3
fuzzy clustering terutama Fuzzy-C-Means
Clustering (FCM) adalah untuk
mengoptimasi parameter-parameter dalam
FCM.
Pertanyaan yang muncul kemudian
dalam penerapan GA pada FCM adalah
sejauh mana peningkatan kinerja FCM
dengan pendekatan GA tersebut. Parameterparameter
FCM apa yang kemudian harus
dipertimbangkan dalam penerapan GA, latar
belakang inilah yang mendasari
dilakukannya penelitian ini.
Adapun tujuan penelitian ini adalah
mengkaji penerapan algoritma genetika
dalam fuzzy clustering, utamanya FCM,
serta mengkaji sejauh mana algoritma
genetika dapat meningkatkan unjuk kerja
fuzzy clustering.
Fuzzy-C-Means clustering
Pada pendekatan tegas (crisp), untuk
setiap objek ke-k (k=1...n) secara tegas
hanya dapat menjadi anggota cluster ke-i
(i=1..c), dengan keputusan menjadi anggota
kluster ke-i berdasarkan jarak minimal
objek ke-k dengan pusat-pusat kluster ke-i.
Algoritma pendekatan tegas dengan jumlah
kluster k Clustering dan pusat kluster
ditentukan dengan cara rata -rata ini sering
disebut sebagai K-Means.
Pada pendekatan fuzzy metode
klustering berdasarkan kenyataan bahwa
objek-objek tertentu mungkin secara tegas
tidak dapat dikelompokkan pada kluster
tertentu. Dengan pendekatan fuzzy setiap
objek ke-k (k=1,2,..,n) dianggap menjadi
anggota dari semua kluster ke-i (i=1,2,..,c)
dengan fungsi keanggotaan antara 0 sampai
1. Keputusan objek ke-i menjadi anggota
kluster ke-j berdasarkan fungsi keanggotaan
yang terbesar. Model clustering seperti ini
terkenal dengan sebutan Fuzzy-C-Means
Clustering (FCM).
Banyak macam fungsi objektif telah
dirumuskan, baik yang pendekatan tegas
(crisp) maupun pendekatan fuzzy (Sato and
Sato, 1995). Untuk menghasilkan formulasi
yang presisi dalam menentukan kriteria
klustering dapat ditempuh dengan metode
fungsi objektif (objective-function methods),
yaitu dengan mengukur kemampuan untuk
dilibatkan dalam kluster sebagai fungsi dari
c (yaitu cacah kluster) dengan suatu fungsi
objektif tertentu (Zimmerman, 1991). Fuzzy
clustering FCM dengan fungsi tujuan
menggunakan jarak euclidean
mengasumsikan bentuk fungsi tujuan
spherical. Untuk data tertentu kondisi
spherical mungkin tidak terpenuhi.
Pemilihan fungsi tujuan dan kriteria
jarak dengan demikian sangat tergantung
pada sebaran data objek. Untuk fungsi
tujuan spherical dimana FCM dengan jarak
eucledian didefinisikan, kriteria kluster yang
baik selanjutnya adalah kluster yang
meminimalkan fungsi tujuan Jm yang
dirumuskan sebagai fungsi dari U dan V
sebagai berikut :
Jm(U,V)= ( - x k )
1
2
1
å å
= =
n
k
ik i
m
ik
c
i
m D v (1)
untuk: i=1,2,…,c dan k=1,2,…,n.
Matrik U Î Mcn adalah matrik partisi
dengan ordo cxn dengan elemen matrik mik.
Untuk klustering secara tegas mik Î {0,1},
yaitu bernilai 1 jika objek k anggota kluster i
dan 0 jika tidak. Untuk klustering secara
fuzzy mik Î [0,1] yang bernilai real. Nilai
parameter m merupakan derajat ke-fuzzi-an
dari proses klustering dengan nilai mÎ[1,¥
). V=[v1, v2,.., vc] adalah matrik parameter
prototipe (pusat kluster) viÎÂp . Dik
2(vi , xk )
adalah jarak dari vektor xk ke pusat kluster
vi.
Struktur kluster terbaik yang dicari
adalah penyelesaian minimum (minimizer)
untuk persamaan (1) yang dapat diselesaikan
dengan proses iterasi untuk penyelesaian
optimasi fungsi. Pada penyesuaian iterasi
mula-mula dibangkitkan vektor pusat kluster
secara acak dan kemudian iterasi dilakukan
untuk mengupdate matrik U. Iterasi
dilakukan sampai matrik U relatif tidak
berubah. Berikut adalah nilai U dan V
berturut-turut yang digunakan dalam iterasi:
Berkala MIPA, 17(2), Mei 2007
4
untuk i 1,2,..., c; k 1,2,..., n ( 2 )
1
1
1
2
1 /( 1)
2
= =
ú ú
û
ù
ê ê
ë
é
-
ú ú
û
ù
ê ê
ë
é
-
=
å=
-
c
j
m
k j
m
k i
ik
x v
x v
m
Dengan nilai U yang telah diupdate,
maka vektor pusat kluster diperbaharui
dengan :
v 1 untuk i 1,2,..., c
1
1
i = å =
å =
=
n
k
ik
m
n ik
k
m
ik
m x
m
(3)
Proses penyelesaian optimasi secara
klasik sering menghantar pada penyelesaian
yang merupakan optimum lokal dari
himpunan penyelesaian yang mungkin.
Pendekatan algoritma genetika dapat
menjadi alternatif yang dapat diterapkan
pada proses penyelesaian optimasi yang
menghindari optimum lokal.
Algoritma Genetika
Algoritma genetika dikembangkan
pertama kali oleh Holland tahun 1975 (Gen
and Cheng,2000). Sejak dikembangkan
sampai saat ini GA ini terus menjadi objek
riset dalam berbagai aplikasi. Alasan
mengapa GA banyak menjanjikan, antara
lain banyak problem dibidang sains dan
teknik tidak dapat dipecahkan dengan
algoritma deterministik biasa meskipun
dengan waktu yang meningkat secara
polynomial.
Secara umum algoritma ini memiliki
prosedur yang dapat dirumuskan sebagai
berikut Procedure Genetic Algoritms
Begin
tß 0
initialize P(t)
evaluate P(t)
while (not termination condition )
do
begin
recombine P(t) to yield C(t)
evaluate C(t)
select P(t+1) from P(t) and C(t)
t ß t+1
end
end
Dengan t = generasi, P(t)= Populasi pada
generasi t , dan C(t)=Populasi tambahan atau
individu baru (offspring) dari hasil proses
operasi genetik Cross Over dan Mutasi.
Encoding.
Dalam algoritma genetika pengkodean
(encoding) solusi problem kedalam suatu
kromosom merupakan isu penting. Populasi
awal yang berisi N kromosom dibangkitkan
secara random yang menjangkau
keseluruhan ruang solusi. Proses evolusi
dilakukan dengan melakukan operasi
genetik (cross-over dan mutasi) dan
melakukan seleksi kromosom untuk generasi
berikutnya sampai sejumlah generasi yang
dikehendaki dengan panduan fungsi fitness.
Algoritma genetika pada dua ruang,
yaitu ruang solusi (disebut phenotip) dan
ruang coding (disebut genotip). Operasi
genetika (cross over dan mutasi) dilakukan
pada ruang genotip sementara operasi
seleksi dilakukan pada ruang phenotip.
Dalam binary encoding variabel keputusan
diwakili oleh deretan bit 0,1 yang
panjangnya disesuaikan dengan ruang
pencarian. Tiap bit 0,1 dapat dianggap
sebagai sebuah gen. Untuk optimasi 2
variabel misalnya, maka solusi adalah x1
dan x2.
Integer dan literal permutation
encoding adalah kode terbaik untuk problem
combinatorial optimization karena inti dari
problem ini adalah mencari kombinasi atau
permutasi terbaik dari item solusi terhadap
kendala yang ada. Untuk problem yang lebih
komplek encoding menggunakan data
struktur yang lebih sesuai.
Fungsi fitness.
Fungsi fitness adalah fungsi yang
digunakan untuk menjustifikasi apakah
suatu kromosom layak bertahan. Pada setiap
generasi dipilih kromosom yang mendekati
solusi dengan mengevaluasi fungsi
kecocokan dari kromosom tersebut. Fungsi
ini didefinisikan sedemikian sehingga
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
5
semakin besar nilai fitness semakin besar
probabilitas untuk terseleksi pada generasi
berikutnya. Untuk maksimasi maka fungsi
tujuan dapat dijadikan sebagai fungsi fitness,
sehingga kromosom yang mewakili nilai
fungsi besar akan memiliki probabilitas
terseleksi yang besar juga. Untuk minimasi
dapat dirumuskan sedemikian sehingga
fungsi tujuan yang semakin kecil maka
memiliki fungsi fitness yang besar.
Pada penyelesaian yang berada diluar
daerah visible dapat digunakan suati
modifikasi fungsi fitness dengan
menambahkan suatu fungsi yang sering
disebut sebagai fungsi penalti, sehingga
fungsi fitness menjadi :
fitness(x)=f(x)+p(x) (4)
Seleksi.
Setiap anggota populasi diwakili
deretan string (disebut kromosom) dengan
panjang tertentu. Elemen string tersebut
dapat berupa digit 0,1 (untuk binary
encoding), bilangan real (untuk real
encoding), atau elemen lain. Untuk ukuran
populasi N yang biasanya dipertahankan
tetap prosedur seleksi diperlukan untuk
memilih anggota populasi yang mana yang
akan tetap eksis pada generasi berikutnya.
Fungsi fitness digunakan untuk
menjustifikasi apakah kromosom layak
dipertahankan atau tidak dalam generasi
berikutnya.
Sebelum dilakukan seleksi jumlah
anggota populasi ditambah dengan hasil
offspring dari proses operasi genetik yang
dapat berupa cross over dan mutasi. Hasil
operasi genetik dan populasi semula
selanjutnya diseleksi dengan metode tertentu
untuk diambil n anggota populasi yang
terbaik. Untuk kasus minimasi maka yang
terpilih adalah n anggota populasi dengan
nilai fitness yang terkecil.
Crossover.
Proses operasi crossover dirancang
untuk mencari kemungkinan yang lebih baik
dari anggota populasi yang telah ada. Dari
pasangan induk yang terpilih berdasarkan
seleksi fungsi fitness diambil sejumlah
pasangan dengan probabilitas Pc untuk
dikenakan operasi crossover.
Mutasi.
Mutasi dalam konteks binary encoding
adalah perubahan pada bit tunggal (bit 0 jadi
1 dan sebaliknya) anggota populasi yang
terpilih. Banyaknya bit yang mengalami
mutasi pada setiap generasi diatur oleh
probabilitas mutasi (Pm) yang nilainya
merupakan cacah bit mutasi dibagi cacah bit
total dalam populasi.
Algoritma Genetika Untuk Fuzzy
Clustering.
Algoritma genetika (GA) sebagai
teknik optimasi dapat diterapkan pada
clustering yang berbasis optimasi fungsi
tujuan. Pada pendekatan GA untuk fuzzyclustering
fungsi fitness diambil dari fungsi
objektif yang diminimumkan, yaitu
Jm(U,V).
Validitas Clustering dan Classification
Rate.
Hasil akhir FCM atau GGA-FCM
adalah V,U dan Rm tertentu untuk suatu c
yang diinputkan. Pada beberapa kasus c
yang tepat mungkin tidak diketahui. Untuk
itu beberapa pendekatan telah diusulkan
untuk menentukan berapa sebaiknya c
sehingga hasil klustering dapat dianggap
terbaik. Ukuran ini dikenal sebagai validitas
klustering. Chi et.al. (1996) merangkum
setidaknya ada empat alat ukur, yaitu :
1. Koefisien Partisi (partition
coefficient)
Koefisien Partisi didefinisikan
sebagai fungsi U dan c:
åå
= =
=
c
i
n
k
ik u
n
F U c
1 1
( )2
1
( , ) (5)
Koefisien partisi ini mengukur kedekatan
dari semua sampel masukan terhadap
prototipe yang terpilih.
2. Entropy partisi (Parttion Entropy)
åå
= =
= -
c
i
n
k
ik ik u u
n
H U c
1 1
log( )
1
( , ) (6)
Entropy partisi (0<H(u,c)<log c)
diterjemahkan sebagai derajat
ketidakpastian (degree of fuzzyness) dari
objek. H(U,c) besar yang menunjukkan
hasill klustering yang jelek.
Berkala MIPA, 17(2), Mei 2007
6
3. Fungsi validitas Kekompakan dan
separasi (compactness and
separation validity function)
| |
1
( , ) 2
min | |
i, k
1 1
2 2
v k v i
c
i
n
k
ik k i u x v
S U c n
-
å å
= =
-
=
(7)
S(U,c) adalah rasio antara rata-rata jarak
sampel dengan prototipe yang terpilih
dengan minimum jarak antar prototipe.
Classification rate.
Keberhasilan clustering terkadang
diukur juga melalui kemampuan clustering
tersebut dalam klasifikasi objek. Hal ini
dapat ditentukan apabila objek-objek yang
diklasifikasi telah diketahui berasal dari
suatu klas tertentu. Banyaknya objek yang
dapat diklasifikasikan dengan tepat sesuai
dengan klas dari mana objek tersebut berasal
disebut sebagai classification rate. Index ini
dapat dituliskan sebagai :
CR= x100%
N
n
(8)
Dimana : n=banyaknya objek yang dapat
diklasifikasi dengan benar N=banyaknya
objek yang diklasifikasi
Algoritma Fuzzy clustering konvensional
(FCM).
Berikut diuraikan algoritma fuzzy
clustering konvensional, yaitu penyelesaian
fuzzy clustering dengan cara iteratif dengan
melakukan update pada matrik keanggotan
U dan matrik prototipe kluster V. Dalam
algoritma diperlukan : Sampel objek
sebanyak n, tiap objek p parameter,
dituliskan : X={x1,x2,…,xn} xi
ÎRp ,
i=1,2,…,n. Ditentukan dalam proses
penyelesaian melalui iterasi :
U=[mik] matrik ukuran cxn ; i=1,2,…,c ;
k=1,2,…,n; V={v1,v2,…,vc} i=1,2,…,c
Berikut adalah algoritma yang diajukan :
1. Initialization step :
Tentukan: n=cacah objek yang akan
dikluster ; p=cacah parameter dalam tiap
objek; c=cacah kluster; t=0 (iterasi ke);
m=derajat fuzziness = dipilih 2;
e=nilai yang cukup kecil mendekati
0
Tentukan secara acak : U(0) dan V(0)
2. Iteration step :
a). Dengan menggunakan U(t) ,
hitung pusat kluster V(t) menurut rumus :
untuk i 1,2,..., c, (9)
v 1
1
1
i
=
= å
å =
=
n
k
ik
m
n ik
k
m
ik
m x
m
b). Dengan menggunakan V(t) ,
update membership U(t) ,dengan rumus
:
untuk i 1,2,..., c; k 1,2,..., n (10)
1
1
1
2
1 /( 1)
2
= =
ú ú
û
ù
ê ê
ë
é
-
ú ú
û
ù
ê ê
ë
é
-
=
å= -
c
j
m
k j
m
k i
ik
x v
x v
m
c). Jika max( |mik
(t) - mik
(t-1) | ) < e
berhenti, Jika tidak ulangi langkah 2.a).
Diagram alir untuk Fuzzy Clustering
seperti tersaji dalam Gambar 3.
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
7
n o
y e s
S T A R T
T e n t u k a n : m ,
t = 0
T e n t u k a n s c r a c a k :
U ( t ) d a n V ( t )
B a c a : x
c
F o r i = 1 t o c
N o r m a l i s a s i x
F o r i = 1 t o c
F o r k = 1 t o n
m a x ( ¦ μ i k ( t ) - μ i k ( t - 1 ) ¦ ) < e
S T O P
t = t + 1 å
=
-
ú ú
û
ù
ê ê
ë
é
-
ú úû
ù
ê êë
é
-
=
c
j
m
k j
m
k i
ik
x v
x v
1
2
1 / ( 1 )
2
1
1
m
å
å =
=
=
n
k
i k
m
n ik
k
m
ik
x
1
1
i
v 1 m
m
Algoritma Fuzzy Clustering dengan
Pendekatan Algoritma genetika
(GeneticGuidedAlgorithm for Fuzzy c-
Means = GGA-FCM)
Pada pendekatan algoritma genetika
untuk penyelesaian fuzzy clustering
ditempuh pilihan untuk menggunakan
pendekatan Prototype-based algorithms,
yaitu meng-evolusikan matrik pusat cluster
V. Beberapa hal yang ditentukan adalah :
Encoding dan Struktur kromosom :
Encoding yang digunakan adalah real
encoding . Struktur kromosom untuk V
dalam populasi yang dievolusikan adalah
vektor real beranggotakan cxp elemen
(c=cacah kluster dan p cacah elemen dalam
objek), seperti dalam Gambar 4.
1 2 … p 1 2 … p 1 2 … p
… … …
v1 v2
Fungsi Fitness :
Fungsi fitness yang digunakan adalah
objective function Jm, yaitu:
Jm(U,V)= ( - x k )
1
2
1
å å
= =
n
k
ik i
m
ik
c
i
m D v (11)
Dimana mik dikalkulasi dengan :
untuk i 1,2,..., c; k 1,2,..., n
1
1
1
2
1 /( 1 )
2
= =
ú ú
û
ù
ê ê
ë
é
-
ú ú
û
ù
ê ê
ë
é
-
=
å=
-
c
j
m
k j
m
k i
ik
x v
x v
m
(12)
dan jarak Dik
2 menggunakan jarak eucledian.
Gambar 3. Diagram Alir Fuzzy Clustering (FCM)
Gambar 4. Struktur Kromosom untuk Encoding V
Berkala MIPA, 17(2), Mei 2007
8
Operasi Genetik .
Cross-Over:
Operasi cross over dipilih metode onepoint
cross-over, yaitu untuk tiap kromosom
induk ditetapkan 1 titik secara random antara
1 sampai cxp, misalkan disebut titik r.
Selanjutnya offspring didapatkan dengan
mensilangkan (cross-over) nilai mulai posisi
r sampai akhir kromosom. Untuk lebih
jelasnya urutan cross over disajikan dalam
Gambar 5.
Langkah 1. Pilih titik r : angka random antara 1 sampai cxp
Induk-1 … … …
Induk-2 … … …
Langkah 2. Tukarkan nilai vektor antara titik r sampai akhir
r
Offspring-
1
… … …
Offspring-
2
… … …
Mutasi :
Metode mutasi yang dipilih adalah
Nonuniform mutation dengan algoritma
untuk mutasi dapat dituliskan sebagai
berikut :
1. Pilih satu induk yang akan dimutasi
berdasarkan fungsi fittness dari
kromosom anggota populasi
2. Tentukan digit (posisi) gen yang
akan dimutasi, dengan menentukan k=
<1= bilangan random <= n
3. Pilih gen yang dimutasi, yaitu : xk
4. Tentukan batas bawah (xk
L)dan
batas atas (xk
U)
5. Nilai offspring diperoleh (xk’)
dipilih secara acak dari salah satu :
xk’= xk’+D(t, xk
U- xk) atau
xk’= xk’+D(t, xk - xk
L)
Dengan kisaran (range) nilai real
untuk xk adalah [xk
L
, xk
U].
Nilai D(t, xk - xk
L) atau D(t, xk
U- xk)
dari kriteria itu diberikan oleh :
D(t ,y)=yr(1-t/T)b, dengan r = bilangan
random kisaran [0,1] dan b adalah
bilangan bulat.
Mutasi V
k= round(rand *(n-1))+1
Pilih xk dari V
Tentukan xL dan xU
Pilih secara acak
xk’= xk’+ rand*(xkU- xk) (1-t/T)b atau
xk’= xk’+ rand*(xk - xkL) (1-t/T)b
RETURN
Gambar 6. Diagram Alir Mutasi
Gambar 5. One-point cross over untuk kromosom
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
9
2. PEMBAHASAN
Kasus yang dijadikan bahan pengujian
algoritma-algoritma yang diteliti adalah
Kasus 1. Data dua dimensi dengan jumlah
sampel 14 objek
Tabel 1. Data vektor atribut untuk 14
objek
Objek
Ke-k
X(k)
X1
(k) X2
(k)
1 1 1
2 8 4
3 2 6
4 2 1
5 8 0
6 2 2
7 8 2
8 4 5
9 7 3
10 1 2
11 9 3
12 1 5
13 9 1
14 5 6
Kasus 2. Data matrik pixel dari citra peta
berukuran 134 x 153 x 3 dengan derajat
keabuan 0 sampai 255 sebagai Gambar 8
(Chi et.al., 1996). Dari kasus-kasus yang
dicobakan dibandingkan hasil Fuzzy-
Clustering konvensional dan Genetic
Algorithm Fuzzy Clustring ditinjau dari
beberapa aspek antara lain : waktu
komputasi, Classification rate, Cluster
Validity.
Pengujian kasus 1
Secara visual data kasus 1 (14 objek dua
dimensi) dapat digambarkan seperti Gambar
9.
Dari Tabel 2 terlihat bahwa semakin
besar nilai C maka nilai Jm (untuk m=2
ditulis sebagai J2) semakin kecil. Apabila
nilai C sama dengan n maka nilai J2 akan
sama dengan 0. Untuk nilai c tertentu,
kluster yang baik adalah yang memberikan
J2 terkecil dari trial yang dilakukan
berulang. Apabila nilai c yang dicobakan
bermacam-macam dan akan dicari nilai c
Gambar 7. Diagram Alir Fuzzy Genetik Clustering (GGA-FCM)
n o
yes
S T A R T
T e n t u k a n : m ,
N , T , P c , P m
t = 0
T e n t u k a n N k r o m o s o m V
B a c a : x
c
Normalisasi x
Tentukan U s e c a r a
konvensional
T e n t u k a n N b u a h f i t n e s s ( V )
P i l i h d u a i n d u k C r o s s O v e r
C r o s s - O v e r
T e n t u k a n K r o m o s o m y a n g a k a n
d i k e n a i m u t a s i
T a m b a h k a n d u a o f f s p r i n g k e
d a l a m p o p u l a s i
Ulangi
d e n g a n p r o p o r s i P c
Ulangi
dengan proporsi Pm
P i l i h N t e r b a i k d a r i ( p o p u l a s i +
o f f s p r i n g h a s i l o p . g e n e t i k )
T a m b a h k a n o f f s p r i n g k e d a l a m
p o p u l a s i
t = t + 1
Mutasi
S T O P
t = T
Berkala MIPA, 17(2), Mei 2007
10
terbaik maka valilditas kluster FU,HU dan
SU dapat dijadikan pedoman. Nilai c yang
baik ditinjau dari derajat ke-fuzzy-an apabila
FU cukup besar dan HU serta SU cukup
kecil. Dari tabel 2 terlihat bahwa untuk
ukuran kluster c=3 dan c=5 merupakan
kluster yang baik. Pengujian data kasus 1
dengan algoritma genetika ditetapkan
beberapa parameter algoritma genetika,
yaitu :
Jumlah populasi (nP) = 30;Jumlah generasi
(nG) = 500;Probabilitas CrossOver (Pc) =
0.2; Probabilitas Mutas (Pm) = 0.1; Nilai m
=2;Trial = 100 (ulangan runs)
Tabel 2. Hasil Kluster dengan FCM untuk m=2
C Iter J2 FU HU SU
2 26 1.2359 0.8325 0.2899 0.1006
3 37 0.4759 0.8196 0.3624 0.0877
4 63 0.2729 0.7524 0.4967 0.1475
5 58 0.2248 0.7031 0.6142 0.0829
6 39 0.1270 0.6698 0.6474 0.1874
Pengujian algoritma untuk cacah cluster c=3
dan c=4 hasil pelacakan terbaik GGA-FCM
dapat disajikan seperti dalam Gambar 10.
Garis-garis dalam grafik ada peta pelacakan
dari titik random awal inisialisasi menuju
titik akhir (konvergensi) kluster optimal.
Perbandingan secara visual untuk metode
FCM dan GGA-FCM menampakkan hasil
yang hampir sama. Untuk lebih detail
perbandingan dapat diteliti melalui nilai
optimal Jm yang diperoleh dan parameterparameter
clustering melalui validitas
cluster. Untuk itu pengujian untuk nilai-nilai
c yang lebih lengkap, yaitu c=2,3,4,5 dan 6
hasilnya adalah seperti tabel 3 berikut.
Gambar 9. Plot Data 14 objek Pengujian
dengan metode iteratif FCM
untuk cacah kluster c=2,c=3,
c=4, c=5 dan c=6.
Gambar 10. Peta pelacakan cluster untuk
c=3 dan c=4
Gambar 8. Citra Peta (Chi et.al.,
1996)
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
11
Tabel 3 Hasil Kluster dengan GGA-FCM untuk m=2
C Rerata J2 FU HU SU
2 0.9543 0.8712 0.2091 0.0996
3 0.4143 0.8262 0.3122 0.0711
4 0.2511 0.7629 0.4227 0.1286
5 0.1126 0.7138 0.5932 0.0729
6 0.0932 0.6988 0.6025 0.1123
Jika hasil kluster GGA-FCM dalam tabel 4
dibandingkan dengan hasil FCM dalam
Tabel 3 terlihat bahwa nilai-nilai J2 sebagai
fungsi tujuan yang diminimalkan pada
GGA-FCM memiliki nilai yang lebih kecil,
untuk semua C. Ini menunjukkan bahwa
secara rerata pusat-pusat kluster yang
ditemukan oleh GGA-FCM lebih baik dari
FCM.
Beban Komputasi Untuk Data Kasus 1
Beban komputasi untuk data kasus 1
ditentukan berdasarkan cacah operasi
floating point (flops) dari algoritma tersebut.
Secara eksak beban komputasi tidak dapat
ditentukan disebabkan faktor random yang
muncul dalam pembangkitan data awal,
sehingga untuk jumlah kluster yang sama
dapat terjadi cacah flops yang berbeda cukup
signifikan. Pendekatan yang dilakukan untuk
menentukan beban komputasi dilakukan
dengan mengulang runing program untuk
cacah kluster yang sama dan menentukan
rerata beban komputasi dan standard deviasi
beban komputasi .
Gambar 12. Hubungan Cacah cluster
dengan flops untuk FCM dan GGAFCM
Gambar 11. Posisi pusat kluster (*) terhadap data (o) untuk data kasus 1, dengan C=3,4 dan 5
pada metode FCM dan GGA-FCM
Berkala MIPA, 17(2), Mei 2007
12
Tabel 4. Rerata dan standard deviasi beban komputasi clustering FCM
Cacah cluster
(C)
Run FCM GGA-FCM
Rerata
flops
StdDev
flops
Rerata
flops
StdDev
flops
2 10 30.075 2.802 60.125 5.324
3 10 88.972 5.430 124.567 8.247
4 20 168.260 58.040 276.545 76.235
5 20 356.230 240.870 632.421 405.754
6 20 788.000 323.860 1.432.402 511.176
Dari Tabel 4. dan Gambar 12. terlihat bahwa
cacah flops meningkat signifikan dan
cenderung eksponensial dengan
bertambahnya cacah cluster. Dari grafik juga
terlihat bahwa GGA-FCM memiliki cacah
flops yang lebih besar dan bahkan hampir
dua kali cacah flops untuk algoritma FCM.
Classification Rate untuk Data Kasus 1
Untuk membandingkan classification
rate data kasus 1 dengan pendekatan dua
algoritma FCM dan GGA-FCM dilakukan
proses klasifikasi dari kluster yang diperoleh
untuk beberapa pilihan c. Hasilnya dapat
disajikan dalam Tabel 5.
Tabel 5. Classification rate clustering FCM
dan GGA-FCM
Cacah
cluster (C)
FCM GGAFCM
2 95.2 % 95.4 %
3 96.1 % 96.7 %
4 98.3 % 99.4 %
5 99.2 % 99.5 %
6 98.6 % 98.4 %
Dari tabel 5. terlihat bahwa kedua metode
tidak jauh berbeda dalam menghasilkan
kluster untuk proses klasifikasi objek yang
ditunjukkan oleh nilai classifcation rate.
Nilai terbaik clasifikasi diperoleh untuk
cacah kluster c=5 untuk algoritma GGAFCM.
Pengujian dengan Kasus 2
Aplikasi klustering dalam pengolahan
citra dapat ditunjukkan dalam upaya
mengubah citra aras keabuan (grayscale
image) menjadi citra hitam-putih (black
white image). Dalam citra asli ada derajat
keabuan yang diwakili oleh nilai keabuan
yang menyusun setiap pixel citra. Untuk
sebuah peta setiap pixel penyusun peta dapat
dikelompokkan sebagai pixel background
(warna putih) atau foreground (warna hitam
sebagai bentuk peta yang dapat berupa jalan,
atau keterangan peta). Data citra berikut
diambilkan dari Chi.et.all (1996) yang
merupakan citra ukuran 134 x 153 x 3 pixel
dengan setiap pixelnya 8bit skala keabuan.
Hasil cluster untuk beberapa nilai c=2, c=4
dan c=8 dan digambarkan hasilnya seperti
dalam Gambar 13.
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
13
Dari hasil cluster untuk berbagai
ukuran cluster terlihat bahwa dari sisi
perbaikan citra, maka hasil yang didapatkan
masih kurang memuaskan. Salah satu
manfaat yang dapat diperoleh dari hasil
clustering adalah variasi skala keabuan yang
jauh lebih sederhana dengan pengklusteran
(atau lebih dikenal dengan istilah segmentasi
citra) yang dapat dimanfaatkan misalnya
untuk kompresi citra. Untuk Citra peta
tersebut penurunan ukuran file dapat
didekati dengan hasil cluster.
Untuk pengolahan citra yang bertujuan
penajaman citra, metode clustering dengan
FCM dan GGA-FCM belumlah dapat
memberikan hasil yang baik. Pendekatan
rule-base fuzzy clustering dalam hal ini
dapat merupakan alternatif yang lebih baik
dalam penajaman citra. Gambar 14 adalah
contoh hasil penajaman citra dengan rule -
base fuzzyclustering dari Chi et.all. (1996).
Tabel 6. Classification rate clustering
FCM dan GGA-FCM
Tipe Cacah
pixel
Cacah Bit
per pixel
Ukuran
file
Citra
asli
134 x
153 x 3
8 bit 100 %
Cluster
c=2
134 x
153 x 3
1 bit 12.5 %
Cluster
c=4
134 x
153 x 3
2 bit 25.0 %
Cluster
c=8
134 x
153 x 3
3 bit 37.5 %
Gambar 14. Citra Peta dan Hasil Penajaman Citra dengan
Rule-Base dengan 34-Fuzzy Rule
Gambar 13. Clustering GGA-FCM untuk
c=2, c=4 dan c=8
Cluster c=4 Cluster c=8
Cluster asli Cluster c=2
Berkala MIPA, 17(2), Mei 2007
14
3. KESIMPULAN
Beberapa kesimpulan yang dapat diperoleh
dari penelitian ini antara lain dapat diuraikan
sebagai berikut :
1. Metode klustering dengan algoritma
genetika (GGA-FCM) dapat
memperbaiki kinerja FCM dengan
metode iterasi konvensional terutama
ditinjau dari fungsi tujuan Jm dan
koefisien Classification Rate.
2. Jika ditinjau dari beban komputasi dan
waktu komputasi metode GGA-FCM
masih relatif lebih kompleks dan
memerlukan cacah flops yang jauh lebih
besar dari metode FCM konvensional.
Namun dengan perkembangan prosesor
yang semakin baik kemungkinan
kompleksitas komputasi dan waktu
komputasi dapat diatasi.
3. Algoritma genetika (GGA-FCM),
meskipun membutuhkan waktu
komputasi lebih banyak tetapi dapat
memberikan jawaban yang lebih baik
dari metode metode iteratif
konvensional (FCM).
4. Untuk aplikasi pengolahan citra yang
berupa penajaman citra algoritma
GGA-FCM belum dapat digunakan,
tetapi untuk segmentasi citra FCM
maupun GGA-FCM dapat diterapkan
dan dapat menghasilkan citra dengan
komposisi bit yang lebih sederhana dan
ukuran file yang lebih kecil.
DAFTAR PUSTAKA
Belanche L. and Nebot A., 2002,
Intelligent Data Analysis and Data
Mining, Wright State University.
Chi, Z., Yan, H. and Pham, T., 1996,
Fuzzy Algorithms : With
Application to Image Processing
and Pattern Recognition, Advanve
in Fuzzy System-Application and
Theory, Vol.10., Word Scientific,
Singapore.
Gen, M. and Cheng, R., 2000, Genetic
Algorithms and Engineering
Optimization, John Wiley & Sons,
New York.
Hamzah, A, 2001, Pengenalan Pola
dengan Fuzzy Clustering,
ACADEMIA ISTA, Vol.4.No.1.,
Lembaga Penelitian, Institut Sains
dan Teknologi AKPRIND,
Yogayakarta.
Sato, M. and Sato Y., 1995, Fuzzy
Clustering with Multiple
Objectives Functions, Kluwer
Academic Publisher, Boston.
Zimmerman, H.J., 1991, Fuzzy Set
Theory and Its Applications, 2nd
Ed., Norwel, Massachusetts.
1
PENGGUNAAN ALGORITMA GENETIKA DALAM
PENINGKATAN KINERJA FUZZY CLUSTERING UNTUK
PENGENALAN POLA
(Application of Genetic Algorithm to Enhance the Performance of Clustering
Fuzzy in Pattern Recognition)
Naniek Widyastuti1, Amir Hamzah1
1Fakultas Teknologi Industri, Institut Sains & Teknologi AKPRIND Yogyakarta
ABSTRAK
Algoritma genetika (AG) adalah metode untuk menyelesaikan persoalan optimasi berbasis
teori evolusi dalam biologi. Algoritma ini bekerja pada populasi calon penyelesaian yang
disebut kromosom yang awalnya dibangkitkan secara random dari ruang penyelesaian
fungsi tujuan. Dengan menggunakan mekanisme opearator genetik yaitu persilangan dan
mutasi populasi dievolusikan melalui fungsi fitness yang diarahkan pada kondisi
konvergensi. Algoritma ini dapat diterapkan dalam banyak area fungsi-fungsi optimasi,
salah satu penerapannya adalah fungsi objektif berbasis fuzzy clustering.
Fuzzy clustering bertujuan mengelompokkan n objek yang disajikan dengan vektor
kedalam C-cluster berdasarkan kesamaannya dengan pusat cluster yang diukur melalui
fungsi jarak. Fungsi tujuan Jm didefinisikan sebagai fungsi V (matriks sifat prototipe)
dan U ( fungsi keanggotaan Fuzzy dari objek i: 1, 2, . . . .,n menjadi anggota cluster j: 1, 2,
. . . . , c) yang diminimumkan melalui iterasi. Karena sensitivitas inisiasi random terjebak
dalam minimum lokal, pendekatan genetik biasanya dapat diterapkan untuk
menghilangkan masalah diatas.
Penelitian ini ditujukan untuk mempelajari unjuk kerja AG pada masalah fuzzy
clustering, khususnya fuzzy C Mean (FCM). Guided GA (GGA) sebagai alternatif FCM
diperkenalkan melalui kode MATLAB, kedua algoritma ini dibandingkan melalui tiga
kasus numerik. Unjuk kerja FCM dan GGA-FCM diuji melalui beberapa parameter
seperti kesahihan cluster, kompleksitas, laju klasifikasi komputasi. Hasilnya
menunjukkan bahwa GGA-FCM mempunyai unjuk kerja yang lebih baik dibandingkan
FCM dalam bentuk Jm, kesahihan cluster dan laju klasifikasi, meskipun dalam
kompleksitas komputasi lebih rumit dan memerlukan waktu lebih banyak.
Kata kunci : fuzzy cluctering, Algoritma Genetika, GGA-FCM, FCM.
ABSTRACT
Genetic Algorithm(GA) is a method for solving optimization problem that based on
evolutionary theory in biology. This algorithm work with a population of candidate
solutions named as chromosom that initially generated randomly from the area of the
solution space of objective function. By using a mechanism of genetic operator i.e. crossover
and mutation the population is evoluted controlled by fitness function that directed to
konvergence condition. This algorithms can be applied in many area of function
optimizations, one of those is applications on objective function based fuzzy clustering.
Fuzzy clustering aims to cluster n objects represented by feature vectors into c cluster
based on similarity to the cluster center measured by a distance function. Objective
function Jm was defined as function of V (matrix of feature prototype) and U(fuzzy
Berkala MIPA, 17(2), Mei 2007
2
membership function of object i:1,2,..,n become member of cluster j:1,2,…,c) to be
minimized through iteration. Because of sensitivity to random initialization to be trapped
in local minima, genetic approach generally can be applied to reduce this problem.
This research was aimed to study the performance of GA approach to the problem of
fuzzy clustering, mainly fuzzy-c-mean (FCM). The Guided Genetic Algorithm as an
alternative to FCM, called GGA-FCM was introduced to be coded in MATLAB script.
The two algorithms was compared through the tests of those algorithms with three
numerical cases. The performance of both FCM and GGA-FCM was examined by some
parameters such as cluster validity, complexity of computation classification rate. The
results showed that GGA-FCM has better performance than FCM in terms of Jm, cluster
validity and classification rate, although in term of computational complexity is more
complex and time consuming.
Keywords: fuzzy clustering, genetic algorithm, GGA-FCM, FCM
Makalah diterima tanggal 3 April 2007
1. PENDAHULUAN
Pengenalan pola (pattern recognition)
merupakan konsep yang sangat luas
aplikasinya dalam banyak bidang antara lain
: biomedical (EEG,ECG,Röntgen, Nuclear,
Tomography,Tissue,Cells,Chromosomes,
meteorolgy (remote sensing), industrial
inspection (robotic vision) dan digital
microscopy. Beberapa aplikasi dalam bidang
komputer dan informatika diantaranya :
Speech recognition, speaker identification,
character recognition, signature verification,
image segmentation dan artifcial
intelligence.
Belanche and Nebot (2002)
menggambarkan pengenalan pola secara
garis besar sebagai serangkaian kegiatan
yang mencakup: kegiatan pengukuran dunia
nyata dengan alat ukur yang
menggambarkan fenomena yang akan
diukur diikuti serangkaian kegiatan:
preprosesor, ekstrak feature, klasifikasi atau
diskrips i pola (lihat Gambar 1). Kegiatan
yang fital dalam pengenalan pola adalah
kegiata klasifikasi dari ruang feature yang
diperoleh dari kegiatan seleksi dan ekstrak
feature.
Metode yang lebih baik dari metode
clustering secara tegas adalah aplikasi teori
fuzzy dalam proses kluster (fuzzy
clustering). Hamzah (2001) menunjukkan
bahwa proses kluster secara fuzzy (fuzzy
clustering) menunjukkan hasil yang lebih
baik dan lebih alami dibandingkan dengan
proses kluster dengan pendekatan tegas.
Sejak dikembangkan pertama kali oleh
Holland tahun 1975, algoritma genetika
(Genetic Algoritms=GA) terus mengalami
perkembangan dalam banyak aplikasi (Gen
and Cheng 2000). Pesatnya perkembangan
applikasi GA pada berbagai problem
optimasi dipacu oleh perkembangan
teknologi komputer dan mikro prosesor.
Salah satu minat dalam aplikasi
genetic -fuzzy system adalah genetic -fuzzy
clustering. Pada fuzzy clustering berbasis
fungsi tujuan persoalan mencari kluster
terbaik akan identik dengan persoalan
optimasi fungsi tujuan. Penggunaan
algoritma genetika untuk fuzzy clustering
dimungkinkan dapat meningkatkan unjuk
kerja fuzzy clustering. Penerapan GFS pada
Gambar 1. Skema Kegiatan dalam Pengenalan Pola(Belanche
and Nebot, 2002)
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
3
fuzzy clustering terutama Fuzzy-C-Means
Clustering (FCM) adalah untuk
mengoptimasi parameter-parameter dalam
FCM.
Pertanyaan yang muncul kemudian
dalam penerapan GA pada FCM adalah
sejauh mana peningkatan kinerja FCM
dengan pendekatan GA tersebut. Parameterparameter
FCM apa yang kemudian harus
dipertimbangkan dalam penerapan GA, latar
belakang inilah yang mendasari
dilakukannya penelitian ini.
Adapun tujuan penelitian ini adalah
mengkaji penerapan algoritma genetika
dalam fuzzy clustering, utamanya FCM,
serta mengkaji sejauh mana algoritma
genetika dapat meningkatkan unjuk kerja
fuzzy clustering.
Fuzzy-C-Means clustering
Pada pendekatan tegas (crisp), untuk
setiap objek ke-k (k=1...n) secara tegas
hanya dapat menjadi anggota cluster ke-i
(i=1..c), dengan keputusan menjadi anggota
kluster ke-i berdasarkan jarak minimal
objek ke-k dengan pusat-pusat kluster ke-i.
Algoritma pendekatan tegas dengan jumlah
kluster k Clustering dan pusat kluster
ditentukan dengan cara rata -rata ini sering
disebut sebagai K-Means.
Pada pendekatan fuzzy metode
klustering berdasarkan kenyataan bahwa
objek-objek tertentu mungkin secara tegas
tidak dapat dikelompokkan pada kluster
tertentu. Dengan pendekatan fuzzy setiap
objek ke-k (k=1,2,..,n) dianggap menjadi
anggota dari semua kluster ke-i (i=1,2,..,c)
dengan fungsi keanggotaan antara 0 sampai
1. Keputusan objek ke-i menjadi anggota
kluster ke-j berdasarkan fungsi keanggotaan
yang terbesar. Model clustering seperti ini
terkenal dengan sebutan Fuzzy-C-Means
Clustering (FCM).
Banyak macam fungsi objektif telah
dirumuskan, baik yang pendekatan tegas
(crisp) maupun pendekatan fuzzy (Sato and
Sato, 1995). Untuk menghasilkan formulasi
yang presisi dalam menentukan kriteria
klustering dapat ditempuh dengan metode
fungsi objektif (objective-function methods),
yaitu dengan mengukur kemampuan untuk
dilibatkan dalam kluster sebagai fungsi dari
c (yaitu cacah kluster) dengan suatu fungsi
objektif tertentu (Zimmerman, 1991). Fuzzy
clustering FCM dengan fungsi tujuan
menggunakan jarak euclidean
mengasumsikan bentuk fungsi tujuan
spherical. Untuk data tertentu kondisi
spherical mungkin tidak terpenuhi.
Pemilihan fungsi tujuan dan kriteria
jarak dengan demikian sangat tergantung
pada sebaran data objek. Untuk fungsi
tujuan spherical dimana FCM dengan jarak
eucledian didefinisikan, kriteria kluster yang
baik selanjutnya adalah kluster yang
meminimalkan fungsi tujuan Jm yang
dirumuskan sebagai fungsi dari U dan V
sebagai berikut :
Jm(U,V)= ( - x k )
1
2
1
å å
= =
n
k
ik i
m
ik
c
i
m D v (1)
untuk: i=1,2,…,c dan k=1,2,…,n.
Matrik U Î Mcn adalah matrik partisi
dengan ordo cxn dengan elemen matrik mik.
Untuk klustering secara tegas mik Î {0,1},
yaitu bernilai 1 jika objek k anggota kluster i
dan 0 jika tidak. Untuk klustering secara
fuzzy mik Î [0,1] yang bernilai real. Nilai
parameter m merupakan derajat ke-fuzzi-an
dari proses klustering dengan nilai mÎ[1,¥
). V=[v1, v2,.., vc] adalah matrik parameter
prototipe (pusat kluster) viÎÂp . Dik
2(vi , xk )
adalah jarak dari vektor xk ke pusat kluster
vi.
Struktur kluster terbaik yang dicari
adalah penyelesaian minimum (minimizer)
untuk persamaan (1) yang dapat diselesaikan
dengan proses iterasi untuk penyelesaian
optimasi fungsi. Pada penyesuaian iterasi
mula-mula dibangkitkan vektor pusat kluster
secara acak dan kemudian iterasi dilakukan
untuk mengupdate matrik U. Iterasi
dilakukan sampai matrik U relatif tidak
berubah. Berikut adalah nilai U dan V
berturut-turut yang digunakan dalam iterasi:
Berkala MIPA, 17(2), Mei 2007
4
untuk i 1,2,..., c; k 1,2,..., n ( 2 )
1
1
1
2
1 /( 1)
2
= =
ú ú
û
ù
ê ê
ë
é
-
ú ú
û
ù
ê ê
ë
é
-
=
å=
-
c
j
m
k j
m
k i
ik
x v
x v
m
Dengan nilai U yang telah diupdate,
maka vektor pusat kluster diperbaharui
dengan :
v 1 untuk i 1,2,..., c
1
1
i = å =
å =
=
n
k
ik
m
n ik
k
m
ik
m x
m
(3)
Proses penyelesaian optimasi secara
klasik sering menghantar pada penyelesaian
yang merupakan optimum lokal dari
himpunan penyelesaian yang mungkin.
Pendekatan algoritma genetika dapat
menjadi alternatif yang dapat diterapkan
pada proses penyelesaian optimasi yang
menghindari optimum lokal.
Algoritma Genetika
Algoritma genetika dikembangkan
pertama kali oleh Holland tahun 1975 (Gen
and Cheng,2000). Sejak dikembangkan
sampai saat ini GA ini terus menjadi objek
riset dalam berbagai aplikasi. Alasan
mengapa GA banyak menjanjikan, antara
lain banyak problem dibidang sains dan
teknik tidak dapat dipecahkan dengan
algoritma deterministik biasa meskipun
dengan waktu yang meningkat secara
polynomial.
Secara umum algoritma ini memiliki
prosedur yang dapat dirumuskan sebagai
berikut Procedure Genetic Algoritms
Begin
tß 0
initialize P(t)
evaluate P(t)
while (not termination condition )
do
begin
recombine P(t) to yield C(t)
evaluate C(t)
select P(t+1) from P(t) and C(t)
t ß t+1
end
end
Dengan t = generasi, P(t)= Populasi pada
generasi t , dan C(t)=Populasi tambahan atau
individu baru (offspring) dari hasil proses
operasi genetik Cross Over dan Mutasi.
Encoding.
Dalam algoritma genetika pengkodean
(encoding) solusi problem kedalam suatu
kromosom merupakan isu penting. Populasi
awal yang berisi N kromosom dibangkitkan
secara random yang menjangkau
keseluruhan ruang solusi. Proses evolusi
dilakukan dengan melakukan operasi
genetik (cross-over dan mutasi) dan
melakukan seleksi kromosom untuk generasi
berikutnya sampai sejumlah generasi yang
dikehendaki dengan panduan fungsi fitness.
Algoritma genetika pada dua ruang,
yaitu ruang solusi (disebut phenotip) dan
ruang coding (disebut genotip). Operasi
genetika (cross over dan mutasi) dilakukan
pada ruang genotip sementara operasi
seleksi dilakukan pada ruang phenotip.
Dalam binary encoding variabel keputusan
diwakili oleh deretan bit 0,1 yang
panjangnya disesuaikan dengan ruang
pencarian. Tiap bit 0,1 dapat dianggap
sebagai sebuah gen. Untuk optimasi 2
variabel misalnya, maka solusi adalah x1
dan x2.
Integer dan literal permutation
encoding adalah kode terbaik untuk problem
combinatorial optimization karena inti dari
problem ini adalah mencari kombinasi atau
permutasi terbaik dari item solusi terhadap
kendala yang ada. Untuk problem yang lebih
komplek encoding menggunakan data
struktur yang lebih sesuai.
Fungsi fitness.
Fungsi fitness adalah fungsi yang
digunakan untuk menjustifikasi apakah
suatu kromosom layak bertahan. Pada setiap
generasi dipilih kromosom yang mendekati
solusi dengan mengevaluasi fungsi
kecocokan dari kromosom tersebut. Fungsi
ini didefinisikan sedemikian sehingga
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
5
semakin besar nilai fitness semakin besar
probabilitas untuk terseleksi pada generasi
berikutnya. Untuk maksimasi maka fungsi
tujuan dapat dijadikan sebagai fungsi fitness,
sehingga kromosom yang mewakili nilai
fungsi besar akan memiliki probabilitas
terseleksi yang besar juga. Untuk minimasi
dapat dirumuskan sedemikian sehingga
fungsi tujuan yang semakin kecil maka
memiliki fungsi fitness yang besar.
Pada penyelesaian yang berada diluar
daerah visible dapat digunakan suati
modifikasi fungsi fitness dengan
menambahkan suatu fungsi yang sering
disebut sebagai fungsi penalti, sehingga
fungsi fitness menjadi :
fitness(x)=f(x)+p(x) (4)
Seleksi.
Setiap anggota populasi diwakili
deretan string (disebut kromosom) dengan
panjang tertentu. Elemen string tersebut
dapat berupa digit 0,1 (untuk binary
encoding), bilangan real (untuk real
encoding), atau elemen lain. Untuk ukuran
populasi N yang biasanya dipertahankan
tetap prosedur seleksi diperlukan untuk
memilih anggota populasi yang mana yang
akan tetap eksis pada generasi berikutnya.
Fungsi fitness digunakan untuk
menjustifikasi apakah kromosom layak
dipertahankan atau tidak dalam generasi
berikutnya.
Sebelum dilakukan seleksi jumlah
anggota populasi ditambah dengan hasil
offspring dari proses operasi genetik yang
dapat berupa cross over dan mutasi. Hasil
operasi genetik dan populasi semula
selanjutnya diseleksi dengan metode tertentu
untuk diambil n anggota populasi yang
terbaik. Untuk kasus minimasi maka yang
terpilih adalah n anggota populasi dengan
nilai fitness yang terkecil.
Crossover.
Proses operasi crossover dirancang
untuk mencari kemungkinan yang lebih baik
dari anggota populasi yang telah ada. Dari
pasangan induk yang terpilih berdasarkan
seleksi fungsi fitness diambil sejumlah
pasangan dengan probabilitas Pc untuk
dikenakan operasi crossover.
Mutasi.
Mutasi dalam konteks binary encoding
adalah perubahan pada bit tunggal (bit 0 jadi
1 dan sebaliknya) anggota populasi yang
terpilih. Banyaknya bit yang mengalami
mutasi pada setiap generasi diatur oleh
probabilitas mutasi (Pm) yang nilainya
merupakan cacah bit mutasi dibagi cacah bit
total dalam populasi.
Algoritma Genetika Untuk Fuzzy
Clustering.
Algoritma genetika (GA) sebagai
teknik optimasi dapat diterapkan pada
clustering yang berbasis optimasi fungsi
tujuan. Pada pendekatan GA untuk fuzzyclustering
fungsi fitness diambil dari fungsi
objektif yang diminimumkan, yaitu
Jm(U,V).
Validitas Clustering dan Classification
Rate.
Hasil akhir FCM atau GGA-FCM
adalah V,U dan Rm tertentu untuk suatu c
yang diinputkan. Pada beberapa kasus c
yang tepat mungkin tidak diketahui. Untuk
itu beberapa pendekatan telah diusulkan
untuk menentukan berapa sebaiknya c
sehingga hasil klustering dapat dianggap
terbaik. Ukuran ini dikenal sebagai validitas
klustering. Chi et.al. (1996) merangkum
setidaknya ada empat alat ukur, yaitu :
1. Koefisien Partisi (partition
coefficient)
Koefisien Partisi didefinisikan
sebagai fungsi U dan c:
åå
= =
=
c
i
n
k
ik u
n
F U c
1 1
( )2
1
( , ) (5)
Koefisien partisi ini mengukur kedekatan
dari semua sampel masukan terhadap
prototipe yang terpilih.
2. Entropy partisi (Parttion Entropy)
åå
= =
= -
c
i
n
k
ik ik u u
n
H U c
1 1
log( )
1
( , ) (6)
Entropy partisi (0<H(u,c)<log c)
diterjemahkan sebagai derajat
ketidakpastian (degree of fuzzyness) dari
objek. H(U,c) besar yang menunjukkan
hasill klustering yang jelek.
Berkala MIPA, 17(2), Mei 2007
6
3. Fungsi validitas Kekompakan dan
separasi (compactness and
separation validity function)
| |
1
( , ) 2
min | |
i, k
1 1
2 2
v k v i
c
i
n
k
ik k i u x v
S U c n
-
å å
= =
-
=
(7)
S(U,c) adalah rasio antara rata-rata jarak
sampel dengan prototipe yang terpilih
dengan minimum jarak antar prototipe.
Classification rate.
Keberhasilan clustering terkadang
diukur juga melalui kemampuan clustering
tersebut dalam klasifikasi objek. Hal ini
dapat ditentukan apabila objek-objek yang
diklasifikasi telah diketahui berasal dari
suatu klas tertentu. Banyaknya objek yang
dapat diklasifikasikan dengan tepat sesuai
dengan klas dari mana objek tersebut berasal
disebut sebagai classification rate. Index ini
dapat dituliskan sebagai :
CR= x100%
N
n
(8)
Dimana : n=banyaknya objek yang dapat
diklasifikasi dengan benar N=banyaknya
objek yang diklasifikasi
Algoritma Fuzzy clustering konvensional
(FCM).
Berikut diuraikan algoritma fuzzy
clustering konvensional, yaitu penyelesaian
fuzzy clustering dengan cara iteratif dengan
melakukan update pada matrik keanggotan
U dan matrik prototipe kluster V. Dalam
algoritma diperlukan : Sampel objek
sebanyak n, tiap objek p parameter,
dituliskan : X={x1,x2,…,xn} xi
ÎRp ,
i=1,2,…,n. Ditentukan dalam proses
penyelesaian melalui iterasi :
U=[mik] matrik ukuran cxn ; i=1,2,…,c ;
k=1,2,…,n; V={v1,v2,…,vc} i=1,2,…,c
Berikut adalah algoritma yang diajukan :
1. Initialization step :
Tentukan: n=cacah objek yang akan
dikluster ; p=cacah parameter dalam tiap
objek; c=cacah kluster; t=0 (iterasi ke);
m=derajat fuzziness = dipilih 2;
e=nilai yang cukup kecil mendekati
0
Tentukan secara acak : U(0) dan V(0)
2. Iteration step :
a). Dengan menggunakan U(t) ,
hitung pusat kluster V(t) menurut rumus :
untuk i 1,2,..., c, (9)
v 1
1
1
i
=
= å
å =
=
n
k
ik
m
n ik
k
m
ik
m x
m
b). Dengan menggunakan V(t) ,
update membership U(t) ,dengan rumus
:
untuk i 1,2,..., c; k 1,2,..., n (10)
1
1
1
2
1 /( 1)
2
= =
ú ú
û
ù
ê ê
ë
é
-
ú ú
û
ù
ê ê
ë
é
-
=
å= -
c
j
m
k j
m
k i
ik
x v
x v
m
c). Jika max( |mik
(t) - mik
(t-1) | ) < e
berhenti, Jika tidak ulangi langkah 2.a).
Diagram alir untuk Fuzzy Clustering
seperti tersaji dalam Gambar 3.
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
7
n o
y e s
S T A R T
T e n t u k a n : m ,
t = 0
T e n t u k a n s c r a c a k :
U ( t ) d a n V ( t )
B a c a : x
c
F o r i = 1 t o c
N o r m a l i s a s i x
F o r i = 1 t o c
F o r k = 1 t o n
m a x ( ¦ μ i k ( t ) - μ i k ( t - 1 ) ¦ ) < e
S T O P
t = t + 1 å
=
-
ú ú
û
ù
ê ê
ë
é
-
ú úû
ù
ê êë
é
-
=
c
j
m
k j
m
k i
ik
x v
x v
1
2
1 / ( 1 )
2
1
1
m
å
å =
=
=
n
k
i k
m
n ik
k
m
ik
x
1
1
i
v 1 m
m
Algoritma Fuzzy Clustering dengan
Pendekatan Algoritma genetika
(GeneticGuidedAlgorithm for Fuzzy c-
Means = GGA-FCM)
Pada pendekatan algoritma genetika
untuk penyelesaian fuzzy clustering
ditempuh pilihan untuk menggunakan
pendekatan Prototype-based algorithms,
yaitu meng-evolusikan matrik pusat cluster
V. Beberapa hal yang ditentukan adalah :
Encoding dan Struktur kromosom :
Encoding yang digunakan adalah real
encoding . Struktur kromosom untuk V
dalam populasi yang dievolusikan adalah
vektor real beranggotakan cxp elemen
(c=cacah kluster dan p cacah elemen dalam
objek), seperti dalam Gambar 4.
1 2 … p 1 2 … p 1 2 … p
… … …
v1 v2
Fungsi Fitness :
Fungsi fitness yang digunakan adalah
objective function Jm, yaitu:
Jm(U,V)= ( - x k )
1
2
1
å å
= =
n
k
ik i
m
ik
c
i
m D v (11)
Dimana mik dikalkulasi dengan :
untuk i 1,2,..., c; k 1,2,..., n
1
1
1
2
1 /( 1 )
2
= =
ú ú
û
ù
ê ê
ë
é
-
ú ú
û
ù
ê ê
ë
é
-
=
å=
-
c
j
m
k j
m
k i
ik
x v
x v
m
(12)
dan jarak Dik
2 menggunakan jarak eucledian.
Gambar 3. Diagram Alir Fuzzy Clustering (FCM)
Gambar 4. Struktur Kromosom untuk Encoding V
Berkala MIPA, 17(2), Mei 2007
8
Operasi Genetik .
Cross-Over:
Operasi cross over dipilih metode onepoint
cross-over, yaitu untuk tiap kromosom
induk ditetapkan 1 titik secara random antara
1 sampai cxp, misalkan disebut titik r.
Selanjutnya offspring didapatkan dengan
mensilangkan (cross-over) nilai mulai posisi
r sampai akhir kromosom. Untuk lebih
jelasnya urutan cross over disajikan dalam
Gambar 5.
Langkah 1. Pilih titik r : angka random antara 1 sampai cxp
Induk-1 … … …
Induk-2 … … …
Langkah 2. Tukarkan nilai vektor antara titik r sampai akhir
r
Offspring-
1
… … …
Offspring-
2
… … …
Mutasi :
Metode mutasi yang dipilih adalah
Nonuniform mutation dengan algoritma
untuk mutasi dapat dituliskan sebagai
berikut :
1. Pilih satu induk yang akan dimutasi
berdasarkan fungsi fittness dari
kromosom anggota populasi
2. Tentukan digit (posisi) gen yang
akan dimutasi, dengan menentukan k=
<1= bilangan random <= n
3. Pilih gen yang dimutasi, yaitu : xk
4. Tentukan batas bawah (xk
L)dan
batas atas (xk
U)
5. Nilai offspring diperoleh (xk’)
dipilih secara acak dari salah satu :
xk’= xk’+D(t, xk
U- xk) atau
xk’= xk’+D(t, xk - xk
L)
Dengan kisaran (range) nilai real
untuk xk adalah [xk
L
, xk
U].
Nilai D(t, xk - xk
L) atau D(t, xk
U- xk)
dari kriteria itu diberikan oleh :
D(t ,y)=yr(1-t/T)b, dengan r = bilangan
random kisaran [0,1] dan b adalah
bilangan bulat.
Mutasi V
k= round(rand *(n-1))+1
Pilih xk dari V
Tentukan xL dan xU
Pilih secara acak
xk’= xk’+ rand*(xkU- xk) (1-t/T)b atau
xk’= xk’+ rand*(xk - xkL) (1-t/T)b
RETURN
Gambar 6. Diagram Alir Mutasi
Gambar 5. One-point cross over untuk kromosom
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
9
2. PEMBAHASAN
Kasus yang dijadikan bahan pengujian
algoritma-algoritma yang diteliti adalah
Kasus 1. Data dua dimensi dengan jumlah
sampel 14 objek
Tabel 1. Data vektor atribut untuk 14
objek
Objek
Ke-k
X(k)
X1
(k) X2
(k)
1 1 1
2 8 4
3 2 6
4 2 1
5 8 0
6 2 2
7 8 2
8 4 5
9 7 3
10 1 2
11 9 3
12 1 5
13 9 1
14 5 6
Kasus 2. Data matrik pixel dari citra peta
berukuran 134 x 153 x 3 dengan derajat
keabuan 0 sampai 255 sebagai Gambar 8
(Chi et.al., 1996). Dari kasus-kasus yang
dicobakan dibandingkan hasil Fuzzy-
Clustering konvensional dan Genetic
Algorithm Fuzzy Clustring ditinjau dari
beberapa aspek antara lain : waktu
komputasi, Classification rate, Cluster
Validity.
Pengujian kasus 1
Secara visual data kasus 1 (14 objek dua
dimensi) dapat digambarkan seperti Gambar
9.
Dari Tabel 2 terlihat bahwa semakin
besar nilai C maka nilai Jm (untuk m=2
ditulis sebagai J2) semakin kecil. Apabila
nilai C sama dengan n maka nilai J2 akan
sama dengan 0. Untuk nilai c tertentu,
kluster yang baik adalah yang memberikan
J2 terkecil dari trial yang dilakukan
berulang. Apabila nilai c yang dicobakan
bermacam-macam dan akan dicari nilai c
Gambar 7. Diagram Alir Fuzzy Genetik Clustering (GGA-FCM)
n o
yes
S T A R T
T e n t u k a n : m ,
N , T , P c , P m
t = 0
T e n t u k a n N k r o m o s o m V
B a c a : x
c
Normalisasi x
Tentukan U s e c a r a
konvensional
T e n t u k a n N b u a h f i t n e s s ( V )
P i l i h d u a i n d u k C r o s s O v e r
C r o s s - O v e r
T e n t u k a n K r o m o s o m y a n g a k a n
d i k e n a i m u t a s i
T a m b a h k a n d u a o f f s p r i n g k e
d a l a m p o p u l a s i
Ulangi
d e n g a n p r o p o r s i P c
Ulangi
dengan proporsi Pm
P i l i h N t e r b a i k d a r i ( p o p u l a s i +
o f f s p r i n g h a s i l o p . g e n e t i k )
T a m b a h k a n o f f s p r i n g k e d a l a m
p o p u l a s i
t = t + 1
Mutasi
S T O P
t = T
Berkala MIPA, 17(2), Mei 2007
10
terbaik maka valilditas kluster FU,HU dan
SU dapat dijadikan pedoman. Nilai c yang
baik ditinjau dari derajat ke-fuzzy-an apabila
FU cukup besar dan HU serta SU cukup
kecil. Dari tabel 2 terlihat bahwa untuk
ukuran kluster c=3 dan c=5 merupakan
kluster yang baik. Pengujian data kasus 1
dengan algoritma genetika ditetapkan
beberapa parameter algoritma genetika,
yaitu :
Jumlah populasi (nP) = 30;Jumlah generasi
(nG) = 500;Probabilitas CrossOver (Pc) =
0.2; Probabilitas Mutas (Pm) = 0.1; Nilai m
=2;Trial = 100 (ulangan runs)
Tabel 2. Hasil Kluster dengan FCM untuk m=2
C Iter J2 FU HU SU
2 26 1.2359 0.8325 0.2899 0.1006
3 37 0.4759 0.8196 0.3624 0.0877
4 63 0.2729 0.7524 0.4967 0.1475
5 58 0.2248 0.7031 0.6142 0.0829
6 39 0.1270 0.6698 0.6474 0.1874
Pengujian algoritma untuk cacah cluster c=3
dan c=4 hasil pelacakan terbaik GGA-FCM
dapat disajikan seperti dalam Gambar 10.
Garis-garis dalam grafik ada peta pelacakan
dari titik random awal inisialisasi menuju
titik akhir (konvergensi) kluster optimal.
Perbandingan secara visual untuk metode
FCM dan GGA-FCM menampakkan hasil
yang hampir sama. Untuk lebih detail
perbandingan dapat diteliti melalui nilai
optimal Jm yang diperoleh dan parameterparameter
clustering melalui validitas
cluster. Untuk itu pengujian untuk nilai-nilai
c yang lebih lengkap, yaitu c=2,3,4,5 dan 6
hasilnya adalah seperti tabel 3 berikut.
Gambar 9. Plot Data 14 objek Pengujian
dengan metode iteratif FCM
untuk cacah kluster c=2,c=3,
c=4, c=5 dan c=6.
Gambar 10. Peta pelacakan cluster untuk
c=3 dan c=4
Gambar 8. Citra Peta (Chi et.al.,
1996)
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
11
Tabel 3 Hasil Kluster dengan GGA-FCM untuk m=2
C Rerata J2 FU HU SU
2 0.9543 0.8712 0.2091 0.0996
3 0.4143 0.8262 0.3122 0.0711
4 0.2511 0.7629 0.4227 0.1286
5 0.1126 0.7138 0.5932 0.0729
6 0.0932 0.6988 0.6025 0.1123
Jika hasil kluster GGA-FCM dalam tabel 4
dibandingkan dengan hasil FCM dalam
Tabel 3 terlihat bahwa nilai-nilai J2 sebagai
fungsi tujuan yang diminimalkan pada
GGA-FCM memiliki nilai yang lebih kecil,
untuk semua C. Ini menunjukkan bahwa
secara rerata pusat-pusat kluster yang
ditemukan oleh GGA-FCM lebih baik dari
FCM.
Beban Komputasi Untuk Data Kasus 1
Beban komputasi untuk data kasus 1
ditentukan berdasarkan cacah operasi
floating point (flops) dari algoritma tersebut.
Secara eksak beban komputasi tidak dapat
ditentukan disebabkan faktor random yang
muncul dalam pembangkitan data awal,
sehingga untuk jumlah kluster yang sama
dapat terjadi cacah flops yang berbeda cukup
signifikan. Pendekatan yang dilakukan untuk
menentukan beban komputasi dilakukan
dengan mengulang runing program untuk
cacah kluster yang sama dan menentukan
rerata beban komputasi dan standard deviasi
beban komputasi .
Gambar 12. Hubungan Cacah cluster
dengan flops untuk FCM dan GGAFCM
Gambar 11. Posisi pusat kluster (*) terhadap data (o) untuk data kasus 1, dengan C=3,4 dan 5
pada metode FCM dan GGA-FCM
Berkala MIPA, 17(2), Mei 2007
12
Tabel 4. Rerata dan standard deviasi beban komputasi clustering FCM
Cacah cluster
(C)
Run FCM GGA-FCM
Rerata
flops
StdDev
flops
Rerata
flops
StdDev
flops
2 10 30.075 2.802 60.125 5.324
3 10 88.972 5.430 124.567 8.247
4 20 168.260 58.040 276.545 76.235
5 20 356.230 240.870 632.421 405.754
6 20 788.000 323.860 1.432.402 511.176
Dari Tabel 4. dan Gambar 12. terlihat bahwa
cacah flops meningkat signifikan dan
cenderung eksponensial dengan
bertambahnya cacah cluster. Dari grafik juga
terlihat bahwa GGA-FCM memiliki cacah
flops yang lebih besar dan bahkan hampir
dua kali cacah flops untuk algoritma FCM.
Classification Rate untuk Data Kasus 1
Untuk membandingkan classification
rate data kasus 1 dengan pendekatan dua
algoritma FCM dan GGA-FCM dilakukan
proses klasifikasi dari kluster yang diperoleh
untuk beberapa pilihan c. Hasilnya dapat
disajikan dalam Tabel 5.
Tabel 5. Classification rate clustering FCM
dan GGA-FCM
Cacah
cluster (C)
FCM GGAFCM
2 95.2 % 95.4 %
3 96.1 % 96.7 %
4 98.3 % 99.4 %
5 99.2 % 99.5 %
6 98.6 % 98.4 %
Dari tabel 5. terlihat bahwa kedua metode
tidak jauh berbeda dalam menghasilkan
kluster untuk proses klasifikasi objek yang
ditunjukkan oleh nilai classifcation rate.
Nilai terbaik clasifikasi diperoleh untuk
cacah kluster c=5 untuk algoritma GGAFCM.
Pengujian dengan Kasus 2
Aplikasi klustering dalam pengolahan
citra dapat ditunjukkan dalam upaya
mengubah citra aras keabuan (grayscale
image) menjadi citra hitam-putih (black
white image). Dalam citra asli ada derajat
keabuan yang diwakili oleh nilai keabuan
yang menyusun setiap pixel citra. Untuk
sebuah peta setiap pixel penyusun peta dapat
dikelompokkan sebagai pixel background
(warna putih) atau foreground (warna hitam
sebagai bentuk peta yang dapat berupa jalan,
atau keterangan peta). Data citra berikut
diambilkan dari Chi.et.all (1996) yang
merupakan citra ukuran 134 x 153 x 3 pixel
dengan setiap pixelnya 8bit skala keabuan.
Hasil cluster untuk beberapa nilai c=2, c=4
dan c=8 dan digambarkan hasilnya seperti
dalam Gambar 13.
Naniek Widyastusti dkk, Penggunaan Algoritma Genetika
13
Dari hasil cluster untuk berbagai
ukuran cluster terlihat bahwa dari sisi
perbaikan citra, maka hasil yang didapatkan
masih kurang memuaskan. Salah satu
manfaat yang dapat diperoleh dari hasil
clustering adalah variasi skala keabuan yang
jauh lebih sederhana dengan pengklusteran
(atau lebih dikenal dengan istilah segmentasi
citra) yang dapat dimanfaatkan misalnya
untuk kompresi citra. Untuk Citra peta
tersebut penurunan ukuran file dapat
didekati dengan hasil cluster.
Untuk pengolahan citra yang bertujuan
penajaman citra, metode clustering dengan
FCM dan GGA-FCM belumlah dapat
memberikan hasil yang baik. Pendekatan
rule-base fuzzy clustering dalam hal ini
dapat merupakan alternatif yang lebih baik
dalam penajaman citra. Gambar 14 adalah
contoh hasil penajaman citra dengan rule -
base fuzzyclustering dari Chi et.all. (1996).
Tabel 6. Classification rate clustering
FCM dan GGA-FCM
Tipe Cacah
pixel
Cacah Bit
per pixel
Ukuran
file
Citra
asli
134 x
153 x 3
8 bit 100 %
Cluster
c=2
134 x
153 x 3
1 bit 12.5 %
Cluster
c=4
134 x
153 x 3
2 bit 25.0 %
Cluster
c=8
134 x
153 x 3
3 bit 37.5 %
Gambar 14. Citra Peta dan Hasil Penajaman Citra dengan
Rule-Base dengan 34-Fuzzy Rule
Gambar 13. Clustering GGA-FCM untuk
c=2, c=4 dan c=8
Cluster c=4 Cluster c=8
Cluster asli Cluster c=2
Berkala MIPA, 17(2), Mei 2007
14
3. KESIMPULAN
Beberapa kesimpulan yang dapat diperoleh
dari penelitian ini antara lain dapat diuraikan
sebagai berikut :
1. Metode klustering dengan algoritma
genetika (GGA-FCM) dapat
memperbaiki kinerja FCM dengan
metode iterasi konvensional terutama
ditinjau dari fungsi tujuan Jm dan
koefisien Classification Rate.
2. Jika ditinjau dari beban komputasi dan
waktu komputasi metode GGA-FCM
masih relatif lebih kompleks dan
memerlukan cacah flops yang jauh lebih
besar dari metode FCM konvensional.
Namun dengan perkembangan prosesor
yang semakin baik kemungkinan
kompleksitas komputasi dan waktu
komputasi dapat diatasi.
3. Algoritma genetika (GGA-FCM),
meskipun membutuhkan waktu
komputasi lebih banyak tetapi dapat
memberikan jawaban yang lebih baik
dari metode metode iteratif
konvensional (FCM).
4. Untuk aplikasi pengolahan citra yang
berupa penajaman citra algoritma
GGA-FCM belum dapat digunakan,
tetapi untuk segmentasi citra FCM
maupun GGA-FCM dapat diterapkan
dan dapat menghasilkan citra dengan
komposisi bit yang lebih sederhana dan
ukuran file yang lebih kecil.
DAFTAR PUSTAKA
Belanche L. and Nebot A., 2002,
Intelligent Data Analysis and Data
Mining, Wright State University.
Chi, Z., Yan, H. and Pham, T., 1996,
Fuzzy Algorithms : With
Application to Image Processing
and Pattern Recognition, Advanve
in Fuzzy System-Application and
Theory, Vol.10., Word Scientific,
Singapore.
Gen, M. and Cheng, R., 2000, Genetic
Algorithms and Engineering
Optimization, John Wiley & Sons,
New York.
Hamzah, A, 2001, Pengenalan Pola
dengan Fuzzy Clustering,
ACADEMIA ISTA, Vol.4.No.1.,
Lembaga Penelitian, Institut Sains
dan Teknologi AKPRIND,
Yogayakarta.
Sato, M. and Sato Y., 1995, Fuzzy
Clustering with Multiple
Objectives Functions, Kluwer
Academic Publisher, Boston.
Zimmerman, H.J., 1991, Fuzzy Set
Theory and Its Applications, 2nd
Ed., Norwel, Massachusetts.
FUNGSI ALGORITMA
Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-87
MEMBANGUN TOOLBOX ALGORITMA EVOLUSI FUZZY UNTUK MATLAB
Syafiul Muzid1, Sri Kusumadewi2
1Sekolah Pascasarjana Magister Ilmu Komputer, Universitas Gadjah Mada, Yogyakarta
e-mail: aakzid@yahoo.com
2Jurusan Teknik Informatika, Fakultas Teknologi Industri, Universitas Islam Indonesia, Yogyakarta
e-mail: cicie@fti.uii.ac.id
ABSTRAKSI
Algoritma evolusi fuzzy adalah sebuah teknik komputasi hasil perpaduan antara algoritma genetika
dengan sistem fuzzy. Dalam algoritma evolusi fuzzy, tahapan proses sebuah masalah dapat diselesaikan seperti
tahapan yang ada dalam algoritma genetika. Namun untuk penentuan parameter-parameter genetika seperti
halnya nilai probabilitas rekombinasi (crossover) dan nilai probabilitas mutasi dihasilkan melalui sistem fuzzy.
Algoritma evolusi fuzzy diharapkan menghasilkan hasil yang lebih optimal.
MATLAB adalah sebuah perangkat lunak yang mempunyai beberapa toolbox yang menerapkan konsep
algoritma genetika dan logika fuzzy. Sedangkan toolbox yang menerapkan konsep algoritma evolusi fuzzy
sampai saat ini belum tersedia.
Diharapkan dengan adanya toolbox yang menerapkan konsep algortima evolusi fuzzy dapat membantu
pengguna untuk mempelajari dan memanfaatkan dari algoritma evolusi fuzzy..
Kata kunci: Algoritma genetika, fuzzy, toolbox, Matlab, Evolusi, Algoritma evolusi fuzzy.
1. PENDAHULUAN
1.1 Latar Belakang Masalah
Perkembangan teknologi informasi yang
semakin pesat membuat manusia untuk
memanfaatkan teknologi tersebut semakin tinggi.
Konon, komputer hanya sebagai alat bantu untuk
pekerjaan manusia. Namun sekarang tidak dapat
dipungkiri bahwa komputer telah mampu
menggantikan manusia untuk melakukan sebuah
pekerjaan.
Hal itu semakin terbukti ketika mulai
munculnya metode-metode komputasi yang dapat
dikerjakan oleh komputer. Soft Computing adalah
suatu model pendekatan untuk melakukan
komputasi dengan meniru akal manusia dan
memiliki kemampuan untuk menalar dan belajar
pada lingkungan yang penuh dengan ketidakpastian
[JAN97]. Soft Computing dimanfaatkan untuk
memecahkan masalah dengan menggunakan
pendekatan dalam melakukan penalaran. Proses
pendekatan tersebut dapat dilakukan dengan
fungsional maupun melalui pencarian random.
Diantara komponen pembentuk soft
computing adalah sistem fuzzy, komputasi
evolusioner atau algoritma genetika, dan penalaran
dengan probabilitas. Setiap komponen dapat berdiri
sendiri dalam implementasinya. Penerapan suatu
komponen dalam suatu masalah akan menghasilkan
suatu hasil yang dapat diterima, akan tetapi belum
tentu maksimal.
Dengan bermunculannya metode-metode
komputasi tersebut, terdapat beberapa perangkat
lunak yang memberikan kemudahan bagi pengguna
untuk memanfaatkan metode-metode tersebut
dengan fasilitas toolbox. MATLAB merupakan
salah satu perangkat lunak yang memberikan
fasilitas tersebut.
Toolbox dalam perangkat lunak MATLAB
merupakan perpustakaan fungsi yang membantu
pengguna untuk memecahkan suatu kelompok
permasalahan dengan perangkat lunak MATLAB
sesuai dengan konsep penyelesaian yang
diinginkannya. Penggunaan toolbox tersebut
bersifat dinamis yang mana dapat menyelesaikan
beberapa jenis masalah yang berbeda. Pada toolbox
tersebut dapat ditambahkan fungsi-fungsi baru yang
akan lebih membantu pengguna dalam
menyelesaikan suatu masalah dengan cepat.
Pada MATLAB sudah ada beberapa toolbox
yang sudah ter-generate didalamnya. Toolbox
tersebut antara lain adalah Fuzzy Logic Toolbox
yang menerapkan konsep algoritma logika fuzzy
dan Genetic Algorithm and Direct Search Toolbox
yang menerapkan konsep algoritma genetika.
Seiring berjalannya waktu, karena penerapan
suatu komponen dalam suatu masalah akan
menghasilkan suatu hasil yang dapat diterima, akan
tetapi belum tentu maksimal. Akhirnya muncul
sebuah ide yang menggabungkan antar metode
yang ada, antara lain muncul metode Evolusi
Fuzzy, yaitu gabungan dari metode algoritma
genetika dan sistem fuzzy. Dimana parameterparameter
yang biasanya ada dalam algoritma
genetika didapatkan dari sistem fuzzy.
Metode yang baru muncul ini belum dapat
difasilitasi oleh MATLAB sebagai salah satu
perangkat lunak yang menerapkan teknik
komputasi.
1.2 Rumusan Masalah
Sesuai dengan latar belakang masalah yang
telah diuraikan sebelumnya, maka dapat
dirumuskan permasalahannya, yaitu: Bagaimana
merancang dan membangun serta
Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-88
mengimplementasikan sebuah toolbox yang
menggunakan konsep algoritma evolusi fuzzy?
1.3 Tujuan Penelitian
Penelitian yang dilakukan memiliki beberapa
tujuan, antara lain:
1. Membantu pengguna untuk memahami teori
algoritma evolusi fuzzy dengan mudah.
2. Membuat toolbox dalam MATLAB untuk
penerapan konsep algoritma evolusi fuzzy.
3. Membuat fungsi baru dalam MATLAB untuk
penerapan konsep algoritma evolusi fuzzy yang
bisa digunakan secara dinamis oleh pengguna.
1.4 Manfaat Penelitian
Dengan adanya penelitian yang dilakukan ini
diharapkan dapat memberi manfaat antara lain:
1. Menambah perbendaharaan perangkat lunak,
terutama di bidang sistem cerdas dengan
MATLAB.
2. Sistem yang dibuat dapat digunakan untuk
mengimplementasikan toolbox algoritma
evolusi fuzzy dengan mudah.
3. Menghasilkan fungsi-fungsi baru yang
menerapkan algoritma evolusi fuzzy yang
dapat digunakan oleh pengguna.
1.5 Metodologi Penelitian
Adapun metode-metode yang akan
digunakan adalah dengan menggunakan metode
flow chart (diagram alir), karena dirasa paling
cocok untuk menyelesaikan masalah yang akan
dihadapi.
2. LANDASAN TEORI
2.1 Algoritma Evolusi Fuzzy (Fuzzy
Evolutionary Algorithm)
Algoritma evolusi fuzzy adalah sebuah
teknik komputasi gabungan antara algoritma
genetika dan logika fuzzy. Metode ini hampir sama
dengan metode algoritma genetika, namun
parameter-parameter yang dipakai dihasilkan dari
sebuah sistem fuzzy.
Dalam algoritma evolusi fuzzy, proses yang
terjadi atau alur proses sama seperti dengan
algoritma genetika, yang dikenalkan oleh John
Holland dari Universitas Michigan (1975), dimana
algoritma genetika merupakan teknik pencarian
heuristik berdasar mekanisme evolusi biologis yang
meniru dari teori Darwin dan operasi genetika pada
kromosom.
Dalam algoritma evolusi fuzzy terdapat
enam tahap utama, yaitu:
1. Representasi kromosom.
2. Inisialisasi Populasi.
3. Fungsi evaluasi.
4. Seleksi.
5. Operator genetika, meliputi operator
rekombinasi (crossover) dan mutasi.
6. Penentuan parameter, yaitu parameter
kontrol algoritma genetika, yaitu: ukuran
populasi (popsize), peluang crossover (pc),
dan peluang mutasi (pm). Dalam penentuan
parameter ini dilakukan proses sistem fuzzy
untuk mendapatkan nilai yang akan
digunakan sebagai parameter.
2.2 Algoritma Fuzzy Evolusi Model Xu
Pada algoritma evolusi fuzzy terdapat
berbagai metode yang digunakan dalam perpaduan
antara algoritma genetika dan sistem fuzzy.
Diantaranya adalah model yang dikemukan
oleh Xu, yaitu algoritma evolusi fuzzy yang sistem
fuzzy digunakan pada penentuan parameter adalah
menggunakan sistem inferensi fuzzy metode
mamdani. Metode mamdani ini juga dikenal dengan
metode Max-Min. Metode ini dikenalkan oleh
Ebrahim Mamdani (1975). Metode mamdani yang
digunakan oleh Xu untuk algoritma evolusi fuzzy
adalah menggunakan dua (2) buah masukan dan
dua (2) buah keluaran.
Dua buah masukan yang digunakan adalah:
1. Jumlah Populasi yang digunakan.
2. Jumlah generasi yang akan diproses.
Sedangkan dua buah keluaran yang akan
dihasilkan adalah:
1. Nilai probabilitas rekombinasi (crossover).
2. Nilai probabilitas mutasi.
Dalam menentukan nilai yang dihasilkan
melalui sistem fuzzy perlu dibuat aturan-aturan
fuzzy yang digunakan untuk penentuan hasil.
Dalam model Xu aturan fuzzy yang
digunakan didasarkan dari masukan jumlah
populasi yang diinginkan serta jumlah maksimum
generasi. Dari dua masukan tersebut akan
menghasilkan nilai untuk probabilitas rekombinasi
dan probabilitas mutasi. Aturan yang ditentukan
oleh Xu dapat dilihat dalam tabel 2.1 dan tabel 2.2.
Tabel 1. Aturan untuk nilai probabilitas
rekombinasi (crossover)
Pc Population Size
Generation small medium large
short medium small small
medium large large medium
long very large very large large
Tabel 2. Aturan untuk nilai probabilitas mutasi.
Pm Population Size
Generation small medium large
short large medium small
medium medium small very small
long small very small very small
Dengan aturan diatas, jumlah populasi dan
maksimum generasi yang dimasukkan akan
dianalisa dengan metode Mamdani, sehingga
didapatkan nilai probabilitas crossover dan
probabilitas mutasi yang mana akan dipakai dalam
iterasi.
Dalam algoritma evolusi fuzzy, aturan-aturan
fuzzy yang telah dibuat harus sudah
diimplementasikan terlebih dahulu sebelum proses
iterasi dilakukan. Dari model Xu yang digunakan
Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-89
sesuai tabel 2.1 dan tabel 2.2 didapatkan sebanyak
sembilan (9) aturan, yaitu:
• IF (Populasi is SMALL) AND (Generasi is
SHORT)
THEN (ProbCrossover is MEDIUM) AND
(ProbMutasi is LARGE).
• IF (Populasi is MEDIUM) AND (Generasi is
SHORT)
THEN (ProbCrossover is SMALL) AND
(ProbMutasi is MEDIUM).
• IF (Populasi is LARGE) AND (Generasi is
SHORT)
THEN (ProbCrossover is SMALL) AND
(ProbMutasi is SMALL).
• IF (Populasi is SMALL) AND (Generasi is
MEDIUM)
THEN (ProbCrossover is LARGE) AND
(ProbMutasi is MEDIUM).
• IF (Populasi is MEDIUM) AND (Generasi is
MEDIUM)
THEN (ProbCrossover is LARGE) AND
(ProbMutasi is SMALL).
• IF (Populasi is LARGE) AND (Generasi is
MEDIUM)
THEN (ProbCrossover is MEDIUM) AND
(ProbMutasi is VERYSMALL).
• IF (Populasi is SMALL) AND (Generasi is
LONG)
THEN (ProbCrossover is VERYLARGE) AND
(ProbMutasi is SMALL).
• IF (Populasi is MEDIUM) AND (Generasi is
LONG)
THEN (ProbCrossover is VERYLARGE) AND
(ProbMutasi is VERYSMALL).
• IF (Populasi is LARGE) AND (Generasi is
LONG)
THEN (ProbCrossover is LARGE) AND
(ProbMutasi is VERYSMALL).
Aturan-aturan di atas akan
diimplementasikan dalam sistem fuzzy mamdani,
tetapi perlu diperhatikan supaya sistem fuzzy
mamdani dapat menghasilkan hasil tentunya
diperlukan semesta pembicaraan dan domain yang
memberikan nilai batas untuk setiap himpunan yang
ada pada tiap variabel. Misal nilai untuk semesta
pembicaraan pada variabel populasi adalah [0 100],
yang berarti dalam variabel populasi memiliki batas
semesta pembicaraan mulai batas nilai nol (0)
sampai nilai seratus (100). Sedangkan misal domain
untuk himpunan SMALL pada variabel populasi
adalah [20 50], yang berarti batas populasi
dikatakan SMALL jika bernilai antara duapuluh
(20) dan limapuluh (50).
Selain itu, diperlukan juga fungsi
keanggotaan yang menjelaskan pemetaan titik-titik
input data ke dalam nilai keanggotaannya (sering
juga disebut dengan derajat keanggotaan) yang
memiliki interval antara 0 sampai 1. Misal fungsi
keanggotaan untuk himpunan LARGE pada
variabel populasi menggunakan fungsi kurva S
seperti pada gambar 1.
Adapun semesta pembicaran dan domain
yang digunakan dalam model Xu, ditentukan oleh
peneliti karena hal ini belum ditemukan studi
literatur yang menjelaskan tentang hal ini. Gambar
1 sampai gambar 4 adalah gambar yang
menjelaskan tentang semesta pembicaraan dan
domain yang digunakan peneliti.
Gambar 1. Fungsi keanggotaan himpunan LARGE
pada variabel populasi.
Gambar 1. Semesta pembicaraan dan domain
untuk variabel populasi.
Gambar 2. Semesta pembicaraan dan domain
untuk variabel generasi.
Gambar 3. Semesta pembicaraan dan domain
untuk variabel probabilitas crosover.
Gambar 4. Semesta pembicaraan dan domain
untuk variabel probabilitas mutasi.
Dibawah ini ini adalah gambar proses sistem
fuzzy mamdani yang digunakan di atas.
1
0 ℜ1 domain
derajat
keanggotaan
μ[x]
ℜn
Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-90
Gambar 5. Alur proses sistem fuzzy mamdani.
2.3 Arsitektur Algoritma Evolusi Fuzzy
Gambar 6 adalah gambar arsitektur dari
algoritma evolusi fuzzy.
Gambar 6. Arsitektur algoritma evolusi fuzzy
Dari gambar diatas dapat dilihat bahwa
proses yang digunakan dalam algoritma evolusi
fuzzy bahwa nilai statistik dari populasi dan
generasi yang ada dimasukkan dalam proses fuzzy
sehingga menhasilkan parameter yang kemudian
akan digunakan dalam proses algoritma genetika
sehingga akan menghasilkan keluaran akhir.
3. PEMBAHASAN
3.1 Analisis dan Perancangan Sistem
Perangkat lunak yang dikembangkan diberi
nama FEA (Fuzzy Evolutionary Algorithm), yang
dibangun menggunakan perangkat lunak
MATLAB.
a. Masukan sistem
Masukan yang akan digunakan adalah:
1. Fungsi untuk pencarian nilai fitness.
2. Jumlah variabel.
3. Jumlah bit untuk setiap variabel.
4. File fuzzy yang akan digunakan untuk mencari
nilai parameter probabilitas rekombinasi dan
probabilitas mutasi.
5. Jumlah populasi.
6. Jumlah maksimum generasi.
7. Model representasi kromosom beserta
parameter kromosom.
8. Model seleksi.
9. Model rekombinasi (crossover).
10. Model mutasi.
11. Jumlah kromosom yang akan dipertahankan
(elitisme).
12. Model plot, yang mana akan menjadi keluaran
sistem.
b. Keluaran sistem
Adapun keluaran dari sistem algoritma
evolusi fuzzy adalah berupa grafik himpunan
setelah melalui proses iterasi serta nilai fitness
terbaik, nilai fitness terburuk, nilai fitness rata-rata
serta nilai terbaik untuk setiap individu yang
ditampilkan pada command windows.
3.2 Implementasi Sistem
Dalam sistem yang dibangun hanya
dibutuhkan satu (1) buah jendela utama sebagai
pusat interaksi pengguna dengan sistem, dan satu
(1) buah jendela keluaran sebagai hasil dari proses
sistem.
a. Jendela utama
Dalam toolbox yang dibuat hanya
menggunakan sebuah form yaitu halaman utama,
sekaligus sebagai tempat pengguna berinteraksi
dengan perangkat lunak ini. Pengguna dapat
memasukkan model-model variabel input serta
parameter-parameter yang akan digunakan dalam
iterasi proses. Seperti gambar 7.
Gambar 7. Jendela utama
3.3 Hasil Pengujian
Pengujian program perangkat lunak toolbox
algoritma evolusi fuzzy bertujuan untuk
mengetahui apakah perangkat lunak tersebut sudah
dapat berjalan sesuai dengan fungsi-fungsi yang
diharapkan dan apakah sudah sesuai dengan tujuan
dari pembuatan perangkat lunak tersebut. Dalam
pengujian digunakan suatu masalah optimasi fungsi
sederhana dimana menggunakan toolbox algoritma
evolusi fuzzy untuk mencari nilai minimal dari
sebuah fungsi h seperti dibawah ini dengan x1,x2 ∈
[0; 1], karena hasil yang diinginkan adalah
minimalisasi maka dalam pendeklarasian fungsi
fitness adalah 1/h.
h(x1,x2) = 1000(x1 – 2x2)2 + (1 – x1)2 ...(1)
Diasumsikan fungsi diatas dibuat dalam
bahasa MATLAB dengan nama fungsinya
FeaEvaluateFcn.
Contoh:
• Fitness Function : FeaEvaluateFcn
• Number of Variabel : 2
• Number of Bit : 5
• File FIS :default
• Population Size : 100
• Max. Generation : 100
• Cromossom Type : Biner
• Top Range : 1
• Bottom Range : 0
• Selection Method :Roulette Wheel
Fuzzy Goverment
Evolutionary Algorithm
Object Problem
Parameters Statistics
Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-91
• Crossover Method : One Point
• Mutation Method : Change
• Plot Function : Best Fitness
Setelah pengguna memasukkan input, dan
memilih tombol “START”, maka grafik output
akan keluar, seperti pada gambar 8. Sedang gambar
9 adalah contoh hasil keluaran proses algoritma
evolusi fuzzy yang muncul pada command
windows.
Best Fitness
Mean Fitness
Gambar 8. Grafik plot output.
Gambar 9. Hasil keluaran yang muncul pada
command windows.
3.4 Hasil Analisis
Dari hasil pengujian diatas dapat diambil
kesimpulan dari kinerja program toolbox algoritma
evolusi fuzzy yaitu:
a. Pengecekan kesalahan (error handling) yang
bersifat masukan pengguna dapat dilakukan
oleh sistem.
b. Dapat menghasilkan hasil optimal dari iterasi.
c. Fungsi yang dibuat dapat dipakai dalam versi
Command Windows.
4. PENUTUP
4.1 Simpulan
Setelah melalui tahapan analisis, desain,
pengkodean dan pengujian maka penulis dapat
mengambil beberapa kesimpulan bahwa sistem
toolbox algoritma evolusi fuzzy akan dapat
membantu pengguna untuk menggunakan metode
algoritma evolusi fuzzy, antara lain :
a. Membantu pengguna untuk mempelajari
algoritma evolusi fuzzy dengan mudah.
b. Membantu pengguna untuk
mengimplementasikan masalah yang ada
dengan toolbox algoritma evolusi fuzzy.
c. Membantu pengguna untuk menggunakan
fungsi baru yang dibuat.
d. Memberikan hasil yang lebih optimum dalam
suatu permasalahan yang diselesaikan dengan
metode algoritma evolusi fuzzy.
4.2 Saran
Saran untuk pengembangan algoritma
evolusi fuzzy adalah:
a. Diharapkan dalam pengembangan perangkat
lunak selanjutnya dapat lebih dinamis dan
fleksibel dengan data-data input.
b. Diharapkan dalam pengembangan perangkat
lunak selanjutnya menggunakan model-model
yang lebih lengkap.
c. Diharapkan dalam pengembangan perangkat
lunak selanjutnya antarmuka bisa lebih user
friendly.
PUSTAKA
[AWA06] Away, G.A., The Shortcut of MATLAB
Programming, Bandung, Informatika,
2006.
[CHA98] Chanas, S., dan Kuchta, D. Fuzzy
Integer Transportation Problem. Journal
in Fuzzy Set & System 98 hlm. 291 –
298, 1998.
[GEN97] Gen, M., dan Cheng, R., Genetic
Algorithms and Engineering Design,
New York, John Wiley & Sons, Inc,
1997.
[JAN97] Jang, J.S.R., Sun, C.T., dan Mizutani,
E., Neuro-Fuzzy and Soft Computing.
London, Prentice Hall, 1997.
[KUS02] Kusumadewi, S, Analisis Desain Sistem
Fuzzy menggunakan Toolbox MATLAB,
Yogyakarta, Graha Ilmu, 2002.
[KUS03] Kusumadewi, S. Artificiall Intelligence :
Teknik dan Aplikasinya. Yogyakarta ,
Graha Ilmu, 2003.
[KUS05] Kusumadewi, S, dan Purnomo, H.,
Penyelesaian Masalah Optimasi dengan
Teknik-teknik Heuristik, Yogyakarta,
Graha Ilmu, 2005.
[SUY05] Suyanto, Algoritma Genetika dalam
MATLAB, Yogyakarta, ANDI Offset,
2005.
[TET01] Tettamanzi, A., dan Tomassini, M., Soft
Computing, New York, Springer, 2001.
Yogyakarta, 16 Juni 2007
B-87
MEMBANGUN TOOLBOX ALGORITMA EVOLUSI FUZZY UNTUK MATLAB
Syafiul Muzid1, Sri Kusumadewi2
1Sekolah Pascasarjana Magister Ilmu Komputer, Universitas Gadjah Mada, Yogyakarta
e-mail: aakzid@yahoo.com
2Jurusan Teknik Informatika, Fakultas Teknologi Industri, Universitas Islam Indonesia, Yogyakarta
e-mail: cicie@fti.uii.ac.id
ABSTRAKSI
Algoritma evolusi fuzzy adalah sebuah teknik komputasi hasil perpaduan antara algoritma genetika
dengan sistem fuzzy. Dalam algoritma evolusi fuzzy, tahapan proses sebuah masalah dapat diselesaikan seperti
tahapan yang ada dalam algoritma genetika. Namun untuk penentuan parameter-parameter genetika seperti
halnya nilai probabilitas rekombinasi (crossover) dan nilai probabilitas mutasi dihasilkan melalui sistem fuzzy.
Algoritma evolusi fuzzy diharapkan menghasilkan hasil yang lebih optimal.
MATLAB adalah sebuah perangkat lunak yang mempunyai beberapa toolbox yang menerapkan konsep
algoritma genetika dan logika fuzzy. Sedangkan toolbox yang menerapkan konsep algoritma evolusi fuzzy
sampai saat ini belum tersedia.
Diharapkan dengan adanya toolbox yang menerapkan konsep algortima evolusi fuzzy dapat membantu
pengguna untuk mempelajari dan memanfaatkan dari algoritma evolusi fuzzy..
Kata kunci: Algoritma genetika, fuzzy, toolbox, Matlab, Evolusi, Algoritma evolusi fuzzy.
1. PENDAHULUAN
1.1 Latar Belakang Masalah
Perkembangan teknologi informasi yang
semakin pesat membuat manusia untuk
memanfaatkan teknologi tersebut semakin tinggi.
Konon, komputer hanya sebagai alat bantu untuk
pekerjaan manusia. Namun sekarang tidak dapat
dipungkiri bahwa komputer telah mampu
menggantikan manusia untuk melakukan sebuah
pekerjaan.
Hal itu semakin terbukti ketika mulai
munculnya metode-metode komputasi yang dapat
dikerjakan oleh komputer. Soft Computing adalah
suatu model pendekatan untuk melakukan
komputasi dengan meniru akal manusia dan
memiliki kemampuan untuk menalar dan belajar
pada lingkungan yang penuh dengan ketidakpastian
[JAN97]. Soft Computing dimanfaatkan untuk
memecahkan masalah dengan menggunakan
pendekatan dalam melakukan penalaran. Proses
pendekatan tersebut dapat dilakukan dengan
fungsional maupun melalui pencarian random.
Diantara komponen pembentuk soft
computing adalah sistem fuzzy, komputasi
evolusioner atau algoritma genetika, dan penalaran
dengan probabilitas. Setiap komponen dapat berdiri
sendiri dalam implementasinya. Penerapan suatu
komponen dalam suatu masalah akan menghasilkan
suatu hasil yang dapat diterima, akan tetapi belum
tentu maksimal.
Dengan bermunculannya metode-metode
komputasi tersebut, terdapat beberapa perangkat
lunak yang memberikan kemudahan bagi pengguna
untuk memanfaatkan metode-metode tersebut
dengan fasilitas toolbox. MATLAB merupakan
salah satu perangkat lunak yang memberikan
fasilitas tersebut.
Toolbox dalam perangkat lunak MATLAB
merupakan perpustakaan fungsi yang membantu
pengguna untuk memecahkan suatu kelompok
permasalahan dengan perangkat lunak MATLAB
sesuai dengan konsep penyelesaian yang
diinginkannya. Penggunaan toolbox tersebut
bersifat dinamis yang mana dapat menyelesaikan
beberapa jenis masalah yang berbeda. Pada toolbox
tersebut dapat ditambahkan fungsi-fungsi baru yang
akan lebih membantu pengguna dalam
menyelesaikan suatu masalah dengan cepat.
Pada MATLAB sudah ada beberapa toolbox
yang sudah ter-generate didalamnya. Toolbox
tersebut antara lain adalah Fuzzy Logic Toolbox
yang menerapkan konsep algoritma logika fuzzy
dan Genetic Algorithm and Direct Search Toolbox
yang menerapkan konsep algoritma genetika.
Seiring berjalannya waktu, karena penerapan
suatu komponen dalam suatu masalah akan
menghasilkan suatu hasil yang dapat diterima, akan
tetapi belum tentu maksimal. Akhirnya muncul
sebuah ide yang menggabungkan antar metode
yang ada, antara lain muncul metode Evolusi
Fuzzy, yaitu gabungan dari metode algoritma
genetika dan sistem fuzzy. Dimana parameterparameter
yang biasanya ada dalam algoritma
genetika didapatkan dari sistem fuzzy.
Metode yang baru muncul ini belum dapat
difasilitasi oleh MATLAB sebagai salah satu
perangkat lunak yang menerapkan teknik
komputasi.
1.2 Rumusan Masalah
Sesuai dengan latar belakang masalah yang
telah diuraikan sebelumnya, maka dapat
dirumuskan permasalahannya, yaitu: Bagaimana
merancang dan membangun serta
Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-88
mengimplementasikan sebuah toolbox yang
menggunakan konsep algoritma evolusi fuzzy?
1.3 Tujuan Penelitian
Penelitian yang dilakukan memiliki beberapa
tujuan, antara lain:
1. Membantu pengguna untuk memahami teori
algoritma evolusi fuzzy dengan mudah.
2. Membuat toolbox dalam MATLAB untuk
penerapan konsep algoritma evolusi fuzzy.
3. Membuat fungsi baru dalam MATLAB untuk
penerapan konsep algoritma evolusi fuzzy yang
bisa digunakan secara dinamis oleh pengguna.
1.4 Manfaat Penelitian
Dengan adanya penelitian yang dilakukan ini
diharapkan dapat memberi manfaat antara lain:
1. Menambah perbendaharaan perangkat lunak,
terutama di bidang sistem cerdas dengan
MATLAB.
2. Sistem yang dibuat dapat digunakan untuk
mengimplementasikan toolbox algoritma
evolusi fuzzy dengan mudah.
3. Menghasilkan fungsi-fungsi baru yang
menerapkan algoritma evolusi fuzzy yang
dapat digunakan oleh pengguna.
1.5 Metodologi Penelitian
Adapun metode-metode yang akan
digunakan adalah dengan menggunakan metode
flow chart (diagram alir), karena dirasa paling
cocok untuk menyelesaikan masalah yang akan
dihadapi.
2. LANDASAN TEORI
2.1 Algoritma Evolusi Fuzzy (Fuzzy
Evolutionary Algorithm)
Algoritma evolusi fuzzy adalah sebuah
teknik komputasi gabungan antara algoritma
genetika dan logika fuzzy. Metode ini hampir sama
dengan metode algoritma genetika, namun
parameter-parameter yang dipakai dihasilkan dari
sebuah sistem fuzzy.
Dalam algoritma evolusi fuzzy, proses yang
terjadi atau alur proses sama seperti dengan
algoritma genetika, yang dikenalkan oleh John
Holland dari Universitas Michigan (1975), dimana
algoritma genetika merupakan teknik pencarian
heuristik berdasar mekanisme evolusi biologis yang
meniru dari teori Darwin dan operasi genetika pada
kromosom.
Dalam algoritma evolusi fuzzy terdapat
enam tahap utama, yaitu:
1. Representasi kromosom.
2. Inisialisasi Populasi.
3. Fungsi evaluasi.
4. Seleksi.
5. Operator genetika, meliputi operator
rekombinasi (crossover) dan mutasi.
6. Penentuan parameter, yaitu parameter
kontrol algoritma genetika, yaitu: ukuran
populasi (popsize), peluang crossover (pc),
dan peluang mutasi (pm). Dalam penentuan
parameter ini dilakukan proses sistem fuzzy
untuk mendapatkan nilai yang akan
digunakan sebagai parameter.
2.2 Algoritma Fuzzy Evolusi Model Xu
Pada algoritma evolusi fuzzy terdapat
berbagai metode yang digunakan dalam perpaduan
antara algoritma genetika dan sistem fuzzy.
Diantaranya adalah model yang dikemukan
oleh Xu, yaitu algoritma evolusi fuzzy yang sistem
fuzzy digunakan pada penentuan parameter adalah
menggunakan sistem inferensi fuzzy metode
mamdani. Metode mamdani ini juga dikenal dengan
metode Max-Min. Metode ini dikenalkan oleh
Ebrahim Mamdani (1975). Metode mamdani yang
digunakan oleh Xu untuk algoritma evolusi fuzzy
adalah menggunakan dua (2) buah masukan dan
dua (2) buah keluaran.
Dua buah masukan yang digunakan adalah:
1. Jumlah Populasi yang digunakan.
2. Jumlah generasi yang akan diproses.
Sedangkan dua buah keluaran yang akan
dihasilkan adalah:
1. Nilai probabilitas rekombinasi (crossover).
2. Nilai probabilitas mutasi.
Dalam menentukan nilai yang dihasilkan
melalui sistem fuzzy perlu dibuat aturan-aturan
fuzzy yang digunakan untuk penentuan hasil.
Dalam model Xu aturan fuzzy yang
digunakan didasarkan dari masukan jumlah
populasi yang diinginkan serta jumlah maksimum
generasi. Dari dua masukan tersebut akan
menghasilkan nilai untuk probabilitas rekombinasi
dan probabilitas mutasi. Aturan yang ditentukan
oleh Xu dapat dilihat dalam tabel 2.1 dan tabel 2.2.
Tabel 1. Aturan untuk nilai probabilitas
rekombinasi (crossover)
Pc Population Size
Generation small medium large
short medium small small
medium large large medium
long very large very large large
Tabel 2. Aturan untuk nilai probabilitas mutasi.
Pm Population Size
Generation small medium large
short large medium small
medium medium small very small
long small very small very small
Dengan aturan diatas, jumlah populasi dan
maksimum generasi yang dimasukkan akan
dianalisa dengan metode Mamdani, sehingga
didapatkan nilai probabilitas crossover dan
probabilitas mutasi yang mana akan dipakai dalam
iterasi.
Dalam algoritma evolusi fuzzy, aturan-aturan
fuzzy yang telah dibuat harus sudah
diimplementasikan terlebih dahulu sebelum proses
iterasi dilakukan. Dari model Xu yang digunakan
Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-89
sesuai tabel 2.1 dan tabel 2.2 didapatkan sebanyak
sembilan (9) aturan, yaitu:
• IF (Populasi is SMALL) AND (Generasi is
SHORT)
THEN (ProbCrossover is MEDIUM) AND
(ProbMutasi is LARGE).
• IF (Populasi is MEDIUM) AND (Generasi is
SHORT)
THEN (ProbCrossover is SMALL) AND
(ProbMutasi is MEDIUM).
• IF (Populasi is LARGE) AND (Generasi is
SHORT)
THEN (ProbCrossover is SMALL) AND
(ProbMutasi is SMALL).
• IF (Populasi is SMALL) AND (Generasi is
MEDIUM)
THEN (ProbCrossover is LARGE) AND
(ProbMutasi is MEDIUM).
• IF (Populasi is MEDIUM) AND (Generasi is
MEDIUM)
THEN (ProbCrossover is LARGE) AND
(ProbMutasi is SMALL).
• IF (Populasi is LARGE) AND (Generasi is
MEDIUM)
THEN (ProbCrossover is MEDIUM) AND
(ProbMutasi is VERYSMALL).
• IF (Populasi is SMALL) AND (Generasi is
LONG)
THEN (ProbCrossover is VERYLARGE) AND
(ProbMutasi is SMALL).
• IF (Populasi is MEDIUM) AND (Generasi is
LONG)
THEN (ProbCrossover is VERYLARGE) AND
(ProbMutasi is VERYSMALL).
• IF (Populasi is LARGE) AND (Generasi is
LONG)
THEN (ProbCrossover is LARGE) AND
(ProbMutasi is VERYSMALL).
Aturan-aturan di atas akan
diimplementasikan dalam sistem fuzzy mamdani,
tetapi perlu diperhatikan supaya sistem fuzzy
mamdani dapat menghasilkan hasil tentunya
diperlukan semesta pembicaraan dan domain yang
memberikan nilai batas untuk setiap himpunan yang
ada pada tiap variabel. Misal nilai untuk semesta
pembicaraan pada variabel populasi adalah [0 100],
yang berarti dalam variabel populasi memiliki batas
semesta pembicaraan mulai batas nilai nol (0)
sampai nilai seratus (100). Sedangkan misal domain
untuk himpunan SMALL pada variabel populasi
adalah [20 50], yang berarti batas populasi
dikatakan SMALL jika bernilai antara duapuluh
(20) dan limapuluh (50).
Selain itu, diperlukan juga fungsi
keanggotaan yang menjelaskan pemetaan titik-titik
input data ke dalam nilai keanggotaannya (sering
juga disebut dengan derajat keanggotaan) yang
memiliki interval antara 0 sampai 1. Misal fungsi
keanggotaan untuk himpunan LARGE pada
variabel populasi menggunakan fungsi kurva S
seperti pada gambar 1.
Adapun semesta pembicaran dan domain
yang digunakan dalam model Xu, ditentukan oleh
peneliti karena hal ini belum ditemukan studi
literatur yang menjelaskan tentang hal ini. Gambar
1 sampai gambar 4 adalah gambar yang
menjelaskan tentang semesta pembicaraan dan
domain yang digunakan peneliti.
Gambar 1. Fungsi keanggotaan himpunan LARGE
pada variabel populasi.
Gambar 1. Semesta pembicaraan dan domain
untuk variabel populasi.
Gambar 2. Semesta pembicaraan dan domain
untuk variabel generasi.
Gambar 3. Semesta pembicaraan dan domain
untuk variabel probabilitas crosover.
Gambar 4. Semesta pembicaraan dan domain
untuk variabel probabilitas mutasi.
Dibawah ini ini adalah gambar proses sistem
fuzzy mamdani yang digunakan di atas.
1
0 ℜ1 domain
derajat
keanggotaan
μ[x]
ℜn
Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-90
Gambar 5. Alur proses sistem fuzzy mamdani.
2.3 Arsitektur Algoritma Evolusi Fuzzy
Gambar 6 adalah gambar arsitektur dari
algoritma evolusi fuzzy.
Gambar 6. Arsitektur algoritma evolusi fuzzy
Dari gambar diatas dapat dilihat bahwa
proses yang digunakan dalam algoritma evolusi
fuzzy bahwa nilai statistik dari populasi dan
generasi yang ada dimasukkan dalam proses fuzzy
sehingga menhasilkan parameter yang kemudian
akan digunakan dalam proses algoritma genetika
sehingga akan menghasilkan keluaran akhir.
3. PEMBAHASAN
3.1 Analisis dan Perancangan Sistem
Perangkat lunak yang dikembangkan diberi
nama FEA (Fuzzy Evolutionary Algorithm), yang
dibangun menggunakan perangkat lunak
MATLAB.
a. Masukan sistem
Masukan yang akan digunakan adalah:
1. Fungsi untuk pencarian nilai fitness.
2. Jumlah variabel.
3. Jumlah bit untuk setiap variabel.
4. File fuzzy yang akan digunakan untuk mencari
nilai parameter probabilitas rekombinasi dan
probabilitas mutasi.
5. Jumlah populasi.
6. Jumlah maksimum generasi.
7. Model representasi kromosom beserta
parameter kromosom.
8. Model seleksi.
9. Model rekombinasi (crossover).
10. Model mutasi.
11. Jumlah kromosom yang akan dipertahankan
(elitisme).
12. Model plot, yang mana akan menjadi keluaran
sistem.
b. Keluaran sistem
Adapun keluaran dari sistem algoritma
evolusi fuzzy adalah berupa grafik himpunan
setelah melalui proses iterasi serta nilai fitness
terbaik, nilai fitness terburuk, nilai fitness rata-rata
serta nilai terbaik untuk setiap individu yang
ditampilkan pada command windows.
3.2 Implementasi Sistem
Dalam sistem yang dibangun hanya
dibutuhkan satu (1) buah jendela utama sebagai
pusat interaksi pengguna dengan sistem, dan satu
(1) buah jendela keluaran sebagai hasil dari proses
sistem.
a. Jendela utama
Dalam toolbox yang dibuat hanya
menggunakan sebuah form yaitu halaman utama,
sekaligus sebagai tempat pengguna berinteraksi
dengan perangkat lunak ini. Pengguna dapat
memasukkan model-model variabel input serta
parameter-parameter yang akan digunakan dalam
iterasi proses. Seperti gambar 7.
Gambar 7. Jendela utama
3.3 Hasil Pengujian
Pengujian program perangkat lunak toolbox
algoritma evolusi fuzzy bertujuan untuk
mengetahui apakah perangkat lunak tersebut sudah
dapat berjalan sesuai dengan fungsi-fungsi yang
diharapkan dan apakah sudah sesuai dengan tujuan
dari pembuatan perangkat lunak tersebut. Dalam
pengujian digunakan suatu masalah optimasi fungsi
sederhana dimana menggunakan toolbox algoritma
evolusi fuzzy untuk mencari nilai minimal dari
sebuah fungsi h seperti dibawah ini dengan x1,x2 ∈
[0; 1], karena hasil yang diinginkan adalah
minimalisasi maka dalam pendeklarasian fungsi
fitness adalah 1/h.
h(x1,x2) = 1000(x1 – 2x2)2 + (1 – x1)2 ...(1)
Diasumsikan fungsi diatas dibuat dalam
bahasa MATLAB dengan nama fungsinya
FeaEvaluateFcn.
Contoh:
• Fitness Function : FeaEvaluateFcn
• Number of Variabel : 2
• Number of Bit : 5
• File FIS :default
• Population Size : 100
• Max. Generation : 100
• Cromossom Type : Biner
• Top Range : 1
• Bottom Range : 0
• Selection Method :Roulette Wheel
Fuzzy Goverment
Evolutionary Algorithm
Object Problem
Parameters Statistics
Seminar Nasional Aplikasi Teknologi Informasi 2007 (SNATI 2007) ISSN: 1907-5022
Yogyakarta, 16 Juni 2007
B-91
• Crossover Method : One Point
• Mutation Method : Change
• Plot Function : Best Fitness
Setelah pengguna memasukkan input, dan
memilih tombol “START”, maka grafik output
akan keluar, seperti pada gambar 8. Sedang gambar
9 adalah contoh hasil keluaran proses algoritma
evolusi fuzzy yang muncul pada command
windows.
Best Fitness
Mean Fitness
Gambar 8. Grafik plot output.
Gambar 9. Hasil keluaran yang muncul pada
command windows.
3.4 Hasil Analisis
Dari hasil pengujian diatas dapat diambil
kesimpulan dari kinerja program toolbox algoritma
evolusi fuzzy yaitu:
a. Pengecekan kesalahan (error handling) yang
bersifat masukan pengguna dapat dilakukan
oleh sistem.
b. Dapat menghasilkan hasil optimal dari iterasi.
c. Fungsi yang dibuat dapat dipakai dalam versi
Command Windows.
4. PENUTUP
4.1 Simpulan
Setelah melalui tahapan analisis, desain,
pengkodean dan pengujian maka penulis dapat
mengambil beberapa kesimpulan bahwa sistem
toolbox algoritma evolusi fuzzy akan dapat
membantu pengguna untuk menggunakan metode
algoritma evolusi fuzzy, antara lain :
a. Membantu pengguna untuk mempelajari
algoritma evolusi fuzzy dengan mudah.
b. Membantu pengguna untuk
mengimplementasikan masalah yang ada
dengan toolbox algoritma evolusi fuzzy.
c. Membantu pengguna untuk menggunakan
fungsi baru yang dibuat.
d. Memberikan hasil yang lebih optimum dalam
suatu permasalahan yang diselesaikan dengan
metode algoritma evolusi fuzzy.
4.2 Saran
Saran untuk pengembangan algoritma
evolusi fuzzy adalah:
a. Diharapkan dalam pengembangan perangkat
lunak selanjutnya dapat lebih dinamis dan
fleksibel dengan data-data input.
b. Diharapkan dalam pengembangan perangkat
lunak selanjutnya menggunakan model-model
yang lebih lengkap.
c. Diharapkan dalam pengembangan perangkat
lunak selanjutnya antarmuka bisa lebih user
friendly.
PUSTAKA
[AWA06] Away, G.A., The Shortcut of MATLAB
Programming, Bandung, Informatika,
2006.
[CHA98] Chanas, S., dan Kuchta, D. Fuzzy
Integer Transportation Problem. Journal
in Fuzzy Set & System 98 hlm. 291 –
298, 1998.
[GEN97] Gen, M., dan Cheng, R., Genetic
Algorithms and Engineering Design,
New York, John Wiley & Sons, Inc,
1997.
[JAN97] Jang, J.S.R., Sun, C.T., dan Mizutani,
E., Neuro-Fuzzy and Soft Computing.
London, Prentice Hall, 1997.
[KUS02] Kusumadewi, S, Analisis Desain Sistem
Fuzzy menggunakan Toolbox MATLAB,
Yogyakarta, Graha Ilmu, 2002.
[KUS03] Kusumadewi, S. Artificiall Intelligence :
Teknik dan Aplikasinya. Yogyakarta ,
Graha Ilmu, 2003.
[KUS05] Kusumadewi, S, dan Purnomo, H.,
Penyelesaian Masalah Optimasi dengan
Teknik-teknik Heuristik, Yogyakarta,
Graha Ilmu, 2005.
[SUY05] Suyanto, Algoritma Genetika dalam
MATLAB, Yogyakarta, ANDI Offset,
2005.
[TET01] Tettamanzi, A., dan Tomassini, M., Soft
Computing, New York, Springer, 2001.
FUNGSI ALGORITMA
Penulis : Reza Yoga Anindita
Fakultas : Sains dan Teknologi
Program Studi : Matematika
IPK : 3.03
Pembimbing I : Drs. H. Sediono, M.Si
Pembimbing II : Drs. Sulyanto, M.Si
Deteksi Model Arma Secara Otomatis Dengan Algoritma Box -
Jenkins Berdasarkan Fungsi Residual
Abstrak :
Metode Box-Jenkins merupakan metode pemodelan time series yang terdiri dari 3 tahap yaitu identifikasi,
estimasi, dan diagnostik model. Metode ini memerlukan banyak pekerjaan manual dan keterampilan
statistik dalam pembentukan model sementara, terutama dalam memeriksa plot fungsi autocorrelation dan
fungsi parsial autocorrelation dari deret waktu.
Tujuan dari penulisan skripsi ini adalah pertama algoritma yang diusulkan, digunakan untuk memeriksa
sampel fungsi autocorrelation atau fungsi parsial autocorrelation residual model, yang merupakan kunci
dari perbedaan utama dari metode Box-Jenkins. Kedua, algoritma yang diusulkan dapat mengidentifikasi
karakteristik correlograms, sebuah langkah penting dalam proses pemodelan time series.
Berdasarkan Hasil penerapan Data dengan Algoritma Box-Jenkins diperoleh dugaan model AR (1) dan
MA (1)dengan persamaan:
dan
Kata Kunci : Pemodelan Time Series, Metode Box-Jenkins, Fungsi Autokorelasi, Identifikasi, Estimasi, dan
Diagnostik.
Keyword :
keyword-1, keyword-2, keyword-3, ... dst
Page 1
Fakultas : Sains dan Teknologi
Program Studi : Matematika
IPK : 3.03
Pembimbing I : Drs. H. Sediono, M.Si
Pembimbing II : Drs. Sulyanto, M.Si
Deteksi Model Arma Secara Otomatis Dengan Algoritma Box -
Jenkins Berdasarkan Fungsi Residual
Abstrak :
Metode Box-Jenkins merupakan metode pemodelan time series yang terdiri dari 3 tahap yaitu identifikasi,
estimasi, dan diagnostik model. Metode ini memerlukan banyak pekerjaan manual dan keterampilan
statistik dalam pembentukan model sementara, terutama dalam memeriksa plot fungsi autocorrelation dan
fungsi parsial autocorrelation dari deret waktu.
Tujuan dari penulisan skripsi ini adalah pertama algoritma yang diusulkan, digunakan untuk memeriksa
sampel fungsi autocorrelation atau fungsi parsial autocorrelation residual model, yang merupakan kunci
dari perbedaan utama dari metode Box-Jenkins. Kedua, algoritma yang diusulkan dapat mengidentifikasi
karakteristik correlograms, sebuah langkah penting dalam proses pemodelan time series.
Berdasarkan Hasil penerapan Data dengan Algoritma Box-Jenkins diperoleh dugaan model AR (1) dan
MA (1)dengan persamaan:
dan
Kata Kunci : Pemodelan Time Series, Metode Box-Jenkins, Fungsi Autokorelasi, Identifikasi, Estimasi, dan
Diagnostik.
Keyword :
keyword-1, keyword-2, keyword-3, ... dst
Page 1
FUNGSI ALGORITMA
xii
SKRIPSI
PENGOPTIMALAN FUNGSI NONLINEAR TANPA KENDALA
MENGGUNAKAN ALGORITMA GENETIKA
Skripsi ini diajukan untuk memenuhi
salah satu persyaratan dalam mencapai derajat
Sarjana Pendidikan
Diajukan Oleh
MEY ANA PURBAYANTI
05015009
PROGRAM STUDI MATEMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS AHMAD DAHLAN
YOGYAKARTA
2009
xiii
A. Kesimpulan
Berdasarkan pembahasan yang telah disajikan pada bab sebelumnya, dapat
ditarik kesimpulan sebagai berikut :
1. Secara singkat kerja dari Algoritma Genetika adalah pertama membangkitkan
sebuah populasi yang berisi sejumlah kromosom, kromosom-kromosom
tersebut akan berevolusi secara berkelanjutan yang disebut generasi. Kedua,
mengkodekan kromosom yang telah dibangkitkan menjadi individu x dalam
interval yang diinginkan. Ketiga, menghitung nilai fitness dari individu x .
Keempat, melakukan seleksi untuk memperoleh individu yang baik untuk
menjdi orang tua. Kelima, memindahsilangkan dua buah kromosom untuk
mendapatkan sebuah kromosom yang lebih baik (pindah silang / crossover).
Tahap keenam adalah mutasi, yaitu untuk semua gen yang ada, jika bilangan
acak yang dibangkitkan kurang dari probabilitas mutasi yang ditentukan maka
ubah gen tersebut dengan kebalikannya (0 menjadi 1, dan 1 menjadi 0). Proses
akan berulang, sampai sejumlah generasi yang telah ditentukan.
2. Hasil implementasi dari kerja algoritma genetika adalah sebagai berikut :
Permasalahan :
Maksimumkan f x 4x3 3x2 6x 1
x 0
Parameter yang digunakan pada algoritma genetika :
Jumlah kromosom ( N ) yang digunakan adalah 100.
xiv
Jumlah bit atau gen yang digunakan adalah 25.
Generasi maksimum yang diinginkan adalah 500.
Probabilitas crossover c P adalah 0.85.
Probabilitas mutasi m P adalah 0.1.
Parameter-parameter tersebut dimasukan dalam program utama dari algoritma
genetika, dan diperoleh hasil sebagai berikut :
Fitness terbaik adalah 6.
Nilai x yang memaksimumkan fungsi adalah 1.002 .
Niali maksimum fungsi adalah 6.
3. Perbandingan dari metode Newton Raphson dengan Algoritma Genetika yang
jelas terlihat adalah :
Metode Newton Raphson
a. Hanya menggunakan satu titik sebagai nilai awal.
b. Perhitungan menggunakan kalkulus diferensial.
c. Jika nilai awal tidak dipilih dengan tepat, maka dapat terjadi bahwa
metodenya konvergen ke suatu minimum lokal atau sama sekali tidak
konvergen.
Algoritma Genetika
a. Menggunakan beberapa titik sebagai nilai awal.
b. Menggunakan perhitungan biasa.
xv
c. Dapat menghindari keadaan optimum lokal, karena menggunakan
beberapa titik sebagai nilai awal.
4. Kelemahan dari Algoritma Genetika adalah karena semua komponen
Algoritma Genetika bersifat random atau acak mengakibatkan solusi yang
dihasilkan berbeda-beda pada setiap kali running. Tetapi kejadian ini dapat
dihindari dengan memilih nilai-nilai parameter dengan tepat, maka Algoritma
Genetika dapat memberika solusi yang dapat diterima.
5. Kelemahan Metode Newton-Raphson adalah memiliki permasalahan dalam
implementasinya. Permasalahan terjadi antara lain jika titik pendekatan berada
pada titik ekstrim atau puncak sehingga nilai penyebut atau f 'x akan
menjadi nol dan hasil akhir perhitungan akan menjadi tak terhingga.
B. Saran
Algoritma Genetika yang telah dibahas merupakan bentuk dari Algoritma
Genetika standar. Pada dasarnya Algoritma ini memiliki enam komponen. Tetapi
banyak metode yang bervariasi yang diusulkan pada masing-masing tersebut.
Masing-masing komponen mempunyai kelebihan dan kekurangan. Suatu metode
yang bagus untuk menyelesaikan masalah A belum tentu bagus untuk masalah B
bahkan tidak bisa bisa menyelesaikan masalah C. Untuk itu diperlukan studi
lanjut untuk mengimplementasikan Algoritma Genetika ini ke dalam
permasalahan lain yang lebih kompleks.
SKRIPSI
PENGOPTIMALAN FUNGSI NONLINEAR TANPA KENDALA
MENGGUNAKAN ALGORITMA GENETIKA
Skripsi ini diajukan untuk memenuhi
salah satu persyaratan dalam mencapai derajat
Sarjana Pendidikan
Diajukan Oleh
MEY ANA PURBAYANTI
05015009
PROGRAM STUDI MATEMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS AHMAD DAHLAN
YOGYAKARTA
2009
xiii
A. Kesimpulan
Berdasarkan pembahasan yang telah disajikan pada bab sebelumnya, dapat
ditarik kesimpulan sebagai berikut :
1. Secara singkat kerja dari Algoritma Genetika adalah pertama membangkitkan
sebuah populasi yang berisi sejumlah kromosom, kromosom-kromosom
tersebut akan berevolusi secara berkelanjutan yang disebut generasi. Kedua,
mengkodekan kromosom yang telah dibangkitkan menjadi individu x dalam
interval yang diinginkan. Ketiga, menghitung nilai fitness dari individu x .
Keempat, melakukan seleksi untuk memperoleh individu yang baik untuk
menjdi orang tua. Kelima, memindahsilangkan dua buah kromosom untuk
mendapatkan sebuah kromosom yang lebih baik (pindah silang / crossover).
Tahap keenam adalah mutasi, yaitu untuk semua gen yang ada, jika bilangan
acak yang dibangkitkan kurang dari probabilitas mutasi yang ditentukan maka
ubah gen tersebut dengan kebalikannya (0 menjadi 1, dan 1 menjadi 0). Proses
akan berulang, sampai sejumlah generasi yang telah ditentukan.
2. Hasil implementasi dari kerja algoritma genetika adalah sebagai berikut :
Permasalahan :
Maksimumkan f x 4x3 3x2 6x 1
x 0
Parameter yang digunakan pada algoritma genetika :
Jumlah kromosom ( N ) yang digunakan adalah 100.
xiv
Jumlah bit atau gen yang digunakan adalah 25.
Generasi maksimum yang diinginkan adalah 500.
Probabilitas crossover c P adalah 0.85.
Probabilitas mutasi m P adalah 0.1.
Parameter-parameter tersebut dimasukan dalam program utama dari algoritma
genetika, dan diperoleh hasil sebagai berikut :
Fitness terbaik adalah 6.
Nilai x yang memaksimumkan fungsi adalah 1.002 .
Niali maksimum fungsi adalah 6.
3. Perbandingan dari metode Newton Raphson dengan Algoritma Genetika yang
jelas terlihat adalah :
Metode Newton Raphson
a. Hanya menggunakan satu titik sebagai nilai awal.
b. Perhitungan menggunakan kalkulus diferensial.
c. Jika nilai awal tidak dipilih dengan tepat, maka dapat terjadi bahwa
metodenya konvergen ke suatu minimum lokal atau sama sekali tidak
konvergen.
Algoritma Genetika
a. Menggunakan beberapa titik sebagai nilai awal.
b. Menggunakan perhitungan biasa.
xv
c. Dapat menghindari keadaan optimum lokal, karena menggunakan
beberapa titik sebagai nilai awal.
4. Kelemahan dari Algoritma Genetika adalah karena semua komponen
Algoritma Genetika bersifat random atau acak mengakibatkan solusi yang
dihasilkan berbeda-beda pada setiap kali running. Tetapi kejadian ini dapat
dihindari dengan memilih nilai-nilai parameter dengan tepat, maka Algoritma
Genetika dapat memberika solusi yang dapat diterima.
5. Kelemahan Metode Newton-Raphson adalah memiliki permasalahan dalam
implementasinya. Permasalahan terjadi antara lain jika titik pendekatan berada
pada titik ekstrim atau puncak sehingga nilai penyebut atau f 'x akan
menjadi nol dan hasil akhir perhitungan akan menjadi tak terhingga.
B. Saran
Algoritma Genetika yang telah dibahas merupakan bentuk dari Algoritma
Genetika standar. Pada dasarnya Algoritma ini memiliki enam komponen. Tetapi
banyak metode yang bervariasi yang diusulkan pada masing-masing tersebut.
Masing-masing komponen mempunyai kelebihan dan kekurangan. Suatu metode
yang bagus untuk menyelesaikan masalah A belum tentu bagus untuk masalah B
bahkan tidak bisa bisa menyelesaikan masalah C. Untuk itu diperlukan studi
lanjut untuk mengimplementasikan Algoritma Genetika ini ke dalam
permasalahan lain yang lebih kompleks.
FUNGSI ALGORITMA
ALGORITMA DAN PEMROGRAMAN 2
Oleh: Anis Cherid, M.T.I.
STRING DALAM BAHASA C
Dalam bahasa pemrograman C, string adalah array bertipe karakter (char). Untuk menampilkan string yang dikandung oleh sebuah array, karakter format yang yang dipergunakan adalah "%s". Ketika kita menginstruksikan komputer untuk menampilkan string, komputer akan memeriksa satu per satu elemen array dan menampilkannya ke layar monitor. Komputer akan berhenti memeriksa elemen array yang selanjutnya jika menemukan null character ('\0'). Perhatikan program di bawah ini:
#include <stdio.h>
void main(){
char nama[20];
nama[0]='B';
nama[1]='u';
nama[2]='d';
nama[3]='i';
nama[4]='m';
nama[5]='a';
nama[6]='n';
nama[7]='\0';
printf("%s\n",nama);
/* output : Budiman */
nama[4]='\0';
printf("%s\n",nama);
/* output : Budi ---- karena elemen 4 berisi null */
}
String juga bisa dideklarasikan dan sekaligus diinisialisasi dengan cara sebagai berikut:
char namaSaya[20]="Budiman";
char namaDia[]="Wati";
char *namaNya="Indah";
char namaKu[]={'B','u','d','i','m','a','n','\0'};
Berbeda dengan Bahasa Pascal, Bahasa C tidak mengijinkan diisinya sebuah nilai string secara langsung, sehingga statement berikut ini akan menimbulkan compile error:
namaKu[]="Budiman"; /* ERROR */
namaKu="Budiman"; /* JUGA ERROR */
Untuk mengisi string dengan sebuah nilai secara langsung, kita harus menggunakan fungsi strncpy (singkatan dari string-n-copy) atau fungsi sprintf (singkatan dari string-print-format). Untuk menggunakan fungsi strncpy dibutuhkan file header <string.h>. Berikut ini adalah bentuk pemanggilan kedua fungsi tersebut:
strncpy (string tujuan, string asal, jumlah karakter string asal yang akan disalin);
sprintf (string tujuan, "format string", var1, var2, var3, ...);
#include <stdio.h>
#include <string.h>
void main(){
char namaKu[256]="Budiman";
char namaSaya[256]="12345678901234567890";
int umurSaya=35;
strncpy(namaSaya,"Bukan Budiman",13);
printf("%s\n",namaSaya);
/* output : Bukan Budiman4567890
"Bukan Budiman" = 13 huruf + 1 karaker NULL.
Jika disalin sebanyak 13 huruf ke string namaSaya,
maka karakter NULL tidak dikopi ke dalam string namaSaya
*/
strncpy(namaSaya,"Adi",4);
printf("%s\n",namaSaya);
/* ouput : Adi
"Adi" = 3 huruf + 1 karakter NULL.
Jika dikopi sebanyak 4 huruf, maka karakter NULL
ikut terkopi ke dalam string namaSaya
*/
strncpy(namaSaya,namaKu,256);
/* cara paling baik menggunakan fungsi strncpy, yaitu
menuliskan jumlah karakter yang akan dikopi sebanyak
ukuran maksimum string tujuan.
*/
printf("%s\n",namaSaya);
/* output : Budiman */
sprintf(namaSaya, "%s adalah %s dan berumur %d tahun",
namaKu, namaKu, umurSaya);
printf(namaSaya);
/* output : Budiman adalah Budiman dan berumur 35 tahun
*/
}
Untuk mengisi variabel string dari keyboard, Bahasa C menyediakan fungsi fgets dan fflush. Kombinasi kedua fungsi ini akan menghasilkan efek yang sama dengan instruksi readln dalam Bahasa Pascal. Perhatikan cara penggunaannya dalam program di bawah ini:
/* Contoh penggunaan FGETS dan FFLUSH untuk membaca string
dari keyboard */
#include <stdio.h>
#include <string.h>
void main(){
char nama[11];
printf("Silakan masukkan nama anda:");
fgets(nama,11,stdin);
fflush(stdin);
printf("Selamat pagi, %s.\n",nama);
printf("%s mempunyai 2 e-mail pagi ini.",nama);
}
Dalam program di atas, jika nama yang diketikkan lebih dari 10 karakter, maka karakter ke-11 dan seterusnya akan diabaikan. Tetapi jika nama yang dimasukkan 9 karakter atau kurang, maka string akan diakhiri dengan NEWLINE-CHARACTER dan NULL-CHARACTER ("\n\0"). Dalam contoh program di atas, jika nama yang dimasukkan adalah "Sukmawati" (9 karakter), maka output yang dihasilkan adalah:
Selamat pagi, Sukmawati
.
Sukmawati
mempunyai 2 e-mail pagi ini.
Ini adalah masalah dari fungsi fgets yang harus ditangani oleh pemrogram. Untuk menangani masalah tersebut, program harus mampu memeriksa jika elemen array string sebelum NULL-CHARACTER adalah NEWLINE-CHARACTER, kemudian menggantinya "\n" tersebut dengan "\0". Perhatikan program di bawah ini, yang merupakan perbaikan dari program sebelumnya:
/* Perbaikan untuk mengatasi masalah NEWLINE-CHARACTER */
#include <stdio.h>
#include <string.h>
void main(){
char nama[11];
int i,max=10;
do {
printf("Silakan masukkan nama anda:");
fgets(nama,11,stdin);
fflush(stdin);
for (i=0;i<=max;i++){
if(nama[i]=='\n'){
nama[i]='\0';
break; /*Keluar dari for-loop*/
}
}
if (i>0){
break; /*Keluar dari while-loop*/
} else {
printf("Anda belum memasukkan nama...\n");
}
} while (i==0);
printf("Selamat pagi, %s.\n",nama);
printf("%s mempunyai 2 e-mail pagi ini.",nama);
}
Contoh program di atas terdiri dari sebuah do/while-loop dan di dalam do/while-loop tersebut terdapat for-loop. Struktur do/while-loop dalam program di atas berguna untuk memastikan bahwa operator sudah memasukkan namanya, meskipun hanya terdiri dari sebuah karakter. Sedangkan struktrur for-loop berguna untuk mengganti NEWLINE-CHARACTER dengan NULL-CHARACTER. Struktur perulangan untuk mengganti karakter tersebut dapat disederhanakan dengan menggunakan fungsi yang berguna untuk menentukan lokasi sebuah karakter di dalam sebuah string (fungsi strchr), sehingga:
for (i=0;i<=max;i++){
if(nama[i]=='\n'){
nama[i]='\0';
break; /*Keluar dari for-loop*/
}
}
dapat diubah menjadi:
if(strchr(nama,'\n')){
strchr(nama,'\n')[0]='\0';
}
Bahasa Pascal mengijinkan dilakukannya operasi penjumlahan string, misalnya namaLengkap:='Ahmad'+' '+'Dahlan'. Dalam Bahasa C, diperlukan fungsi strcat.
/* Contoh Menjumlahkan String dengan STRCAT */
#include<stdio.h>
#include<string.h>
void main(){
char namaLengkap[256];
char *namaDepan="Kyai";
char *namaTengah="Ahmad";
char *namaBelakang="Dahlan";
strcat(namaLengkap,namaDepan);
printf("%s\n",namaLengkap);
/*output: Kyai*/
strcat(namaLengkap," ");
strcat(namaLengkap,namaTengah);
printf("%s\n",namaLengkap);
/*output: Kyai Ahmad*/
strcat(namaLengkap," ");
printf("%s\n", strcat(namaLengkap,namaBelakang));
/*output: Kyai Ahmad Dahlan*/
}
Untuk mencari terdapat atau tidaknya sebuah string di dalam string lainnya, fungsi yang dipergunakan adalah strstr.
/* Contoh mencari string di dalam string dengan STRSTR */
#include<stdio.h>
#include<string.h>
void main(){
char namaLengkap[]="Kyai Ahmad Dahlan";
char namaDicari[]="Dahlan";
if (strstr(namaLengkap,namaDicari)){
printf("%s terdapat dalam %s",namaDicari,namaLengkap);
}
}
Program di atas akan menghasilkan output:
Dahlan terdapat dalam Kyai Ahmad Dahlan.
Di bawah ini disajikan program Pascal untuk memisahkan digit bilangan integer dengan tanda titik dan mengubah tanda desimal dari titik menjadi koma.
program format_bilangan_dengan_pemisah_angka;
uses wincrt;
function formatstrbil(i:string):string;
var
j:integer;
begin
j:=pos('.',i);
if j<>0 then begin
i[j]:=',';
j:=j-1;
end else
j := length(i);
while j>3 do begin
j := j - 3;
insert ('.', i, j+1);
end;
formatstrbil:=i;
end;
var
strbil:string;
bil:real;
posisiError:integer;
begin
posisiError := 0;
repeat
write('Silakan masukkan sebuah bilangan: ');
readln(strbil);
val(strbil, bil, posisiError);
if posisiError<>0 then
writeln('Yang anda masukkan bukan bilangan real');
until posisiError = 0;
writeln(formatstrbil(strbil));
end.
Hasil penerjemahan program di atas menjadi program Bahasa C dapat dilihat di bawah ini. Program berbahasa C ini sangat intensif menggunakan pointer dan menggunakan fungsi strtod untuk mengkonversi string menjadi bilangan bertipe double.
/* Format bilangan dengan pemisah angka */
#include <stdio.h>
#include <string.h>
#include <stdlib.h> /* untuk fungsi strtod */
void formatstrbil(char *i){
char *j, *k, temp[256];
int p, ptemp=0;
j = k = strchr(i,'.');
if (j>0){
p = strlen(i)-1;
while (p>j-i){
temp[ptemp++]=i[p];
p--;
}
temp[ptemp++]=',';
k = --j;
} else {
j = k = strchr(i,0) - 1;
}
while (j-i>=0){
temp[ptemp++]= j[0];
if ((k-j+1)%3==0 && k-j!=0 && j-i!=0){
temp[ptemp++]= '.';
}
j--;
}
ptemp--;
p=0;
while (ptemp>=0)
i[p++]=temp[ptemp--];
i[p]=0;
}
main(){
char strbil[256], *error;
double bil;
do {
printf("Silakan masukkan sebuah bilangan: ");
fgets(strbil, 256, stdin);
if (strchr(strbil, '\n')) strchr(strbil, '\n')[0]=0;
bil = strtod(strbil, &error);
if (*error!=0)
printf("Yang anda masukkan bukan bilangan double\n");
} while (*error!=0);
formatstrbil(strbil);
printf(strbil);
}
Berikut ini adalah program untuk menampilkan tulisan bergerak seperti dalam "news ticker". Di dalamnya terdapat algoritma untuk melakukan jeda (pause) selama durasi tertentu, dengan ketentuan bahwa 1 durasi sama dengan 1 timer-tick atau 1/18 detik.
/* Program News Ticker */
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <dos.h> /* dibutuhkan untuk tipe struct time dan fungsi
gettime() */
main(){
char a[256];
int i, mulai, durasi;
struct time tmulai;
clrscr();
printf("Silakan masukkan teks untuk ditampilkan:");
fgets(a, 256, stdin);
if (strchr(a, '\n')) strchr(a, '\n')[0]=0;
for (i=80-strlen(a); i>0; i--) strcat(a," ");
clrscr();
do {
a[255]=a[0];
i=0;
while (a[i]!=0){
a[i]=a[i+1];
i++;
}
a[i-1]=a[255];
a[255]=0;
gotoxy(1,10);
printf("%80s",a);
gettime(&tmulai);
durasi=3; /* 3 timer-tick */
do {
mulai = tmulai.ti_hund;
do {
gettime(&tmulai);
} while (mulai==tmulai.ti_hund);
} while (--durasi);
} while (!kbhit());
}
Berikut ini disajikan program untuk menampilkan penyebutan bilangan. Program ini secara intensif menggunakan array di dalam algoritmanya, sehingga terlihat rumit. Di dalamnya terdapat teknik agar sebuah fungsi bisa mengembalikan nilai dalam bentuk string.
/* Program mengubah bilangan integer menjadi string penyebutannya */
#include <stdio.h>
#include <math.h>
char *penyebutan(long double);
void main(){
long double x=112456709123450.0;
printf(penyebutan(x));
}
char *penyebutan(long double b){
char *unit[]={"trilyun","milyar","juta","ribu",""};
char *bilangan[]={"se","dua","tiga","empat","lima","enam","tujuh",
"delapan","sembilan","sepuluh","sebelas","duabelas","tigabelas",
"empatbelas","limabelas","enambelas","tujuhbelas","delapanbelas",
"sembilanbelas"};
static char str[256];
int a[15],i, belas;
str[0]=0;
for (i=0;i<15;i++){
a[i]=b/pow(10,14-i);
b=b-a[i]*pow(10,14-i);
}
belas=0;
for (i=0;i<15;i++){
if (a[i]!=0){
if (a[i]==1&&i%3==1){
strcat(str, bilangan[a[i]*10+a[i+1]-1]);
belas=1;
} else if (a[i]==1&&(i%3!=0&&i!=9)&&i%3!=1){
strcat(str, "satu");
} else {
strcat(str, bilangan[a[i]-1]);
}
if(i%3==0){
strcat (str, "ratus ");
} else if(i%3==1&&!belas){
strcat(str, "puluh ");
}
}
i+=1*belas;
if (i%3==2&&(a[i-2]!=0||a[i-1]!=0||a[i]!=0)){
strcat(str, " ");
strcat(str, unit[i/3]);
strcat(str, " ");
}
i+=1*belas;
belas=0;
}
return str;
}
REFERENSI
[BOR97] Borland. 1997. Turbo C++ 5.0 Help. Borland Inc.
Langganan:
Postingan (Atom)