Sudoku dengan menggunakan Algoritma Genetika.
Dalam
membuat puzzle Sudoku harus memiliki solusi. Pengguna permainan kemudian dapat
melakukan permainan untuk menyelesaikan puzzle tersebut. Kemudian untuk penyelesaian
puzzle menggunakan Algoritma Genetika. Sebelum memasuki proses tersebut,
terlebih dahulu dicari kandidat-kandidat solusi untuk masing-masing kotak
puzzle. Hal ini bertujuan untuk mengeliminasi kandidat-kandidat solusi yang
tidak mungkin.
Contoh, jika suatu kotak telah terisi dengan angka 9, maka angka 9 tersebut dieliminasi dari kandidat pada kotak-kotak di baris, kolom, dan region yang sama.
Contoh, jika suatu kotak telah terisi dengan angka 9, maka angka 9 tersebut dieliminasi dari kandidat pada kotak-kotak di baris, kolom, dan region yang sama.
Dengan
langkah tersebut, diharapkan Algoritma Genetika akan memiliki konvergensi yang
baik. Solusi dari suatu puzzle diapatkan jika suatu kromosom memiliki nilai fitness
yang sempurna, karena kromosom dengan nilai fitness di bawah nilai fitness
sempurna berarti bukan solusi dari puzzle Sudoku.
Pada
Algoritma Genetika, satu kromosom adalah satu kandidat solusi puzzle. Karena
nilai yang mungkin pada solusi adalah antara 1 sampai dengan 9, maka
representasi kromosom yang digunakan adalah deretan bilangan bulat (integer)
dengan panjang kromosom sama dengan jumlah kotak yang kosong pada puzzle. Nilai
fitness diambil dari panjang kromosom dikurangi dengan jumlah gen error.
Gen error adalah gen yang berisi angka
yang berulang pada baris, kolom, atau region. Metode seleksi yang digunakan
adalah Roulette-Wheel.
Puzzle
Sudoku direpresentasikan dengan array dua dimensi. Puzzle ini harus memenuhi
aturan dalam permainan Sudoku, yaitu tidak boleh ada angka yang berulang pada
baris, kolom, dan region. Puzzle ini kemudian dikosongkan beberapa kotaknya
yang jumlahnya tergantung pada tingkat kesulitan permainan. Tekniknya,
kandidat-kandidat pada setiap cell direpresentasikan dengan sebuah List. Pada
kondisi awal, list tersebut berisi angka 1 hingga 9. Karena papan berukuran
9x9, penyimpanan cell-cell tersebut dilakukan menggunakan array dua dimensi
dengan ukuran 9x9. Kemudian looping dilakukan untuk semua cell tersebut, dari
kiri ke kanan, atas ke bawah. Untuk masing-masing cell, diambil angka secara
random dari kandidat-kandidat yang tersedia untuk cell tersebut. Kemudian angka
yang terpilih tersebut dihapuskan dari kandidat pada cell-cell pada baris,
kolom, dan region yang sama. Dengan teknik ini, satu puzzle Sudoku yang valid
dapat dibangkitkan dalam waktu yang cukup cepat (< 1 detik).
Kromosom
adalah representasi solusi dari suatu masalah pada Algoritma Genetika. Pada Sudoku,
kromosom adalah representasi suatu solusi dari puzzle yang berisi angka-angka
yang akan diisikan pada kotak-kotak yang kosong sehingga panjang kromosom
adalah sama dengan jumlah kotak yang kosong pada puzzle. Nilai untuk
masing-masing gen pada kromosom diambil secara acak dari kandidat-kandidat pada
setiap cell. Kandidat nilai untuk setiap kromosom adalah angka 1 hingga 9. Pada
pemrograman, kromosom direpresentasikan dengan array of integer (int[]).
Untuk
menghitung nilai fitness masing-masing kromosom, terlebih dahulu
dihitung jumlah angka yang berulang pada baris, kolom, dan region pada puzzle
setelah angka-angka pada kromosom diisikan pada kotak-kotak yang kosong pada
puzzle. Fungsi fitness yang digunakan cukup sederhana, yaitu adalah
pengurangan panjang kromosom dengan jumlah angka yang berulang sehingga
kromosom yang merupakan solusi puzzle adalah kromosom yang mempunyai nilai fitness
sebesar panjang kromosom.
Metode
seleksi yang digunakan adalah metode Roulette-Wheel yang membuat
kromosom-kromosom dengan nilai fitness tinggi memiliki kemungkinan
terpilih yang tinggi pula. Probabilitas keterpilihan setiap kromosom ditentukan
dengan cara membagi nilai fitness kromosom tersebut dengan total nilai fitness.
Untuk itu, yang terlebih dahulu harus dihitung adalah total nilai fitness.
Kemudian dilakukan pembagian masing-masing nilai fitness dengan total fitness
tersebut. Nilai tersebut adalah probabilitas setiap kromosom yang berkisar
antara nol dan satu. Kemudian pada proses pemutaran roda roulette,
teknisnya juga sederhana. Suatu bilangan acak dibangkitkan, dengan jangkauan
nilai antara nol dan satu. Nilai acak tersebut kemudian dibandingkan dengan
nilai probabilitas masing-masing kromosom. Pembandingan dilakukan dari kromosom
yang terkecil. Kromosom yang memiliki nilai fitness yang lebih besar
atau sama dengan nilai acak akan menjadi individu yang terpilih.
Source
: http://www.eepis-its.edu/uploadta/downloadmk.php?id=1221