Implementation of the Firefly Algorithm in the Case of N-Queens Problem
Implementasi Algoritma Firefly pada Kasus N-Queens Problem
Abstract
N-Queen problem is a form of puzzle game that uses chess rules for the queen on the standard chessboard with modified size. The challenge of the n-queen problem is finding the N ( N is positive integer) queens position on the chessboard, so that no queen can attack another queen on the board in a single move. Implementation of firefly algorithm in n-queens problem in this study aims to find n-queen problem solutions and count the number of iterations to achieve the optimal solution of each queen which will then be compared with the results of Sarkar and Nag's research (2017). This study uses an experimental method with a number of N between 10 to 20 and uses a population of 15 and 1000 firefly. The results showed that the firefly algorithm is able to find all the optimal solutions for the queen's position on a chessboard with dimensions 10 to 20 in a population of 1000 firefly. The firefly algorithm can find the optimal solution fewer iterations compared to the genetic algorithm. According to the experiment, firefly algorithm shows better performance in finding the optimal solution compared to genetic algorithm.
Downloads
References
Y. Huang, “Computing quantum discord is NP-complete Computing quantum discord is NP-complete,” 2014.
L. Bianchi, M. Dorigo, L. M. Gambardella, and W. J. Gutjahr, “A survey on metaheuristics for stochastic combinatorial optimization,” Nat. Comput., vol. 8, no. 2, pp. 239–287, 2009.
E.-G. Talbi, METAHEURISTICS - From Design To Implementation, vol. 66. 2012.
S. Desale, A. Rasool, S. Andhale, and P. Rane, “Heuristic and Meta-Heuristic Algorithms and Their Relevance to the Real World: A Survey,” Int. J. Comput. Eng. Res. Trends, vol. 351, no. 5, pp. 2349–7084, 2015.
C. A. Cusack, “Online Games as Social-Computational Systems for Solving NP-complete Problems Running Head : SOCIAL-COMPUTATIONAL GAMES Online Games as Social-Computational Systems for Solving NP-complete Problems Charles A . Cusack , Jeff Largent , Ryan Alfuth , Kimberly Klask Hope College,” no. January, 2015.
S. Sathyapriya, R. Stephen, and V. S. J. Irudayaraj, “Survey on N-Queen Problem with Genetic Algorithm,” no. 2, pp. 54–59, 2018.
U. Sarkar and S. Nag, “An Adaptive Genetic Algorithm for Solving N-Queens Problem,” 2017.
A. S.Farhan, W. Z. Tareq, and F. H. Awad, “Solving N Queen Problem using Genetic Algorithm,” Int. J. Comput. Appl., vol. 122, no. 12, pp. 11–14, 2015.
W. N. Mahfud, “Penerapan Algoritma Kunang-kunang (Firefly Algorithm) Dalam Knight Tour Problem Pada Papan Catur,” Biomass Chem Eng, vol. 49, no. 23–6, pp. 22–23, 2015.
A. Hatamlou, “Solving Travelling Salesman Problem Using Heart Algorithm,” Int. J. Appl. Evol. Comput., vol. 8, no. 4, pp. 32–42, 2018.
A. Habiboghli and T. Jalali, “A Solution to the N-Queens Problem Using Biogeography-Based Optimization,” Int. J. Interact. Multimed. Artif. Intell., vol. 4, no. 4, p. 20, 2017.
S. Alharbi and I. Venkat, “A Genetic Algorithm Based Approach for Solving the Minimum Dominating Set of Queens Problem,” vol. 2017, 2017.
Z. Wang, D. Huang, J. Tan, T. Liu, K. Zhao, and L. Li, “BioSystems A parallel algorithm for solving the n -queens problem based on inspired computational model,” BioSystems, vol. 131, pp. 22–29, 2015.
S. Mukherjee, S. Datta, P. B. Chanda, and P. Pathak, “Comparative Study of Different Algorithms to Solve N Queens Problem,” Int. J. Found. Comput. Sci. Technol., vol. 5, no. 2, pp. 15–27, 2015.
S. Nickolas, “Institutional Repository A hybrid discrete firefly algorithm for solving multi-objective flexible job shop scheduling problems,” pp. 0–26, 2015.
A. Baykaso and F. B. Ozsoydan, “Adaptive firefly algorithm with chaos for mechanical design optimization problems,” vol. 36, pp. 152–164, 2015.
R. Moazenzadeh, B. Mohammadi, S. Shamshirband, and K. Chau, “Mechanics Coupling a firefly algorithm with support vector regression to predict evaporation in northern Iran,” vol. 2060, 2018.
V. Rajinikanth and M. S. Couceiro, “RGB Histogram based Color Image Segmentation Using Firefly Algorithm,” Procedia - Procedia Comput. Sci., vol. 46, no. Icict 2014, pp. 1449–1457, 2015.
J. Mathew and D. . Vijayakumar, “Scalable parallel clustering using modified Firefly algorithm,” IOSR J. Comput. Eng., vol. 16, no. 6, pp. 14–24, 2014.
S. Yu, S. Zhu, Y. Ma, and D. Mao, “A variable step size firefly algorithm for numerical optimization,” Appl. Math. Comput., vol. 263, pp. 214–220, 2015.
L. Olatomiwa, S. Mekhilef, S. Shamshirband, and K. Mohammadi, “ScienceDirect A support vector machine – firefly algorithm-based model for global solar radiation prediction,” vol. 115, pp. 632–644, 2015.
Y. Zhang and L. Wu, “Rigid image registration based on normalized cross correlation and chaotic firefly algorithm,” Int. J. Digit. Content Technol. its Appl., vol. 6, no. 22, pp. 129–138, 2012.
J. E. Aghazadeh Heris and M. A. Oskoei, “Modified genetic algorithm for solving n-queens problem,” 2014 Iran. Conf. Intell. Syst. ICIS 2014, 2014.
A. F. J. Al-gburi, S. Naim, and A. N. Boraik, “Hybridization of Bat and Genetic Algorithm to Solve N-Queens Problem,” vol. 7, no. 4, pp. 626–632, 2018.
R. G. Sharma, “Implementation of n-Queens Puzzle using Meta-heuristic algorithm ( Cuckoo Search ),” vol. 2, no. 3, 2013.
M. T. Sarvetamin, A. Khatibi, and M. H. Zahedi, “A New Approach to Solve N-Queen Problem with,” vol. 4, no. 2, 2018.
X. S. Yang, “Firefly algorithms for multimodal optimization,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 5792 LNCS, pp. 169–178, 2009.
Copyright (c) 2020 Jurnal RESTI (Rekayasa Sistem dan Teknologi Informasi)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Copyright in each article belongs to the author
- The author acknowledges that the RESTI Journal (System Engineering and Information Technology) is the first publisher to publish with a license Creative Commons Attribution 4.0 International License.
- Authors can enter writing separately, arrange the non-exclusive distribution of manuscripts that have been published in this journal into other versions (eg sent to the author's institutional repository, publication in a book, etc.), by acknowledging that the manuscript has been published for the first time in the RESTI (Rekayasa Sistem dan Teknologi Informasi) journal ;
