Improving Performance of The Genetic Algorithm on NP-Complete Problem

Herimanto Herimanto, Muhammad Zarlis, Syahril Efendi

Abstract


Non-Deterministic Polynomial Complete Problem is the most challenging problem and also engaging in algorithm strategy. One representation of this problem is the sudoku numbers game. To fill an empty sudoku puzzle, a specific formula does not apply, but filling in sudoku is a matter of decision. So it takes a special algorithm and strategy to solve it. As such, the case of the sudoku numbers game has been widely praised as the topic of finding the best results. One of the methods used is a genetic algorithm. However, due to many processes and data used in the implementation of genetic algorithms, the results obtained are often not optimal. This research will introduce a special strategy in implementing genetic algorithms in NP-Complete problems, namely by optimizing the genetic algorithm in the process of population formation. From the test results, it is found that the application of the genetic algorithm with optimization results in smaller time data and test data compared to the algorithm without optimization.

Keywords


Algorithm Strategy, Genetic, Optimization

Full Text:

PDF

References


E. Utami, J. Istiyanto, and S. Raharjo, Metodologi Penelitian Pada Ilmu Komputer. Yogyakarta,: Seminar Nasional Teknologi 2007 (SNT 2007), 2007.

K. De Jong, J. William, and W. Spears, “Using Genetic Algorithms to Solve NP-Complete Problems,” Proceedings Of The Third International Conference On Genetic Algorithms, vol. 3, pp. 124–132, Jul. 1998.

D. I. R. Munir, “Teori P, NP, dan NP-Complete,” Bahan Kuliah IF2211 Strategi Algoritma Program Studi Teknik Informatika ITB, p. 36, 2018.

A. Milton and C. Ortega-Sanchez, “Development and analysis of genetic algorithms: Sudoku case study,” in TENCON 2012 IEEE Region 10 Conference, Cebu, Philippines, Nov. 2012, pp. 1–6, doi: 10.1109/TENCON.2012.6412205.

D. J. M. Weiss, “Genetic Algorithms and Sudoku,” Midwest Instruction and Computing Symposium, vol. 1, no. 4 April 2009, p. 9, 2009.

N. Thirer, “About the FPGA implementation of a genetic algorithm for solving Sudoku puzzles,” in 2012 IEEE 27th Convention of Electrical and Electronics Engineers in Israel, Eilat, Israel, Nov. 2012, pp. 1–3, doi: 10.1109/EEEI.2012.6377058.

T. Mantere and J. Koljonen, “Solving, rating and generating Sudoku puzzles with GA,” in 2007 IEEE Congress on Evolutionary Computation, Singapore, Sep. 2007, pp. 1382–1389, doi: 10.1109/CEC.2007.4424632.

Y. Sato and H. Inoue, “Solving Sudoku with genetic operations that preserve building blocks,” in Proceedings of the 2010 IEEE Conference on Computational Intelligence and Games, Copenhagen, Denmark, Aug. 2010, pp. 23–29, doi: 10.1109/ITW.2010.5593375.

M. Mitchell, An introduction to genetic algorithms, 7. print. Cambridge, Mass., 1999.

B. H. Arabi, “Solving NP-complete Problems Using Genetic Algorithms,” in 2016 UKSim-AMSS 18th International Conference on Computer Modelling and Simulation (UKSim), Cambridge, United Kingdom, Apr. 2016, pp. 43–48, doi: 10.1109/UKSim.2016.65.

F. Gerges, G. Zouein, and D. Azar, “Genetic Algorithms with Local Optima Handling to Solve Sudoku Puzzles,” in Proceedings of the 2018 International Conference on Computing and Artificial Intelligence - ICCAI 2018, Chengdu, China, 2018, pp. 19–22, doi: 10.1145/3194452.3194463.

Afriyudi, Anggoro Suryo Pramudyo, and M. Akbar, “Penyelesaian Puzzle Sudoku menggunakan Algoritma Genetik,” 2008, doi: 10.13140/RG.2.1.4921.6726.




DOI: https://doi.org/10.30743/infotekjar.v6i1.3909

Refbacks

  • There are currently no refbacks.


Copyright (c) 2021 Herimanto, Muhammad Zarlis, Syahril Efendi

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

InfoTekJar (Jurnal Nasional Informatika dan Teknologi Jaringan)

Program Studi Teknik Informatika - Universitas Islam Sumatera Utara
Website : http://jurnal.uisu.ac.id/index.php/infotekjar/index
Email : infotekjar@ft.uisu.ac.id

InfoTekJar : Jurnal Nasional Informatika dan Teknologi Jaringan) is licensed under a Creative Commons Attribution 4.0 International License