Solving N-Queens Problem Using Subproblems based on Genetic Algorithm

摘要

Nowadays, permutation problems with large state spaces and the path to solution is irrelevant such as N-Queens problem has the same general property for many important applications such as integrated-circuit design, factory-floor layout, job-shop scheduling, automatic programming, telecommunications network optimization, vehicle routing, and portfolio management. Therefore, methods which are able to find a solution are very important. Genetic algorithm (GA) is one the most well-known methods for solving N-Queens problem and applicable to a wide range of permutation problems. In the absence of specialized solution for a particular problem, genetic algorithm would be efficient. But holism and random choices cause problem for genetic algorithm in searching large state spaces. So, the efficiency of this algorithm would be demoted when the size of state space of the problem grows exponentially. In this paper, the subproblems used based on genetic algorithm to cover this weakness. This proposed method is trying to provide partial view for genetic algorithm by locally searching the state space. This method works to take shorter steps toward the solution. To find the first solution and other solutions in N-Queens problem using proposed method: dividing N-Queens problem into subproblems, which configuring initial population of genetic algorithm. The proposed method is evaluated and compares it with two similar methods that indicate the amount of performance improvement.