genetic-algorithm - 使用遗传算法求解数独

Question

我承担了使用遗传算法创建数独求解器的任务。

初始化 :将给定值存储在每个染色体中，然后随机生成值，使得每一行都是值 1 到 9 的有效排列。

健身 :由每行、列和方格中的“不合适”值的数量相加确定。

健身功能 : 典型的轮盘赌选择

选择 :随机，但使用轮盘赌加权。

跨界 :从两个 parent 中随机选择不同的行，创建一个 child 。 (我还实现了一个交叉，一次从两个 parent 中随机选择 3 行 - 以保持良好的迷你网格)。以下是两个示例子项，每个子项来自每个交叉方法:

Parent 1 row 1
Parent 2 row 2
Parent 1 row 3
Parent 2 row 4
Parent 1 row 5
Parent 2 row 6
Parent 2 row 7
Parent 1 row 8
Parent 1 row 9

Parent 1 row 1
Parent 1 row 2
Parent 1 row 3
Parent 2 row 4
Parent 2 row 5
Parent 2 row 6
Parent 1 row 7
Parent 1 row 8
Parent 1 row 9

突变 :最初我只是在两个随机位置交换值，但这实际上使算法变得更糟，因为它在行中引入了重复，而这些行是有效的排列。所以我改变了突变(当突变的机会在 25% - 50% 范围内时，这似乎表现最好)随机选择一行，然后随机化该行的顺序(将给定值保留在正确的位置) .

我还尝试了一个突变，它选择一个随机行，然后在该行中选择两个随机(非给定)位置并交换它们，但这也使性能变得更糟。 (与两个随机位置的交换不同，我不明白为什么这种突变会使性能变得如此糟糕，但是随机化整行的突变会使性能更好)

我的算法还没有解决任何困难的难题。它经常会接近(在只有 6 到 10 个冲突的范围内)，但它永远无法找到解决方案(它可能会找到局部最小值并卡住)。

为了改进算法，我添加了用完全随机的板替换大部分人口(表现最差的染色体)的能力，但这似乎影响很小。

我的方法有哪些弱点？我怎样才能提高性能？

与交叉相比，数独似乎可以从突变中获得更好的性能。

Answer 1

我用 GA 解决了一些数独难题，使用这种方法:
http://fendrich.se/blog/2010/05/05/solving-sudoku-with-genetic-algorithms/

数独有很多错误的局部最小值，因此保持种群多样性非常重要。不要过于贪婪地收敛。这是许多难题的关键。收敛极慢。

我不喜欢轮盘赌选择。它是一种收敛过快、过于依赖适应度函数的玩具。例如，您可以使用锦标赛选择。

我同意交叉应用很难。您可以将其视为一种大突变，恰好是一个交叉。