介绍
优化是一个广阔的研究领域，有着数百年的历史。它处理各种优化问题和解决方法。尽管早期优化的特点是开发能够找到最优解的算法，但最终人们发现许多优化问题无法有效地解决最优问题。此类问题的著名示例是连续优化域中的多模态不可微函数 [ 1 , 2 ] 和离散优化域中的 NP 难题 [ 3 – 5]]。随着功能日益强大的计算机的出现，启发式算法已迅速成为解决困难优化问题的主流方法，在许多情况下取代了精确算法的使用。换句话说，研究的重点已经从设计和开发找到最佳解决方案的算法转移到设计和开发能够快速提供良好解决方案（尽管不能证明是最优的）的算法。自从 Glover [ 6 ]的开创性工作以来，指代此类算法的最常用术语是元启发式算法。

人们已经进行了许多尝试来提供术语“元启发式”的定义，该定义既精确又涵盖文献中提出的所有不同的元启发式。我们在本文中采用的元启发式网络[ 7 ]提供的定义如下：
“元启发式是一组算法概念，可用于定义适用于各种不同问题的启发式方法。换句话说，元启发式算法可以被视为一种通用的算法框架，只需相对较少的修改即可应用于不同的优化问题，以使其适应特定的问题。”
一些最流行和性能最好的元启发法包括进化计算 [ 8 – 12 ]、禁忌搜索 [ 13 , 14 ]、模拟退火 [ 15 , 16 ]、蚁群优化 [ 17 – 19 ]、粒子群优化 [ 20 – 22 ]，以及迭代局部搜索[ 23 , 24 ]。

为了提高元启发式实施的效率，研究人员重新定义了各种元启发式的组成部分，并探索了实施它们的新方法。然而，由此产生的大量可能使用的组件大大增加了设计过程的复杂性。因此，手动实现元启发式方法（即逐一手工制作组件）的效率变得较低。
为了解决这个问题，并受到受自然过程（例如进化计算、模拟退火、蚁群优化和粒子群优化）启发的元启发法早期成功的推动，元启发法社区的一些成员提出了基于“新颖”的元启发法。基于一组不同的隐喻。然而，这种方法不仅是低效的手动设计方法的另一个例子，而且还给整个领域带来了许多不良后果。主要的负面后果是，大多数时候，所提出的“新颖”元启发法的唯一新颖之处是使用新的且令人困惑的术语。对这些“新颖”的元启发法的分析表明，通过改变用于描述它们的术语，它们通常可以准确地映射到已经发布的元启发法。25-34 ] 。​

另一种方法是提出自动算法设计方法，其中人类的参与不太重要[ 35 ]并且不需要新颖的隐喻。这些自动方法的开发及其在创建有效的元启发式实现中的应用是当前元启发式领域的中心主题。在本文中，我们详细研究了自动设计方法，并描述了如何使用它来创建新一代高性能元启发式实现。在对自动设计方法进行检查之后，我们对元启发学领域的基本方面进行了一些思考，我们相信这将有助于推动该领域的发展。

本文的其余部分安排如下。“元启发式”部分通过解释元启发式的主要特征和分类来对元启发式进行一般介绍。“元启发式的手动设计”部分详细阐述了手动算法设计方法的缺点，并讨论了“新颖”的基于隐喻的算法的趋势及其对该领域的负面影响。“元启发式自动设计”部分描述了自动算法设计范例及其在从自动配置框架开发高性能元启发式实现中的用途。“讨论”部分介绍了我们对该领域三个基本方面的改进的观点：研究的重点、元启发式实施的基准测试方式以及新元启发式的创建。

元启发法
从广义上讲，元启发法是一种优化技术，它从搜索空间中提取信息并使用它来将搜索引导到可以找到高质量解决方案的区域。大多数元启发法具有以下特征： 它们是迭代的，即通过优化过程基于起点或完整的初始解决方案构建/扰动解决方案，该优化过程由多个重复迭代的步骤组成；他们使用随机化——也就是说，他们在一个或多个组件中使用随机变量；它们具有用户定义的终止标准，例如，达到最大计算时间或获得最低期望质量的解决方案。

元启发法可以以不同的方式进行分类。例如，它们可以是建设性的，也可以是扰乱性的，具体取决于它们创建新候选解决方案的方式。它们可以是基于记忆的，也可以是没有记忆的，具体取决于它们是否记住解决方案（或解决方案组件）。它们也可以是基于隐喻的或非基于隐喻的，具体取决于它们是否受到隐喻的启发。然而，区分它们的最常见方法之一是通过每次迭代中处理的解决方案的数量，即区分单一解决方案和基于群体的解决方案。

在单一解决方案元启发法中，优化过程基于通过微小变化迭代改进的单一解决方案。这种类型的元启发式的例子包括禁忌搜索[ 13 ]、模拟退火[ 16 , 36 ]和迭代局部搜索[ 23 ]。相比之下，基于群体的元启发法并行维护多个解决方案，并将它们组合起来创建新的解决方案。大多数群体智能[ 22,37-39 ]和进化算法[ 8-12,40 ]都属于这一类。

基于群体和单一解决方案的元启发法具有不同的、通常是互补的优化能力。例如，虽然基于群体的元启发法通常更擅长探索搜索空间并快速识别一些最有前途的区域，但单一解决方案元启发法往往在改进现有解决方案方面更有效。因此，通常将这两种类型的元启发式方法结合起来以产生能够更好地执行鲁棒优化的元启发式实现。这样做的两种方法是基于组件的混合方法，其中基于群体的元启发法包括单解决方案元启发法作为其过程中的附加组件，以及算法顺序混合法，其中两个元启发法相继执行，41 , 42 ]。

