使用遗传算法解决数独

Question

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

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

适应度:由每行,每列和方格中的"不合适"值的数量确定,加在一起.

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

选择:随机,但使用轮盘赌加权.

交叉:随机选择两个父母的各行,创建一个孩子.(我还实现了一个交叉,从父母双方一次随机选择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个冲突),但它永远无法找到解决方案(它可能会找到局部最小值并卡住).

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

我的方法有哪些弱点？如何提高性能？

看起来Sudoku可能会让自己从突变中获得更好的表现,而不是交叉.

Answer 1

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

数独有许多错误的局部最小值,因此保持种群多样性非常重要.不要太贪婪地收敛.这是许多难题的关键.收敛极其缓慢.

我不喜欢轮盘赌选择.它是一种收敛太快而且过于依赖健身功能的玩具.例如,您可以使用锦标赛选择.

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

Answer 2

据我所知，以编程方式解决 soduko 的最佳策略是使用布尔可满足性问题