计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (16): 49-51.

• 研究、探讨 • 上一篇    下一篇

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

帅训波1,马书南2   

  1. 1.中国石油勘探开发研究院 廊坊分院 地球物理与信息研究所,河北 廊坊 065007
    2.北京工业大学 计算机学院,北京 100022
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-06-01 发布日期:2011-06-01

Solving N-queens algorithm based on boolean genetic operator

SHUAI Xunbo1,MA Shunan2   

  1. 1.Institute of Geophysics and Information,Langfang Branch of Research Institute of Petroleum Exploration and Development,PetroChina,Langfang,Hebei 065007,China
    2.College of Computer Science & Technology,Beijing University of Technology,Beijing 100022,China

  • Received:1900-01-01 Revised:1900-01-01 Online:2011-06-01 Published:2011-06-01

摘要: 应用回溯法求解规模较大的N皇后问题时,时间开销巨大。从提出布尔遗传算子角度,增强遗传算法局部搜索性能,与具有良好全局搜索性能的矩阵遗传算子组合应用,对N皇后问题求解。采用自然数和二进制互换的编码方式,应用N皇后的约束条件构造适应度函数,保证了算法的全局收敛性。通过与回溯法和相关遗传算法比较,实验证实了该方法应用于求解N皇后问题,具有良好的搜索效率和求解质量。

关键词: N皇后问题, 布尔遗传算子, 适应度函数, 遗传算法

Abstract: 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.

Key words: N-queens problem, boolean genetic operator, fitness function, genetic algorithm