[论文分享]IEEE TEVC 2024 基于自回归学习的自动化元启发式算法设计

摘要

元启发式算法的自动化设计提供了一条有吸引力的途径，可以减少人类的努力，并获得超越人类直觉的增强性能。当前的自动化方法在固定结构内设计算法并从头开始操作。这在充分发现元启发式族的潜力和从先前的设计经验中获益方面存在明显的差距。为了弥合这一差距，本文提出了一种基于自回归学习的设计器，用于元启发式算法的自动化设计。我们的设计器将元启发式算法设计制定为序列生成任务，并利用自回归生成网络来处理该任务。这提供了两个进步。首先，通过自回归推理，设计器生成具有不同长度和结构的算法，从而能够充分发现元启发式族的潜力。其次，设计器神经元中学习和积累的先验设计知识可以被检索出来，用于为未来的问题设计算法，为开放式问题解决算法的持续设计铺平了道路。对数字基准和现实世界问题的广泛实验表明，所提出的设计者在25个测试问题中的24个问题上生成的算法优于所有人类创建的基准。生成的算法显示了各种结构和行为，合理地适合不同的问题解决环境。

代码可在以下网址获得https://github.com/auto4opt/ALDes.

一个元启发式算法的自动设计算法。序列化处理是本文的主要切入点。

简介

元启发式是一种随机搜索方法，它将无梯度局部改进与跳出局部最优的高级策略相结合。它涉及一个丰富的算法家族，从基于邻域搜索到进化和群体算法。这些算法可用于任何具有可用解决方案表示、解决方案质量评估和局部性概念的问题。

给定一个目标问题，为了获得足够好的解决方案，有必要在搜索组件、算法结构和超参数的丰富选择上仔细设计元启发式算法。设计通常是人为的，通常费力、无法追踪某些设计决策的动机，并且容易受到意外的人为偏见的影响，更不用说人类设计师并不总是有空了。这推动了元启发式算法的自动化设计。

自动化设计可以找到现有算法的实例/变体或看不见的算法，以适应目标问题的解决。这与自动算法选择和自动超参数配置不同。前者从一组算法中选择现成的算法；后者配置给定算法的超参数。自动化设计可以通过问题实例的目标分布离线进行，也可以通过搜索轨迹在线进行。本文重点介绍离线自动化设计，它适用于可以提供先验计算资源（用于算法设计）的场景，以随后解决从目标域中提取的许多问题实例。

已经引入了几种方法来离线自动设计元启发式算法。代表包括SMAC、irace、ParamILS和离线超启发式。SMAC使用贝叶斯优化来学习一个代理函数，该函数对算法到其在目标问题上的性能的映射进行建模。irace提出了迭代竞速来为目标问题选择所需的算法，随后使用所需算法来近似算法的采样分布。ParamILS采用迭代局部搜索来开发所需的算法；开发了强化和封顶策略来节省算法评估。离线超启发式采用高级启发式/元启发式，例如遗传编程，来生成低级元启发式算法。

上述方法显示了两个共同点。首先，它们操纵固定长度的矢量化算法表示，即算法组件的分类索引及其条件超参数的连接；需要特定的算法模板来确定组件的执行逻辑。这使得设计偏向于元启发式家族中的特定类型的算法。其次，给定一个目标问题，他们中的大多数都是从头开始设计的。尽管可以使用先前的算法作为起点，但关于问题的某些设计决策的动机的知识是无法追踪的。这些知识可能会为未来的设计提供见解。这两点在充分发现元启发式家族的潜力和从先前的设计知识中获益方面存在明显的差距。

总结了先前已有算法两个主要不足，一是只能基于已有算法的组件进行排列组合，二是无法解释设计的动机。

在本文中，我们通过提出用于元启发式算法自动化设计的基于自回归学习的设计器（ALDes）来弥合这一差距。我们在ALDs中提供以下贡献：

•我们将元启发式算法设计制定为序列生成任务。为此，我们提出了一种新的序列表示方法。该表示不仅标记了算法组件和超参数，还标记了“指针”。与特定模板中的向量表示不同，我们表示中的指针决定了每个组件的执行逻辑，重要的是，可以形成序列、分支和循环执行。这使得序列表示可以表达任意的算法结构，而不需要特定的模板。

•我们利用自回归生成网络来处理序列生成任务。与当前正交操纵固定长度向量表示的每个实体的方法不同，我们借用了transformer的顺序生成能力，以先前生成的实体为条件，一次一个地自回归生成实体。自回归序列生成将自动化算法设计的边界推向了一个新的水平：设计具有不同长度和结构的算法，能够充分发现元启发式家族的潜力

