我正在编写一个用于解数独谜题的遗传算法，希望能得到一些建议。该算法偶尔能解出谜题（在同一谜题上大约10次中有1次成功，最多迭代1,000,000次），我正在尝试获取关于变异率、重新填充和拼接的一些建议。由于这是我第一次尝试，我觉得自己做得还不够完美，任何建议都将不胜感激。

算法简要概述

适应度函数

计算每列、每行和每个3*3子方块中数字1到9的唯一值的数量。这些子集中的每个唯一值相加后除以9，得到一个介于0和1之间的浮点值。这些值的总和再除以27，提供一个总的适应度值，范围在0到1之间。1表示谜题已被解出。

种群大小：100

选择：

轮盘法。每个节点的选择是随机的，其中包含较高适应度值的节点有更大的被选中机会

繁殖：随机选择两个染色体/棋盘，交换一个随机选择的子集（行、列或3*3子集）。子集的选择（哪一行、哪一列或哪个方块）是随机的。生成的棋盘被引入到种群中。

繁殖率：每个周期种群的12%。每个迭代有六次繁殖，导致每个算法周期产生12个新染色体。

变异：在最高适应度没有改善的10次迭代后，变异以种群2%的速率发生。下面列出了三种变异方法，它们的选择概率权重各不相同。

1：交换随机选择的数字。该方法选择两个随机数字并在整个棋盘上交换它们。这种方法似乎在算法早期的增长模式中对增长影响最大。选择概率为25%

2：引入随机变化：随机选择两个单元格并更改它们的值。这种方法似乎有助于防止算法过早收敛。选择概率为65%

3：计算棋盘上每个数字的数量。一个已解的棋盘包含每个数字1到9的计数为9。这种方法将任何出现次数少于9次的数字随机交换为出现次数超过9次的数字。这似乎对算法有积极影响，但仅谨慎使用。选择概率为10%

我的主要问题是应该以什么速率应用变异方法。似乎随着变异率的增加，我能更快地得到初步结果。然而，当结果接近正确结果时，我认为较高的变异率引入了太多不良的染色体和基因进入种群。然而，较低的变异率似乎使算法过早收敛。

最后一个问题是是否有更好的变异方法。

回答：

你可以随着时间逐渐降低变异率，以获得你描述的那种收敛行为。但我实际上认为通过修改算法的其他部分可能会有更大的收益。

轮盘选择法通常会施加非常高的选择压力。它往往会导致过程早期就迅速丧失多样性。通常，采用二元锦标赛选择法开始实验会更好。这是一种更渐进的压力形式，而且同样重要的是，它的控制要好得多。

有了较不激进的选择机制，你可以负担得起产生更多的后代，因为你不必担心产生太多最佳一两个个体的近似副本。与其让种群的12%产生后代（可能因为交配池中父母的重复而更少），我会选择100%。你不一定需要确保每个父母都参与，但只需生成与父母数量相同的后代即可。

然后，某种形式的轻度精英主义可能会有所帮助，这样你就不会失去好的父母。也许保留父母种群中最好的2-5个个体，如果它们比最差的2-5个后代更好的话。

有了精英主义，你可以使用稍高的变异率。你的三个操作符似乎都很有用。（注意，#3实际上是嵌入在你的遗传算法中的一种局部搜索形式。这通常在性能方面是一个巨大的优势。你实际上可以将#3扩展为一个更复杂的方法，循环直到它无法找出如何进行进一步的改进。）

我没有看到你三个变异操作符的明显更好/更差的权重设置。我认为在这一点上，你已经完全进入了实验参数调整的领域。另一个想法是向过程中注入一些知识，例如，早期在它们之间随机选择。稍后，当算法正在收敛时，倾向于选择你认为更有可能帮助完成“几乎已解”棋盘的变异操作符。