尽管大多数元启发法具有相同的高级特征（即，它们是迭代的、随机的，并且具有用户定义的终止标准，如上所述），但它们在许多方面可能有所不同，包括用于对搜索进行采样的特定机制空间、他们组织搜索过程的方式，以及他们用来控制探索与利用权衡的机制。在某些情况下，这些方面是通过从自然、社会或人造过程中汲取灵感在元启发法中实现的。使用“基于灵感”的方法创建的元启发法通常被称为基于隐喻的元启发法[ 43 ]。

事实上，从其他知识领域寻找灵感的方法对于设计一些性能最佳的元启发法非常重要。早在 20 世纪 70 年代，利用自然发生的优化过程（例如自然选择的进化，激发了进化计算 [ 8 , 9 ]）来制定新的优化算法就开始吸引计算机科学和工程领域的研究人员。然而，正是在20世纪80年代和90年代初，从其他知识领域寻找灵感的方法开始在优化领域得到大力探索，并成为其发展的主要推动力。值得注意的是，在这几十年里，热力学原理被用来开发模拟退火[ 16，[ 36 ]，一些蚂蚁物种的觅食行为被用来开发蚁群优化[ 44-46 ]，鸟群的动态和社会相互作用被用来开发粒子群优化[ 20-22 ]。

由于它们的成功，这些基于隐喻的元启发法成为优化文献中研究最广泛、理解最透彻的技术之一。他们成功的原因不是他们的灵感来源；而是他们的灵感来源。相反，他们引入了新颖且有用的算法概念，可以方便地用于优化。然而，元启发式研究界的一些成员仍然继续提出“新颖的”基于隐喻的元启发式，其唯一的新颖之处在于所选择的隐喻和术语。

元启发法的手动设计
元启发式手动设计的一般问题
从历史上看，新的元启发式方法和具有改进性能的元启发式实现是通过手动设计创建的，也就是说，算法设计者根据他们的知识（经验、理论或直觉）和专业知识手动设计或修改设计[35 , 47 ]。

尽管手动设计对于实现高性能元启发法非常有用，但它的效率正在降低。事实上，元启发式的高性能实现的设计需要在大量可能的元启发式组件中进行选择，并微调其参数的值，并且期望开发人员依靠自己的知识和专业知识来执行是不现实的。有效地完成这些任务。人类算法设计者受到他们以前的经验的影响，并且他们可以尝试的设计数量受到限制；因此，设计过程既耗时又容易出错。在实践中，手动设计的主要缺点是它限制了探索新的元启发式设计的灵活性以及所开发的元启发式的通用性。此外，
这种灵活性的限制是由于元启发法传统上被认为是整体块的事实造成的。也就是说，它们具有预定义的刚性结构。这种严格的结构限制了修改元启发式行为的选项：设计者可以调整元启发式的参数值或重新定义其组件[ 48 ]。然而，高性能混合元启发式实现[41、42、49、50]的存在凸显了超越原始整体块界限的元启发式设计的重要性。然而，手动创建混合设计很困难。

普遍性限制是由于以下事实造成的：在大多数情况下，元启发式的初始开发是在考虑到某些应用的情况下进行的；因此，所开发的元启发法的性能往往对于开发元启发法所针对的特定问题或问题类别非常好，但对于其他问题或问题类别则不太好。一般来说，当元启发式算法应用于与其最初开发的问题具有不同特征的问题时，或者当优化场景具有初始元启发式设计中未考虑的特定约束时，元启发式算法的性能往往会大幅下降，例如只允许运行有限的时间或无法使用与问题相关的信息（例如，黑盒场景或不明确的现实生活问题）[51、52 ] 。​ 在这种情况下，必须针对新问题设计新的元启发式实现，以获得良好的结果。

然而，手动调整元启发式算法以提出新的元启发式实现的过程非常费力，并且存在一些潜在的缺陷。首先，如上所述，新的元启发式实现的设计者可以首先尝试通过使用不同的参数值或根据他/她的知识修改实现中的一个或多个元启发式组件来增强元启发式的行为。和专业知识，可能会阻碍元启发法的表现。如果这个过程（仅取决于人类设计者的能力）不能产生预期的结果，那么唯一的选择可能是从头开始设计和实现新的元启发式方法。然而，后一个任务比前一个任务更具挑战性，因为算法设计者现在必须创建更好的设计

最后，手动设计使元启发式设计成为一个主观过程，其中某些设计决策背后的基本原理仍然隐藏在人类设计师的脑海中，因此设计师学到的东西不会与研究界的其他人分享。在实践中，手动设计涉及通过反复试验在大量选项中找到良好的算法设计。为了减少选项的数量，算法设计者消除了根据他们的知识认为不适用于当前问题的设计。经过实验测试但未产生良好结果的设计通常会被丢弃，而不是在技术论文中报告。详细了解哪些设计被认为不适合测试以及哪些设计已被证明不成功将有助于指导新设计的创建。

基于隐喻的“新颖”元启发式问题
无论好坏，手动设计都是以自然系统中观察到的优化过程为指导的。尽管从自然中汲取灵感在基于隐喻的元启发法的早期是成功的，但当诸如进化计算、蚁群优化、模拟退火和粒子群优化等创新且性能良好的元启发法被提出时，情况已不再如此。相反，提出“新颖”元启发法的论文已变得司空见惯，其中隐喻的使用并没有提供自然行为和实施的优化过程之间的清晰映射。
在过去的几十年里，来自最多样化的自然、人工甚至超自然行为的数百个隐喻已被用来开发“新颖”的基于隐喻的元启发法。在大多数情况下，这些元启发法基于简单的数学模型，这些模型模糊地匹配激发它们的行为，并使用复杂的隐喻描述来呈现，这使得它们难以理解（下面提供了一些示例）。最近，一些最广泛的基于隐喻的“新颖”元启发法已经接受了严格的分析，这些分析提供了令人信服的证据，证明它们不是新颖的，而是成熟元启发法的复制品或微小变体，并且它们唯一的新颖性是正在使用新的隐喻和术语 [ 25 – 27，29-34 ] 。​

特别是，在提出“新颖”的基于隐喻的元启发法的论文中发现了三个主要问题[ 53 ]。首先，他们引入了缺乏科学依据的无用隐喻——例如僵尸、轮回和智能水滴——并使用了新的术语，使人们难以理解所提出的想法。其次，它们缺乏有意义的新颖性，因为通常提出的想法是已知的。第三，他们使用了糟糕的实验验证和比较实践，例如将在最新计算机上运行的“新颖”元启发法与在旧计算机上运行的旧算法进行比较，并且他们使用的基准测试台包含可以被“新颖”元启发法利用的偏差，因此支持他们的表现。[ 54]中提供了这种不公平比较的例子]，其中通过实验证明，“新颖”的粘菌、蝴蝶和哈里斯鹰元启发法等，利用中心偏置算子，当测试台包含具有最佳解决方案的问题时，可以提高其效率。搜索空间的中心。

