一种求解N皇后问题的优化组合遗传算法

基于遗传算子优化组合思想,采用二进制编码方式,选择矩阵遗传算子和布尔遗传算子组合应用对N皇后问题求解,避免了常规遗传算法的杂交率和变异率选取.从N皇后问题的约束条件角度,构造适应度评价函数,保证了算法的全局收敛性.实验结果表明,本文算法具有良好的搜索效率和求解质量,运行一次在收敛代数内可以搜索到多个解,当皇后数N较大时,搜索到解的效率越明显好于常规遗传算法.

An Optimized and Combined Genetic Algorithm for N-Queens Problem

Based on the concept of optimized combination of genetic operators,in this paper a new genetic algorithm using binary code for N-Queens problem is constructed with matrix genetic operator and Boolean genetic operator,which does not require parameters of crossover probability and mutation probability.A fitness function is designed to adapt constraint of N-Queens problem and to ensure the convergence of the constructed genetic algorithm.Experiments results show that the efficiency of the algorithm is better than current genetic algorithm when the number of queens is great,and it can find multiple solutions in one search process.