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.

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

Postingan populer dari blog ini

Bentuk sederhana dari Grafik Komputer

Step by Step Mendaftar Blog di Blogspot