•我们通过记忆和检索所提出的ALD神经元内的先验知识，从先前的设计经验中学习。与目前从头开始独立处理每个算法设计任务的方法不同，我们学习目标问题的分解嵌入，并学习以端到端的方式根据问题生成算法。通过输入新问题，可以检索ALDs神经元中积累的设计知识，用于新问题的算法设计。这为持续设计开放式问题解决算法铺平了道路。

•我们在23个伪布尔优化（PBO）基准和两个实际应用中广泛研究了ALDes。结果表明，具有固定算法结构的比较基线并不适用于所有问题。相比之下，ALDes发现了具有不同邻域定义、搜索行为和结构的算法，合理地适用于不同的问题，并在25个问题中的24个问题上超越了所有人为创建的基线。对连续算法设计任务的进一步实验说明了ALDs利用先验知识进行未来设计的能力。

此算法的自动化设计和自动化编程类似，通过逻辑进行组合，跳出了算法组件组合的局限，然后再架上利用自回归网络的学习，实现算法自动化设计。

背景及相关工作

元启发式算法的自动化设计

在不失一般性的情况下，元启发式算法的离线自动化设计旨在处理以下任务：

其中A是指要设计的算法；Ą是由算法组件和超参数构成的设计空间；g（A|i）是A在问题实例i上运行A所获得的性能。性能可以是解决方案质量、运行时间或任何时候的性能等。

实例i来自目标问题域It，其中t表示第t个算法设计任务。特别地，T=1表示具有固定目标问题域的一次性算法设计任务。该设计需要从头开始操作，而无需事先学习和使用经验。T>1表示具有一系列（或开放式）目标问题域的连续算法设计任务。该设计允许从先前任务中积累知识，以便快速适应新任务。这种情况与追求通用和开放式自动化系统相一致。

由于元启发式算法执行随机搜索，因此需要估计G上的预期性能；在实践中，这是通过多次运行A来实现的，从而得到g∈G的多个值。

对于连续问题，设计空间A中的算法组件可以是计算基元，例如+、−、∗、/，也可以是现有的运算符，例如高斯变异。对于离散问题，基元和运算符之间没有明确的区别，例如，swap是一个代表性的搜索运算符，也是一个计算基元。具有运算符的设计空间可以通过从先前算法和用户的领域专业知识中做出良好的设计选择来形成，因此在许多工作中都有很好的记录。在本文中，我们遵循这些原则，在算子级别进行自动化设计。

元启发式算法的离线自动化设计方法大多源于超参数配置领域。它们将算法组件表示为分类参数；将分类参数及其条件超参数连接起来，形成算法的向量表示；可以通过操纵向量表示来生成算法。由于算法设计任务的黑盒和NP难性质，基于搜索的方法在操纵算法的向量表示方面占主导地位。

基于GP的方法，主要是指基于树的GP，在计算基元级别上进行算法设计，因为GP树在基元上表示程序的表现力。他们通常生成单个算法运算符而不是整个算法，例如，生成选择运算符，因为表示整个算法会导致一棵大树，并且可能无法在大搜索空间上找到合适的树。相比之下，本文侧重于在操作员级别生成完整的算法。已经有一些基于树的GP研究在操作员级别生成了算法。然而，他们采用了固定的进化算法结构，而没有研究不同元启发式算法之间的多样性。

这些设计方法在特定的算法模板内进行操作。模板确定表示中涉及的算法组件的可行执行逻辑。例如，模拟退火（SA）、粒子群优化（PSO）和遗传算法（GA）模板分别用于设计SA、PSO和GA的新变体。这限制了设计某种类型的元启发式，而不是探索整个元启发式家族。此外，这些基于搜索的方法从头开始独立处理每个算法设计任务。尽管先前的算法可以用作起始设计点，但关于某些目标问题的某些设计决策的动机的知识是无法追踪的，失去了未来重用的见解和准则。

在本文中，我们致力于通过提出基于自回归学习的元启发式算法设计器来突破离线自动化设计中的两个基本局限性。

主要还是解决之前的自动设计算法只能在已有的算法框架上进行设计的局限性。

使用transformer生成序列

Transformer是一种神经网络架构，最初用于自然语言处理中的序列到序列学习。

