遗传算法求解N皇后问题的优化

王振义

(1.太原理工大学计算机与软件学院，山西太原030024;2.山西大同大学物理与电子科学学院，山西大同037009)

遗传算法求解N皇后问题的优化

王振义1,2

(1.太原理工大学计算机与软件学院，山西太原030024;2.山西大同大学物理与电子科学学院，山西大同037009)

∶采用vector容器高效的染色体整数编码和成熟的泛型算法，改良遗传算法求解N皇后问题，说明此方法更通用、简洁和高效.

∶N皇后问题 适应值 遗传算法 STL

1 N皇后问题描述

八皇后问题是著名的数学家Gauss于1850年提出的.要求横、竖、斜方向上都不能有两个及两个以上皇后在同一条直线上，问题也可以推广到N个皇后.求解这一问题的算法很多，过去一般用穷举法、回溯法求解.由于其时间复杂度为O(N!)，是一个NP难问题.对于皇后变多耗时激增的计算机求解问题，就需利用非常规的技术求解.解决的办法通常是编写快速的算法，或是采用多个CPU并行计算或分布式计算.本文使用STL中的容器和泛型算法对基本遗传算法进行改进，达到满意的效果.

2 遗传算法

遗传算法(Genetic Algorithms，简称GA)，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，基于生物学进化原理的一种全局搜索算法.通过用计算机模拟生物进化过程，使群体不断优化，并在进化过程中逐渐接近最优解.其特点是简单、通用、鲁棒性强和适于并行处理.把遗传算法用于求解NP完全问题，可为求解NP完全问题给出新的思路.

遗传算法的框架是由Holland提出的，可描述为:

①随机产生初始种群;

②利用适应度函数对个体计算函数值;

③按一定的概率选择对个体进行选择、交叉、变异等操作产生新种群;

④重复②、③两步，直到找到最佳解或迭代次数达到指定的上限;

3 STL(Standard Template Library)

STL是C++标准库的一部分，全称叫做标准模板库，它的作用就是提供一些泛型算法和容器.

使用STL主要有如下理由:

①效率高:算法通常比程序员产生的循环更高效.

②正确性:写循环时比调用算法更容易产生错误.

③可维护性:算法通常使代码比相应的显式循环更干净、更直观.

在进行遗传算法求解N皇后问题的计算中，当基因数量和总群数量较大时，使用遗传算法对数据的处理，需多次用到数组循环，这是相当耗时的.本文采用vector容器存放数据，运用STL泛型算法处理数据，如accumulate求和，max_element求最大值，remove和copy配合着对vector数据重排等，为用遗传算法求解N皇后问题的数据处理带来极大的便捷、简洁和高效.

4 编程实现

N皇后问题要求，每行，每列，主次对角线都只有一个棋子存在.这里采用整数编码，每个染色体都是由N个基因的整数组成，取值范围是1-N.编码位置和数值代表皇后所处行和列的位置.这样，保证了在每行，每列只有一个皇后，一个染色体代表着一种棋盘的布局.例设染色体用G=(G1，G2，…Gi… Gn)表示，Gi代表在第i行上的皇后放在第Gi列的位置.采用VC作为平台，在建立main程序后，建立基因组类和群体类.

4.1 基因组类∶CGenome

成员 vector＜int＞ vecBits;//表示一个染色体

dFitness;//染色体对应的适应度.成员函数有:

CreateGenome函数创建个体.首先生成一个按从小到大顺序排列的基因组，再用random_shuffle函数使这个染色体中的基因随机重排，得到新的个体.

UpdateFitnessScore计算适应度.在主次对角线上的彼此有一个冲突数记为1，累加本染色体中所有的冲突后加1，再求倒数作为适应度，显然冲突越多，对应的适应度值越小，没有任何冲突时，值为1，表示找到了一个合适的解.

4.2 种群类∶CPopulation

成员

vector＜CGenome＞ vGenomes;//群体

vector＜CGenome＞::iterator vGit;//迭代器

vector＜CGenome＞ vBabyGenomes;//下级群体

intm_iBestIndex;//最好个体的索引

intm_iWorstIndex;//最好个体的索引

