【论文阅读】（2017）The late acceptance Hill-Climbing heuristic

---

论文来源：（2017）The late acceptance Hill-Climbing heuristic
作者：Edmund K. Burke 等人

---

一、摘要

• 本文介绍了一种新的非常简单的搜索方法，称为延迟接受爬山（LAHC）。
• 这是一种局部搜索算法，当候选成本函数优于之前的多次迭代时，它接受非改进移动。这个数字作为一个算法输入参数出现，它决定了搜索过程的总处理时间。
• 本文用一系列旅行推销员和考试时间表基准问题对该方法的性质进行了实验研究。
• 此外，我们还将LAHC与采用冷却计划的著名搜索技术进行了公平的比较：模拟退火（SA）、阈值接受（TA）和大洪水算法（GDA）。
• 此外，我们还讨论了该方法在赢得国际比赛中的成功，以自动解决幻方问题。
• 我们的实验表明，LAHC方法简单、易于实现，而且是一种有效的搜索过程。
• 对于大多数研究实例（尤其是大型实例），其平均性能优于竞争方法。
• 此外，LAHC方法在规模独立性方面具有额外的优势（与上述基于冷却计划的方法相比）。我们举了一个例子，旅行推销员问题中成本函数的重新缩放会显著降低三种基于冷却计划的技术的性能，但绝对不会影响LAHC的性能。

---

二、Late Acceptance Hill Climbing

延迟接受启发式的初始思想相当简单：接受条件中的控制参数取自搜索历史。

这种启发式方法可以被视为HC的扩展，只有一个区别：在贪婪爬山中，将候选解决方案与当前解决方案进行比较，但在延迟接受爬山（LAHC）中，将一个候选方案与之前几次迭代的当前解决方案相比较。

除了新的接受条件，LAHC的其他细节与其他本地搜索方法（如HC、SA、TA或GDA）相同，即，算法从随机初始解开始，并迭代地接受或拒绝候选，直到出现停止条件。

基本上，LAHC可以采用其接受规则，同时保持当前成本函数先前值的固定长度L h（历史长度）列表。将候选成本与列表的最后一个元素进行比较，如果更好，则接受候选。在验收程序之后，更新列表，即，将新的当前成本添加到列表的开头，并从列表的结尾删除最后一个元素。注意，在仅接受的情况下，增加的当前成本等于候选成本，但在拒绝的情况下则等于先前的值。

长度 $L_h$ 显示为该技术的单个算法（和用户指定）参数。
列表的实际初始化可以自动完成，即使在第一次迭代时没有先前的记录。我们在这里看到了两种可能的变体：

• 我们可以生成 $L_h$ 始终接受的移动并记录目标函数的值
• 或者只指定列表中的所有元素等于初始成本。

初步测试没有显示这些变体之间的性能有任何明显差异，但我们认为第二个变体更可取，因为它节省了CPU时间。应该注意的是，当初始列表包含比初始成本高得多的所有值时，第二个变量就变成了第一个变量。但是，我们不建议使用比初始成本低得多的值来初始化列表，因为在这种情况下，LAHC在开始时会变成HC。

除了基本的变体之外，延迟接受的想法可以以各种各样的方式实施到实践中。事实上，拟议的LAHC可以有大量的变化和扩展。尽管其中许多仍然未被开发，但我们的测试揭示了一些修改，我们注意到LAHC的性能有一定的改善。第4.2节给出了这些测试的结果。首先，我们建议将延迟接受规则与贪婪规则相结合（如SA、TA和GDA中所做的），即始终接受非恶化的移动。因此，其在第i次迭代时的最终验收条件可由公式1表示。

在该公式中，$C_i^{\ast }$ 是候选成本，$C_{i-1}$ 是当前成本，$C_{i-L_h}$ 表示当前解 $L_h$ 迭代的成本，等于$f(i$ % $L_h$)，%为取余符号。显然，当 $L_h$ 等于1或0时，LAHC就是贪婪HC。因此，当 $L_h$ 等于2或更高时，LAHC获得其独特的性质。

