PENERAPAN ALGORITME GENETIKA DALAM SISTEM PERMAINAN TEBAK ANGKA
HERMAN GUSTI ANUGRAH
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
PENERAPAN ALGORITME GENETIKA DALAM SISTEM PERMAINAN TEBAK ANGKA
HERMAN GUSTI ANUGRAH
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Program Studi Ilmu Komputer
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
ABSTRACT HERMAN GUSTI ANUGRAH. Application of Genetic Algorithms in the Number Guessing Game System. Supervised by YENI HERDIYENI. The number guessing game is a modified game of mastermind created by Mordecai Meirowitz in 1970. The goal of the game is to guess a hidden sequence of numbers stored by others (human or computer) based on values obtained at each guess iteration. In this study, the game is applied into the system by using genetic algorithms, a method that has been successfully utilized to implement the mastermind game on the computer and get an effective solution for the game. Genetic algorithms work through a process of natural selection or commonly known as the evolutionary process, which will continue running until the system finds the optimal 4-digit series of numbers. The system is designed in order to guess those hidden numbers with minimal iterations using c++ programming language. The output of the program shows that the performance is determined by the first guess iteration. Keywords: genetic algorithms, number guessing game.
Penguji: 1 Ir. Julio Adisantoso, M.Kom. 2 Annisa, S.Kom., M.Kom.
Judul Skripsi : Penerapan Algoritme Genetika dalam Sistem Permainan Tebak Angka Nama : Herman Gusti Anugrah NRP : G64086036
Menyetujui:
Pembimbing
Dr. Yeni Herdiyeni, S.Si., M.Kom. NIP. 19750923 200012 2 001
Mengetahui: Ketua Departemen Ilmu Komputer
Dr. Ir. Agus Buono, M.Si., M.Kom. NIP. 19660721 99302 1 001
Tanggal Lulus:
RIWAYAT HIDUP Penulis dilahirkan di Bogor, pada tanggal 13 Oktober 1986, sebagai anak kedua dari tiga bersaudara dari pasangan Bapak Tonny Wahyudi dan Ibu Dwi Wiworo Mulyati. Penulis menyelesaikan pendidikan sekolah menengah umum di SMAN 3 Bogor pada tahun 2004 dan menyelesaikan pendidikan Program Studi Diploma 3 Informatika, Institut Pertanian Bogor pada tahun 2007. Pada tahun 2008, penulis diterima bekerja di salah satu perusahaan swasta di Bogor dan melanjutkan pendidikan ke jenjang Strata I Institut Pertanian Bogor jurusan Ilmu Komputer pada tahun yang sama.
PRAKATA Puji dan syukur penulis panjatkan kepada Allah Subhanahu wa ta’ala atas segala curahan rahmat dan karunia-Nya sehingga tulisan akhir ini berhasil diselesaikan. Selawat serta salam tak lupa selalu tercurahkan kepada baginda besar Nabi Muhammad shalallahu ‘alaihi wa salam, keluarganya, para sahabat, dan para pengikutnya hingga akhir zaman. Terima kasih penulis ucapkan kepada pihak yang telah membantu dalam penyelesaian tulisan akhir ini, antara lain: Kedua orang tua penulis, kakak dan adik penulis, serta seluruh keluarga atas doa, cinta, restu, kasih sayang, dukungan, nasihat, dan perhatian yang diberikan kepada penulis. Ibu Dr. Yeni Herdiyeni, S.Si., M.Kom. selaku dosen pembimbing. Bapak Ir. Julio Adisantoso, M.Kom. dan Ibu Annisa, S.Kom., M.Kom. selaku dosen penguji. Bapak Mushthofa S.Kom., M.Sc. yang telah bersedia meluangkan waktunya untuk berbagi ide tentang tulisan akhir ini. Teman-teman Alih Jenis Ilkom angkatan 3, atas bantuan, waktu, dan pengalaman yang tak terlupakan. Semoga tulisan akhir ini dapat bermanfaat, amin.
Bogor, Juli 2012
Herman Gusti Anugrah
DAFTAR ISI Halaman DAFTAR GAMBAR ............................................................................................................................. vi PENDAHULUAN Latar Belakang .................................................................................................................................. 1 Tujuan ............................................................................................................................................... 1 Ruang Lingkup .................................................................................................................................. 1 Manfaat ............................................................................................................................................. 1 TINJAUAN PUSTAKA Permainan Tebak Angka ................................................................................................................... 1 Algoritme Genetika ........................................................................................................................... 2 Proses Algoritme Genetika................................................................................................................ 3 METODE PENELITIAN Representasi ...................................................................................................................................... 4 Deret Angka Target ........................................................................................................................... 4 Deret Angka Tebakan ....................................................................................................................... 4 Evaluasi Fitness ................................................................................................................................ 4 Seleksi Individu ................................................................................................................................. 4 Mutasi ............................................................................................................................................... 5 Pindah-Silang .................................................................................................................................... 5 Rule ................................................................................................................................................... 5 Kondisi Stop ...................................................................................................................................... 5 Evaluasi Sistem ................................................................................................................................. 5 HASIL DAN PEMBAHASAN Deret Angka Target ........................................................................................................................... 6 Deret Angka Tebakan ....................................................................................................................... 6 Evaluasi Fitness ................................................................................................................................ 6 Mutasi ............................................................................................................................................... 7 Pindah-Silang .................................................................................................................................... 7 Evaluasi Sistem ................................................................................................................................. 7 KESIMPULAN DAN SARAN Kesimpulan ....................................................................................................................................... 7 Saran ................................................................................................................................................. 7 DAFTAR PUSTAKA ............................................................................................................................. 7 LAMPIRAN ........................................................................................................................................... 8
v
DAFTAR GAMBAR Halaman 1 2 3 4 5
Permainan tebak angka ....................................................................................................................... 1 Siklus algoritme genetika (Goldberg 1989) ........................................................................................ 3 Alur metode penelitian ........................................................................................................................ 3 Probabilitas nilai fitness ...................................................................................................................... 4 Grafik uji pengaruh nilai fitness .......................................................................................................... 6
vi
1
PENDAHULUAN Latar Belakang Permainan komputer sangat banyak ragamnya dan terus berkembang. Salah satu jenisnya adalah permainan yang bersifat kompetisi antara komputer dan manusia. Hal ini tentu membutuhkan suatu penelitian agar komputer dapat memiliki kecerdasan yang menyerupai manusia dan menyelesaikan masalah yang ada pada permainan layaknya manusia. Penelitian ini membahas proses pembangunan sebuah sistem permainan tebak angka otomatis. Permainan tebak angka adalah suatu permainan menebak deret angka tersembunyi yang disimpan oleh pihak lain (manusia ataupun komputer) berdasarkan nilainilai yang didapatkan di setiap iterasi penebakan. Permainan ini merupakan hasil modifikasi dari permainan yang telah ada sebelumnya, yaitu permainan mastermind yang diciptakan oleh Mordecai Meirowitz pada tahun 1970 (Marcel 2009). Pada awal permainan tebak angka, pihak lawan akan menyimpan satu deret angka berjumlah n digit, lalu pemain akan mencoba menebak deret angka tersebut, mendapatkan hasilnya, membangkitkan deret angka untuk penebakan selanjutnya berdasarkan hasil yang didapat, dan melakukan penebakan kembali hingga semua digit angka tersembunyi tersebut berhasil ditebak (tebakangka.com). Pada penelitian sebelumnya, telah dibahas penerapan algoritme genetika pada permainan mastermind dan menghasilkan sebuah kesimpulan bahwa algoritme genetika hanya membutuhkan sedikit iterasi penebakan untuk mendapatkan solusi yang tepat pada permainan tersebut (Berghman et al. 2009). Oleh karena itu, pada penelitian ini, akan dilakukan percobaan untuk menerapkan algoritme genetika pada permainan tebak angka yang memiliki jenis dan aturan yang menyerupai permainan mastermind. Setiap digit dari deret angka akan dipandang sebagai suatu gen pada algoritme genetika dan selanjutnya diproses hingga mendapatkan hasil yang diinginkan. Tujuan Tujuan dari penelitian ini adalah menerapkan algoritme genetika di dalam sistem permainan tebak angka. Ruang Lingkup Ruang lingkup penelitian ini meliputi:
Jumlah digit angka yang digunakan pada penelitian ini adalah empat digit. Faktor keberhasilan diukur dari jumlah iterasi penebakan yang seminimal mungkin, bukan dari kecepatan proses penebakannya. Manfaat Hasil dari penelitian ini diharapkan dapat berguna untuk mengukur kinerja algoritme genetika di dalam permainan tebak angka dan juga mengembangkan fitur dari permainan tebak angka, yaitu fitur penebakan dengan posisi penebak angka adalah komputer (sistem).
TINJAUAN PUSTAKA Permainan Tebak Angka Permainan ini dilakukan antara dua pihak, yaitu pihak yang menyimpan angka target (codemaker) dan pihak yang melakukan proses penebakan (codebreaker). Ilustrasi permainan dapat dilihat pada Gambar 1. Output proses penebakan
Submit angka tebakan Penebak (codebreaker)
Penyimpan angka (codemaker)
Gambar 1 Permainan tebak angka. Di dalam prosesnya, terdapat beberapa aturan yang berlaku, yaitu: Deret angka n-digit (n = 1, 2,…, 10) yang disimpan oleh pihak lawan terdiri atas D = (d1, d2,…, dn), d = 0, 1,…, 9. Setiap digit angka dari deret tersebut tidak boleh ada yang berulang/sama antara satu dengan lainnya. Jadi, jumlah kemungkinan deret angka target (worst case jumlah penebakan) adalah permutasi 4 dari 10 angka: 10!
P(10,4) = (10-4)! =
10! 6!
= 7 x 8 x 9 x 10
= 5040 kemungkinan Satu kali pencocokan deret angka tebakan dengan deret angka target dihitung sebagai satu iterasi penebakan. Hasil dari setiap iterasi penebakan direpresentasikan melalui dua buah variable yang juga berfungsi untuk menentukan besarnya nilai fitness bagi deret angka tebakan yang ada. Variable tersebut adalah:
2
1 c (correct): Variable ini akan bertambah pada hasil jika salah satu digit pada deret angka tebakan sama dengan yang ada pada deret angka target dan terletak pada posisi yang sama pula.
didapatkan suatu susunan kromosom yang terbaik, yang merepresentasikan kemungkinan solusi dari persoalan yang ada (Melanie 1996).
2 m (misplace): Variable ini akan bertambah pada hasil jika salah satu digit pada deret angka tebakan sama dengan yang ada pada deret angka target, tetapi terletak pada posisi yang berbeda (Tabel 1).
Gen: sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu kesatuan gen yang dinamakan kromosom. Dalam algoritme genetika, gen ini bisa berupa nilai biner, float, integer, karakter, maupun kombinatorial.
Contoh: Target 5678 Tebakan 5689
Alel: nilai dari gen. Kromosom: gabungan membentuk nilai tertentu.
Tabel 1 Contoh verifikasi deret (n = 4) Angka tebakan 5 6 8 9
Digit posisi Tebakan Target 1 1 2 2 3 4 4 Total hasil
Beberapa definisi penting algoritme genetika, yaitu:
Hasil c c m 2c 1m
Permainan akan berakhir ketika hasil yang diharapkan telah didapat, yaitu nc 0m, yang berarti n angka yang ada pada deret tebakan tersedia dan terletak pada digit yang sama dengan deret angka target. Algoritme Genetika Algoritme genetika ditemukan oleh John Holland pada tahun 1960-an. Pada tahun yang sama, algoritme tersebut dikembangkan bersama dengan murid dan rekannya hingga tahun 1970-an. Berbeda dengan strategi evolusi dan pemrograman evolusioner, tujuan awal dari pengembangan algoritme tersebut sebenarnya bukan untuk menyelesaikan masalah tertentu, tetapi lebih kepada mempelajari fenomena proses adaptasi yang terjadi di alam dan mencoba mencari cara untuk menerapkannya pada sistem komputer. Seiring dengan banyaknya interaksi dari para peneliti tentang metode dan pendekatan evolusioner, istilah “algoritme genetika” pun menjadi umum digunakan. Algoritme genetika memanfaatkan proses seleksi alamiah atau yang biasa dikenal dengan proses evolusi. Proses ini melibatkan perubahan gen pada suatu individu melalui proses perkembang-biakan yang bertujuan menyesuaikan diri dengan lingkungan hidupnya. Proses evolusi yang terjadi pada gengen tersebut akan terus berjalan hingga
menyangkut
gen-gen
yang
Individu: menyatakan satu nilai atau keadaan yang menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat. Populasi: merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi. Generasi: menyatakan satu siklus proses evolusi atau satu iterasi di dalam algoritme genetika. Nilai fitness: nilai yang menyatakan baik tidaknya suatu solusi (individu). Seleksi: proses yang digunakan untuk memilih individu-individu yang akan terlibat dalam proses pindah-silang dan mutasi. Seleksi dengan mesin Roulette: metode ini merupakan metode seleksi yang paling sederhana. Cara kerjanya sebagai berikut: 1 Hitung nilai individu.
fitness
masing-masing
2 Hitung total nilai fitness semua individu. 3 Hitung probabilitas dari tiap individu. 4 Dari probabilitas tersebut, hitung jatah masing-masing individu pada selang angka 1 – 100. 5 Bangkitkan bilangan acak antara 1 – 100. 6 Dari bilangan acak yang dihasilkan, tentukan individu mana yang terpilih dalam proses seleksi. Mutasi: operator ini berperan untuk menggantikan gen yang hilang dari populasi akibat proses seleksi yang memungkinkan
3
munculnya gen yang tidak muncul pada inisialisasi populasi.
Populasi awal
Random Mutation: mengganti gen yang akan dimutasi dengan nilai acak. Shift Mutation: menggeser nilai gen yang akan dimutasi sebesar nilai tertentu (ε).
Populasi baru
Evaluasi fitness
Reproduksi: mutasi dan pindah-silang
Seleksi indvidu
Pindah-silang: proses mengombinasikan dua individu untuk memperoleh individuindividu baru yang diharapkan mempunyai nilai fitness yang lebih baik. Pindah-silang Satu Titik: posisi pindahsilang k (k = 1, 2, …, N-1) dengan N (panjang kromosom) diseleksi secara acak. Variable-variable ditukar antarkromosom pada titik tersebut untuk menghasilkan anak. Pindah-silang Banyak Titik: m posisi penyilangan ki (k = 1, 2, …, N-1, i = 1, 2, …, m) dengan N (panjang kromosom) diseleksi secara acak dan tidak diperbolehkan ada posisi yang sama, serta diurutkan naik (Satriyanto 2009).
Gambar 2 Siklus algoritme genetika (Goldberg 1989).
METODE PENELITIAN Alur penelitian untuk mencari solusi efisien pada permainan tebak angka dapat dilihat pada Gambar 3.
Proses Algoritme Genetika Setelah diberikan suatu masalah yang jelas dan juga representasi string sebagai kandidat dari solusi yang dicari, algoritme genetika yang paling sederhana bekerja dengan cara berikut (Gambar 2): 1 Populasi baru akan dibangkitkan secara acak, yang di dalamnya terdiri atas n l-bit buah kromosom yang merupakan kandidat solusi dari problem yang ada. 2 Hitung nilai fitness dari setiap kromosom yang ada di dalam populasi dengan menggunakan fungsi fitness yang telah ditentukan.
Pembangkitan deret angka target oleh server
Pembangkitan deret angka tebakan secara acak oleh client (komputer)
Algoritme genetika Seleksi individu
Reproduksi: mutasi dan pindah-silang
3 Pilih beberapa pasang kromosom untuk dijadikan induk berdasarkan nilai fitnessnya. 4 Lakukan proses pindah-silang dan mutasi pada kromosom induk tersebut hingga populasi baru yang berpotensi memiliki nilai fitness lebih tinggi tercipta. 5 Gantikan populasi yang ada dengan populasi yang baru terbentuk tadi. Lakukan kembali penghitungan nilai fitness dari setiap kromosom dengan menggunakan fungsi fitness yang telah ditentukan (langkah no.2) hingga solusi optimal berhasil ditemukan (Melanie 1996).
Deret angka tebakan baru
Target belum ditemukan Evaluasi fitness
Target ditemukan Evaluasi sistem
Gambar 3 Alur metode penelitian.
4
Fungsi fitness xc + ym
Representasi Sebelum proses pencarian solusi dilakukan, kondisi yang ada pada permainan harus terlebih dahulu direpresentasikan ke dalam algoritme genetika. Hasil representasinya adalah: Setiap digit angka yang ada pada deret angka tebakan dan deret angka target dianggap sebagai sebuah gen yang bertipe integer. Contoh: 1234.
x: Jumlah variable c (x = 0, 1, 2, 3, 4) y: Jumlah variable m (y = 0, 1, 2, 3, 4) Setiap variable akan diberi bobot masingmasing untuk mendapatkan nilai real-nya. Jika bobot c = 10, bobot m = 5, dan hasil penebakan adalah 2c 1m, nilai fitness-nya: x = 2; y = 1; Nilai fitness = 2(10) + 1(5) = 20 + 5 = 25
Kumpulan gen tersebut akan membentuk suatu kromosom, yaitu kumpulan deret angka tebakan yang akan dimanipulasi sebelum dicocokkan dengan deret angka target.
Jika nilai fitness belum mencapai jumlah 40 (4c 0m), yang berarti target belum berhasil ditemukan, proses algoritme genetika pun dilakukan berdasarkan hasil yang didapat dari iterasi penebakan sebelumnya.
Proses manipulasi sejumlah kromosom akan menghasilkan sebuah individu, yaitu deret angka tebakan yang siap dicocokkan dengan deret angka target.
Seleksi Individu
Setiap individu yang tercipta akan dianggap sebagai satu generasi, yang berarti juga satu iterasi penebakan. Deret Angka Target Berdasarkan Gambar 3, langkah pertama yang harus dilakukan dalam penelitian ini adalah pembangkitan deret angka target yang akan menjadi acuan berhasil atau tidaknya sebuah penebakan yang dihasilkan dari algoritme genetika. Deret angka yang terdiri dari empat digit angka dan mengacu pada aturan permainan tersebut akan disimpan oleh codemaker dan nantinya akan dicocokkan dengan deret angka tebakan dari codebreaker. Deret Angka Tebakan Proses penebakan pun dilakukan. Pada iterasi pertama, komputer selaku codebreaker akan membangkitkan deret angka tebakan secara acak. Hal ini dilakukan karena tidak tersedianya informasi apapun yang bisa membedakan besar/kecilnya nilai fitness antara sekumpulan deret angka yang mungkin dibangkitkan. Proses algoritme genetika itu sendiri akan mulai dijalankan pada iterasi penebakan kedua dan seterusnya. Evaluasi Fitness Deret angka tebakan yang dibangkitkan secara acak tersebut dicocokkan dengan deret angka target yang disimpan oleh codemaker. Output yang dihasilkan direpresentasikan melalui variable c (correct) dan m (misplace).
Tahap selanjutnya pada algoritme genetika adalah seleksi individu. Proses tersebut dilakukan dengan cara memilih sejumlah deret angka yang ada di dalam variable history, yang didapatkan dari iterasi penebakan sebelumnya berdasarkan besar/kecilnya nilai fitness. Metode seleksi yang digunakan pada penelitian ini adalah metode Mesin Roulette, yang melibatkan nilai fitness dan probabilitas. Setelah dihitung nilai fitness masing-masing individu dan total keseluruhannya, didapatkan probabilitas dan jatah per individu (Gambar 4). Contoh: Probabilitas: Individu 1 = 10% Individu 2 = 20% Individu 3 = 30% Individu 4 = 40% Jatah per individu: Individu 1 1 – 10 Individu 2 11 – 30 Individu 3 31 – 60 Individu 4 61 – 100 Individu 2 11 – 30
Individu 3 31 – 60
20% 30%
10%
Individu 1 1 – 10
40%
Individu 4 61 – 100
Gambar 4 Probabilitas nilai fitness.
5
Selanjutnya, bangkitkan bilangan acak antara 1 – 100. Jika didapatkan bilangan seperti berikut: 69, 18, 86, dan 41, individu yang terpilih adalah individu 4, individu 2, dan individu 3. 69 Individu 4 (61 – 100) 18 Individu 2 (11 – 30) 86 Individu 4 (61 – 100) 41 Individu 3 (31 – 60) Mutasi Deret angka yang terpilih tadi akan diproses lebih lanjut dengan operator-operator pada algoritme genetika hingga didapatkan sebuah deret angka baru yang siap untuk dicocokkan kembali dengan deret angka target. Operator algoritme genetika yang pertama yaitu mutasi. Gen-gen pada individu terpilih akan diubah nilainya dengan bilangan acak (Random Mutation). Deret angka induk: 1
2
3
4
Deret angka anak: 1
6
3
4
Jika deret angka baru keluar dari ruang solusi (memiliki angka yang sama), dibutuhkan teknik mutasi lainnya (Basuki 2003). Contoh: 1
3
3
4
Proses ini dilakukan berdasarkan peluang mutasi yang ditetapkan sebelumnya. Jika peluang acak yang dibangkitkan oleh sistem berjumlah lebih kecil dari peluang mutasi, proses mutasi pun dilakukan. Pindah-Silang Operator algoritme genetika yang kedua yaitu pindah-silang. Gen-gen yang bersesuaian pada individu terpilih (induk) akan saling ditukar pada satu digit tertentu (pindah-silang satu titik) untuk mendapatkan individu baru (anak). Deret angka induk: 1
2
3
4
5
6
7
8
Deret angka anak: 1
2
7
4
5
6
3
8
Proses ini dilakukan berdasarkan peluang pindah-silang yang ditetapkan sebelumnya. Jika peluang acak yang dibangkitkan oleh sistem berjumlah lebih kecil dari peluang pindahsilang, proses pindah-silang pun dilakukan. Rule Beberapa rule dibangun untuk menunjang kinerja dari algoritme genetika. Rule-rule tersebut akan berfungsi pada setiap perubahan yang terjadi dari deret-deret yang ada pada history dan berusaha memprediksi angka-angka mana saja yang telah tepat letaknya ataupun yang tidak ada dalam deret target sehingga angka-angka tersebut dapat dihilangkan dan memperkecil ruang pencarian. Beberapa rule yang dibangun, yaitu: Jika hasil penebakan adalah 0c 0m, seluruh angka pada deret tebakan tersebut tidak terdapat pada deret target dan harus dihilangkan dari ruang pencarian. Jika nilai fitness deret anak sama dengan induk dan m bernilai 0, hilangkan angka sebelum dan sesudah perubahan dari ruang pencarian karena kedua angka tersebut tidak memberikan pengaruh apapun pada deret. Jika c bertambah 1 dari tebakan sebelumnya, hilangkan angka sebelum perubahan dari ruang pencarian dan tandai digit letak angka tersebut. Jika c berkurang 1 dan m tetap, hilangkan angka sesudah perubahan dari ruang pencarian dan tandai digit letak angka tersebut. Jika c berkurang 1 dan m bertambah 1, tandai digit letak angka tersebut. Jika c tetap dan m berkurang 1, hilangkan angka sesudah perubahan dari ruang pencarian. Kondisi Stop Program akan berhenti jika kondisi 4c 0m telah tercapai atau iterasi penebakan telah mencapai 50 kali. Evaluasi Sistem Setelah terbentuk, sistem pun lalu dievaluasi menggunakan satu buah soal yang dibangkitkan secara acak. Kinerjanya akan dinilai berdasarkan pengaruh nilai fitness (jumlah variable c dan m) dari deret tebakan awal dan juga dibandingkan dengan worst case dari jumlah penebakan.
6
HASIL DAN PEMBAHASAN
Deret Angka Tebakan Pada iterasi pertama, komputer selaku codebreaker akan membangkitkan deret angka tebakan secara acak. Pada tahap ini, dilakukan sebuah pengujian untuk mengetahui pengaruh nilai fitness deret tebakan awal terhadap banyaknya iterasi penebakan. Pengujian ini dilakukan terhadap tiga belas kemungkinan kondisi jumlah variable hasil penebakan. Pada setiap kondisi, dibangkitkan lima deret angka berbeda, lalu dijadikan sebagai deret tebakan pada iterasi pertama. Penebakan dilakukan sebanyak sepuluh kali untuk tiap deret dan dicari rata-ratanya. Dari kelima deret tebakan di masing-masing kondisi tadi, dicari rata-ratanya kembali (Tabel 2). Tabel 2 Hasil uji pengaruh nilai fitness (dengan pembulatan) Kemungkinan hasil penebakan iterasi ke-1 0c 0m 0c 1m 0c 2m 0c 3m 0c 4m 1c 0m 1c 1m 1c 2m 1c 3m 2c 0m 2c 1m 2c 2m 3c 0m
Rata-rata jumlah iterasi keseluruhan 11 24 20 22 13 12 11 11 17 7 10 25 4
Proses pengujian ini membuktikan bahwa nilai fitness dari deret tebakan awal (iterasi pertama) mempengaruhi jumlah iterasi penebakan keseluruhan. Pada Gambar 5, terlihat bahwa semakin besar jumlah c dan m yang didapat pada iterasi pertama, semakin sedikit jumlah iterasi keseluruhan yang dibutuhkan untuk menebak deret target.
30 25 20 15 10 5 0 0c 0m 0c 1m 0c 2m 0c 3m 0c 4m 1c 0m 1c 1m 1c 2m 1c 3m 2c 0m 2c 1m 2c 2m 3c 0m
Deret angka target dibangkitkan secara acak oleh codemaker sebanyak satu buah, yaitu deret angka 3714. Deret angka tersebut akan dijadikan sebagai soal uji coba program untuk pengujian pengaruh nilai fitness deret tebakan awal terhadap banyaknya iterasi penebakan.
Jumlah Iterasi
Deret Angka Target
Kemungkinan hasil penebakan iterasi ke-1 (nilai fitness)
Gambar 5 Grafik uji pengaruh nilai fitness. Terdapat dua kasus yang tidak sesuai dengan pola grafik. Kasus yang pertama, yaitu pada kondisi 0c 0m yang memiliki jumlah iterasi keseluruhan yang lebih sedikit dibandingkan dengan kondisi 0c 1m (yang notabene memiliki nilai fitness lebih besar dari kondisi 0c 0m). Hal ini terjadi karena pada kondisi 0c 1m, sistem tidak memperoleh informasi yang cukup berarti. Sistem hanya memperoleh informasi bahwa terdapat hasil 1m tanpa mengetahui hasil tersebut diberikan untuk digit yang mana. Pada kondisi 0c 0m, sistem memperoleh informasi bahwa seluruh digit angka yang ada pada deret tebakan tersebut salah (tidak terdapat pada deret target) sehingga sistem langsung menandai angka-angka tersebut dan otomatis memperkecil ruang pencarian berikutnya. Kasus yang kedua yaitu tidak tertebaknya deret angka target hingga batas iterasi telah tercapai (50) ataupun iterasi yang dibutuhkan sangat tinggi. Kasus tersebut terjadi pada beberapa deret tebakan di kondisi tertentu, yaitu: 2471 (kondisi 0c 3m), 3471 (kondisi 1c 3m), 3417 (kondisi 2c 2m), dan 3741 (kondisi 2c 2m). Evaluasi Fitness Proses ini menggunakan sebuah fungsi fitness yang mengandung dua variable yang perlu ditetapkan bobotnya, yaitu c dan m. Variable inilah yang nantinya akan menentukan besar kecilnya nilai fitness suatu deret tebakan serta peluang terpilihnya deret tersebut dalam proses seleksi. Fungsi fitness xc + ym Target yang akan dicapai oleh program yaitu 4c 0m. Oleh karena itu, c harus memiliki bobot yang lebih besar daripada m agar deret tebakan pada history yang mengandung hasil c dapat terseleksi dengan mudah.
7
Berdasarkan hasil percobaan, didapatkan bobot untuk c sebesar 40 dan bobot untuk m sebesar 15 (selisih 25). Jika selisih nilai kedua variable tersebut lebih besar, deret pada history yang memiliki hasil m akan berpeluang sangat kecil untuk terpilih dalam proses seleksi. Sebaliknya, jika selisih nilainya lebih kecil (yang berarti bobot c dan m hampir sama besar), deret pada history yang memiliki hasil c akan semakin sulit terpilih dalam proses seleksi dan mengakibatkan kondisi 4c 0m akan semakin lama tercapai. Mutasi Jenis mutasi yang dipakai yaitu Random Mutation. Peluang mutasi ditetapkan sebesar 0.1 agar variable c dan m yang telah didapatkan sebelumnya tidak mudah hilang ataupun tergantikan (konvergensi mudah didapatkan). Pindah-Silang Jenis pindah-silang yang dipakai yaitu pindah-silang satu titik. Hal ini dilakukan agar informasi yang muncul pada saat terjadinya perubahan deret dapat lebih mudah dilihat. Peluang pindah-silang ditetapkan sebesar 0.85 agar deret-deret pada history yang memiliki nilai fitness tinggi dapat dengan mudah digabungkan dan membentuk deret anak baru yang diharapkan mempunyai nilai fitness yang lebih tinggi dari deret induknya. Evaluasi Sistem Berdasarkan hasil uji pengaruh nilai fitness yang telah dilakukan sebelumnya, jumlah ratarata iterasi keseluruhan yang diperlukan sistem untuk menebak deret angka target adalah 4 kali untuk batas bawah dan 25 kali untuk batas atas. Jika dibandingkan dengan worst case jumlah penebakan sebesar 5040, jumlah rata-rata iterasi keseluruhan tadi berada sangat jauh di bawahnya. Hal ini membuktikan bahwa algoritme genetika yang diterapkan di dalam permainan tebak angka ini cukup efektif.
KESIMPULAN DAN SARAN Kesimpulan Dari beberapa percobaan yang dilakukan terhadap deret angka, diperoleh kesimpulan berikut: Algoritme genetika cukup efektif untuk diterapkan pada kasus optimasi permainan tebak angka.
Hasil dari deret tebakan pada iterasi pertama mempengaruhi kinerja penebakan sistem dan menentukan jumlah iterasi keseluruhan yang dibutuhkan sistem untuk mencapai solusi yang tepat. Kinerja algoritme genetika cukup terbantu dengan dibangunnya beberapa rule. Saran Hal yang dapat dilakukan pada penelitian selanjutnya yaitu memperlihatkan kinerja penebakan sistem pada deret di atas empat digit ataupun menyertakan data waktu penyelesaian permainan sebagai faktor penilaian lainnya.
DAFTAR PUSTAKA Basuki A. 2003. Strategi Menggunakan Algoritma Genetika. http://lecturer.eepisits.edu/~basuki/lecture/StrategiAlgoritmaGe netika.pdf [29 Apr 2010]. Berghman L, Goossens D, Leus R. 2009. Efficient Solutions for Mastermind Using Genetic Algorithms. Leuven: K. U. Leuven Press. Goldberg DE. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. Boston: Addison−Wesley. Marcel J. 2009. Aplikasi Algoritma Genetik pada Permainan Mastermind. http://informatika.stei.itb.ac.id/~rinaldi.muni r/Stmik/2009-2010/Makalah2009/Makalah IF3051-2009-030.pdf [12 Okt 2011]. Melanie M. 1996. An Introduction to Genetic Algorithms. Cambridge: MIT Press. Satriyanto E. 2009. Bab 7 Algoritma Genetika. http://lecturer.eepis-its.edu/~kangedi/materi kuliah/Kecerdasan Buatan/Bab 7 Algoritma Genetika.pdf [22 Jun 2010].
LAMPIRAN
9
Lampiran 1 Hasil uji pengaruh nilai fitness Kemung kinan hasil
Jumlah iterasi percobaan keDeret
Ratarata (dibulat kan)
1
2
3
4
5
6
7
8
9
10
2095
20
16
16
18
15
15
16
17
16
15
16
6908
11
10
10
10
11
9
10
9
12
10
10
8562
9
9
10
10
13
10
9
9
11
10
10
5028
10
14
13
13
12
13
17
12
11
15
13
9856
6
6
6
7
6
7
5
9
5
6
6
0c 0m
Jumlah iterasi keseluruhan
11
7580
25
25
27
26
29
27
32
26
29
27
27
5961
19
23
24
19
27
24
23
23
26
24
23
2603
17
16
23
19
18
19
20
20
19
22
19
8249
22
31
27
25
27
27
29
28
26
28
27
9426
19
24
26
23
26
24
24
20
28
27
24
0c 1m
Jumlah iterasi keseluruhan
24
4158
23
21
24
26
24
25
22
25
24
27
24
6351
17
18
15
17
16
16
20
17
16
18
17
8472
22
21
18
20
18
23
20
22
18
20
20
1386
20
22
15
17
18
20
17
18
16
18
18
7230
22
21
22
24
18
20
21
23
19
21
21
0c 2m
Jumlah iterasi keseluruhan
20
1573
21
23
22
21
18
21
20
25
23
17
21
4138
15
17
18
23
17
14
19
17
16
18
17
2471
15
18
19
50
50
50
50
50
50
50
40
7340
10
14
11
15
17
14
13
17
15
14
14
1463
23
19
20
18
21
23
18
20
22
19
20
0c 3m
Jumlah iterasi keseluruhan
22
4137
11
17
14
15
18
13
15
17
14
18
15
1347
15
16
16
14
11
18
14
15
13
20
15
7431
10
11
15
10
12
11
13
9
11
12
11
4371
9
15
11
18
14
17
13
15
17
11
14
1437
10
13
12
15
11
12
10
16
11
12
12
0c 4m
Jumlah iterasi keseluruhan
13
10
Lanjutan Kemung kinan hasil
Jumlah iterasi percobaan keDeret
Ratarata (dibulat kan)
1
2
3
4
5
6
7
8
9
10
2709
9
15
11
8
12
14
10
9
12
14
11
8624
9
8
11
10
15
11
10
9
10
7
10
3950
12
11
10
15
12
14
10
15
13
10
12
6815
21
23
17
15
18
20
17
18
15
20
18
9762
9
13
15
9
11
10
13
9
12
11
11
1c 0m
Jumlah iterasi keseluruhan
12
7084
7
6
9
12
8
9
13
10
8
10
9
5316
15
13
9
12
10
9
13
15
12
13
12
3942
18
21
15
13
15
18
15
16
14
18
16
8701
6
9
6
12
9
11
8
12
10
9
9
6394
14
12
11
8
11
10
14
8
17
9
11
1c 1m
Jumlah iterasi keseluruhan
11
4917
13
14
11
10
12
15
10
15
10
12
12
1738
6
8
10
9
8
12
11
9
8
11
9
3461
12
10
11
12
11
16
13
12
15
10
12
5374
12
11
10
11
15
11
14
8
10
12
11
4703
11
12
10
17
13
15
11
12
9
12
12
1c 2m
Jumlah iterasi keseluruhan
11
7134
8
13
6
10
11
9
7
9
12
7
9
3471
50
50
50
50
50
50
50
50
50
50
50
4317
11
7
9
11
8
10
13
9
8
6
9
1743
10
15
7
10
12
9
10
9
11
7
10
1374
14
9
10
12
7
9
7
10
8
6
9
1c 3m
Jumlah iterasi keseluruhan
17
3815
4
5
5
4
5
6
5
4
5
7
5
2719
4
4
5
3
6
4
3
5
4
4
4
3024
10
8
11
10
9
7
10
9
15
11
10
9764
5
8
5
11
8
10
7
11
9
8
8
3610
5
6
9
5
6
8
6
5
7
6
6
2c 0m
Jumlah iterasi keseluruhan
7
11
Lanjutan Kemung kinan hasil
Jumlah iterasi percobaan keDeret
Ratarata (dibulat kan)
1
2
3
4
5
6
7
8
9
10
4719
8
7
10
7
12
16
10
9
12
9
10
3751
6
8
11
8
12
10
7
9
5
6
8
3416
15
13
16
10
13
11
10
12
10
12
12
1704
6
5
7
5
10
14
8
7
10
8
8
3817
13
12
10
15
12
11
17
12
8
13
12
2c 1m
Jumlah iterasi keseluruhan
10
3417
50
50
50
50
50
50
50
50
50
50
50
3741
50
50
50
50
50
50
50
50
50
50
50
7314
8
8
8
8
8
8
8
8
8
8
8
1734
8
8
8
8
8
8
8
8
8
8
8
4713
8
6
8
8
9
8
8
7
10
8
8
2c 2m
Jumlah iterasi keseluruhan
25
3704
4
4
3
4
3
5
4
3
6
4
4
3814
3
3
4
3
2
3
3
3
4
3
3
2714
6
5
5
7
5
3
6
5
4
5
5
3794
5
4
3
4
6
4
5
3
4
3
4
3715
6
7
6
7
6
5
9
6
5
6
6
3c 0m
Jumlah iterasi keseluruhan
4