基于隐喻的“新颖”元启发式趋势的负面后果远远超出了一些受牵强行为启发并在具有方法论问题的论文中提出的算法的存在。由于这种基于不科学实践的趋势，数百种“新颖”的基于隐喻的元启发法已经在文献中发表[ 55 ]。这种趋势之所以持续存在，很大程度上是因为手动设计仍然是创建元启发法的主要方法。在本小节的其余部分中，我们将解释为什么“新颖”的基于隐喻的元启发法存在问题，列出其一些负面后果，并概述为解决该问题所做的努力。

比喻匆忙
自 2000 年代中期以来，优化领域出现了寻找“有趣”行为的热潮，这些行为大多是自然和社会现象的例子，可以用来设计“新颖”的元启发法。在提出这种元启发式的众多论文中，作者使用了以下步骤序列：（a）他们首先声称发现了一种在优化中具有应用的新行为，（b）他们提出了为什么在他们看来，行为很有趣，并提供了基于“有趣”行为的其他“新颖”元启发式的广泛列表，（c）他们使用行为术语而不是优化中通常使用的术语来描述他们提出的元启发式，并且（d ）他们将“新颖”的元启发式与其他优化技术进行比较，

与其他作者（例如[ 56 ]）一样，我们避免引用提出错误的基于隐喻的元启发法的出版物。邀请读者访问进化计算图鉴 [ 55] 获取此处讨论的元启发法列表，或使用其名称（在文本中以斜体给出）在 Google Scholar 上搜索特定的元启发法。作为一个具体的例子，我们考虑灰狼优化器。据其作者称，这种元启发法的灵感来自“灰狼组织狩猎的方式”，遵循“严格的社会等级制度”。为了描述元启发式，作者引入了一个新术语，其中候选解决方案被称为“狼”，“包”（即候选解决方案集）中的三个最佳解决方案被称为“阿尔法”， “beta”狼和“delta”狼，问题的最优值是狼正在狩猎的“猎物”。如[ 30,32 ]所示]，灰狼优化器元启发式基于在每次迭代时计算超三角形的质心的思想，该超三角形的顶点是三个最佳解决方案（即“alpha”、“beta”和“delta”）的位置。然后，计算出的质心用于偏置剩余解（即“包”）的移动。灰狼优化器元启发法在一组 29 个连续函数以及一些经典的工程设计问题上进行了评估，所有函数都具有低维度和/或最优值位于搜索空间的中心。与 PSO、差分进化 (DE) [ 57 ] 和协方差矩阵适应进化策略 (CMA-ESs) [ 54]进行比较]，发现具有相似的性能。考虑到“新颖的”灰狼优化元启发式算法后来被证明是 PSO 的变体 [ 30 , 32 ]，这种性能上的相似性并不令人惊讶。

流行的基于“小说”隐喻的元启发法的另一个例子是布谷鸟搜索，它是使用“布谷鸟的寄生行为”的隐喻来描述的。在这种元启发式中，初始解决方案被称为“布谷鸟”，而受到干扰的解决方案被称为“鸡蛋”。布谷鸟搜索元启发式基于这样的想法：一些“布谷鸟”在其他鸟类的“巢”中产下“蛋”（它们是搜索空间中的随机点），并且这些“蛋”中只有一些在下一个鸟儿中仍然存在。迭代。布谷鸟搜索的作者将他们的元启发式算法与遗传算法和 PSO 的第一个版本进行了比较。使用 13 个连续函数进行比较，这些函数在搜索空间的中心都有一个最优解。由于作者没有提供有关函数维数的任何信息，因此最初很难评估其结果的质量。然而，布谷鸟搜索被证明是一种利用DE重组机制的进化策略[31 ]，因此并没有提高现有技术水平。

隐喻热潮的后果
已经发表了大约 500 篇提出“新颖”的基于隐喻的元启发法的论文 [ 33 , 58 ]。其中许多论文的作者声称提出了一种受某种“智能”行为启发的新技术，甚至开辟了一条新的研究途径。例如，参见 Satish Gajawada 的“博士后：人类优化”。尽管人们越来越意识到这些“新颖”的元启发法在该领域引起的问题，但元启发法社区的一些成员仍在继续积极提出更多此类元启发法。
提出“新颖”元启发法的论文发表所引起的主要问题之一是将文献碎片化为数十个几乎无法区分的领域[ 53 , 56]。这种碎片化的直接后果是文献混乱，其中相同的想法和概念被使用新隐喻衍生的不同术语反复重新引入。这反过来又使得元启发法的比较变得越来越具有挑战性。例如，“灰狼狩猎”和“杜鹃下蛋”的优化能力很难进行比较。此外，当人们分析为这些元启发法提出的数学模型时，结果发现它们要么是多年前发布的优化技术的副本要么是微小的变化。

