英语原文共 8 页
目录
中文翻译
使用遗传算法解决,评估和生成数独谜题
Timo Mantere and Janne Koljonen
摘要:本文研究了利用遗传算法(GA)解决,评定和生成数独谜题所涉及的问题。数独是一种数字拼图,它最近成为了在世界范围流行的现象。数独可以被视为一种约束满足问题。当用遗传算法求解时,它可以作为多目标优化问题来处理。本研究之中有三个目标是:1)测试遗传算法优化是否是解决数独谜题的有效方法,2)遗传算法是否可用于有效地生成新的谜题,还有3)遗传算法是否可用作评估给定数独谜题难度的评级机制。而本次研究中最后的目标,就是测试对于人类数独解决测试者而言有难度的数独,对于遗传算法求解模型来说也有难度。本文提出的结果似乎支持这样的结论,即遗传算法优化可以很好地满足这些目标。
引言
本文研究是否可以用遗传算法有效地解决,评定和生成数独问题。遗传算法(GA)是一种模拟自然界中发生的达尔文进化[1]的优化方法。
根据维基百科[2],数独是一种来自日本的逻辑游戏,最近在欧洲和北美洲广受欢迎。然而,第一个数独谜题是发表在1979年的美国拼图杂志上的,后来它传播至日本,并于1986年在日本开始流行,后来它在2005年左右成为西方世界的现象[3]。数独,可以说是非常受欢迎和令人上瘾,因为它非常具有挑战性,但同时规则非常简单[4]。
数独问题由9times;9网格组成,共81个位置,分为9个3times;3子网格。数独问题的解决方案是每个行,列和子网格都包含从1到9各整数一个且仅有一个。
数独问题以这样的方式呈现:在网格中给出一些静态数字,这些数字是预先给出的,不能更改或移动。已给出的数字的数量实际并不能决定数独的难度[4],对数独进行评级是数独问题生成中最困难的事情之一,并且大约有15到20个因素会对难度等级产生影响[2]。
已给定的数字矩阵可以是
对称的或非对称的。在对称情况下,矩阵中存在相对于中心的位置对称的多对给定数字。图1显示了由GA生成的数独问题的一个示例。它包含38个给定的数字,并且其他43个空置位数字是可被唯一确定的。这个问题具有非对称的数量,因为数字不是相对于中心点对称的。这个数独的解决方案如图2所示。其中,开头给出的静态数字(图1)与原来的位置完全相同。
在这项研究中,我们试图评估遗传算法如何有效地解决报纸和www.sudoku.com[6]中提出的数独问题。此外,我们评估GA算法效率是否与这些数独问题的所谓难度等级相关。第三个目标是利用从前两个目标中获得的信息,用GA生成新的问题,并评估新问题的难度。
图1一个已有38个确定数字的初始数独
在第一部分中,我们提出数独问题,及遗传算法解题模型和相关其他的工作,第二部分介绍了提出的相关方法,第三部分展示了研究最终获得的结果,第四部分讨论了研究结果及其含义。
遗传算法
所有遗传算法[7]都是基于计算机的优化方法,它们使用自然界的达尔文进化论[1]作为模型和灵感。在该算法框架内,一个问题的解决方案基础被编码为由几个基因组成的染色体的个体。不过与自然相反的是,GA的个体(表型)通常确定性地从染色体(基因型)衍生而来。也就是说,在GA个体“生命时间”期间,年龄或环境并不会改变表型。这些虚拟个体会被反映为适应度函数的问题所测试。每个虚拟个体获得的适应度越好,被选为新个体父母的机会就越大。为了给新一代腾出空间,获得适应度最差的个体将被削除。,同时,GA算法使用交叉和突变操作,创建新的个体。
图2 图1数独的解(字体较粗的数字为已给出的数字)
在交叉操作中,我们会利用已经事先选择好的方法,从父母那里选择新染色体的基因,例如一点、两点或均匀交叉法。在突变操作中,我们会随机地或者使用一些预定义的策略,来改变染色体的随机基因。GA策略通常是精英主义的,因此遵循了达尔文进化论的“适者生存”原则。
相关的工作
数独问题,在约束规划和可满足性研究等方法上,得到了广泛研究[8][9][10]。这些方法对于解决数独也很有效,但不能为每个数独问题提供解决方案。不过,在本次研究中,我们会专注于用进化的方法解决数独。使用GA算法解决数独的主要原因,是为了更多地了解GA算法在包含约束的组合问题中的解决能力,并希望学习新技巧以使GA算法在解决使用GA解决数独的主要原因是为了更多地了解GA在受约束的组合问题中的能力,并希望学习新技巧以使其在解决这个问题领域时更有效。
目前为止,学术领域似乎已有一些关于使用GA方法解决数独问题的科学论文。Moraglio等人[5]已经使用GA与乘积的几何交叉算法解决数独。他们声称他们的几何交叉算法比登山者算法和单独的突变表现得更好。他们的方法有效地解决了[6]中容易的数独,但是对于解决中等难度或更加难的数独问题有困难。他们还承认,进化算法不是解决数独的最有效技术,但是数独是一个有趣的算法开发研究案例。
Nicolau和Ryan[11]使用了一种不同的方法来解决数独:他们的GAuGE(使用语法进化的遗传算法)优化了逻辑运算的顺序,然后应用这些逻辑运算来找到解决方案。
Gold[12]使用了GA来生成新的数独谜题,但该方法似乎效率低下,因为在他们的例子中,他们的GA需要35700代才能想出一个新的开放式数独问题解决方案。在我们的结果中,我们创建了一个新的开放数独解决方案,平均有101代(2020次试验)。
还有一个可用的“数独制造者”[13]软件,据说内部使用遗传算法,并声称生成的数独通常很难解决。遗憾的是,没有详细说明如何使用GA以及生成新数独的速度。
数独的规则意味着解决方案的每列和每行中的数字之和是相等的。因此,数独显然与古代魔方问题(拉丁方)有关,而古代魔方问题中必须填充给定的正方形大小,以使每列和每行的总和相等。在此之前,魔方问题已经用GA算法[14][15]解决了,并且Evonet Flying circus团队[16]也演示了一个魔方解算器。
数独也可以被视为约束满足问题,其中所有行和列总和必须等于45。受约束的优化问题已经用进化算法有效地优化,例如[17][18][19]。
另一个相关问题是生成半色调灰度图像的阈值矩阵[20]。在生成半色调灰度图像时,通过将每个像素的值与阈值矩阵中的对应位置的值进行比较,将图像的灰度值转换为黑色或白色两个值。阈值矩阵中的值应均匀分布;阈值矩阵的每一行和每列中的阈值和应该几乎相等。由Bayer[21]建立的最著名的灰度值阈值矩阵在同一个维度(行或列)中具有相等的阈值和,而在另一维度(分别为列或行)中它们以有规律的方式呈现出差别。此外,阈值的均匀性也要求局部性保持,即任何固定大小的子区域应该具有几乎均匀分布的阈值和。这可以保证结果图像不包含大簇黑色或白色像素。阈值矩阵先前已由GA优化,例如 在[15],[22],[23],[24]和[25]中。
本次研究提出的方法
为了测试所提出的方法,我们决定使用整数编码的精英主义倾向GA策略。GA染色体的大小为81个整数,分为一组9个数字,共9组子块。其中均匀交叉操作仅在子块之间应用,交换突变的序列仅在子块内部应用。
本次研究中预设交换突变概率为0.6,这是尝试突变的数量比例,与本次研究中的实际突变不相等,具体请参见随后的突变细节。
本次研究中人口规模(POP)为21,精英比率(ELIT)为1,通过以下算法选择交配个体x1和x2,可以获得最佳个体:
for( i=POP-1; igt;=ELIT; i--){
x1 = ( int )(i * Math.random() );
x2 = ( int )(i * Math.random() );
hellip;hellip;
}
所有新个体都是首先通过应用交叉操作,再对交叉操作产生的结果进行突变操作后得到的。但是,算法有可能选择x1=x2,在这样的选择中只有突变操作才会改变新个体的基因型。找到一个解决上述问题的方法是阻止这种情况发生的唯一条件,毕竟我们的策略方案使得我们永远不会找不到解决方法。
图3 数独游戏在本研究使用的GA算法中的表现。一个可能的解决方案(个体)是81个的数字阵列被划分成九个数字的九个子块。交叉点只能出现在子块之间(标记为垂直线)。辅助数组用于检查固定位置,如果有一个不等于零的数字,在优化期间无法更改该数字,只有零的位置可以自由更改。
除了数独的基本规则外,给定的固定数字也必须在解决过程中保持不变。因此,数独的解决方案必须遵循以下四个条件:
- 每行必须包含1到9间的每个整数,
- 每列必须包含1到9间的每个整数,
- 每个3x3子网格必须包含1到9间的每个整数,
- 给定的数字必须保持在原始位置。
条件4)可以在用于创建新数独谜题的新的开放式数独解决方案中省略。在数独问题的解决过程中,条件4)必须始终满足。通过适当的求解方法,可以控制条件1)至3)之一,因此只有三个条件可以进行优化。
我们选择了对GA策略进行编程,使得算法可以自动满足条件3)和4),并且仅优化条件1)和2)。数独有9行9列,所以解决策略必须满足18个约束公式。
本研究中使用的GA策略是针对此问题或其他网格类型组合问题而定制的。而该GA策略是最初为魔方解算器[15]和其他组合问题编程的组合问题型GA的修改策略。需要注意,该GA没有使用可能在3x3子网格中生成非法情况的直接突变或交叉操作。然而在非最佳情况下,数独的行和列中可能会有出现了不止一次的整数。以及,遗传算子被规定不允许移动初始数独已给出的固定数字。这一约束由辅助数组保证,该数组指示了数字在其网格位置上是否固定。
在解决方案中,我们决定将数独拼图抽象表示为81个数字的二维整数数组矩阵。该矩阵被分成包括九个数字的九个子块(构建块),对应了从左到右和从上到下的3times;3子网格。在解决各数独问题时,GA策略中的交叉操作仅直接操作整个3times;3的子块。因此,交叉点不能位于构建块内(图3)。
突变操作
首先应注意,突变操作仅应用于各3times;3的子块内部。最初,我们使用了三种不同的突变策略,这些策略通常用于组合优化:交换突变,3交换突变和插入突变。但实际上,由于3交换和插入突变实际上也只是交换或双交换突变的优化,后来我们用子块内的1到5个交换突变的序列形式替换了它们。这样做是因为我们的测试运行表明只有交换突变的GA策略比交换,3交换和插入突变的GA表现更好。
在交换突变中,两个位置的值要进行交换。每次在子块内尝试突变时,GA都会检查辅助数组。如果改变随机选择的位置是非法的,则本轮的突变将被省略。此外,如果我们随机发起比如5个突变组成的序列操作,在交换突变的两个位置合法的情况下,我们才会让GA执行突变。因此,尽管进行1-,2-,3-,4-或5-交换序列操作的机会相等,实际上大多数时候序列操作是无法进行的。在有些情况下,第一次交换尝试就被判定非法,使得没有突变操作被执行,这意味着实际的突变百分比远低于前面提到的0.6。
不过使用不同数量的顺序交换进行的测试也指出,仅具有一个交换突变的GA几乎与同时具有1至5个交换突变序列操作的GA表现得一样好,因此大多数较长的交换突变序列操作被过早中止的事实,实际是无害的。
在本研究的GA中,还有一个特殊规则,以控制突变操作是进行还是放弃。在此规则中,我们有另一个辅助表,告诉每个数字在每行和每列中出现的次数。在算法尝试进行突变尝试时,它会影响一列或两列,一行或两行,总共3或4行和列向量。在最佳情况下,进行交换的两个数字应该总共只出现在这些向量中两次。
以上是毕业论文外文翻译,课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。