作为循环神经网络的替代方案，transformer通过使用自注意力在序列中每对令牌之间的许多快捷关系路径中学习，提供了强大的序列生成能力。这种序列生成能力对设计任务很有吸引力，例如设计神经架构、药物分子和射频波形，因为要设计的对象（序列）通常具有各种结构（长度），并且对象的组成部分（序列的标记）是相互依赖的。众多快捷关系路径也有利于从复杂的输入（设计任务的环境）中学习有价值的特征，这对部分可观察或黑盒设计环境具有重要意义。在本文中，我们利用transformer的生成和学习能力来自动设计元启发式算法。

提出的方法

当前的自动化设计方法在固定结构内生成算法，阻止了该结构之外可能有前景的算法。此外，它们通常从头开始运行。关于问题的某些设计决策的动机的先验知识是无法追踪的，失去了对未来设计的见解和原则。

1） 算法设计作为序列生成：我们将元启发式算法的自动化设计表述为自回归序列生成任务。

我们介绍了两个吸引人的特点。

首先，我们以先前生成的实体为条件，一次一个地自回归生成实体（tokens）。这与元启发式算法的组件是依赖的，并且组件可能具有条件超参数的性质是一致的。其次，我们可以生成不同长度的序列，使我们能够生成多样化的算法。相比之下，之前的设计通常会正交操纵固定长度算法的每个实体，以捕捉依赖性并提供多样化。

2） 将算法表示为序列：我们提出了一种新的元启发式算法的序列表示，以适应该公式。序列表示不仅标记了算法组件和超参数，还标记了指针和条件。具体来说，我们将每个组件、超参数、指针和条件分别视为序列的标记。组件标记后面是它的超参数（如果有的话）标记、指针标记和条件标记。它们构成了一个片段。多个片段被排列成序列。

在代码片段中，指针ptr决定了运行组件comp后的执行流。我们定义了三个指针，forward、iterate和fork。第一个指针使执行流指向下一个代码段的组件；中间使comp迭代；最后一个分支将流量头分叉到下一个组件和某些后续组件。fork会带来一个控制参数令牌，以确定要链接到哪些后续组件。cond条件调节了comp的计算成本。我们定义了两种条件，即计数条件（执行次数）和事件条件（执行到事件发生为止）。我们的新表示可以形成序列、分支和循环执行，从而在没有模板的情况下表示各种算法结构。这无法通过固定长度向量表示的常见做法来实现。

下图显示了我们的序列表示的实例化。

工作流

我们利用自回归生成网络来处理序列生成任务。下图显示了工作流。

1） 架构：从图中可以看出，该网络包含四个主要模块，即问题嵌入、序列嵌入、transformer和掩码采样。

问题嵌入将非结构化（例如符号表达式）目标问题嵌入到ALDes中。它只适用于从连续算法设计任务的先前经验中学习，对于一次性任务来说是不必要的。

在连续任务中，ALDes必须通过嵌入来识别不同任务中的目标问题。因此，它可以从先前问题的设计经验中学习，并为新问题的设计提取相关经验。而在一次性算法设计任务中，它没有，因为只有一个固定的目标问题域。

transformer模块学习特征并捕获当前序列中令牌的依赖关系，预测下一个令牌。我们使用transformer，因为它在序列生成中有良好的跟踪记录，通过自注意力从序列标记之间的许多快捷关系路径中学习。

掩码采样通过对候选token进行采样来预测下一个令牌。通常的序列生成任务涉及同质标记（例如，自然语言序列中的单词）；采样时应考虑每个token。相比之下，我们的任务涉及序列中具有特定顺序的异构token。鉴于此，我们可以在采样中屏蔽意外类型的token：在第一轮token预测中，除了组件之外的所有token都被屏蔽。这确保了序列从组件开始。如果组件有超参数，则只有超参数标记在后续轮次中才会被取消屏蔽。如果组件没有超参数或超参数已经生成，则只有指针标记是未屏蔽的。同样，只有条件标记在指针标记后才会被取消屏蔽。

给定上述模块，工作流程从输入算法的序列表示开始到序列嵌入。初始序列由一个“开始”标记组成，它提示ALDes开始标记预测。嵌入后，序列经过位置编码、变换和掩码采样，输出下一个token。然后将输出的token放入序列中，开始下一轮token预测。输出“结束”标记后，工作流终止。

从以往经验中学习