CGenome m_CCurrentBestGenome;//目前最好的个体CGenomem_CBestGenome;//当代最好的个体CGenomem_CWorstGenome;//当代最糟的个体建立一些算法函数完成指定功能.

①初始化种群:(GenerateInitialPopulation)

完成每个种群的初始化，同时调用CGenome建立的UpdateFitnessScore对每个个体进行计算.

②选择算子(SelectionOperator)

按赌轮选择，保证适应度较高的个体将有更多的机会遗传到下一代群体中.在计算总的适应度时用到了 accumulate(vG.begin()，vG.end()，0.0，Add);其中 Add(const double Val，const CGenome&element){return Val＋element.dFitness;}就是对类中成员适应度(dFitness)的累加.

③交叉算子(CrossoverOperator)

当随机数小于交叉概率(这里取0.75)时，进行交叉运算，由于新种群的个体是随机产生的，选用相邻(也可以随机配对)的个体作为父母本进行交叉.不同于位编码的交叉，为确保同行同列不冲突，新个体中的数字不能有重复的.先随机生成单个交叉点的位置，子代个体的前半段直接拷入交叉点前父(母)的前半段，母(父)本中删除个体前半段已有的数字作为个体的后半段.

④变异算子(MutationOperator)

为了避免出现早熟收敛，当随机数小于变异概率(这里取0.2)时随机生成两个基因位，交换两个位置的基因，对个体进行变异，这里用到了swap函数.

⑤干预进化(PerformEvolution)

运用 max_element(vG.begin()，vG.end()，best);记录当前群体中最好(或最糟)的个体，以及对应的索引编号，其中best为自定义的判断式，容器中的相邻项比较，后的数大时为真进行代换，最后得到适应度最大的个体，最糟的结果是利用后面的数小时为真，也就是得到整个群体中适应度最小的个体.用最优的个体替换掉最糟的个体，保证最优的个体直接进入下一代，剔除最糟的个体保证的整个群体有更大的适应度.

表1 和其它文献用时对比(t/s)

测试条件:染色体长度等于皇后数，种群大小选200，交叉概率0.75，变异概率0.2，最大代数根据要求皇后的数量决定，一般取200即可，可以通过试解后在调整.

通过在VC＋＋集成编辑环境下的运行，本程序用时明显小于回溯法用时[5]，对皇后数量大于100的问题求解，明显优于基本遗传算法.此方法稍加修改就可以解决其他问题，如旅行商和其它数值类求解问题.本文利用容器和调用算法的方法，对其他类似问题的算法的优化有一定借鉴意义.

[1]李建华.智能组卷系统与遗传算法[J].山西大同大学学报：自然科学版，2009，25(3):14-16.

[2]胡能发.一种二元单亲演化差基因变异算法[J].长江大学学报:自然科学版，2004，1(1):74-76.

[3]宋晓霞.遗传算法中初始群体技术的改进与实现[J].计算机工程与设计，2007，28(22):5485-5487.

[4]马永，贾俊芳.遗传算法研究综述[J].山西大同大学学报:自然科学版，2007，23(3):11-13.

[5]刘娟，欧阳建权，陈良军.用混合遗传算法求解N皇后问题[J].湘潭大学自然科学学报，2007，29(2):37-41.

[6]杨凯，罗文俊.基于BIT位运算的N皇后问题解法[J].贵州师范大学学报:自然科学版，2009，27(2):96-98.

Genetic A lgorithm Optim ization of N Queens Problem

WANG Zhen－yi1,2
(1.College of Computer and Software，Taiyuan University of Technology，Taiyuan S hanxi，030024;2.School of Physics and Electronics Science，ShanxiDatong University，Datong Shanxi，037009)

This literary grace is with high-efficient chromosome integer code of vector container and ripe suffused withing type algorithm，can improve the algorithm algorithm and solve N queen's question，which prove s thismethod is common，more succinct and high-efficient.

N Queen;f itness;Genetic Algorithm;STL

∶TP18

∶A

∶1674－0874（2010）02－0013－02

∶2010-01-08

∶王振义(1955-)，男，山西大同人，副教授，研究方向:算法.

〔编辑 高海〕