数独和声搜索算法分析

×××软计算快报3（2021）100017数独问题的和声搜索算法分析瑞秋·H Chae a，Amelia C. Regan b，*本科生，麻省理工学院，剑桥，MA，美国b美国加州大学欧文分校计算机科学系教授A R T I C L EI N FO关键词：数独谜题和声搜索元搜索局部搜索A B标准和谐搜索元启发式算法已被用于解决许多不同的优化问题。几篇论文研究了它解决数独谜题的有效性。另一篇论文声称，它是无效的解决数独难题，并进一步说，该方法本身缺乏新颖性相比，其他进化算法。本文分析了和声搜索中的搜索过程时，应用到一个特定的数独难题在早期的研究。基本和声搜索过程重新实现和测试，以评估其性能，并验证其适用性的具体例子。我们发现，虽然这个问题的方法的批评是有效的，性能可以提高一个相当简单的修改。首先，我们提出了一个新的目标函数的搜索过程。提出的目标函数有助于搜索方法找到合适的解。其次，介绍了和声搜索的改进形式--和声搜索与局部搜索相结合，并通过比较局部搜索与改进形式和声搜索的性能，分析了改进形式和声搜索在和声搜索过程中的“即兴”作用对于一个特定的问题，改进的和声搜索算法在合适的时间内产生一个具有新目标函数的唯一解。然后对各种数独问题进行了扩展实验。我们发现，虽然修改后的搜索过程更快地产生解决方案，它遭受相同的问题，原来的方法，它有时无法找到一个可行的解决方案。1. 介绍近年来，人们对元分析在组合优化问题中的应用进行了大量的研究。虽然其中一些努力得到了认可和尊重，但另一些努力由于不可预测的表现和缺乏理论基础而面临批评。基于爵士音乐的和声搜索（HS）算法由Geem[9]提出。自提出以来，由于其结构简单、易于应用，HS已被应用于调度优化[6]、可靠性问题[27]和设施布局设计[11]等领域的问题。HS甚至能够对离散变量求导[7]，并且结果可以与参数设置无关[10] 。 然 而 ， Weyland[25] 提 出 了 它 的 新 颖 性 和 局 限 性 的 问 题 ，Weyland[26]对 Geem[8]提出的数独应用提出了批评。Geem[8]给出的结果不能被Weyland[26]验证，HS算法的适用性问题就摆在了人们的面前。我们的研究重点是分析HS作为数独求解器的可用性，引入改进的搜索的方法，并比较原始的搜索方法和我们的修改。请注意，我们并没有解决Wey-land[25]中提到的围绕Harmony搜索的新颖性的争论，然后在Kim[12]和Saka等人[20]中多次反驳。我们只是简单地证明了一些简单的改进可以提高算法在数独问题上的性能。数独谜题将1到9之间的一位数分配给9 9矩阵X中的每个位置。一个数字不能在每一行、每一列和9个3 3块中重复。如图1所示，每个谜题都有一些已经填充了数字的单元格。这个谜题以其令人上瘾的性质而闻名[13]，已经被开发和发布为移动应用程序的许多版本进一步普及。数独谜题的难度不仅取决于预先填充的单元格的数量，还取决于为每个单元格找到合适值所需的技术[19]第10段。 一个空的数独网格有6个。6710 21 可能的组合[5，19]，但预填充的单元格用作约束并减少可能组合的数量* 通讯作者。电子邮件地址：rchae@mit.edu（R.H.Chae），aregan@uci.edu（A.C. Regan）。https://doi.org/10.1016/j.socl.2021.100017接收日期：2020年5月14日;接收日期：2021年5月10日;接受日期：2021年2021年8月8日网上发售2666-2221/©2021的作者。发表通过ElsevierB.V.这是一个开放接入文章下的CCby-NC-ND许 可 证（http://creativecommons.org/licenses/by-nc-nd/4.0/）中找到。可在ScienceDirect上获得目录列表软计算快报杂志首页：www.sciencedirect.com/journal/soft-computing-lettersR.H. Chae和A.C. Regan软计算快报3（2021）1000172×IJ（）×9IJIJ∑3个IJ搜索解决数独难题。此外，我们分析了和声搜索过程的效果，通过比较其结果的变体包含局部搜索。在接下来的部分中，我们在讨论和声搜索之前探索了数独的数学形式。第3节描述了Geem[8]中使用的基本和声搜索，我们提出了一个可能的目标函数来更准确地解决数独问题本节将介绍和详细介绍HS算法的扩展形式第四部分将以往的研究结果与本研究进行了比较。对该算法进行了分析，并给出了进一步的应用最后，我们在第五得出结论。2. 数独问题公式化图1中的数独谜题可以被建模为线性程序[2]。具体来说，它可以被建模为一个二进制整数规划（BIP）一般的n n难题。决策变量定义如下：Fig. 1. Sudoku Puzzle的例子[8]。xk={1，如果元素 i、j n个n矩阵包含整数k0，否则这个问题是线性规划的特殊情况，因为它只考虑约束，可以建模为约束规划[1，2]。因此，目标函数仅被设置为零，如在等式中。(1)并且约束被设置为对其可满足性起作用。最小0（1）S. t. ∑x k= 1，j= 1.. 9，k = 1，.....，第九章（二）图二. 和谐搜索i=19近年来，许多涉及数独的研究工作已经应用于∑x k=1，i=1.. 9，k=1，.....，第九章（三）进化搜索算法，如遗传算法[14]，粒子群优化[17]，人工蜂群算法[18]。 关于元启发式方法的详细讨论可以在Lewis[13]和Mishra等人[15]。在Mishra等人[15]中，j=13qJ3Σx k=1，p=1.. 3，q=1.. 3，k=1，.....，第九章（四）元算法在数独游戏中的性能进行了介绍和分析，但没有包括HS算法。如前所述，我们的论文分析了HS的性能及其对数独的适用性，并不打算支持 或 反 驳 Weyland[26] 或 Geem[8] 中 提 出 的 先 前 研 究 。Coelho 和Laporte[3]中引入了专门为数独谜题设计的启发式算法，并且具有出色的解决时间。因此，将HS的性能与专门为解决数独谜题而设计的其他算法进行比较并不是一个新的贡献。我们的研究主要是在探索HS的性能，并提出了一个修改，这将改善这些难题。我们提出了HS算法与一些修改，嵌入局部=q-2i=3p-2见图4。 重新调整程序。R.H. Chae和A.C. Regan软计算快报3（2021）1000173图三. HM施工过程。R.H. Chae和A.C. Regan软计算快报3（2021）1000174图五、2-opt算法中的双向交换示例。表1实验的结果HMS HMCR PAR算法在迭代中寻找唯一解以获得最优解Weyland[26]和本研究中104次迭代Weyland[26]和本研究中的106次迭代在Geem[8]经协调制度调整后嵌入式本地搜索（HS2E）10.50.70.920.50.70.9100.50.70.9500.50.70.90.010066395167（0.05）20.100337655541（0.1）150.500422n/a（0）140.01002873978（0.35）10.1003413297840（0.15）70.50056n/a（0）30.0100260828969（0.05）1360.100n/a90892（0.1）610.500100388848（0.25）190.010031180210（0.05）120.10094502616（0.1）120.500175n/a（0）140.010010215930（0.3）20.10077364327（0.1）160.50099n/a（0）110.0100n/a203425（0.15）110.100n/a54147（0.2）190.5001325126627（0.15）30.010049450860（0.35）250.100280825597（0.05）70.500188n/a（0）180.010056546484（0.05）20.10014633106（0.15）110.500259n/a（0）330.01001808199（0.15）4图六、在方 程中 生成最优目标值0的 解 决 方 案 的 示 例 。（ 十二）、R.H. Chae和A.C. Regan软计算快报3（2021）100017599∑ ∑+-ijIJIJ∑x=1，i=1.. 9，j = 1，.....，第九章（五）IJIJ-最小值Σxk=1⃒ ∑xk+=3Q1⃒⃒=3个p XK1⃒=-（八）i1ij-⃒BJ1ij-⃒拉吉 3 Q 2我 3 p 2pS. t. i = 1，...，9，j=1，...，9，k=1，...，9，p=1，...，3，q=1，...，3∑9xk=1，i=1，k=1ijxk=1，n（i，j，k）∈G（10）xk∈ {0，1}，ni，j（11）图7.第一次会议。迭代次数的主效应图。图8.第八条。迭代次数的交互作用效应图。见图9。响应优化。9由于目标函数的不同，和声搜索的构造方法不能与搜索过程的构造方法相比。然而，我们能够比较的唯一性解决方案和解决一个特定的数独问题的时间在两个算法。该公式使用CPLEX 12.6在Intel Core i5 CPU，8G内存计算机上进行编码和执行，该计算机在0.01秒内为Geem[8]中给出的示例问题生成最优解。通过CPLEX应用程序检查了使用扩展示例的附加测试（第4.3节）。额外的测试在0.02秒内为最困难的问题生成了最佳解决方案。因此，根据求解时间对每个算法的性能进行评级是无效的。相反，对搜索程序本身进行有效性测试。3. 和声搜索Harmony Search的方法受到爵士音乐家即兴创作过程的启发。这种方法有三个阶段：初始化、即兴创作和记忆更新。和声记忆大小（HMS）被定义为称为和声记忆（HM）的解向量的数量。在初始化阶段，应确定HMS、和声记忆考虑率（HMCR）和音高调整率（PAR）。两个参数，HMCR和PAR，用于构建一个解决方案，为下一代即兴阶段使用随机选择一个新的HM。在生成新的HM之后，基于其解质量来更新HM的新组;如果新生成的HM比前一组中的HM更好，则将新的HM包括到新一代HM中，其中去除最差值。 图 2说明了HM的程序。3.1. 数独基本HS模型正如前面提到的，数独是通过在单元格中填充基季k=1xk=1，n（i，j，k）∈G（6）xk∈ {0，1}，ni，j（7）当量(2) 通过Eq。(4)表示应该为每行、列和块分配单个数字，其中m表示子矩阵x的维数。当量(5)确保每个单元格都必须有一个数字。在等式中，给定的数被设置为1。 其中G表示小区位置的集合和在该小区处具体给出的数字。当量(7)限制变量只能使用二进制。该约束程序可以另一种方式公式化如下：数字1到9，同时遵守矩阵x中的“单一数字”规则[2]。因此，BIP的目标函数不是问题的焦点，约束才是。然而，表3使用HS2E解决数独问题所需的迭代次数简单（36）中等（29）硬（23）简体中文简体中文中文（简体）最小值241969765166262645020708(run时间）（0.6s）（6.8秒）（354秒）（891）（1523年）（1098秒）中位数8822264525678046365191397216998.5成功概率100%百分之七十七百分之六十三百分之八十七百分之六十七百分之八十表2R.H. Chae和A.C. Regan软计算快报3（2021）1000176HS 2 E和2-opt算法的比较Min迭代次数是说Max求解时间（秒）最小值中值是说MaxHS2E139.554.23840.070.750.914.952-opt20379.5584.134420.489.3314.2283.53R.H. Chae和A.C. Regan软计算快报3（2021）10001779999999（∑9（∑99（∑（∑9（∑9（∑∈∕=+≤=+==+=+=+==闪烁=+=像HS这样的改进类型的方法学的一个重要特点是，它们对给定的问题有一种指导性的方法。换句话说，该算法决定是否适应新的解决方案或保留以前的解决方案在每次迭代中取决于结果值。因此，设定目标函数对于开发适当的解决方案非常重要。Mishra等人。[15]引入了各种目标函数，用于使用进化元算法解决数独问题。在Geem[8]中，目标函数基于每行，列和块的总和，如下所示：启发式方法采用某些方法来避免这种重复。在Pacurib等人[18]中，使用罚函数来避免重复，许多其他研究人员在方法中使用了阻塞机制[14，16，22，23]。我们在Eq中提出的目标函数。(9)更严格，因此鼓励在每行、列和块中没有任何重复的解决方案，但它不需要这些解决方案。因此，在每次迭代的最后阶段，在每行中出现多次的数字将被替换为当前行中不存在的另一个数字最小化Z=∑⃒∑xij-45+∑⃒∑xij-45+∑⃒∑xst-45图4示出了在每次迭代的最后阶段中的重新调整的过程。由于数字3在（a）中出现了两次，因此前3被替换为i=1j=1j=1i=1r=1（s，t）∈Br（十二）a 4如（b）所示。4是可接受的替代，因为它在替代之前不存在于行中。如果（a）中的第二个单元格是一个给定的数字，不能被替换，那么第二个3被替换为4。其中，xij=第i行和第j列的单元格，Br=布洛克河数独矩阵X的特征要求每行、列和块的和必须为45。因此，当单个数的分配满足其约束条件时，给定的目标函数应为零.已经提到，给定的目标函数并不能保证数字1到9在一行、一列和一个块中只显示一次[8]。然而，在Geem[8]中没有引入特定的方法来避免这种违规，并且预计迭代本身将驱动该过程生成预期的解决方案。Weyland[26]中报告了零目标函数值（OFV）的约束违反。因此，我们提出了一个修改的目标函数如下。在一行中存在多于三个相同数字的情况下，除了存在用于替换的附加数字之外，替换过程与图4该过程从左到右查找替换位置。一旦该过程找到要替换的号码的特定位置，则为子站选择尚未在行中示出的随机生成的号码。一旦完成，就找到下一个需要替换的位置。它继续进行，直到所有的数字，1到9，都显示在一行中。这个过程增加了找到解决方案的机会3.3. 修改：嵌入本地搜索最小化Z=∑i=19j=12xij-45+∑j=19i=12xij-45局部搜索的性能通常不如发展良好的元搜索有效，但它可以嵌入到启发式算法中，以改善原始方法的搜索过程2-opt算法+∑r=1+∑r=19（s，t）∈Br9（s，t）∈Br2xst-452SST-60+∑i=19j=12Sij-60+∑j=19i=1Sij-60）2（十三）是一种用于各种组合问题的改进技术，由于其简单和易于实现，因此易于适应。该算法最早由Croes[4]提出来解决旅行推销员问题，从那时起，它已被应用于许多其他组合问题。为了将该过程应用于数独，在每行中执行单个双向交换这是因为其中Sij=（xij-x）2和x=5，分别是1至9的偏差和平均值。如果数字1到9均匀分布，则每行的偏差总和预计为60。使用正方形而不是绝对符号的地方增加了强调非负性条件。此外，包含偏差Sij的项确保数字1到9在行、列和块中只出现对于HS在本研究中解决数独，过程完全遵循Weyland[26]和Geem[8]中所示。整个过程总结在图2中。根据HMS随机生成溶液。新的解决方案不断生成，直到满足最大迭代次数。每个新的解决方案是修改使用三种方法之一：记忆的考虑，音高调整，和随机选择。在每个步骤中，使用记忆考虑来从具有HMCR概率的现有HM之一中选择值，并且使用随机选择来以1-HMCR概率均匀随机地从1到9中选择值。这意味着数独矩阵X中每个单元格中的每个数字都是通过内存考虑或随机选择来分配的。具有PAR概率的另一种方法，称为音调调整，被应用于 一个已经由内存考虑分配的《易经》云：“八。除了数字1和9具有下限和上限时，音调调整以1/HM收缩过程在图3.第三章。3.2. 修改：重新调整Geem[8]中的HS没有明确考虑避免每行，列和块中的每个数字但不少在重新调整过程之后，每次迭代的最终HM在每行中具有可行的数字排列，并且在该阶段不考虑每列的可行性。然而，每行中的数字交换迫使算法通过将每个单元格的“单个数字”放置在每个列和每个块中来搜索最佳目标函数。下面显示的是适用于本研究的2-opt算法。图5呈现了在算法开始时的数字交换的示例。步骤1.设C是HM提供的重新调整的初始解，z是OFV。集合Cc，Zz，i1，j i1，nr1，i，jG，其中G是固定单元的集合，如在Eq. （六）、步骤2. 改变溶液C中单元格i和j中的数字。如果这种交换的结果C′改善了OFV，z′

下载后可阅读完整内容，剩余1页未读，立即下载