PENGENALAN ANGKA DENGAN MENGGUNAKAN ALGORITMA GENETIK
Frengki Agus
[email protected] Pembimbing I : Linda Salma, S.Si., M.T. Pembimbing II : Khusnul Novianingsih,M.Si
Fakultas Teknik dan Ilmu Komputer, Jurusan Teknik Informatika Universitas Komputer Indonesia Abstrak Untuk dapat mengenali angka dengan menggunakan algoritma genetik ada beberapa hal yang harus dilakukan yaitu : memilih gambar angka dan memasukkan parameter algoritma genetik seperti Pc, Pm, Popsize dan Maxgen, lalu merepresentasi kromosom gambar angka ke dalam bentuk bit biner. Setelah itu dilakukan inisialisasi populasi, mencari nilai fitness, melakukan seleksi menggunakan metode roullette wheel, crossover dengan metode single point crossover, dan mutasi dengan mutasi biner. Setelah melakukan proses diatas maka akan dilakukan pemilihan nilai fitness terbaik yang nantinya akan menentukan apakah angka tersebut dikenali atau tidak. Berdasarkan hasil pengujian pada sistem yang telah di bangun menunjukkan bahwa sistem mampu melakukan pengenalan angka dengan tingkat akurasi sebesar 60 %. Untuk menampilkan hasil akhir yang akurat diperlukan kombinasi parameter algoritma genetik yang bervariasi. Semakin besar nilai parameter (Pc, Popsize dan Maxgen ) maka hasilnya akan semakin akurat. Sebaliknya nilai Pm tidak perlu terlalu besar karena akan membuat hasil akhir kurang akurat. Kata Kunci : Algoritma Genetik, Pola Angka, Parameter. Abstract To be able to recognize number by genetic algorithm there are some matters which must be done that is : choosing number picture and isn’t it genetic algorithms parameter like Pc, Pm, Popsize and Maxgen, last chromosome representation draw number to in the form of binary byte, is afterwards population initialitation, searching value of fitness, select to use method of roullette wheel, crossover with method of single point crossover, and mutation with binary mutation. Having taken steps process above hence will be election of value of fitness best which later determine do the number recognized or do not. Based on examination result at system which have been woke up to indicate that system can do reconition of number with accuration level equal to 60 %. To present end result which is accurate to be needed by combination of genetic algorithms parameter which vary. Ad for parameter value (Pc, Popsize, and Maxgen) hence the result of will accurate progressivelly.On the contrary assess Pm needn’t too big because will make less accurate end result. Keywords : Genetic Algorithms, Number Pattern, Parameter.
1.
kecerdasan buatan ( artificial intelligent ) yang dapat membuat komputer menjadi lebih cerdas. Selain itu, pengenalan pola khususnya yang berupa text nantinya dapat dikembangkan dengan suara atau yang lebih dikenal dengan istilah text to speech. Untuk menyelesaikan permasalahan pengenalan pola bisa dilakukan dengan berbagai algoritma, salah satunya dengan menggunakan algoritma genetik. Algoritma genetik merupakan algoritma pencarian yang
Pendahuluan
Dalam dunia teknologi informasi pengenalan pola / recognition pattern memiliki berbagai manfaat. Secara umum, pengenalan pola digunakan untuk mengenali objek dalam citra. Biasanya pengenalan pola digunakan untuk bidang security seperti pembacaan sidik jari, wajah ataupun retina mata. Selain digunakan dalam bidang security, pengenalan pola juga dapat digunakan dalam bidang
1
bekerja berdasarkan mekanisme dari seleksi alam dan genetik. Sehingga nantinya diharapkan algoritma genetik melakukan pengenalan angka meskipun angka tersebut mengalami gangguan seperti bentuk angka yang tidak lengkap. Ada beberapa hal yang harus diperhatikan pada penggunaan algoritma genetik untuk pengenalan angka yaitu memilih representasi masalah ke dalam bentuk string , menentukan operator genetik yang diperlukan, menentukan fungsi fitness, serta menentukan probabilitas yang akan mengatur operator genetik. Sedangkan operator genetik yang dipakai ada 3 yaitu seleksi, crossover, dan mutasi. Parameter yang digunakan yaitu probabilitas crossover , probabilitas mutasi.
4.
Kerjakan langkah-langkah berikut hingga generasi mencapai maksimum generasi a. Generasi = generasi +1 (tambah generasi) b. Seleksi populasi tersebut untuk mendapatkan kandidat induk, P’(generasi) c. Lakukan crossover pada P’(generasi) d. Lakukan mutasi pada P’(generasi) e. Lakukan evaluasi fitness setiap individu pada P’(generasi) f. Bentuk populasi baru : P(generasi) = {P(generasi – 1) yang survive, P’(generasi)}
2. Landasan Teori Teori- teori yang digunakan dalam penelitian ini meliputi pencarian Heuristik dimana metode yang digunakan adalah Algoritma Genetik.
2.1 Definisi Algoritma Genetik Algoritma Genetik merupakan dasar teknik pencarian stokastik yang berdasarkan pada mekanisme yang meniru dari seleksi alam dan evolusi. Istilah yang digunakan dalam algoritma Genetik adalah meminjam dari genetik alam seperti populasi, kromosom dan gen. Algoritma Genetik berbeda dari teknik pencarian konvensional, dimulai dengan kumpulan inisial dari solusi acak yang disebut sebagai populasi.
Gambar 1 Diagram Alir Algoritma Genetik Sederhana
3.
Rancangan Sistem Adapun langkah-langkah penyelesaian pengenalan pengenalan angka dengan algoritma genetik adalah sebagai berikut :
Setiap individu dalam populasi disebut kromosom, yang mewakili suatu solusi dari masalah. Suatu kromosom merupakan sebuah string dari simbol. Kromosom-kromosom tersebut akan melakukan suatu regenerasi melalui ulangan berturut-turut. Dan selama regenerasi, kromosom akan dievaluasi dengan menggunakan suatu ukuran yang disebut fitness value (nilai kesesuaian). Semakin besar nilai fitness suatu kromosom, maka semakin besar kemungkinannya ikut dalam regenerasi. 2.2
3.1
Penetapan Parameter / Input Hal pertama yang dilakukan terhadap algoritma genetik adalah dengan menentukan parameter-parameter yang terbaik. Yang disebut parameter disini adalah parameter kontrol algoritma genetik, yaitu : • ukuran populasi (popsize), yaitu : banyaknya kromosom dalam satu populasi. • probabilitas crossover (Pc), yaitu : peluang yang menunjukkan rasio dari anak yang dihasilkan dalam setiap generasi dengan ukuran populasi. • probabilitas mutasi (Pm), yaitu : peluang yang menunjukkan persentase jumlah total gen yang akan mengalami mutasi. Nilai parameter ini ditentukan berdasarkan permasalahan yang akan dipecahkan. Selain memasukkan nilai parameter di atas, pada program ini juga diharuskan untuk
Langkah Umum Algoritma Genetik
Secara sederhana algoritma genetik terdiri dari langkah-langkah : 1. Generasi = 0 (generasi awal) 2. Inisialisasi populasi awal, P(generasi) secara acak 3. Evaluasi nilai fitness pada setiap individu dalam P(generasi)
2
mutasi. Kedua operator ini merupakan hasil modifikasi dari operator genetik dasar karena perlu disesuaikan dengan masalah yang dihadapi. Ada 3 operator genetik yang digunakan dalam perangkat lunak yaitu : a. Seleksi Seleksi yang digunakan adalah metode roullette wheel (piringan rolet). Seleksi ini bertujuan untuk memberikan kesempatan seleksi yang lebih besar bagi anggota populasi yang memiliki fitness tinggi untuk melakukan seleksi. b. Crossover Crossover yang digunakan adalah Single Point Crossover. c. Mutasi Mutasi yang digunakan adalah mutasi biner yang menghasilkan perubahan acak secara spontan pada kromosom
memasukkan data angka untuk diolah lebih lanjut. 3.2
Representasi Kromosom Masalah yang ada (khususnya angka) akan direpresentasikan ke dalam gen-gen. Gen merupakan elemen-elemen secara acak yang membentuk kromosom. Satu gen biasanya mewakili 1 variabel. Gen akan direpresentasikan ke dalam bentuk string yang dapat diimplementasikan untuk operator genetik. Sebagai contoh, agar data dapat digunakan sebagai input, data ini direpresentasikan ke dalam bentuk biner. Data gambar ini akan diolah menjadi representasi biner, dengan mengambil nilai warna titik tertentu dari bidang gambar. Titik yang berwarna hitam bernilai 1 (satu), sedangkan titik yang kosong bernilai 0 (nol). Jika titik diambil sejumlah 10 x 15 dengan pertimbangan jumlah ini cukup besar agar hasil ekstrasi dari huruf berbeda dapat dibedakan, dan juga tidak terlalu besar untuk diimplementasikan ke dalam algoritma genetik. Rangkaian nilai biner yang akan menjadi bentuk representasi input untuk algoritma genetik. 3.3 Inisialisasi Populasi Dalam hal ini akan dibuat sebuah populasi dari kumpulan kromosom. Alternatif yang digunakan untuk menentukan populasi awal adalah dengan menentukannya secara acak.
3.6
Menentukan keluaran Pada pembangunan perangkat lunak ini diharapkan perangkat lunak berbasis algoritma genetik tersebut dapat mengenali angka yang mengalami beragam variasi. Dan setelah dilakukan proses scan terhadap angka tersebut akan dihasilkan keluaran berupa angka yang dimasukkan. Selain itu, perangkat lunak ini juga akan menampilkan tabel hasil perhitungan, waktu perhitungan serta grafik fitness.
3.4
Fungsi Fitness Suatu angka dapat dikenali jika angka tersebut dapat cocok dengan suatu model angka. Fungsi fitness dari setiap kromosom dapat diperoleh dengan dua tahap, yaitu : 1. Menentukan fungsi tujuan. Fungsi tujuan dari masalah pengenalan angka adalah maksimasi. 2. Menentukan fungsi fitness. F=
∑
bit yang sama antara kromosom
angka yang kromosom
diinputkan dengan angka yang benar.
3.5
Penentuan operator genetik yang dipergunakan Pada proses seleksi, yang diperlukan hanyalah nilai fitness dari suatu string, semakin besar pula kemungkinan dari string tersebut untuk terpilih menjadi calon anggota bagi generasi berikutnya. Sedangkan pada proses rekombinasi, dipergunakan 2 buah operator genetik yaitu operator crossover dan
3
4.1 HASIL UJI COBA Pengukuran waktu komputasi dilakukan dengan berbagai parameter dan beberapa kali percobaan karena diambil waktu komputasi terbaik. Tabel 1 Hasil Uji Coba Angk
Generasi
a
5
Pc ; Pm
Popsize
(%)
Generasi
Fitness
Terbaik
0
350
90 ; 25
95
108
109
1
100
30 ; 5
25
1
131
00:00:00:651
2
20
20 ; 10
40
1
129
00:00:00:240
4
50
40 ; 30
30
1
107
00:00:00:371
4
125
25 ; 35
35
1
101
00:00:00:922
5
225
80 ; 20
80
1
110
00:00:05:548
5
90
15 ; 20
5
1
114
00:00:00:100
6
75
45 ; 15
55
1
112
00:00:01:021
9
380
85 ; 10
20
1
119
00:00:02:243
Kesimpulan
Berdasarkan tujuan penulisan tugas akhir ini ,maka dapat disimpulkan bahwa : 1. Algoritma genetik dapat digunakan untuk mengenali angka yang dibandingkan dengan model angka. 2. Berdasarkan hasil pengujian, algoritma genetik mampu mengenali angka dengan hasil yang cukup akurat dengan tingkat keakuratan sebesar 60 % . Beberapa hal yang dapat mempengaruhi dalam menyelesaikan pengenalan angka dengan menggunakan algoritma genetik adalah sebagai berikut : a. Pengenalan angka dengan menggunakan algoritma genetik untuk mengenali angka sangat dipengaruhi oleh parameterparameter genetik seperti : Pc, Pm, Popsize dan Maxgen. Berdasarkan hasil pengujian , semakin besar nilai Pc, Popsize dan Maxgen maka tingkat kegagalan program dalam mengenali angka semakin kecil. Sedangkan untuk Pm semakin besar nilainya maka tingkat kegagalan program dalam mengenali angka semakin besar.
Gambar 2 Diagram Alir Prosedural Algoritma Genetik
4. Implementasi Bab ini membahas mengenai implementasi dari algoritma genetik dalam mengenali angka . Setelah semua rancangan selesai dibuat dan hal-hal yang diperlukan dalam pembuatan program sudah diperoleh, maka dibuatlah sebuah program aplikasi algoritma genetik untuk mengenali angka dengan menggunakan bahasa pemrograman Delphi 7.0, bekerja sesuai dengan adanya parameter. Kemudian program bekerja dengan cara mengimplementasikan sesuai dengan hasil output yang diinginkan.
DAFTAR PUSTAKA
[1] Desiani, Anita & Arhami, Muhammad; Konsep Kecerdasan Buatan; Penerbit Andi; Yogyakarta; 2006. [2] Kusumadewi, Sri & Purnamo, Hari; Penyelesaian Masalah Optimasi dengan Teknik-teknik Heuristik; Graha Ilmu; 2005.
4
Waktu Perhitungan 00:00:09:724
[3] Martina, Inge; 36 Jam Belajar Komputer Pemrograman Visual Borland Delphi 7; Elex Media Komputindo; Jakarta ; 2004. [4] Pressman , Roger S, Ph.D; Rekayasa Perangkat Lunak ; Penerbit AndiMcGraw Hill;Yogyakarta; 2002.
[5] Saputro, Nico; Pengenalan Huruf Dengan Memakai Algoritma Genetik; http://home.unpar.ac.id/~integral/Volume %208/Integral%208%20No.%202/Pengen alan%20Huruf%20dengan%20Algoritma. PDF.
5