其次，历史记录的方法也可以增强。这里，我们建议只更新具有更好值的列表，并排除具有更差值的任何更新，即，当 $C_i<f_v$ 时，$C_i$ 被分配给 $f_v$，否则 $f_v$ 不会改变。

这些修改会在搜索的最后阶段影响LAHC行为：与其他本地搜索（如SA或GDA）类似，它“变成”HC（停止接受恶化的移动）。这意味着我们可以在这里应用广泛用于HC（以及上述技术）的停止条件，其中当不可能进一步改进时终止搜索。这通常是通过计数非改进（空闲）迭代来检测的。当非改进迭代达到总迭代次数的2%时，我们的算法停止。

为了避免提前终止，搜索的最小长度限制为100000次迭代。参见（Burke&Bykov，2012），了解可能的LAHC停止条件的更详细讨论。

最后，我们提出了列表维护机制的标准 FIFO（先进先出） 优化。这里，列表的元素是不可移动的，并且列表显示为长度为Lh的适应度数组 ( F a = { f 0 , f 1 , f 2 , . . . , f L h − 1 } ) (F_a=\{f_0,f_1,f_2,...,f_{L_h-1}\}) (Fa​={f0​,f1​,f2​,...,fLh​−1​}) 。在第 $i$ 次迭代时，其虚拟起点 $v$ 计算如下：

其中“mod”表示整数除法的余数。现在，将 $f_v$ 的值与候选成本进行比较，在接受或拒绝后，将新的当前成本值分配给 $f_v$ 。图1显示了LAHC最终版本的伪代码。本文中的所有实验均使用该变体进行。

---

第三节和第四节内容较多，我也没怎么细看，如果只需要掌握方法的话看看第二节就可以了，感兴趣可以看看原文，我这里就只放部分内容

三、LAHC技术性能的研究

3.1 Benchmark problems

我们对两类问题进行了实验研究：旅行推销员问题和考试时间表问题。

旅行推销员问题（TSP）是一个经典的（可能也是研究得最深入的）NP难组合优化问题。它有一系列实际应用：从印刷电路板组装到X射线晶体学。通常，这个问题被表述为多个城市之间的距离不同。目标是找到一个最短的封闭游览，而每个城市只游览一次。

一个著名的TSP数据集集合（TSPLIB），可从http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ 。它包含111个数据集，我们在其中选择了7个大小从783到3795个城市的实例进行测试。表1给出了它们的名称和大小。

考试时间表问题是另一个经过深入研究的NP难组合优化问题。它代表了在有限的时间段（通常是房间）内定位大学考试的现实任务。这个问题可以看作是图形着色问题的一个扩展，具有大量附加的软约束和硬约束。尽管考试时间表问题的规范有不同版本（代表不同的制度要求，参见（Burke，Elliman，Ford，&Weare，1996）），但最常见的硬性限制是，任何一个学生都不能同时参加两次考试。其他硬性限制规定了房间的可用性，与ex-ams的持续时间和相应的时间段相匹配。软约束代表了学生和行政偏好，例如学生或更大的学生应提前安排考试间隔时间等。

在本研究中，我们使用了第二届国际时间表竞赛（ITC2007）中给出的考试时间表问题规范。其描述见（McCollum等人，2010）和原始竞赛网站：http://www。cs.qub.ac.uk/itc2007/。该站点还包含12个数据集，我们在本文的实验中使用这些数据集。这些数据集的一些特征如表2所示。应该注意，TSP和考试时间表问题都是最小化问题，因此在我们的所有实验中，结果越低越好。

3.2 Experimental software

使用我们在Delphi 2007中开发的软件对所提出的技术进行了评估，该软件在PC Intel Core i7-3820 3.6千兆赫兹、32 GB RAM、Windows 7 64位操作系统下运行。创建了两个专用模型：第一个用于TSP，第二个用于考试时间表问题

