应用布尔遗传算子求解N皇后问题

摘要

The backtracking algorithm suffers from massive computational time when solving large scale N-Queens problem.Boolean genetic operator is proposed to improve local searching ability of genetic algorithm. By the boolean genetic operator combined with matrix genetic operator which has better global searching ability, an optimization combination genetic algorithm is constructed to solve N-Queens problem.The transform coding between integer and binary,fitness function based on constraint of N-Queens problem are designed to ensure the global convergence of algorithm.The better efficiency of solving N-Queens problem is verified by comparing with backtracking and current genetic algorithm.%应用回溯法求解规模较大的N皇后问题时,时间开销巨大.从提出布尔遗传算子角度,增强遗传算法局部搜索性能,与具有良好全局搜索性能的矩阵遗传算子组合应用,对N皇后问题求解.采用自然数和二进制互换的编码方式,应用N皇后的约束条件构造适应度函数,保证了算法的全局收敛性.通过与回溯法和相关遗传算法比较,实验证实了该方法应用于求解N皇后问题,具有良好的搜索效率和求解质量.