数百种基于隐喻的“新颖”元启发法的发表给人留下了这样的印象：每一个基于“有趣”行为的简单化数学模型都值得添加到元启发学文献中。尽管科学场所有责任确保其产出具有科学价值，但存在方法缺陷和缺乏科学原理的文章尽管无法对该领域做出有意义的贡献，但仍在接受同行评审和发表。例如，考虑以下智能水滴纸的摘录：“在自然界中，我们经常看到水滴在河流、湖泊和海洋中移动……我们也知道水滴没有可见的眼睛，无法找到目的地（湖泊或河流）。” 参见[ 28、29​] 对这种元启发式进行严格分析。

最后，正如 Sörensen [ 43 ]所记录的那样，基于隐喻的“新颖”启发式方法损害了该领域的声誉，并在 Maturana 和 Fouhey 的“幽灵检测的光谱方法”中进行了戏仿。特别是，它们损害了群体智能和进化计算领域，而这些领域被用来证明隐喻的使用是合理的。事实是，尽管隐喻可以指导成功的元启发法的设计，但很少这样做。

努力缓解隐喻热潮
阻止基于隐喻的“新颖”元启发法传播的努力主要包括提高人们对其如何对该领域产生负面影响的认识。最早的工作之一是 Dennis Weyland 的“对和声搜索算法的严格分析”[ 25 ]，它通过逐个组件的比较表明和声搜索是一种进化算法。该论文还指出了一些系统性问题，这些问题使得和声搜索尽管缺乏新颖性，但却变得流行起来。另一个值得注意的例子是 Sörensen 的《元启发学——隐喻暴露》[ 43 ]，这是第一篇明显试图引起人们对元启发学领域“隐喻问题”的关注的论文。

尽管这些论文在已经意识到这个问题的社区之外几乎没有引起共鸣，但它们鼓励其他研究人员采取行动并提出可能的解决方案。大多数这些努力可以分类如下：（a）基于隐喻的元启发法的批判性分析；(b) 建模框架、分类法和无隐喻描述；(c) 编辑政策。
在（a）类中，我们努力澄清“新颖”的元启发法是否存在任何真正的新颖性，并深入了解作者使用特定隐喻的原因。类似于 Weyland [ 25 ] 的基于组件的分析，已经针对以下“新颖”元启发法进行了：基于生物地理学的优化 [ 59 ]、黑洞优化 [ 27 ]、智能水滴 [ 28 , 29 ]、灰狼优化器、飞蛾火焰优化算法、鲸鱼优化、萤火虫算法、蝙蝠算法、蚁狮优化器 [ 30 , 32 ] 和布谷鸟搜索 [ 31]。这些分析的结论很明确：这些“新颖”的元启发法都没有什么新颖之处。在一项焦点略有不同的批判性研究中，梅尔文等人。[ 60 ]证明引力搜索算法作为隐喻是失败的，因为它基于与牛顿引力不一致的数学模型。引力搜索算法的失败表明，在没有合理动机的情况下使用新隐喻可能会导致元启发法无效。

类别 (b) 包括分类法和建模框架，它们根据设计中的模式对元启发式进行分组 [ 26 , 33 , 34 , 61 – 64 ]。这些努力的目标是为元启发式社区提供一种工具，可以识别构成“新颖”元启发式的组件，从而揭示它是否确实新颖。主要挑战是合并足够多的组件。虽然已经朝着这个方向迈出了第一步，但这是一项巨大的努力。
同样在类别 (b) 中，我们找到了研究基于隐喻的元启发法的工作方式及其与其他元启发法的关系的论文。例子包括 Lones 的论文 [ 65 , 66 ]，这些论文使用无隐喻的术语描述了一些基于隐喻的“新颖”元启发法。此外，越来越多的论文旨在通过编制基于隐喻的元启发法列表和/或分析其性能来量化问题[ 54、55、58、67、68 ]。

最后，类别（c）包含明确禁止提交提出基于隐喻的元启发法的论文的编辑政策，除非作者能够提供令人信服的证据证明隐喻的使用有助于先进技术的进步。建立此类政策的一些期刊有4OR [ 69 ]、Journal of Heuristics [ 70 ]、Swarm Intelligence [ 71 ]、ACM Transactions on Evolutionary Learning and Optimization [ 72 ] 和Engineering Applications of Artificial Intelligence [ 73 ]]。制定编辑政策无疑是阻止基于隐喻的元启发学出版的最有效机制之一；然而，这种方法仍然是例外而不是规则。

元启发式自动设计
随着更有效地解决日益复杂的问题的需求不断增长，对更好、更高效的问题解决方法的需求也在增长。这促使研究人员寻找不受手动设计缺点影响的替代设计方法。这项研究的主要目标之一是减少对人类算法设计者的严重依赖，这种依赖使得设计过程存在偏差、耗时且容易出错。自动算法设计方法是手动设计的有力替代方案。这些方法通过利用自动算法配置方法的最新进展，消除了人工参与的需要。

元启发式实现的自动设计是一种相对较新的范例，其中元启发式实现的创建被处理为优化问题，其中包括找到元启发式组件和参数设置的组合，这些组合在应用于所考虑的优化问题时将表现良好。为了实现这一目标，元启发式实现的自动设计方法依赖于两个主要组件：设计空间，即可以通过组合元启发式组件和参数设置获得的所有可能的元启发式设计的集合，以及自动配置工具（ACT） ——也就是说，一个允许探索元启发式设计空间的工具。最近几年，
在元启发式文献中，将元启发式实现的设计作为优化问题的方法有时被称为超启发式。超启发式一词的现代定义如下：“一种用于选择或生成启发式方法来解决计算搜索问题的搜索方法或学习机制”[ 74]]。然而，超启发式的最初研究并不是集中在元启发式实现的自动设计上，而是从预先存在的元启发式实现的组合中选择合适的实现，即所谓的组合优化问题的“选择启发式的启发式” 。目前，元启发式的自动设计采用超启发式方法，其方式与自动设计方法相同，即定义元启发式设计空间并使用优化算法对其进行探索并找到合适的设计。事实上，在绝大多数情况下，自动设计方法和超启发式方法之间的唯一区别在于，超启发式方法使用遗传编程来探索设计空间[ 75 , 76 ]。

