PERANCANGAN ALGORITMA GENETIKA DALAM PENYUSUNAN TEKA-TEKI SILANG 1
Afen Prana Utama1, Edison Sinaga D-3 Manajemen Informatika - STMIK Mikroskil Medan
[email protected] Abstrak
Teka-teki silang merupakan sebuah permainan untuk mengasah otak. Teka-teki silang (TTS) dapat dimanfaatkan dalam bidang pendidikan untuk menguji kemampuan anak didik, sehingga pertanyaan-pertanyaan yang digunakan disesuaikan dengan kebutuhan. Pertanyaannya dibagi menjadi dua kategori yaitu mendatar dan menurun. Penerapan algoritma genetika digunakan untuk mendapatkan suatu pola penyusunan kata dalam ruang-ruang kosong yang paling optimal. Untuk mengetahui optimal atau tidaknya pengisian ruang kosong tersebut, dilakukan dengan melihat banyaknya kombinasi kata yang dapat dibuat atau dapat juga dilihat dari banyaknya sisa ruang kosong TTS tersebut. Jadi, semakin banyak dan baik kombinasi kata yang dibuat untuk mengisi ruang-ruang kosong, maka semakin optimal pengisian tersebut. Solusi ini dapat diatasi apabila membuat TTS dilakukan secara otomatis dengan komputer. Dengan menggunakan algoritma genetika, diharapakan akan mampu membuat kombinasi dari sekumpulan jawaban pertanyaan menjadi sebuah bentuk TTS dengan jumlah pertanyaan yang ditentukan sendiri oleh pengguna, dengan area papan matriks yang digunakan untuk meletakkan jawaban adalah seminimal mungkin. Pertanyaan ditentukan sendiri oleh pengguna dengan tujuan untuk membuat TTS dengan pertanyaan-pertanyaan yang lebih spesifik, misalnya pertanyaan bidang pendidikan, komputer, pertanyaan yang berhubungan dengan biologi dan sebagainya. Kata Kunci: Algoritma Genetika, Teka teki silang, Asah Otak
1.
Pendahuluan Teka-teki silang (TTS) merupakan sebuah permainan untuk mengasah otak. TTS dapat dimanfaatkan dalam bidang pendidikan untuk menguji kemampuan anak didik, sehingga pertanyaan-pertanyaan yang digunakan disesuaikan dengan kebutuhan saja. Untuk membuat sebuah TTS dapat dikatakan mudah, mudah karena kita hanya mengkombinasikan kata yang satu dengan yang lain. Tapi akan sulit apabila jumlah pertanyaan yang digunakan banyak, karena untuk membuat sebuah TTS dari sekumpulan pertanyaan, kita harus mencoba kombinasi yang mungkin dari kata yang ada sampai terbentuk sebuah TTS. Semakin banyak jumlah pertanyaan, maka semakin banyak kombinasi yang harus kita coba. Penerapan algoritma genetika digunakan untuk mendapatkan suatu pola penyusunan kata dalam ruang-ruang kosong yang paling optimal. Untuk mengetahui optimal atau tidaknya pengisian ruang kosong tersebut, dilakukan dengan melihat banyaknya kombinasi kata yang dapat dibuat atau dapat juga dilihat dari banyaknya sisa ruang kosong TTS tersebut. Jadi, semakin banyak dan baik kombinasi kata yang dibuat untuk mengisi ruang-ruang kosong, maka semakin optimal pengisian tersebut. Solusi ini dapat diatasi apabila membuat TTS dilakukan secara otomatis dengan komputer. Batasan-batasan yang dibuat antara lain : 1. TTS yang dibuat adalah TTS dalam bentuk yang kita kenal sekarang ini. Pertanyaan dibagi menjadi dua kategori yaitu mendatar dan menurun.
2. Jawaban pertanyaan mendatar tidak boleh tersusun bersambung dengan jawaban pertanyaan mendatar, dan jawaban pertanyaan menurun tidak boleh tersusun bersambung dengan jawaban pertanyaan menurun 3. Apabila jawaban mengandung karakter selain huruf A..Z, maka karakter tersebut diabaikan. Misalnya apabila jawaban dari sebuah pertanyaan adalah kupu-kupu maka ditulis menjadi kupukupu. 2. Kajian Pustaka 2.1 Teka Teki Silang TTS atau disingkat TTS adalah suatu permainan yang mengharuskan penggunanya untuk mengisi ruang-ruang kosong dengan huruf-huruf yang membentuk sebuah kata berdasarkan petunjuk yang diberikan. Petunjuk biasa dibagi dalam kategori mendatar dan menurun tergantung posisi kata yang harus diisi. TTS (TTS) pertama kali diterbitkan dalam majalah New York World dalam format yang hampir sama dengan TTS yang dikenal pada saat ini. Teka-teki yang sering disebut sebagai TTS yang pertama ini ditemukan oleh Wynne. TTS kemudian menjadi fitur mingguan di majalah tersebut. Dalam perkembangan selanjutnya TTS tidak hanya menjadi fitur sebuah majalah. Buku kumpulan TTS yang pertama diterbitkan oleh Simon dan Schuster pada tahun 1924. TTS menjadi salah satu benda terpopuler pada era tersebut. Di Indonesia sendiri, perkembangan TTS diawali pada tahun 1970-an. Pada waktu itu di Jakarta terbit “Asah Otak”, sebuah majalah TTS dan teka-teki lainnya. Penerbitan ini ternyata juga menuai sukses sehingga banyak terbitan serupa yang mengikuti. 2.2 Algoritma Genetika Algoritma genetika adalah suatu algoritma pencarian (searching) berdasarkan cara kerja melalui mekanisme seleksi alam dan genetik. Tujuannya untuk menentukan struktur-struktur yang disebut individu berkualitas tinggi di dalam suatu domain yang disebut populasi untuk mendapatkan solusi persoalan [4]. Pada tahun 1975, John Holland memperkenalkan algoritma genetika untuk yang pertama kalinya. Algoritma genetika berbeda dengan algoritma konvensional karena dimulai dari suatu himpunan awal yang disebut populasi[3]. Algoritma genetika menggunakan dua prinsip dasar dalam sistem biologis, yaitu seleksi terhadap spesies yang ada dan peningkatan keanekaragaman (gen dengan operasi genetik) [2]. 2.3 Parameter Algoritma Genetika Skema algoritma genetika menentukan bagaimana jalannya proses algoritma genetika, sehingga pada proses ini juga perlu ditentukan parameter algoritma genetika yang akan digunakan, yaitu sebagai berikut: a) Ukuran populasi Ukuran populasi adalah jumlah kromosom yang ada pada populasi. Kromosom merepresentasikan bentuk dari TTS. Memilih ukuran populasi yang tepat akan meningkatkan kinerja algoritma genetika. Apabila ukuran populasi terlalu kecil, maka algoritma genetika hanya mempunyai alternatif solusi yang sedikit. Namun, jika ukuran populasi terlalu, besar proses algoritma genetika akan berjalan lambat. b) Jumlah generasi Satu proses rangkaian algoritma genetika dimulai dari proses seleksi, crossover (pindah silang), mutasi sampai update generasi. Proses algoritma genetika akan dihentikan apabila 180
jumlah generasi sudah terpenuhi. Solusi yang diambil adalah kromosom dengan nilai fitness (nilai kelayakan) terbaik dari generasi terakhir. c) Crossover probability (peluang pindah silang) Peluang crossover (PC) akan menentukan banyaknya crossover (pindah silang) yang terjadi. Nilai PC berkisar dari 0 sampai 1. Apabila nilai PC sama dengan 1, maka seluruh kromosom akan mengalami crossover. Apabila PC sama dengan 0, maka tidak akan terjadi proses crossover, atau dengan kata lain kromosom offspring (kromosom anak hasil pindah silang) akan sama dengan kromosom parent (kromosom induk). 2.4 Kromosom dan Pola Representasi Dalam konsep ilmu biologi dikenal adanya istilah sel. Sel merupakan bagian terkecil yang menyusun organisme. Secara umum organisme terdiri dari sel-sel penyusun. Sebuah sel tersusun dari kumpulan beberapa kromosom. Sebuah kromosom tersusun dari beberapa gen. Gen merupakan sekumpulan DNA (Deoxyribo Nucleic Acid). Konsep biologi semacam ini yang diadaptasi pada algoritma genetika. Dalam algoritma genetika, kromosom merupakan alternatif solusi dari sebuah permasalahan. Kromosom dapat disajikan dalam beberapa bentuk sesuai dengan jenis pengkodean yang digunakan. a) Pengkodean kromosom Pengkodean merupakan bagian yang penting dalam menyelesaikan suatu permasalahan dengan algoritma genetika. Pengkodean adalah pengkorversian masalah dalam dunia nyata menjadi bentuk yang dapat diolah dengan menggunakan algoritma genetika. Pengkodean yang tepat sangat menentukan berhasil atau tidaknya proses algoritma genetika dalam menyelesaikan sebuah permasalahan. Pengkodean yang tepat juga akan menentukan tingkat efisiensi komputasi yang digunakan. Ada beberapa jenis pengkodean yang dapat digunakan dalam algoritma genetika, diantaranya pengkodean biner (binary encoding) dan pengkodean permutasi (permutation encoding). b) Nilai fitness (nilai kelayakan) dan fungsi objektif (fungsi tujuan) Dalam proses evolusi individu yang survive (bertahan hidup) dari proses seleksi alam akan mempunyai kesempatan untuk bereproduksi kembali. Dengan demikian, kemampuan individu untuk dapat beradaptasi dan bertahan hidup untuk selamat sangat penting. Dalam terminologi algoritma genetika kemampuan suatu individu (kromosom) untuk bertahan hidup dapat diukur berdasarkan nilai fitness-nya. Semakin baik nilai fitness (nilai kelayakan) suatu kromosom maka akan semakin baik peluang kromosom tersebut untuk bertahan hidup dan ikut dalam proses reproduksi. Nilai fitness suatu kromosom dapat dihitung dengan menggunakan fungsi objektif. c) Seleksi Proses seleksi bertujuan untuk memilih kromosom yang akan dijadikan sebagai parent (kromosom induk) pada proses crossover (pindah silang). Ada beberapa metode yang dapat dipilih pada proses seleksi, antara lain Roulette Wheel Selection, Rank Selection dan Tournament Selection. 1) Roulette wheel selection Pada roulette wheel selection, kromosom akan dipilih secara acak ditentukan dengan memperhitungkan nilai kelayakan masing-masing kromosom. Semakin besar nilai kelayakan suatu kromosom, semakin besar pula peluang kromosom tersebut untuk terpilih sebagai parent (kromosom induk). Pengkodean roulette wheel dapat dianalogikan seperti permainan roda putar. Pada permainan roda putar, lingkaran roda dibagi menjadi beberapa wilayah. Pada roulette wheel selection, lebar suatu wilayah kromosom ditentukan menurut nilai fitness-nya, 181
semakin besar nilai fitness-nya maka akan semakin besar wilayahnya, dan semakin besar pula peluang kromosom tersebut untuk terpilih. Ilustrasi dari roulette wheel selection dapat dilihat pada Gambar 1.
Gambar 1 Ilustrasi roulette wheel selection Proses roulette wheel selection dijelaskan pada algoritma sebagai berikut: 1. [Sum] Jumlahkan semua nilai fitness (nilai kelayakan) tiap-tiap kromosom pada populasi S. 2. [Select] Generate bilangan random pada interval (0,S)-r. 3. [Loop] secara sekuensial dari kromosom pertama, jumlahkan nilai fitness kromosom-s. Apabila pada kromosom ke-i s>r maka berhenti, maka kromosom i terpilih sebagai kandidat parent. Contoh dari roulett whell selection dapat dilihat pada Tabel 1. Tabel 1. Contoh roulet wheel selection Kromosom
Fitness
Si
Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4 Kromosom 5 Jumlah
20 10 30 10 40 S = 110
20 30 60 70 110
Bil Random r (0, 110) 35 90 45 10 70
Kromosom Terpilih Kromosom 3 Kromosom 5 Kromosom 3 Kromosom 1 Kromosom 4
Pada tabel di atas disimpulkan bahwa ukuran pupulasi adalah 5. Nilai Si merupakan nilai akumulasi dari nilai fitness kromosom ke 1 sampai kromosom ke i. Untuk memilih kromosom yang akan menjadi calon parent maka dibangkitkan bilangan random (0, S). Bilangan random yang dibangkitkan sebanyak 5 buah sesuai dengan ukuran populasinya. Apabila ri < Si dan ri > Si-1 maka kromosom yang terpilih adalah kromosom ke i. Pada tabel di atas r1 = 35, karena 35 < S3 (60) dan 35 > S2 (30) maka kromosom yang terpilih adalah kromosom 3. d) Rank selection Pada pengkodean ranking, kromosom pada populasi diranking sesuai dengan nilai fitnessnya, kemudian kromosom diberi nilai fitness (nilai kelayakan) yang baru sesuai dengan rankingnya. Kromosom dengan ranking terbawah akan mendapat nilai fitness 1, ranking terbawah kedua mendapat nilai fitness 2, demikian seterusnya. Kromosom dengan ranking terbaik akan mendapat nilai fitness N. Tabel 2. Contoh rank selection Kromosom Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4 Kromosom 5 Jumlah
Fitness Awal 20 10 30 40 5
Rangking 3 4 2 1 5
Fitness setelah rangking 3 2 4 5 1 S = 15
182
Si 3 5 9 14 15
Bil.Random R(0,15) 5 3 7 8 13
Kromosom Terpilih Kromosom 2 Kromosom 1 Kromosom 3 Kromosom 3 Kromosom 4
Pada tabel di atas dapat dilihat bahwa rank selection hampir sama dengan roulett whell selection. Hanya saja sebelum kromosom dipilih nilai fitness tiap kromosom diganti sesuai dengan rankingnya. Nilai fitness hasil dari pemeringkatan ini yang kemudian dijadikan acuan pada saat pemilihan kromosom. e) Crossover Crossover atau pindah silang adalah proses pembentukan kromosom anak (offspring). Crossover bertujuan menambah keanekaragaman string dalam satu populasi dengan penyilangan antar-string yang diperoleh dari reproduksi sebelumnya [5]. Beberapa jenis crossover sebagai berikut: 1) Crossover pengkodean biner Ada beberapa metode crossover (pindah silang) dengan pengkodean biner, yaitu sebagai berikut: i) Crossover 1 titik Proses crossover dilakukan dengan memisahkan suatu string menjadi dua bagian dan selanjutnya salah satu bagian dipertukarkan dengan salah satu bagian dari string yang lain yang telah dipisahkan dengan cara yang sama. Tabel 3. Crossover 1 titik Kromosom orangtua 1 11001011 Kromosom orangtua 2 11011111 Keturunan 11001111 ii) Crossover 2 titik Proses crossover (pindah silang) ini dilakukan dengan memilih dua titik crossover. Kromosom keturunan kemudian dibentuk dengan barisan bit dari awal kromosom sampai titik crossover pertama disalin dari orangtua pertama, bagian dari titik crossover pertama dan kedua disalin dari orangtua kedua, kemudian selebihnya disalin dari orang tua pertama lagi. Tabel 4. Crossover 2 titik Kromosom orangtua 1 11001011 Kromosom orangtua 2 11011111 Keturunan 11001111 2) Crossover seragam Crossover (pindah silang) seragam menghasilkan kromosom keturunan dengan menyalin bit-bit secara acak dari kedua orangtuanya. Tabel 5. Crossover seragam Kromosom orangtua 1 11001011 Kromosom orangtua 2 11011111 Keturunan 11001111 3) Arithmatic crossover Kromosom offspring (kromosom anak) diperoleh dengan melakukan operasi aritmatika terhadap parent (induk). Operasi yang dapat dilakukan antara lain AND, OR, XOR dan lainlain. Contoh dari arithmatic crossover dapat dilihat pada gambar di bawah ini:
Gambar 2. Arithmatic crossover 183
4) Crossover pengkodean permutasi Jenis crossover (pindah silang) untuk pengkodean permutasi hanyalah single point crossover. Metode ini dilakukan dengan memilih satu titik crossover p pada kromosom parent (kromosom induk) secara acak. Gen ke-1 sampai gen ke-p pada parent 1 dikopikan menjadi gen offspring (kromosom anak). Sisa gen yang belum terpenuhi diambil dari parent 2 dengan cara sekuensial dari gen ke-1 parent 2 sampai gen terakhir, dengan syarat gen tersebut belum ada dalam kromosom offspring. Contoh dari crossover pada pengkodean permutasi dapat dilihat pada gambar di bawah ini: Parent 1
23415768
Parent 2
51386427
Offspring1
23415867
Offspring2
51382476
Gambar 3. Pengkodean permutasi Titik crossover pada gen ke-4. Offspring pertama dihasilkan dari gen 1 sampai gen 4 parent 1, kemudian gen yang berikutnya pada offspring 1 diambil dari parent 2. Gen parent 2 dicek secara sekuensial dari gen 1 sampai gen 8. Apabila gen yang dicek belum ada pada gen yang diambil dari parent 1 maka gen pada parent 2 tersebut diambil untuk menjadi bagian pada offspring 1. 3. Metode Penelitian 3.1 Analisis Sistem TTS dengan menggunakan algoritma genetika yang akan dibangun dalam penelitian ini diharapkan dapat menghasilkan TTS dengan jumlah pertanyaan yang ditentukan sendiri oleh pengguna. Pertanyaan-pertanyaan yang akan ditampilkan pada pengguna tersebut diperoleh dari database secara acak oleh program. TTS yang telah dibuat dapat disimpan dalam bentuk sebuah file yang memungkinkan pengguna untuk memainkan kembali TTS tersebut pada waktu yang lain. Pertanyaan-pertanyaan yang akan digunakan dalam TTS disimpan dalam database. Database yang berisi pertanyaan-pertanyaan tersebut dapat di-update sehingga koleksi pertanyaan yang tersimpan dapat bertambah. Dengan demikian, pengguna dapat bermain TTS dengan pertanyaan yang lebih bervariasi. TTS yang dibentuk merupakan kumpulan jawaban dari pertanyaan yang digunakan. Jawaban-jawaban pertanyaan disusun sedemikian rupa sehingga saling berpotongan satu sama lain. Untuk membentuk sekumpulan jawaban pertanyaan menjadi TTS digunakan sebuah papan matriks berdimensi dua. Papan matriks dapat dianalogikan seperti sebuah papan catur. Setiap kotak (cell) berada pada koordinat x,y. Pada papan matriks ini nantinya jawaban dari pertanyaan akan diletakkan untuk dibentuk menjadi sebuah TTS. Setiap huruf dari jawaban akan menempati satu cell pada papan matriks. [1] 3.2 Rancangan Sistem Rancangan sistem aplikasi pembuatan TTS yang akan dibangun dengan menggunakan algoritma genetika adalah sebagai berikut: a) Diagram konteks Proses menyeluruh dari aplikasi TTS menggunakan algoritma genetika dapat dilihat dari diagram konteks pada Gambar 4. 184
Gambar 4. Diagram konteks Aplikasi menerima masukan dari pengguna berupa jumlah pertanyaan, permintaan update, pilihan load game dan jawaban pengguna. Jumlah pertanyaan merupakan jumlah dari pertanyaan yang akan digunakan dalam permainan TTS. Permintaan update digunakan pengguna untuk meng-update database pertanyaan. Sedangkan, pilihan load game digunakan untuk memainkan TTS yang telah disimpan sebelumnya dalam bentuk file dengan ekstensi .tts. Selain menerima masukan dari pengguna, aplikasi juga memberikan keluaran kepada pengguna berupa TTS dan jawaban yang benar dari TTS tersebut. 1) DFD level 1 DFD level 1 merupakan penjabaran dari diagram konteks, yang ditunjukkan pada Gambar 5.
Gambar 5. DFD level 1 Pada DFD level 1 digambarkan proses-proses utama yang ada dan terjadi pada sistem. Pada proses TTS Baru, pengguna memasukkan jumlah pertanyaan yang akan digunakan pada permainan TTS. Proses TTS Baru akan memberikan keluaran berupa TTS yang dapat dimainkan oleh pengguna. Proses Update Bank Soal merupakan proses untuk meng-update koleksi pertanyaan yang dimiliki sehingga pertanyaan yang digunakan dalam permainan TTS lebih bervariasi. Pada proses ini juga perlu ditentukan nilai dari parameter algoritma genetika yang akan digunakan, yaitu sebagai berikut: 1. Ukuran populasi Sebuah kromosom merepresentasikan sebuah bentuk TTS. Dengan demikian populasi adalah kumpulan bentuk TTS dalam bentuk kromosom. Ukuran populasi sangat mempengaruhi kinerja algoritma genetika. Apabila ukuran populasi terlalu besar maka komputasi yang dibutuhkan juga akan lebih besar, sehingga waktu yang dibutuhkan juga akan bertambah. Namun apabila ukuran populasi terlalu kecil maka alternatif solusi akan 185
sedikit, sehingga kemungkinan hasil yang didapatkan kurang baik. Ukuran populasi yang digunakan pada penelitian ini adalah 30. 2. Papan matriks Papan matriks merupakan tempat untuk menyusun jawaban dari pertanyaan-pertanyaan menjadi sebuah TTS. Papan matriks bisa dipandang seperti sebuah papan catur berdimensi 2 dengan ukuran 100x100. Karena ukuran papan matriks hanya 100x100, maka dimensi dari TTS yang dapat dibuat maksimal adalah 100x100. 3. Pengkodean Urutan jawaban dan posisi jawaban (mendatar atau menurun) harus dikodekan menjadi bentuk yang dapat diolah dengan algoritma genetika dalam bentuk sebuah kromosom. Sebuah kromosom merupakan susunan dari beberapa gen. Panjang sebuah kromosom adalah jumlah gen yang terdapat pada kromosom tersebut. Sebuah gen berisi jawaban dari sebuah pertanyaan. Dengan demikian, panjang kromosom sama dengan jumlah pertanyaan yang dimasukkan pengguna. Pengkodean yang digunakan adalah pengkodean permutasi. Setiap gen mempunyai dua atribut. Atribut yang pertama berisi id dari sebuah pertanyaan yang akan digunakan dalam permainan TTS. Atribut yang lain berupa atribut orientasi. Atribut orientasi menentukan apakah jawaban dari pertanyaan berada pada posisi mendatar atau menurun pada papan matriks. Nilai dari atribut orientasi adalah 0 atau 1. Jika nilai dari atribut orientasi 0, pertanyaan tersebut termasuk dalam kategori menurun, sebaliknya apabila nilai atribut orientasi adalah 1, maka pertanyaan tersebut masuk dalam kategori mendatar. Sebagai contoh akan dibentuk sebuah TTS dari lima buah pertanyaan, dengan jawaban dari masing-masing pertanyaannya disajikan pada Tabel 6.. Tabel 6. Contoh Pertanyaan Pertanyaan Besar Tidak Kering Hewan Air Benar (Inggris) Hujan Rintik-rintik
Jawaban AKBAR BASAH IKAN TRUE GERIMIS
Id 1 2 3 4 5
Dari jawaban pertanyaan di atas maka dapat dibentuk sebuah kromosom seperti berikut ini:
Gambar 6. Panjang kromosom Panjang kromosom di atas adalah lima, sesuai dengan jumlah gen yang terdapat pada kromosom. Dari kromosom tersebut dapat dilihat pertanyaan yang digunakan sebanyak lima. Jawaban dari pertanyaan-pertanyaan tersebut, satu demi satu diletakkan pada papan matriks untuk dibentuk menjadi sebuah TTS. Jawaban dari pertanyaan-pertanyaan diletakkan secara berurutan diawali dari gen pertama sampai dengan gen yang terakhir. Setiap huruf dari sebuah jawaban akan menempati sebuah koordinat (x, y) pada papan matriks. Untuk jawaban pertanyaan yang ada pada gen 1, huruf pertamanya berada pada koordinat (100,100), 186
sedangkan koordinat untuk jawaban yang terdapat pada gen berikutnya ditentukan dengan mencari perpotongan dari jawaban tersebut dengan jawaban yang sebelumnya yang sudah terletak pada papan matriks. Berdasarkan bentuk kromosom pada gambar di atas maka jawaban pertama yang akan diletakkan pada papan matriks adalah jawaban dari pertanyaan dengan id 5, yaitu “GERIMIS” dengan posisi menurun. Huruf pertama dari kata “GERIMIS” akan diletakkan pada koordinat (100,100), sehingga pada saat kata “GERIMIS” tersebut diletakkan pada papan matriks hasilnya adalah sebagai berikut:
Gambar 7. Bentuk kromosom gerimis Sebelumnya setiap koordinat yang ditempati oleh setiap huruf disimpan dalam sebuah array yang berbeda. Selain itu, koordinat setiap titik potong yang terjadi juga disimpan dalam sebuah array. Dengan demikian diperlukan tiga buah array dimana array pertama akan berisi koordinat setiap huruf pada jawaban pertanyaan menurun, array kedua berisi koordinat setiap huruf pada jawaban pertanyaan mendatar dan array ketiga digunakan untuk menyimpan koordinat titik potong yang terjadi. Berdasarkan Gambar 9. maka isi dari matriks yang digunakan untuk menyimpan koordinat setiap huruf untuk jawaban pertanyaan menurun ditunjukkan pada Gambar 8:
Gambar 8. Koordinat titik potong Jawaban pertanyaan yang diletakkan pada papan matriks berikutnya adalah jawaban pertanyaan yang berada pada gen kedua yang merupakan jawaban dari pertanyaan dengan id 3, yaitu “IKAN” dengan posisi mendatar. Untuk menentukan koordinat dari kata “IKAN”, perlu dilakukan pencarian titik perpotongan antara kata “IKAN” dengan kata yang sudah berada dalam papan matriks. Karena kata IKAN mempunyai posisi mendatar, kata “IKAN” harus berpotongan dengan kata dalam papan matriks yang mempunyai posisi menurun, yaitu kata “GERIMIS”. Untuk mencari titik perpotongan,dilakukan pencocokan setiap huruf dari kata “IKAN” dengan setiap huruf yang ada pada papan matriks. Pencocokan dilakukan secara berurutan dimulai dari huruf pertama yaitu “I”. Untuk mengoptimalkan proses pencocokan, tidak setiap koordinat pada papan matriks dicek. Pengecekan hanya dilakukan pada area yang sudah terisi oleh jawaban yang sebelumnya telah diletakkan. Pada gambar di bawah ini dapat dilihat bahwa area yang akan diperiksa (diarsir) berada pada koordinat (100,100) sampai (100,106).
187
Gambar 9. pencarian titik potong Setelah proses pencarian ditemukan huruf I pada koordinat (100,103). Sebelum koordinat tersebut dipilih sebagai alternatif titik potong, karena gen kedua mempunyai orientasi mendatar, terlebih dahulu diseleksi apakah huruf I pada koordinat (100,103) tersebut dimiliki oleh jawaban pertanyaan menurun, karena jawaban pertanyaan mendatar hanya dapat berpotongan dengan jawaban pertanyaan menurun. Untuk mengecek apakah huruf I pada koordinat (100,103) merupakan jawaban pertanyaan menurun, dilakukan dengan mengecek isi dari array yang digunakan untuk menyimpan koordinat setiap huruf dari jawaban menurun. Kalau koordinat (100,103) ada di dalam array tersebut, maka huruf I pada koordinat (100,103) merupakan jawaban dari pertanyaan menurun. Berdasarkan Gambar 8. dapat dilihat bahwa koordinat (100,103) ada di dalam array yang digunakan untuk menyimpan jawaban pertanyaan menurun. Dapat disimpulkan bahwa huruf I pada koordinat (100,103) adalah jawaban dari pertanyaan menurun. Setelah diketahui bahwa huruf I pada koordinat (100,103) adalah jawaban pertanyaan dari pertanyaan menurun, selanjutnya dicek apakah huruf I pada koordinat (100,103) merupakan titik potong. Ini dilakukan karena satu titik potong hanya boleh dimiliki oleh dua buah jawaban pertanyaan, yaitu satu jawaban pertanyaan mendatar dan satu jawaban pertanyaan menurun. Untuk mengetahui apakah huruf I pada koordinat (100,103) merupakan titik potong, dilakukan dengan mengecek isi dari array yang digunakan untuk menyimpan koordinat titik potong yang terjadi. Apabila koordinat tersebut ada dalam array tersebut, maka huruf I pada koordinat tersebut merupakan titik potong. Berdasarkan Gambar 7. dapat dilihat bahwa belum ada titik potong yang terjadi. Dengan demikian array yang digunakan untuk menyimpan titik potong masih kosong, sehingga dapat disimpulkan bahwa koordinat (100,103) bukan merupakan titik potong. Kemudian dicek apakah papan matriks pada koordinat (100,103) sampai (103,103) kosong. Jika tidak kosong maka dicek apakah koordinat tersebut ada dalam array untuk menyimpan koordinat jawaban menurun. Ini dilakukan untuk menghitung titik potong yang terjadi jika jawaban pertanyaan diletakkan pada koordinat (100,103). Jika ada maka koordinat tersebut masih memenuhi syarat untuk dijadikan sebagai alternatif titik potong. Berdasarkan Gambar 9. dapat dilihat bahwa papan matriks pada koordinat (100,103) berisi I. Karena koordinat (100,103) ada dalam array tempat menyimpan koordinat jawaban menurun, maka koordinat (100,103) merupakan titik potong. Kemudian koordinat (101,103) sampai koordinat (103,103) masih kosong. Dengan demikian titik potong yang ditemukan adalah 1. Selanjutnya dicek apakah papan matriks pada koordinat (100,102) sampai koordinat (103,102) kosong. Jika tidak kosong selanjutnya dicek apakah mempunyai absis yang sama dengan titik potong. Jika tidak maka koordinat (100,103) tidak bisa dijadikan sebagai 188
alternatif titik potong. Ini dilakukan agar tidak ada jawaban pertanyaan mendatar yang terletak saling bersebelahan dengan jawaban pertanyaan mendatar yang lain. Berdasarkan Gambar 9. dapat dilihat bahwa papan matriks pada koordinat (100,102) berisi huruf R. Karena mempunyai absis yang sama dengan titik potong (100) maka kondisi ini masih memenuhi untuk dijadikan sebagai alternatif titik potong. Kemudian dicek isi papan matriks pada koordinat (100,104) sampai koordinat (103,104) apakah kosong. Jika tidak kosong, dicek apakah mempunyai absis yang sama dengan titik potong. Jika ya maka koordinat tersebut masih memenuhi syarat untuk dijadikan sebagai alternatif titik potong. Berdasarkan Gambar 9. dapat dilihat bahwa koordinat (100,104) berisi huruf M. Karena mempunyai absis yang sama dengan titik potong (100) maka koordinat (100,103) masih memenuhi untuk dijadikan sebagai alternatif titik potong. Selanjutnya dicek isi papan matriks pada koordinat (101,104) sampai (103,104). Karena papan matriks pada koordinat tersebut kosong maka jawaban pertanyaan dapat diletakkan pada koordinat (100,103). Apabila koordinat (100,103) diambil sebagai titik potong, maka isi dari papan matriks akan tampak pada Gambar 10 sebagai berikut:
Gambar 10. Kromosom Gerimis dan Ikan alternative Langkah selanjutnya adalah menghitung nilai gen dari alternatif titik potong tersebut. Berdasarkan Gambar 10. di atas, maka nilai gennya adalah: Nilai gen: 1/4 = 0,25. Nilai gen dan alternatif posisi titik potong di atas disimpan. Kemudian dicari huruf I yang lain di dalam papan matriks untuk mencari kemungkinan alternatif titik potong yang lain. Berdasarkan Gambar 9. dapat dilihat bahwa huruf I yang lain berada pada koordinat (100,105). Huruf I pada koordinat (100,105) ini selanjutnya dicek apakah merupakan jawaban pertanyaan menurun karena jawaban ”IKAN” berada pada posisi mendatar. Caranya adalah dengan mengecek isi dari array yang digunakan untuk menyimpan koordinat setiap huruf pada jawaban menurun. Berdasarkan Gambar 8. dapat diketahui bahwa koordinat (100,105) terdapat dalam array yang digunakan untuk menyimpan koordinat setiap huruf untuk jawaban menurun. Setelah diketahui bahwa huruf I pada koordinat (100,105) adalah jawaban pertanyaan menurun, selanjutnya dicek apakah huruf I pada koordinat (100,105) merupakan titik potong. Caranya adalah dengan memeriksa apakah koordinat (100,105) ada dalam array yang digunakan untuk menyimpan koordinat titik potong yang terjadi. Berdasarkan Gambar 8. dapat dilihat bahwa belum ada titik potong yang terjadi, dengan demikian array yang digunakan untuk menyimpan titik potong masih kosong. Dengan demikian huruf I pada koordinat (100,105) bukan merupakan titik potong, sehingga dapat dijadikan sebagai alternatif titik potong. Apabila huruf I pada koordinat (100,105) dijadikan sebagai alternatif titik potong, maka isi papan matriks akan tampak pada Gambar 11. berikut:
189
Gambar 11. Kromosom Gerimis dan Ikan alternative
Langkah selanjutnya adalah menghitung nilai gen dari alternatif titik potong di atas. Nilai gen untuk alternatif titik potong adalah: Nilai gen :1/4 = 0,25. Selanjutnya dilakukan hal yang sama dengan huruf yang berikutnya yaitu huruf K. Sama dengan mencari huruf I pada papan matriks, proses pencarian huruf K juga dilakukan pada koordinat (100,100) sampai koordinat(100,106) seperti tampak pada Gambar 12. berikut:
Gambar 12. Pencarian titik potong Langkah selanjutnya begitu seterusnya sehingga pada gambar di atas terlihat bahwa untuk jawaban pertanyaan yang terdapat pada gen keempat dan gen kelima tidak diletakkan dalam papan matriks. Hal ini disebabkan pada saat jawaban pertanyaan pada gen keempat, yaitu TRUE, akan diletakkan titik potong tidak berhasil ditemukan. Ketentuan lain yang digunakan untuk meletakkan jawaban pertanyaan pada papan matriks adalah sebagai berikut: a. Sebuah titik potong hanya boleh dimiliki oleh dua buah jawaban saja. Contohnya dapat dilihat pada Gambar 13.:
Gambar 13. papan matrik titik potong Pada Gambar 5.3 titik potong pada koordinat (100,104) dimiliki oleh tiga jawaban pertanyaan sekaligus, yaitu “GERIMIS”, “SATU”, dan, “SUKA”. 190
b. Fungsi Objektif Setelah populasi terbentuk, pada tahap selanjutnya dilakukan penghitungan nilai fitness masing-masing kromosom yang ada dalam populasi. Penghitungan nilai fitness diperoleh berdasarkan jumlah jawaban yang berhasil dibentuk menjadi TTS dan jumlah titik perpotongan yang dihasilkan oleh tiap-tiap jawaban pertanyaan. Nilai gen yang dihitung adalah apabila jawaban pertanyaan pada gen tersebut termasuk jawaban pertanyaan yang dapat dibentuk menjadi TTS. Apabila jawaban pertanyaan pada gen tersebut tidak dapat dibuat menjadi TTS (tidak dapat berpotongan dengan jawaban pertanyaan lain) maka gen tersebut diberi nilai 0, dan gen setelah gen tersebut tidak akan dihitung. Nilai fitness suatu kromosom ditentukan dari nilai masing-masing gen. Nilai untuk setiap gen ke-j dapat dihitung dengan persamaan berikut: gen[j]=(p/k) (1) gen[j] : nilai gen ke-j p : jumlah titik potong pada gen tersebut k : jumlah karakter pada gen tersebut Nilai fitness sebuah kromosom adalah total nilai gen pada kromosom tersebut yang berhasil dibuat menjadi TTS. Fungsi objektif untuk menghitung nilai fitness suatu kromosom adalah sebagai berikut:
(2) F : nilai fitness Gen[j] : nilai gen ke-j pada kromosom tersebut c. Skema Seleksi Proses seleksi akan memilih kromosom untuk dijadikan sebagai calon parent pada proses crossover. Proses seleksi akan membentuk sebuah populasi baru yang berisi kromosom calon parent. Metode seleksi yang digunakan adalah Rank Selection. Pada Rank Selection kromosom terlebih dahulu diranking sesuai dengan nilai fitness-nya, kemudian kromosom diberi nilai fitness sesuai rankingnya dengan nilai fitness maksimum adalah sama dengan ukuran populasi. Apabila ada 30 kromosom pada populasi, maka nilai fitness untuk kromosom dengan ranking 1 adalah 30, nilai fitness untuk kromosom dengan ranking 2 adalah 29 dan seterusnya sampai kromosom dengan ranking 30 dengan nilai fitness 1. Dengan demikian kromosom dengan nilai fitness yang kecil tetap punya kesempatan untuk terpilih. d. Parameter Crossover (PC) Crossover atau perkawinan silang adalah proses pembentukan kromosom baru (offspring). Kromosom yang akan mengalami crossover adalah kromosom calon parent yang sudah terpilih melalui proses seleksi. Namun tidak semua kromosom yang terpilih melalui proses seleksi akan mengalami proses crossover. Jumlah kromosom calon parent yang mengalami crossover ditentukan oleh parameter crossover (PC). Nilai PC mempunyai range antara 01. Semakin besar nilai PC maka semakin banyak kromosom yang mengalami crossover. Jika nilai PC sama dengan 0 maka tidak akan ada kromosom yang mengalami proses crossover. Sebaliknya apabila nilai PC sama dengan 1 maka semua kromosom akan mengalami crossover. Apabila tidak ada kromosom yang mengalami crossover maka tidak banyak variasi kromosom yang bisa tercipta, namun apabila terlalu banyak kromosom yang mengalami proses crossover, maka proses komputasi akan semakin besar. Dengan mempertimbangkan faktor tersebut maka nilai PC yang dipakai pada penelitian ini adalah 191
0.5, sehingga diharapkan setengah dari kromosom yang berada pada populasi calon parent akan mengalami crossover. e. Skema Crossover Untuk pengkodean permutasi, metode crossover yang digunakan adalah single point cross over. Untuk memilih kromosom yang menjadi parent, dibangkitkan bilangan random R sebanyak 30 kali, dimana 30 adalah ukuran populasinya. Apabila Ri < PC, maka kromosom i terpilih sebagai parent. Contoh proses untuk memilih kromosom yang akan mengalami crossover dapat dilihat pada Tabel 7.. PC yang digunakan adalah 0.5. Tabel 7. contoh proses memilih parent No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Bilangan Random -r 0.45 0.63 0.71 0.34 0.15 0.23 0.66 0.22 0.11 0.23 0.65 0.84 0.94 0.10 0.02 0.45 0.63 0.71 0.34 0.15 0.23 0.65 0.22 0.11 0.23 0.65 0.84 0.94 0.10 0.02
Terpilih Ya Tidak Tidak Ya Ya Ya Tidak Ya Ya Ya Tidak Tidak Tidak Ya Ya Ya Tidak Tidak Ya Ya Ya Tidak Ya Ya Ya Tidak Tidak Tidak Ya Ya
No 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Bilangan Random -r 0.35 0.77 0.84 0.14 0.70 0.69 0.96 0.88 0.77 0.63 0.44 0.32 0.25 0.15 0.10 0.35 0.77 0.84 0.14 0.70 0.69 0.96 0.88 0.77 0.63 0.44 0.32 0.25 0.15 0.10
Terpilih Ya Tidak Tidak Ya Tidak Tidak Tidak Tidak Tidak Tidak Ya Ya Ya Ya Ya Ya Tidak Tidak Ya Tidak Tidak Tidak Tidak Tidak Tidak Ya Ya Ya Ya Ya
Pada tabel di atas dapat dilihat kromosom terpilih yang akan mengalami crossover. Pada tabel di atas nilai bilangan random ke 1 (r1) adalah 0.45, karena r1 < PC (0.45 < 0.5) maka kromosom 1 terpilih sebagai parent. Kemudian nilai r2 adalah 0.63, karena r2 > PC maka kromosom 2 tidak terpilih sebagai parent. Demikian seterusnya sampai kromosom ke 30 sehingga ada 16 kromosom yang akan mengalami crossover. Pasangan yang akan mengalami crossover diambil secara berurutan. Pada tabel di atas maka kromosom 1 akan berpasangan dengan kromosom 4, kromosom 5 akan berpasangan dengan kromosom 6, kromosom 8 berpasangan dengan kromosom 9 dan seterusnya. Apabila jumlah kromosom yang terpilih adalah ganjil maka kromosom yang terakhir terpilih tidak akan mengalami crossover karena tidak mempunyai pasangan. Contoh crossover dapat dilihat pada Gambar 14. berikut ini. 192
Gambar 14. proses crossover Pada gambar di atas dapat dilihat bahwa proses crossover menggunakan single point crossover. Pada offspring 1, gen 1 sampai dengan gen 3 di ambil dari gen 1 sampai dengan gen 3 pada parent 1. Kemudian gen 4 dan gen 5 pada offspring 1 diambil dari parent 2. Gen yang diambil dari parent 2 adalah gen dengan atribut id pertanyaan yang belum ada pada gen yang diambil dari parent 1 sebelumnya. Gen yang diambil dari parent 1 mempunyai atribut id 5,3 dan 2, maka gen yang diambil dari parent 2 adalah gen 2 yang mempunyai atribut id 1 dan gen 5 yang mempunyai atribut id 4. Pada offspring 2, gen 1 sampai dengan gen 3 diambil dari gen 1 sampai dengan gen 3 pada parent 2. Kemudian gen 4 dan gen 5 pada offspring 2 diambil dari parent 1. Gen yang diambil dari parent 1 adalah gen dengan atribut id pertanyaan yang belum ada pada gen yang diambil dari parent 2 sebelumnya. Gen yang diambil dari parent 2 mempunyai atribut id 2,1 dan 5, maka gen yang diambil dari parent 2 adalah gen 2 yang mempunyai atribut id 3 dan gen 4 yang mempunyai atribut id 4. f. Jumlah Generasi Semakin banyak jumlah pertanyaan, maka semakin banyak pula jumlah generasi. g. Skema Update Generasi Metode update generasi yang digunakan adalah dengan memilih 30 kromosom dengan nilai fitness terbaik. Kromosom yang dipilih adalah kromosom yang dihasilkan dari proses seleksi dan kromosom yang dihasilkan dari proses crossover. 1) Menghitung nilai fitness
Gambar 15. Papan Matriks
Tabel 8. Penghitungan nilai fitness
Dari tabel di atas dapat dilihat bahwa nilai fitness kromosom pada Gambar 5. adalah 0,74. 2) Proses bermain TTS
193
Pengguna memasukkan jawaban dari pertanyaan TTS. Selanjutnya, aplikasi akan menilai jawaban yang dimasukkan pengguna kemudian memberikan jawaban yang benar kepada pengguna. 3) Flowchart Pembentukan TTS
Gambar 16. Diagram alir algoritma genetika yang digunakan
Gambar 17. Rancangan dari form TTS Baru
Gambar 18. rancangan form TTS
Gambar 19. Rancangan sub menu bank soal
Gambar 20. Daftar soal dan jawabn
4. Hasil dan Pembahasan Pengguna memasukkan jumlah pertanyaan, misalkan 10 soal, kemudian aplikasi akan memilih pertanyaan yang akan digunakan dalam TTS secara random. Setiap pertanyaan hanya boleh diambil sekali, atau dipilih secara random oleh program. Setelah pertanyaan dipilih, maka pertanyaan tersebut diproses dengan algoritma genetika untuk dibentuk menjadi sebuah TTS. Melalui proses algoritma genetika maka kromosom terbaik akan dibentuk 194
menjadi TTS. Waktu yang digunakan untuk memproses juga ditampilkan di layar. Gambar 17 di bawah ini adalah TTS hasil dari jumlah soal sebanyak 10.
Gambar 21. Form soal teka teki silang 5. Kesimpulan Algoritma genetika dapat digunakan untuk membuat TTS. Beberapa kesimpulan yang dapat diambil antara lain sebagai berikut: 1. Karena pemilihan soal adalah acak, aplikasi bisa tidak berhasil membuat TTS dengan jumlah pertanyaan seperti yang diinputkan pengguna. 2. Dari hasil pengujian, dapat dilihat bahwa waktu komputasi yang diperlukan untuk membuat TTS sebanding dengan jumlah soal yang digunakan. Referensi [1] Edison Sinaga, 2009., Skripsi: Implementasi Algoritma Genetika Dalam Penyusunan Teka-Teki Silang,STMIK Mikroskil, Medan [2] Kusumadewi, Sri. 2003. Artificial Intelligenci, Teknik dan Aplikasinya, Yogyakarta: Penerbit Graha Ilmu. [3] Lingga, D.E dan Arlando R..2008, Aplikasi algoritma genetika untuk mengoptimalkan pola radiasi susunan antena. [4] Pandjaitan, L.W.2007. Dasar-DasarKomputasi Cerdas. Yogyakarta: Penerbit Andi. [5] Robandi, Imam. 2006. Desain Sistem Tenaga Modern, Optimisasi, Logika Fuzzy, Algoritma Genetika. Yogyakarta: Penerbit Andi.
195
