|
|||||
|
|
| 用混合遗传算法求解N皇后问题 | |
| 引用本文： | 刘娟,欧阳建权,陈良军.用混合遗传算法求解N皇后问题[J].湘潭大学自然科学学报,2007,29(2):37-41. |
| 作者姓名： | 刘娟 欧阳建权 陈良军 |
| 作者单位： | 1. 湖南广播电视大学,湖南,长沙,410004 2. 国防科技大学计算机学院,湖南,长沙,410000;湘潭大学信息工程学院,湖南,湘潭,411105 3. 湘潭大学信息工程学院,湖南,湘潭,411105 |
| 摘 要： | N皇后问题是NP难题,一般求解的方法为回溯法.当问题规模较小时用回溯法能有效求解,但当问题规模较大时其求解时间耗费非常巨大.该文提出用局部搜索与简单遗传算法(SGA)相结合的混合遗传算法(HGA)来求解N皇后问题,用N皇后的约束条件作为遗传算法的适应值函数.设计了高效的染色体编码、初始化种群方法、遗传算子以及局部搜索算子,使它们符合求解问题的需要.通过与回溯法和相关的遗传算法比较,实验证实了用混合遗传算法求解N皇后的有效性. |
| 关 键 词： | N皇后问题 适应值 遗传算法 局部搜索 |
| 文章编号： | 1000-5900（2007）02-0037-05 |
| 修稿时间： | 2006-09-27 |
Solving the N - Queens Problem Using Hyperbrid Genetic Algorithm |
|
| LIU Juan,OUYAN Jian - quan,CHEN Liang - jun.Solving the N - Queens Problem Using Hyperbrid Genetic Algorithm[J].Natural Science Journal of Xiangtan University,2007,29(2):37-41. | |
| Authors: | LIU Juan OUYAN Jian - quan CHEN Liang - jun |
| Institution: | 1. Hunan Radio and TV University,Changsha 410004 China; 2. College of Computer,National University of Defense Technology, Changsha 410072 China; 3. Institute of Information Engineering, Xiangtan University, Xiangtan 411105 China |
| Abstract: | N-Queens Problem is a NP problem.Its common solution is backtracking.When the problem is in small scale,the backtracking may lead to satisfying solution. When the problem is in large scale,it may cost expensive time.In this paper,Hyperbrid Genetic Algorithm(HGA)which is combined with local search and Simple Genetic Algorithm(SGA) is proposed to solve N-Queens Problem.The constraint of N-Queens problem is taken as fitness function of HGA.The efficient coding method,the method of initializing population,genetic operator and local search operator are designed to adapt the problem.The efficiency of solving NQueens Problem is verified by compare with backtracking and current SGA. |
| Keywords: | N-Queens Problem Fitness Genetic Algorithm Local Search |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《湘潭大学自然科学学报》浏览原始摘要信息 | |
| 点击此处可从《湘潭大学自然科学学报》下载免费的PDF全文 | |