元启发式设计空间：基于组件的视图
定义元启发式设计空间的第一步是导出所考虑的元启发式的基于组件的视图。为此，算法设计者首先确定可以实现元启发法的组件的方式（例如，通过研究文献中已提出的元启发法的不同实现），然后根据它们的功能对它们进行分组。以这种方式获得的组件定义了元启发式设计空间，并使用 ACT 进行组合（如下一节所述）。ACT 将这些组件（可以是数字组件、分类组件和从属组件）视为要优化的参数。值为实数或整数的数值参数是经典参数，例如 EC 中的突变率、ACO 中的蒸发率或 PSO 中的粒子惯性。分类参数是特定组件功能的替代方案，例如 EC 中的重组算子、ACO 中的解构造规则或 PSO 中的群体拓扑。最后，从属参数是那些仅对于其他参数的特定值所必需的参数——例如，在 ACO 中，如果选择 MAX – MIN 蚂蚁系统信息素更新规则，则控制信息素的下限和上限的从属参数也应该被选中。这些参数共同构成了参数配置空间 下级参数是那些仅对于其他参数的特定值所必需的参数——例如，在ACO中，如果选择MAX – MIN蚂蚁系统信息素更新规则，则还应该选择控制信息素的下限和上限的下级参数。这些参数共同构成了参数配置空间 下级参数是那些仅对于其他参数的特定值所必需的参数——例如，在ACO中，如果选择MAX – MIN蚂蚁系统信息素更新规则，则还应该选择控制信息素的下限和上限的下级参数。这些参数共同构成了参数配置空间C，由配置工具使用，如下一节所述。

自动配置工具
ACT 最初开发的目的是在参数化软件中自动选择参数值，以最大限度地提高软件的性能[ 77 , 78 ]]。然而，已经提出了更通用的 ACT，允许选择实现的算法组件。在过去十年中，ACT 的使用有所增加，不仅因为它们生成针对特定问题量身定制的高性能算法，还因为廉价计算能力的可用性增加，因为它们的计算成本可能很高。ACT 的工作机制多种多样，从实验设计技术到基于替代模型的方法。ACT 中实现的具体机制决定了它的计算密集程度、它可以处理的参数类型以及可以进行的配置后分析的类型。
ACT 的一般工作流程如图1所示。给定参数配置空间C，执行迭代过程，其中在测试实例集I上使用不同的参数配置c执行所配置的元启发式M ，直到完全使用给定的计算预算b 。迄今为止，已研究开发 ACT 的方法可分为以下几类。

图。1。一般工作流程后跟用于配置元启发式的自动配置工具 (ACT)。

实验设计技术
这些基于使用统计技术来评估性能差异的统计显着性等方面；这些技术的一个例子是 CALIBRA [ 79 ]。

启发式搜索技术
顾名思义，这些包括应用元启发法来处理配置任务。例子包括ParamILS [ 80 ]，它在参数配置空间中实现迭代局部搜索，以及[ 81 ]中提出的工作，其中CMA-ES [ 82 ]用于数值参数的配置任务。

基于替代模型的技术
这些旨在根据算法的先前执行来预测配置景观的形状，目的是避免在无希望的区域上执行的浪费。这种类型最著名的技术是基于序列模型的算法配置（SMAC）[ 83 ]。

迭代的赛车方法
这些基于使用弗里德曼测试及其相关后测试执行顺序统计测试的想法，以创建一个采样模型，可以通过迭代“竞赛”候选配置并丢弃那些表现不佳的配置来完善该模型。irace 包中实现了各种赛车算法[ 47 ]。
尽管 ACT 主要在处理自动配置问题的方式和通用性方面有所不同，但也存在对用户可能很重要的实际差异。例如，当开箱即用时，与基于代理模型的方法（例如 SMAC）相比，迭代竞赛方法（例如 irace）可以在配置过程中施加更高的计算开销，从而使后者更适合具有昂贵目标函数的配置场景。然而，irace、SMAC 和其他积极维护的 ACT 现在允许对其采样模型进行更改，以减少昂贵的配置场景中的计算时间，或者在计算时间充裕时执行更密集的搜索。47、80 ] 。​ 这些机制有助于更有效地利用可用的计算时间，并且对于涉及与时间相关的目标函数的优化问题特别有用。最后，ACT 的一个共同特征是它们提供可用于进行配置后分析的数据，例如参数重要性 [ 84 , 85 ] 和消融分析 [ 86 ]。

元启发式软件框架
MSF 是一种参数化软件工具，用于实现元启发式设计空间。为了自动生成元启发式实现，MSF 与 ACT 结合使用，如上一节所述，ACT 使用不同的配置迭代执行 MSF。ACT 在一组问题实例上评估每个 MSF 配置（即元启发式实现）的性能，直到找到满足用户需求的 MSF 配置。

区分自动配置和自动设计很重要。前者是指对已经定义的元启发式设计的参数值进行微调，而后者是指除了微调其参数值之外，还通过以新的方式重新组合其组件来组成新的元启发式设计。而且，自动配置和自动设计有不同的目标。自动配置的目标是为所考虑的元启发式找到高性能参数设置，而不更改其实现的组件。相比之下，自动设计的目标通常是探索从未考虑过的组件和参数设置的组合。

早期提出的 MSF，除了少数例外（例如 ParadisEO [ 87 , 88]，我们将在下面讨论），仅允许使用 ACT 来执行自动配置任务。如果用户有兴趣使用这些 MSF 执行自动设计任务，他们必须对 MSF 的代码进行重大调整，以使用新的组件和组合它们的规则来扩展其元启发式设计空间。在最坏的情况下，必须完全重新实施 MSF。随着时间的推移，设计 MSF 的方法发生了明显的变化。与早期的同行相比，大多数现代 MSF 都致力于灵活的模块化设计，允许用户应用它们来解决不同类型的问题，并使用新的元启发式组件和组合它们的规则轻松扩展它们。