3.3 Experiments

对LAHC特性的研究是从分析其对算法参数变化的响应开始的：历史长度$L_h$。在第一系列实验中，我们演示了成本函数在整个搜索过程中是如何下降的。该算法与我们的基准问题一起运行多次，同时改变$L_h$。在搜索过程中，每秒记录当前成本。所有这些点都在图中描绘（用曲线连接），其中轴表示当前时间和当前成本。图2显示了U1817实例绘制的四条曲线的示例：$L_h=1$（即Gredy HC）、5000、15000和30000。应注意，为其他基准实例绘制的成本下降图与此示例相似。

在该图中，所有图表都是从相同的初始解决方案开始的，成本函数约为180 0 0 0。HC几乎立即提高了成本。L h=50 0 0的LAHC提高成本的速度较慢；其中$L_h$＝150 0 0甚至更慢，并且$L_h$＝30 0 0 0产生成本函数的最慢（在四条曲线上）改进。这一观察表明，LAHC的一个主要特点是：适应度阵列越长，成本下降越慢。在使用LAHC的所有实验中都观察到了这种行为。此外，这种行为是许多其他单点搜索启发法的典型特征：在SA、TA和GDA中，也可以通过调整冷却系数来调节成本下降的速度（参见Burke等人，2004）。

---

四、LAHC性能评估

4.1 评估方法

4.2 LAHC不同变体的性能

4.3 LAHC与其他技术的比较

4.4 LAHC的规模独立性

---

五、Conclusions and future work

在本文中，我们提出了一种新的局部搜索技术（LAHC），该技术具有一系列独特的特性，可概括如下：

• 它几乎和贪婪的HC一样简单，但更有力量。因此，它可以很容易地在实验和实际系统中实现。此外，开发人员可以用最小的努力通过更强的搜索技术来替代现有系统中的HC。
• 它智能地使用在先前迭代期间收集的信息。它可以被视为自适应记忆编程的另一种变体（见Tailard、Gambardella、Gendreau和Potvin，2001）。
• 它取决于调节CPU时间的单个算法参数。所提出的实验表明，CPU时间与此时间参数大致成正比。相应地，与大多数现代元启发式方法相比，它可以用更少的精力进行很好的调整。这对从业者尤其有吸引力。
• 它在大多数基准问题（尤其是大型问题）上都优于SA、TA和GDA。考虑到竞争对手的算法得到了很好的研究，但对LAHC的研究才刚刚开始，这表明LAHC具有进一步发展的巨大潜力。
• 与基于冷却计划的算法相比，它不依赖于比例。这表明它在非线性问题上具有更强的可靠性，这在新的应用领域可能是有益的。
• 它不使用特定类型问题的属性，因此可以定位为通用元启发式。为了确认LAHC的普遍性，我们对旅行推销员和考试时间表问题进行了实验评估。我们期望它可以应用于其他单点搜索方法适用的任何优化问题。

本文介绍了LAHC的文献。当然，这需要进一步深入研究。可能提出该算法的进一步改进和变化。例如，可以从拟合度数组中随机获取比较值，也可以将其计算为所有元素的平均值。适应度阵列可以是可变长度的，或者可以在某个点重新分配其元素的值（类似于基于冷却计划的方法中的“重新加热”）。此外，在贪婪HC适用的进一步混合方法中，LAHC可能是有益的，例如，在迭代局部搜索或记忆算法中。

此外，还应进一步研究LAHC的性质。当应用于某些特定的非线性问题时，所证明的尺度独立性可能是LAHC的一个额外优势。此外，值得研究图4所示的LAHC角系数。每个粒子的情况都不同，可能反映了所研究问题的某些性质。

最后，我们提出并应用了一种使用成本函数的重新缩放来检验搜索启发式的规模独立性的方法。我们认为这是未来研究的一个很有前途的课题。例如，研究具有相同重新缩放问题的其他搜索方法的性能可能是有益的。