CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Performance Analysis of N-Queen Problem using Backtracking and Genetic Algorithm Techniques

by Vikas Thada, Shivali Dhaka
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 102 - Number 7
Year of Publication: 2014
Authors: Vikas Thada, Shivali Dhaka
10.5120/17829-8667

Vikas Thada, Shivali Dhaka . Performance Analysis of N-Queen Problem using Backtracking and Genetic Algorithm Techniques. International Journal of Computer Applications. 102, 7 ( September 2014), 26-29. DOI=10.5120/17829-8667

@article{ 10.5120/17829-8667,
author = { Vikas Thada, Shivali Dhaka },
title = { Performance Analysis of N-Queen Problem using Backtracking and Genetic Algorithm Techniques },
journal = { International Journal of Computer Applications },
issue_date = { September 2014 },
volume = { 102 },
number = { 7 },
month = { September },
year = { 2014 },
issn = { 0975-8887 },
pages = { 26-29 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume102/number7/17829-8667/ },
doi = { 10.5120/17829-8667 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:32:31.359059+05:30
%A Vikas Thada
%A Shivali Dhaka
%T Performance Analysis of N-Queen Problem using Backtracking and Genetic Algorithm Techniques
%J International Journal of Computer Applications
%@ 0975-8887
%V 102
%N 7
%P 26-29
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper the research work has done comparative analysis of one of the famous NP hard problem: NQueen using traditional Backtraking and Genetic Algorithm(GA). The research work has implemented the solution of the NQueen problem using backtracking and using GA. Both the methods of solving NQueen problem are entirely different. The first one is general method and takes time in days , months and years as N increases. In this paper the time taken by the two methods for a given value of N are compared. The work has restricted values of N upto 50 only as beyond this it is extremely difficult to get the solution of the problem using backtracking method. Both the implementation have been carried out in MATLAB using Pentium Core 2 Duo T6600 Core 2. 2 GHz processor on Windows 8 with 4GB RAM. Because of the random nature of GA instead of time taken in obtaining all possible solutions for a given value of N, the time taken in obtaining say count number of solutions was first determined using GA, then time taken in same number of solutions that is count using backtracking was noted. Results are then presented in tabular manner.

References
  1. Kelly D. Crawford, "Solving n-Queen problem using genetic algorithms"SAC '92 Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing,pp:1039-1047,1994
  2. B. Klabbankoh, O. Pinngern. "applied genetic algorithms in information retrieval" Proceeding of IEEE ,pp. 702-711,Nov 2004
  3. S. S. Satya and P. Simon, "Review on Applicability of Genetic Algorithm to Web Search," International Journal of Computer Theory and Engineering, vol. 1, no. 4, pp. 450-455, 2009.
  4. Shokouhi, M. ; Chubak, P. ; Raeesy, Z " Enhancing focused crawling with genetic algorithms"Vol: 4-6, pp. 503-508,2005.
  5. M. A. Kauser, M. Nasar, S. K. Singh, "A Detailed Study on Information Retrieval using Genetic Algorithm", Journal of Industrial and Intelligent Information vol. 1, no. 3, pp. 122-127 Sep 2013.
  6. J. R. Koza, " Survey Of Genetic Algorithms And Genetic Programming", Proceedings of the Wescon,pp. 589-595,1995
  7. V. Thada, V. Jaglan, "Use of Genetic Algorithm in Web Information Retrieval", International Journal of Emerging Technologies in Computational and Applied Sciences, vol. 7,no. 3,pp. 278-281, Feb,2014
  8. E. Horowitz ,S. Sahni,S. Rajasekaran, " Fundamentals of Computer Algorithms",University Press India. 2007.
  9. Planning and Search, Available at: www. cs. nott. ac. uk/~nza/G52PAS/lecture4. pdf
  10. G. Üçoluk, "Genetic Algorithm Solution of the TSP Avoiding Special Crossover and Mutation",Intelligent Automation & Soft Computing, vol. 8, no. 3, 2002
  11. Brady, R. M. "Optimization Strategies Gleaned from Biological Evolution. " Nature317, 1985, pp. 804.
  12. Davis, L. "Applying Adaptive Algorithms to Epistatic Domains. " Proceedings of theInternational Joint Conference on Artificial Intelligence, 1985, pp. 162-164.
  13. Grefenstette, J. "Incorporating Problem Specific Knowledge into Genetic Algorithms. "Genetic Algorithms and Simulated Annealing, edited by Davis L. , Morgan Kaufmann,Los Altos, CA, pp. 42-60, 1987.
  14. Goldberg, D. E. , and R. Lingle. "Alleles, Loci, and the Traveling Salesman Problem. "Proceedings of the First International Conference on Genetic Algorithms and Their Application, edited by Grefenstette J. , Lawrence Erlbaum Associates, Hillsdale, NJ,1985, pp. 154-159.
  15. Larranaga, P. , C. M. H. Kuijpers, M. Poza, and R. H. Murga. "Decomposing BayesianNetworks: Triangulation of the Moral Graph with Genetic Algorithms. " Statistics andComputing, 1996.
  16. M¨uhlenbein, H. , M. Gorges-Schleuter, and O. Kramer. "Evolution Algorithms in Combinatorial Optimization. " Parallel Computing, 7, 1988, pp. 65-85.
  17. M¨uhlenbein, H. "Parallel Genetic Algorithms, Population Genetics and Combinatorial Optimization. " Proceedings on the Third International Conference on Genetic Algorithms, edited by Schaffer J. , Morgan Kaufmann Publishers, Los Altos, CA, 1989 pp. 416-421.
  18. Syswerda, G. "Schedule Optimization Using Genetic Algorithms. " Handbook of Genetic Algorithms, edited by Davis L. , Van Nostrand Reinhold, New York, 1991,pp. 332-349.
  19. Whitley, D. , T. Starkweather, and D. Shaner. "The Traveling Salesman and Sequence Scheduling: Quality Solutions Using Genetic Edge Recombination. " Handbook of Genetic Algorithms, edited by Davis L. , Van Nostrand Reinhold, New York, 1991, pp. 350-372
Index Terms

Computer Science
Information Sciences

Keywords

NQueen genetic algorithm solutions

Powered by PhDFocusTM