将灵活的模块化 MSF 与 ACT 相结合以实例化特定问题或问题实例分布的临时元启发式实现的一般方法如图2所示。这种方法的目标是通过允许配置工具找到有效的元启发式实现来自动解决新问题。因此，只有在希望向 MSF 添加新的元启发式组件的情况下，人类的参与才是必要的；此外，由于 MSF 的模块化设计，这项任务通常很简单。

图2 . 组合模块化 MSF 和 ACT 的一般方法。
创建 MSF 的主要挑战是定义控制元启发式组件组合方式的规则。有两种主要方法可以实现这一点：算法模板和基于语法的编程。使用算法模板（或自顶向下设计）在于创建参数化算法模板，其中元启发式组件被表示为典型固定算法过程中的可能替代方案。相反，在基于语法的编程（或自下而上的设计）中，组件的正确组合是根据语法（即一组重复应用的“产生式规则”）进行检查的。89 ]。

如表所示，文献中提出的几种 MSF 可以实现元启发式的自动设计。该表显示了每个软件框架中包含的元启发式组件的主要类型以及它可用于解决的问题类型。请注意，表中的最后四个 MSF 具有更一般的性质，因为它们包含来自多个元启发式的组件，并且表中的列表并不详尽。事实上，在最近发表的一篇论文中[ 90]，ParadisEO 的一些当前贡献者和维护者确定了 47 个其他在线可用的 MSF。然而，许多都是闭源的、未维护的和/或不旨在设计新的元启发式实现

下面，我们对表中列出的最后四个 MSF 进行更详细的讨论，即 ParadisEO、HeuristicLab、jMetal 和 EMILI，它们是最全面且维护最活跃的 MSF 之一。在描述了每个 MSF 的一般方面之后，我们提供了一些作品的参考，这些作品探索了它们在自动设计背景下的使用的技术和概念方面。

天堂EO
ParadisEO [ 87,88,90 ]是一个著名的MSF，其最初的开发可以追溯到2000年代初。该 MSF 包括四个主要模块，允许用户组成元启发式设计：用于基于群体的元启发式的进化对象、用于局部搜索算法的移动对象、用于估计分布算法的分布对象估计以及用于多目标优化的多目标进化对象。ParadisEO 的一些关键特性如下：(a) 它具有很高的运行速度（因为它是用 C++ 实现的），(b) 它集成了最先进的基准测试和分析工具，称为 IOHprofiler [ 91] 简化了根据基准比较和评估实现的过程，并且 (c) 它拥有活跃的维护者社区。ParadisEO 应用于解决优化问题已有二十多年了。然而，在早期，它是手动配置的，并且最近才对它在自动设计环境中的使用进行研究。在[ 92 ]中，作者研究了使用 ParadisEO 和 irace 自动生成的 19 种用于 W 模型问题的遗传算法。他们发现 irace 自动生成的实现能够胜过所有手动创建的基线算法，并且 ParadisEO 能够提供的快速计算允许在很短的挂钟时间内处理大型设计空间。

启发式实验室
启发式实验室 [ 93] 是 2000 年代初开发的优化软件系统，其中包含 MSF。在当前版本（2010 年发布的 3.3 版）中，HeuristicLab 的 MSF 具有用于实例化许多不同机器学习 (ML) 算法（例如，神经网络、随机森林和支持向量机）和元启发式算法（例如，遗传算法）的模块。编程、进化计算、粒子群优化和模拟退火）。除了提供 MSF 之外，HeuristicLab 还具有许多有用的功能：(a) 它使用允许表示任意优化算法的元模型，(b) 它允许通过图形用户操作和定义元启发式设计界面，(c) 它可以轻松访问可用于基准测试目的的问题，(d) 提供用于结果分析的交互式图表。请注意，虽然 ParadisEO 和 EMILI（如下所述）是用 C++ 实现的，但 HeuristicLab 是用 C# 实现的，因此速度较慢。除了一篇解决算法选择问题的论文 [94 ]，我们找不到任何专门针对使用 HeuristicLab 进行元启发式自动设计的工作。

