N-QUEENS PROBLEM OPTIMIZATION USING VARIOUS MEMETIC ALGORITHMS

  Vishal Khanna,  Abhishek Bhardwaj,  Sarvesh Chopra

NP hard problems like N-Queens problem are non-polynomial time problems. In this research study, we use the Simulated Annealing local search based MA (SALSMA), Genetic Algorithm(GA) and Hill-Climbing local search based MA (HCLSMA) to optimize N-Queens problem and make complexity analysis on the parameters viz. optimal solutions, time and convergence rate with respect to number of iterations. The MA is a hybrid algorithm, being a combination of the Genetic Algorithm (GA) and a local search algorithm. The performance of the MA is found to be superior to that of a solitary algorithm like GA. The MA solves the N-Queens in two stages. In the first stage, the randomly generated solutions are evolved till they become feasible (i.e., the hard constraints are satisfied) and in the second stage, these solutions are further evolved so as to minimize the violations of the soft constraints. In the final stage, the MA produces optimal solutions in which the hard as well as the soft constraints are completely satisfied.

Keywords- Queens, N-Queens, 8 Queens, Genetic Algorithm, Chromosome, Mutation, Selection, Crossover, Recombination, GA, MA, HCLSMA, SALSMA, Hill-Climbing, Simulated Annealing

Unique Identification Number - IJEDR1702196
Page Number(s) - 1206-1214
Pubished in - Volume 5 | Issue 2 | May 2017
DOI (Digital Object Identifier) -   
Publisher - IJEDR (ISSN - 2321-9939)

  Vishal Khanna,  Abhishek Bhardwaj,  Sarvesh Chopra,   "N-QUEENS PROBLEM OPTIMIZATION USING VARIOUS MEMETIC ALGORITHMS", International Journal of Engineering Development and Research (IJEDR), ISSN:2321-9939, Volume.5, Issue 2, pp.1206-1214, May 2017, Available at :http://www.ijedr.org/papers/IJEDR1702196.pdf