Comparison Two Techniques to Optimizing N-Queens Problem Based on Memetic Algorithm

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), and Step-Counting Hill-Climbing local search based MA (SCHCLSMA) 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 Memetic Algorithm 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.