我正在编写一个遗传算法来解决数独谜题，并希望得到一些输入 . 该算法偶尔解决谜题（在同一个谜题中大约有10次，最多1,000,000次迭代），我试图获得关于突变率，重新种群和拼接的一些信息 . 任何输入都非常感谢，因为这对我来说是全新的，我觉得我没有100％正确的做事 .
快速概述算法
健身功能
计算每列，每行和3 * 3子框中数字1到9的唯一值的数量 . 将子集中的这些唯一值中的每一个求和并除以9，得到0到1之间的浮点值 . 这些值的总和除以27，提供范围在0和1之间的总适应值.1表示解决的谜题 .
人口规模：100
选择：
轮盘赌方法 . 随机选择每个节点，其中包含较高适合度值的节点具有稍微更好的选择机会
繁殖：两个随机选择的染色体/板交换随机选择的子集（行，列或3 * 3子集）子集（行，列或框）的选择是随机的 . 由此产生的董事会被引入人口 .
繁殖率：每周期12％的人口每次迭代有6个复制品，每个循环的算法产生12个新的染色体 .
突变：突变发生率为2％的人口，经过10次迭代后没有提高最高适应度 . 下面列出了三种具有不同选择概率权重的突变方法 .
1：交换随机选择的数字 . 该方法选择两个随机数并在整个电路板上交换它们 . 这种方法似乎对算法增长模式的早期增长影响最大 . 25％的选择机会
2：引入随机变化：随机选择两个单元格并更改其值 . 这种方法似乎有助于防止算法收敛 . ％65的选择机会
3：计算板中每个值的数量 . 求解的板包含1到9之间的每个数字的9的计数 . 该方法采用少于9次的任何数字，并随机地将其与发生超过9次的数字交换 . 这似乎对算法产生了积极的影响，但只是谨慎使用 . 选择的几率为10％
我的主要问题是我应该以什么样的速度应用变异方法 . 似乎随着我增加突变，我的初始结果更快 . 然而，由于结果接近正确的结果，我认为更高的变化率是将过多的坏染色体和基因引入群体 . 但是，由于变化率较低，算法似乎收敛得太早 .
最后一个问题是是否有更好的突变方法 .
2 回答
您可以随时间退化变异率，以获得您所描述的那种收敛行为 . 但实际上我认为通过修改算法的其他部分可能会有更大的收益 .
轮盘选择通常选择非常高的选择压力 . 在这个过程中，它往往会导致很快失去多样性 . 二元比赛选择通常是开始实验的更好地方 . 这是一种更为渐进的压力形式，同样重要的是，它可以更好地控制 .
使用不太激进的选择机制，您可以负担得起 生产环境 更多的后代，因为您不必担心 生产环境 这么多近一个最好的一个或两个人的副本 . 而不是12％的人口产生后代（可能由于交配池中父母的重复而减少），我会100％ . 您不一定需要确保每个父母都参与，但只需生成与父母一样的后代数量 .
某种形式的温和精英主义可能会有所帮助，这样你就不会失去好父母 . 如果他们比最差的2-5个后代更好，也许保留最好的2-5个人来自父母群体 .
有了精英主义，你可以使用更高的突变率 . 你的三个操作员似乎都很有用 . （请注意，＃3实际上是嵌入在遗传算法中的一种局部搜索形式 . 这在性能方面通常是一个巨大的胜利 . 事实上，你可以将＃3扩展为更复杂的方法，直到它无法弄清楚如何进一步改进 . ）
我没有看到明显更好/更糟的一套你的三个变异算子的权重 . 我认为在那一点上，你已经完全属于实验参数调整领域 . 另一个想法是在流程中注入一些知识，例如，在流程的早期，您可以随机选择它们 . 之后，随着算法的收敛，支持您认为更有可能帮助完成“几乎解决”的板的变异算子 .
我曾经使用GA做过一个相当称职的数独求解器 . 这里有关于细节（包括不同的表示和变异）的博客：http://fakeguido.blogspot.com/2010/05/solving-sudoku-with-genetic-algorithms.html