j金属
jMetal [ 95 ]于2009年开发，是一个用Java实现的优化软件系统，它结合了MSF并具有其他有用的功能。jMetal专注于多目标优化；因此，它允许实例化许多专门用于多目标优化的最先进的元启发法，例如 NSGA-II [ 96 ]、GDE3 [ 97 ] 和 IBEA [ 98 ]]。在当前版本中，jMetal 还包含来自多种单目标算法的组件，例如 DE、粒子群优化和 CMA-ES。jMetal的主要特点如下： (a)它提供了一个简单的图形用户界面，允许设置元启发式实现的参数；(b) 它提供了对可用于基准测试目的的五个流行测试平台的访问（例如，ZDT [ 99 ]、DTLZ [ 100 ] 和 WFG [ 101 ]）；(c)它提供了多目标优化中一些最广泛使用的质量指标，即超体积[ 102 ]、传播[ 96 ]、代距离[ 103 ]、倒代距离[ 103 ]]和epsilon[ 104 ]；(d) 它为执行实验研究提供支持，包括自动生成 LaTeX 表、使用 Wilcoxon 检验的统计成对比较和 R 箱线图。使用 jMetal 自动创建元启发式实现的示例包括[ 105 ]和[ 106 ]。
艾米丽
艾米丽 [ 107]] 最初于 2015 年开发，是一个为随机局部搜索算法实现元启发式和特定问题组件的 MSF。在当前版本中，EMILI 主要用于单解元启发法（例如迭代局部搜索、禁忌搜索和模拟退火）；然而，它的设计使其可以轻松扩展到基于人群的元启发法。EMILI 的显着特征是其架构，它使用语法表示来验证算法组件的可能组合。组成元启发式实现的组件及其执行顺序将根据语法进行检查，然后编码为字符串，以便仅生成有效的组合。然后，EMILI 将字符串转换为可由 ACT 执行的参数形式。EMILI 的其他重要特征如下：（a）它实现了算法相关组件和问题相关组件之间的严格分离，以及（b）它可以将算法视为递归元启发式组件。到目前为止，使用 EMILI 自动创建元启发式设计和实现的两个最相关的工作是 [[107 ]，其重点是用于排列流水作业问题的混合随机局部搜索算法，以及[ 108 ]，其重点是用于二次分配和排列流水作业问题的模拟退火。

讨论
在他们 2017 年对元启发式手册的贡献中，“元启发式的历史”[ 109]、Kenneth Sörensen、Marc Sevaux 和 Fred Glover 预测，元启发学发展的下一个转变将是迈向科学时期。尽管预测一个科学领域的科学时期似乎有悖常理，但他们这样做是因为过去的研究极其不科学。大多数这种非科学的研究都与“元启发法的手动设计”中讨论的基于隐喻的“新颖”元启发法有关。这种趋势之所以持续存在，是因为有一个大型社区正在积极“研究”此类算法。此外，已经发表了许多论文，这些论文以积极的态度呈现“新颖”的元启发法，而忽略了有根据的批评和/或断章取义。例如，参见“对搜索和优化的元启发式算法的详尽回顾：分类法、应用程序、

我们坚信，一旦元启发学界科学地审视基于“新颖”隐喻的元启发法和相关研究的趋势，提出“新颖”元启发学的论文将从期刊和会议中撤回，这种趋势将会消失，只留下一个警示故事。呼吁采取更加科学的观点的一个很好的理由是试图统一越来越多的、面临支离破碎风险的研究机构。采用科学观点作为仍在扩展的领域的基线，是防止（重新）出现个人信念凌驾于理性思维的有害趋势的最佳方法。

引导元启发式社区朝着更科学的方向发展的最新尝试之一是“大型元启发式”社区项目[ 110 ]。在这个项目中，几位著名的研究人员提出了他们对该领域的长期愿景，其中包括三个主要概念基础：（a）可扩展和可重用的框架模板，即现代 MSF，如上所述；(b) 白盒问题描述——即使用分析信息以明智的方式指导元启发式选择/构建；(c) 可远程访问的框架、组件和问题，即创建能够广泛重用数据和程序的面向服务的体系结构。

另一种重新聚焦该领域的尝试是最近一封题为“基于隐喻的元启发法，呼吁采取行动：房间里的大象”的公开信[ 53 ]，这封信汇集了大约 100 名希望阻止“新颖”隐喻出版的研究人员——通过采取具体行动，例如呼吁科学期刊就如何管理呈现此类元启发法的文章制定明确的编辑政策。这封公开信是迄今为止为提高人们对基于“新颖”隐喻的元启发法问题的认识而进行的最引人注目的努力之一。

尽管这些文件已经帮助该领域朝着更健康的方向发展，但仍有许多工作要做。特别是，似乎需要付出更多努力来将元启发学界聚集在一起，以解决多年来仍未解决的问题。我们提出了三种从元启发法领域消除不科学方法的方法：（a）增加实验或理论驱动的研究数量，（b）改进元启发法的基准测试方式，以及（c）改变当前的主流方法创建元启发法。

重新思考研究重点
元启发式研究是一门应用科学，涉及优化算法的设计和应用，无论所考虑问题的复杂性如何，该算法都能很好地发挥作用。因此，该领域一直强烈偏向于面向应用的研究，并广泛使用“竞争性测试”来宣称算法性能[ 111 ]。竞争性测试针对给定的一组问题实例和给定的性能测量来测量和比较比较算法的性能[ 112] 但没有解释性能差异。因此，为了推进该领域并增加我们对为什么某些技术在某些问题上效果很好而在其他问题上效果不佳的了解，关键是减少面向应用的研究量与实验或理论驱动的研究量之间的不对称性。

研究元启发式计算模型之间的相互作用及其在不同问题类别上的表现不仅从研究角度来看很重要，从实践角度来看也很重要。例如，实验和理论分析使我们能够：（a）了解元启发法中涉及的思想的可扩展性，从而了解如何使用它们来解决其他问题；(b) 指导新的元启发式组件的开发，以进一步提高性能或解决已知问题；(c) 定义创建元启发式实现的指南，即元启发式组件组合方式的有用指示，以便更容易地创建和测试新设计。

在过去几年中，这一领域似乎已经取得了进步，因为引入由经验证据或理论发现驱动的新优化算法的面向应用的论文现在更加频繁。然而，该领域的研究方式仍然需要克服重要挑战，首先是我们从实验研究中得出结论的方法实践。

重新思考元启发法的基准测试方式
卡尔·萨根普及了“非凡的主张需要非凡的证据”这句话[ 113 ]。在元启发式领域，收集证据（即数据）并用于得出有关元启发式性能的结论的方式多种多样，这一过程通常称为基准测试[ 112 ]。另一方面，有一些关于“新颖”的基于隐喻的算法的文章，这些文章不仅提出了非凡的主张，而且还是不良科学实践的教科书示例（请参阅“基于“新颖”隐喻的元启发式问题”中的讨论） 。另一方面，研究人员创建了新工具来评估元启发式性能[ 114] 并研究使用深度统计分析等现代技术来比较元启发法的新方法[ 115 ]。

一般来说，尽管文献[ 115-118 ]中提供了用于评估优化算法的最先进的方法和工具，但它们并不总是用于评估元启发式性能。例如，仍然普遍观察到在有偏差的测试集上评估的结构性偏差元启发法 [ 54 ] 和有缺陷的实验方法，这些方法呈现不公平的比较，不保证可重复性，并忽略重要的性能指标 [ 111 , 119 – 123 ]。为了解决这些问题，发表元启发学文献的媒体需要实施和系统地执行更高的科学标准。

最近，一些研究人员提出了一套指南和最佳实践来解决不良的基准测试实践[ 112]。这些指南和最佳做法如下： (a) 明确规定基准研究的目标并据此进行设计；(b) 使用在问题的规模、难度和多样性方面全面的基准；(c) 使用手动或自动技术来配置元启发式实施的参数；(d) 使用健全的统计方法来决定应进行哪些实验、每个实验应重复多少次、应收集哪些数据以及如何处理、分析、解释和呈现这些数据；(e) 在没有足够证据或没有界定这种概括适用的明确范围的情况下，避免对结果进行概括。
除了这些指南和最佳实践之外，作者还发现了元启发式基准测试研究中的一些机会和未解决的问题。例如，定期创建/更新测试台以反映不断变化的现实场景中的复杂性的努力被低估了。此外，需要同时测量不同的性能指标（例如，任何时间的行为与固定预算、约束违反成本和鲁棒性），以便在考虑不同目标时提供元启发式行为的更好描述。此外，需要实施健全的数据管理实践，以允许存储、共享和重用来自基准研究的数据。

致力于改进元启发法比较和评估方式的研究的重要性怎么强调都不为过。然而，事实证明，对于一个本质上是实验性的领域来说，广泛实施合理的基准测试实践相对具有挑战性，并且主要侧重于测试元启发法，就好像它们是在其大部分历史中参加比赛的马一样。事实上，尽管努力改进实验实践[ 111,119-122 ] ，但良好的实践尚未被广泛采用，特别是在定期发表基于隐喻的“新颖”元启发法的场所。

重新思考我们创建元启发法的方式
根据本文的讨论，我们认为研究界应该从手动设计转向自动设计，作为创建元启发法的主要方法。这样做需要专注于创建灵活的、自动配置的 MSF，这些 MSF 可以使用新的元启发式组件进行扩展，以便其他研究人员/从业者可以在不同的环境中使用它们。这种方法的长期目标是使创建元启发式的过程自动化，以便当出现新问题时，可以及时且公正地自动创建有效的元启发式实现。在本文中，我们讨论了自动设计方法的主要方面；有兴趣了解如何在概念上和实践中使用它的读者可以参考[ 35，124 , 125 ]，补充了“元启发式软件框架”部分中给出的参考文献。

除了自动设计之外，还出现了几种研究趋势，探索将机器学习集成到元启发式方法中的方法[ 126-129 ]以及使用数据科学工具分析其性能的方法[ 86,130,131 ]。文献已经确定了不同级别的 ML 集成 [ 127 , 129]，例如问题级集成——机器学习可以帮助对优化问题的各个方面（例如目标函数和约束）进行建模以及执行适应度景观分析、算法级集成——机器学习用于选择合适的算法来自算法组合和组件级集成——其中机器学习用于自动执行选择和微调最适合特定问题的算法组件的任务。数据分析工具[例如方差函数分析（ANOVA）[ 130 ]、前向选择[ 131 ]和消融[ 86 ]]已用于从设计过程中收集的数据中获取有关算法性能的知识。
机器学习、数据科学和元启发法之间产生的富有成效的协同作用不仅带来了设计和实现日益有效的算法的新方法，而且还带来了研究这些技术并理解为什么特定设计表现良好而其他设计表现不佳的新方法。尽管文献中已经提供了大量用于创建新设计的元启发式技术和机制，但仍然存在许多机会。例如，我们认为致力于（a）创建建模框架以更好地表征元启发式[ 34 ]是特别有希望的；(b) 开发元启发法基准测试的先进方法，例如创建易于使用的统计工具[ 114 , 115]; (c) 扩展现有的 MSF 生态系统并研究提高其组件可重用性的方法[ 132 ]。

结论
在过去的几十年里，元启发法一直是寻找困难优化问题的近似解决方案的首选方法。然而，尽管它们在优化领域取得了重要进展，但大多数元启发法的创建方式与早期相同，也就是说，它们是一个耗时且容易出错的过程的结果，在该过程中，人类设计者手动创建要在元启发式实现中使用的组件。尽管这种创建元启发式方法在过去很成功，但现在是时候转向一种创建元启发式新方法来避免手动设计的陷阱了。在本文中，我们详细研究了一种称为自动设计的替代方法。
元启发式的自动设计是基于使用基于组件的视图来定义元启发式设计空间，并应用ACT来探索不同的设计，直到找到满足用户需求的设计。对元启发式自动设计的研究已经催生了多个 MSF，这些 MSF 能够使用 ACT 来有效地设计高性能实现。
我们还讨论了基于各种隐喻的“新颖”元启发法的有问题的趋势，这种趋势的存在部分是由于手动设计作为创建元启发法的主要方法的盛行。为了说明为什么基于隐喻的元启发法存在问题，我们从许多文献中选择了两个被高度引用的“新颖”元启发法的例子，并展示了它们如何证明缺乏任何新颖性，因此只是造成混乱和重申已知的根源。想法。
最后，我们讨论了三个有助于元启发学领域进一步发展的基础研究方向：（a）专注于实验或理论驱动的研究，而不是纯粹的应用驱动的研究和竞争性测试，（b）使用最新的技术-评估元启发式的艺术基准测试实践，以及（c）使用现代工具和机制自动创建高性能元启发式实现。

在本文中，我们特别关注三个基本方面中的最后一个，它主张改变元启发式实现的创建方式。自动设计领域正在迅速发展，现代自动设计方法的普及并取代手动设计成为设计新元启发式的主流方法似乎只是时间问题。我们相信，这将有助于彻底结束“新颖”的基于隐喻的元启发法的趋势，并将对我们看待、理解和应用这些优化算法的方式产生积极、持久的影响。