Analisis Kinerja Algoritma Genetika pada Persoalan NP-Complete

Abstract

NP-Complete problem is one of the difficult problems in algorithmic strategy, but also interesting. The Non-Deterministic Polynomial Complete Problem is interesting and difficult because until now there are so many studies that discussed and raised this topic but no one has been able to find the best algorithm for this case in terms of algorithm analysis. One of the topics that can represent the NP-Complete case is the number game sudoku. This game is actually simple, which is to enter a certain symbol into a puzzle containing 9x9 squares. However, in entering numbers and symbols, you must pay attention to some important rules in the game of sudoku, namely that there should be no repeated numbers/symbols in every row, column and block/region of sudoku. This makes sudoku numbers difficult and is classified as an NP-Complete problem. One of the heuristic methods, namely genetics, can be applied in solving sudoku problems. In this study, a special strategy for implementing genetic algorithms on the NP-Complete problem will be introduced, namely by optimizing the population formation process. From the test results, it is found that the application of optimization to the genetic algorithm results in a smaller computation time and amount of data than the genetic algorithm without optimization.

NP-Complete problem adalah salah satu persoalan sulit dalam bidang strategi algoritma namun juga menarik. Permasalahan Non-Deterministic Polynomial Complete Problem dikatakan menarik dan sulit karena hingga saat ini telah banyak penelitian yang membahas dan mengangkat topik ini namun belum ada satupun yang dapat menemukan algoritma terbaik untuk kasus tersebut dari segi analisis algoritma. Salah satu topik yang dapat merepresentasikan kasus NP-Complete adalah permainan angka sudoku. Permainan ini sebenarnya cukup sedarhana, yaitu memasukkan suatu simbol tertentu kedalam sebuah puzzle berisi 9x9 kotak. Namun dalam memasukkan angka maupun simbol harus memperhatikan beberapa aturan penting dalam permainan sudoku, yaitu tidak boleh ada angka/simbol berulang dalam setiap baris, kolom dan blok/region sudoku. Hal in menjadikan permainan angka sudoku menjadi sulit dan tergolong kedalam permasalahan NP-Complete. Salah satu metode heuristik yaitu genetika dapat diterapkan dalam menyelesaikan persoalan sudoku. Pada penelitian ini akan dikenalkan sebuah strategi khusus dalam implementasi algoritma genetika pada persoalan NP-Complete yaitu dengan melakukan optimasi pada proses pembentukan populasi. Dari hasil pengujian didapat penerapan optimasi pada algoritma genetika menghasilkan waktu komputasi dan jumlah data yang lebih kecil dibandingkan dengan algoritma genetika tanpa optimasi.