与从头开始独立处理每个算法设计任务的基于搜索的设计方法不同，ALDes可以在连续的场景中随着时间的推移学习和积累设计知识，以快速适应新问题。这与追求通用和开放式自动化系统是一致的。为此，我们（i）嵌入目标问题，让ALDes识别它们，这样ALDes就可以检索新问题的相关先验知识；（ii）归一化ALDes的训练，以积累先前知识，同时适应新问题。

对于第（ii）点，我们采用可塑权重巩固（EWC）。它可以估计ALDes的每个参数对积累先验设计知识的重要性，并减缓更新重要参数以适应新任务，从而平衡积累和适应。

实验与应用

设置

1） 目标问题：包括代表性的PBO数值基准和两个现实世界的问题。

2） 基线算法：它们包括迭代局部搜索（ILS）、模拟退火（SA）、禁忌搜索（TS）和遗传算法（GA）

3） 实施细节：训练：对于每个PBO问题，100、225和400d实例用于训练；对于每个现实世界的问题，其一半的实例都是用于训练的。在每个问题上，ALDs被训练了100个迭代周期，每个迭代周期生成16个算法。测试：每个PBO问题的625d实例和每个现实世界问题的其余实例用于测试。将从训练好的ALD推断出的算法与测试实例上的基线进行比较。

生成高性能和多样化算法的效率

下显示了测试问题实例的结果，其中Alg∗是从训练的ALDes得出的算法；值越大表示性能越好。

ALDs生成的算法Alg∗（见算法1）是一种可变邻域搜索（VNS）式算法。此外，基于群体的搜索利用了邻域结构（轮盘用于选择要搜索的解决方案，成对选择用于更新解决方案）。这种可变的邻域结构和多样性维护能力使Alg∗在有限的FE内的所有30次运行中达到最优。

图显示了训练曲线。ALDes在这个简单问题上收敛良好。在F1的线性加权版本F3上也观察到了类似的结果。在F4-F10上，ALDes表现出持续的优异性能。

综上所述，在大多数问题中，其表现远远优于竞争对手。这清楚地证实了ALDes在生成高性能算法方面的效率。这支持了我们的动机，即单一的固定算法结构并不总是最适合不同的问题解决。ALDes为不同的问题生成了多样化的算法，例如，具有不同行为的VNS、ILS和GA风格的算法。它还生成了超越直觉的算法，例如处理中立性的无偏算法。如上所述，生成的算法在相应的问题上表现良好。所有这些都清楚地表明了ALDes在生成元启发式家族中的多样化算法以适应不同问题解决方面的效率。

总体上自动设计的算法还是在已有的算法框架之上，只不过本文中的方法将已有的算法组件“拆的更碎”，然后再进行搜索搭建算法。

从以往经验中学习的效率

我们在一系列PBO问题上不断训练所提出的ALDes，以模拟连续的算法设计任务。我们从PBO套件中构建了两个连续的任务：任务1相对容易。任务2具有挑战性。

为了检验ALDes积累先验知识的能力，我们将其与没有EWC的变体进行比较。这种变体的行为类似于微调，即在不考虑先前任务的情况下适应新任务。下图报告了结果。在任务1中，随着训练的进展，带有EWC的ALDes在之前的问题上不断保持其性能，而没有EWC的变体在F1和F2上则无法做到这一点。这一趋势在较难的任务2中更为明显，随着训练的进行，没有EWC的F2、F11和F18的表现下降了一半。具有EWC的ALDes表现相对稳定，显示出其知识积累的能力。

我们进一步研究积累的知识是否可以促进未来问题的设计。下图展示了任务2中F11、F18、F19和F22的训练曲线。F11、F18和F19的持续训练从比从头开始训练高得多的表现开始。积累的知识有助于这种快速适应。随着训练的进行，性能会进一步提高。尽管如此，训练收敛到与一次性曲线相当的性能。总体而言，结果表明，使用EWC，ALDes能够积累从先前任务中学到的知识。这些知识使ALDes能够快速适应未来的设计。即使在概念发生重大偏差的情况下，ALDes也表现出合格的收敛性。所有这些都展示了ALDes在持续设计开放式问题解决算法方面的潜力。

本文介绍了用于元启发式算法自动设计的基于自回归学习的设计器ALDes。ALDes将元启发式算法设计表述为序列生成任务，并提出了元启发式算法的序列表示。本文的方法将传统算法组件拆分的更碎，虽然多数情况下生成的算法还是在传统算法的框架下，但还是能探索到一些意料之外的算法。本文中将ewc引入算法设计，让算法自动设计可以学习到知识更快适应未来的算法设计，这点是我认为比较有突破的一点。