artificial-intelligence - 遗传算法数独——优化变异

Question

我正在编写解决数独谜题的遗传算法，希望得到一些帮助。该算法偶尔会解决难题(大约十分之一的 10 次是在最多 1,000,000 次迭代的同一个难题上)，我正在尝试获得有关突变率、重新填充和剪接的一些信息。非常感谢任何意见，因为这对我来说是全新的，我觉得我做的事情不是 100% 正确。

算法的快速概述

健身功能

统计每列、每行和3*3的子框中数字1到9的唯一值的个数。子集中的每个唯一值相加并除以 9，得到一个介于 0 和 1 之间的 float 值。这些值的总和除以 27，提供介于 0 和 1 之间的总适应度值。1 表示已解决难题。

人口规模:100

选择:

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

复制:两个随机选择的染色体/板交换随机选择的子集(行、列或 3*3 子集)子集(行、列或框)的选择是随机的。将产生的板引入种群。

繁殖率:每个周期 12% 的人口每次迭代有 6 次复制，导致算法的每个循环产生 12 个新染色体。

突变:在最高适应度无改善的 10 次迭代后，突变发生率为 2%。下面列出了三种具有不同选择概率权重的变异方法。

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

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

3:统计棋盘上每个值的个数。已解决的棋盘包含 1 到 9 之间的每个数字 9 的计数。此方法采用出现次数少于 9 次的任何数字，并随机将其与出现次数多于 9 次的数字交换。这似乎对算法有积极影响，但只是很少使用。 %10 的选择机会

我的主要问题是我应该以什么速率应用变异方法。似乎随着我增加突变，我得到了更快的初始结果。然而，随着结果接近正确结果，我认为更高的变化率正在将太多坏染色体和基因引入种群。然而，由于变化率较低，算法似乎过早收敛。

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

Answer 1

您可以随着时间的推移退火突变率以获得您所描述的那种收敛行为。但实际上我认为通过修改算法的其他部分可能会获得更大的 yield 。

轮盘选择通常会施加非常高的选择压力。在这个过程的早期，它往往会导致多样性的快速丧失。二元锦标赛选择通常是开始试验的更好地方。这是一种更渐进的压力形式，同样重要的是，它的控制要好得多。

使用不那么激进的选择机制，您可以负担得起产生更多的后代，因为您不必担心产生那么多最好的一两个个体的近乎复制品。而不是 12% 的人口产生后代(由于 parent 在交配池中重复，可能更少)，我会选择 100%。您不一定需要从字面上确保每个 parent 都参与，但只需生成与 parent 数量相同的后代即可。

某种形式的温和精英主义可能会有所帮助，这样您就不会失去好 parent 。如果最好的 2-5 个个体比最差的 2-5 个后代更好，也许可以从父代种群中保留最好的 2-5 个个体。

有了精英主义，你可以使用更高一点的变异率。您的所有三个运算符(operator)似乎都很有用。 (请注意，#3 实际上是一种嵌入到遗传算法中的局部搜索形式。就性能而言，这通常是 巨大 的胜利。事实上，您可以将 #3 扩展为一种更复杂的方法，循环直到它想不出如何进行任何进一步的改进。)

对于您的三个变异运算符，我没有看到明显更好/更差的一组权重。我认为在这一点上，你已经坚定地处于实验参数调整的范围内。另一个想法是在这个过程中注入(inject)一些知识，例如，在这个过程的早期，你在它们之间随机选择。稍后，随着算法收敛，选择您认为更有可能帮助完成“几乎已解决”的棋盘的变异算子。