八皇后问题的遗传算法实现过程详解.pdf

《八皇后问题的遗传算法实现过程详解.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2012年第8期福建电脑85八皇后问题的遗传算法实现过程详解虞柳江．乐天(浙江海洋学院数理与信息学院浙江舟山316000)【摘要】：八皇后是个经典的NP问题，有许多的求解算法。本文用遗传算法求解八皇后问题，给出详细的实现过程。【关键词】：八皇后，遗传算法，个体评价1√皇后问题描述3．1编码19世纪著名的数学家Gauss在1850年提出遗传算法中传统的编码是二进制编码．本文八皇后问题后．该问题成为各类语言程序设计的采用多值编码。染色体长度取决于皇后的个数。染经典题目八皇后问题要求在8x8格的国际象棋色体中每个基因所处的位置表

2、示其在棋谱中所在上摆放八个皇后，使横、竖、斜方向上都不能有两的行数，基因值表示其所在的列数。如染色体个及两个以上皇后在同一条直线上．问题也可以40752613表示：从O开始数，第0个4表示在第推广到N个皇后穷举法在问题规模不大的情况零行的皇后在第4列．第1个O表示第一行的皇下还可适用，回溯法是求解此问题的经典算法。但后在第O列，以此类推。八皇后问题中皇后不能处N皇后问题是个NP难问题．随着皇后数目的增于同行同列．意味着染色体中07的基因取值不多，求解复杂度激增．就需利用非常规的技术求能出现重复。解。遗传算法在求解一些NP完

3、全问题上得到了3．2个体评价广泛地应用．本文用遗传算法求解八皇后问题，给染色体通常表示了问题的可行解．对可行解出详细的实现过程进行遗传操作寻找最优解。但在八皇后问题中，染2、基本遗传算法求解过程色体仅仅体现同行同列中未出现互攻．在对角线基本遗传以初始种群为基点．经过选择、交上是否出现互攻还未做考虑。在对皇后的位置做叉、变异操作生成新的种群，如此更新种群直到满比较的时候．可以对两个棋子的行数差与列数差足终止条件。其计算步骤如下：进行对比，实现了互攻次数的统计。公式为：(1)将问题空间转换为遗传空间，也就是编Y2一Il_1。公

4、式中(x1，y1)，(x2，y2)分别表示两个码：(2)随机生成P个染色体作为初始种群；皇后所在的位置．即所在的行数和列数。当两个皇(3)染色体评价，也就是按确定的适应度函数后的行数差与列数差比值的绝对值为1的时候．计算各个染色体的适应度：两皇后在同一对角线上，即出现了互攻。每个染色(4)根据染色体适应度，按选择算子进行染色体内的互攻次数为Value，初始值设为O；第O行体的选择：与l7行进行比较．每出现一次互攻则Value的(5)按交叉概率进行交叉操作；值增加1；第l行与2～7行进行比较，以此类推来(6)按变异概率进行变

5、异操作；计算Value值。当Value为0表示没有发生互攻，(7)返回(4)形成新的种群，继续迭代，直到满此染色体就是其中的一个可行解。当Value不为0足终止条件。则进行适应度的计算。一般来说。适应度越大越基本遗传算法给出了基本框架．针对求解的好．而互攻次数为越小越好，所以可以将适应度的问题不同．遗传算法在相应的计算步骤中有不同计算函数设置为：F=1／Value。的设计。本文针对八皇后问题，设计了相应的编3．3选择码，适应度计算方法，交叉和变异操作。选择使用的是经典的赌轮选择方法．与基本3、用遗传算法求解八皇后问题实现过

6、程详解遗传算法的实现无特别之处，此处不赘述。3．4交叉福建电脑2012年第8期经典的单点．多点等交叉因染色体中不能出体的适应值为0时．即表示算法搜索到了一个可现重复的基因值，在该问题中不适用。本文使用部行解，终止算法。若算法运行设置的代数还未找到分匹配交叉。具体操作如下：可行解。同样终止程序运行。11在染色体中随机选取两个点标记为Y，如：4、总结染色体a：01y24y3675：染色体b：12y3Oy4576；J~个本文详细介绍了用遗传算法求解八皇后问题v之间的基因段称为中间段．记录其对应关系2—的求解过程．但要注意的是这只

7、是其中的一种编3，4-0；码。交叉。变异等操作设计方法。还有许多其他的21对染色体a，b的中间段进行交换，形成染方法可以选择。对于各操作采取不同设计方案的色体a：Oly30y3675；染色体b：12y24y4576；遗传算法，其算法性能值得比较讨论。31利用对应关系，对染色体a，b中间段外的基因进行交换，形成染色体a：41y30y2675；染参考文献：色体b：13y24y0576；交叉完成。『11周明，孙树栋等．遗传算法原理及应用．北京：国防工业3．5变异出版社．1999．采用多值编码后．变异操作并不能通过简单f21李鸿．

8、解决N一皇后问题的一个遗传算法．宿州师专学报，2000，7：85-87．的0。1反转实现。本文采取随机地选取染色体内『31谷峰，吴勇，唐俊．基于遗传算法的N皇后r．q题求解．宿的两个基因进行交换来实现。例如随机选取的是州教育学院学报，2002，vo1．5(4)：74—75．6和1两个基因．那么『41刘娟