PENERAPAN KECERDASAN KELOMPOK UNTUK PENYELESAIAN TEKA-TEKI SUDOKU DENGAN METODE PARTICLE SWARM OPTIMIZATION

AGUS LIMBANG WARDANI S KOM, Prof. Dra. Sri Hartati, M.Sc, Ph.D

2015 | Tesis | S2 Ilmu Komputer

Terdapat beberapa cara untuk menyelesaikan teka-teki sudoku dengan komputer yaitu Trial and Error, adaptasi dari intuisi manusia dan menggunakan algoritma optimasi. Particle Swarm Optimization (PSO) adalah salah satu dari metode optimasi yang tedapat dalam kecerdasan kelompok, yang mana populasi pada didasarkan pada penelusuran algoritma dan diawali dengan suatu populasi yang random yang disebut dengan particle. Penelitian ini dilakukan untuk menguji metode untuk menyelesaikan tekateki sudoku dengan beberapa tingkatan dimensi yaitu 4x4 sampai dengan 25x25. Pengujian dilakukan dengan melakukan perubahan jumlah partikel dan melihat pengaruhnya terhadap jumlah iterasi dan waktu tunggu. Hasil dari penelitian ini menunjukkan beberapa hal. Pertama, semakin besar nilai partikel menghasilkan jumlah iterasi yang cenderung menurun. Kedua, pada jumlah iterasi yang sama belum tentu menghasilkan waktu tunggu yang sama. Ketiga, bahwa jumlah iterasi yang lebih kecil belum tentu menghasilkan waktu tunggu yang lebih lama. Keempat, pada ukuran yang lebih besar belum tentu menghasilkan waktu tunggu yang lebih lama. Kelima, pada teka-teki yang memiliki banyak sel dengan kemungkinan satu angka valid atau sedikit kombinasi yang mungkin, PSO akan memperpendek jumlah iterasi, namun untuk teka-teki yang memiliki banyak sel dengan kemungkinan angka lebih dari 1 atau banyak kombinasi yang mungkin, PSO tidak banyak memberikan pengaruh. Keenam, pada dimensi yang besar terdapat perbedaan waktu tunggu yang signifikan antara jumlah partikel 1 dengan jumlah partikel 2 sampai 10. Ketujuh, Pada dimensi dengan bilangan prima cenderung memiliki jumlah iterasi yang lebih banyak dibanding dengan dimensi yang lain. Nilai velocity digunakan untuk menentukan jumlah pengacakan nilai partikel, sehingga partikel terkadang tidak selalu bergerak maju atau bernilai lebih baik.

There are several ways to solve sudoku puzzles with a computer that is Trial and Error, the adaptation of human intuition and using optimization algorithms. Particle Swarm Optimization (PSO) is one of the methods of optimization are found in a group of intelligence, which is based on the population of the algorithm searches and begins with a random population called particle. This study was conducted to test the PSO method to solve sudoku puzzle with several levels of dimensions 4x4 up to 25x25. Testing is done by changing the number of particles and see its effect on the value iteration and waiting time. The results of this study indicate several things. First, the greater the value of the particle yield tends to decrease the number of iterations. Second, the same number of iterations is not necessarily produce the same waiting time. Third, that the smaller the number of iterations is not necessarily produce a longer waiting time. Fourth, the larger size is not necessarily produce a longer waiting time. Fifth, the puzzle that has many cells with the possibility of a valid number or bit combinations are possible, PSO will shorten the number of iterations, but for the puzzle that has many possible numbers of cells with more than one or many combinations are possible, PSO not a lot of influence. Sixth, the large dimensions there are significant differences in waiting times between the number of particles 1 with the number of particles 2 to 10. Seventh, the dimensions of the primes tend to have a greater number of iterations when compared with other dimensions. The value of velocity is used to determine the value of randomization number of particles, so that the particles are sometimes not always move forward or better value.

Kata Kunci : -