无反向传播的 4D 连续蚁群神经网络拓扑搜索

BACKPROPAGATION-FREE 4D CONTINUOUS ANT-BASED NEURAL TOPOLOGY SEARCH

无反向传播的 4D 连续蚁群神经网络拓扑搜索

https://arxiv.org/pdf/2305.06715

摘要

连续蚁群拓扑搜索（CANTS）是一种先前引入的新型自然启发神经架构搜索（NAS）算法，基于蚁群优化（ACO）技术。CANTS利用连续搜索空间间接编码神经架构搜索空间。合成蚂蚁代理根据信息素的密度和分布探索CANTS的连续搜索空间，这深受现实世界中蚂蚁移动方式的启发。这种连续搜索空间使CANTS能够自动化设计任意大小的人工神经网络（ANNs），消除了许多当前NAS算法必须在使用者预定大小的结构内操作的关键限制。本研究通过在其搜索空间中增加第四个维度来扩展CANTS，该维度代表潜在的神经突触权重。增加这一额外维度使得CANTS代理能够在不应用反向传播（BP）的情况下优化ANN的架构和权重，从而显著减少优化过程中的时间消耗：平均至少减少96%的时间消耗，同时保持非常竞争力的优化性能，甚至更优。本研究的实验——使用真实世界数据——表明，与CANTS和ANTS相比，无BP的CANTS算法表现出极具竞争力的性能，同时所需的操作时间显著减少。

1 引言

手工制作人工神经网络架构一直是机器学习（ML）进步的一个障碍，因为它耗时、容易试错，并且需要模型架构师具备重要的领域专业知识[43]。加剧这一问题的是，即使对问题特定的元参数或拓扑特征进行轻微修改，也可能导致模型性能的下降[15, 2]。这导致了对问题特定模型优化的需求，然而，深度神经网络（DNN）的优化，可能涉及数百万个结构元素和大量超参数，被认为是一个NP难问题，并受限于计算资源[1]。最优架构无法通过应用连续函数直接获得，因为与使用损失函数优化神经网络参数（权重）不同，没有明确的函数来衡量架构优化[23]，这是由于架构可能性的组合性和不可微性。因此，已经开发了许多基于元启发式的神经架构搜索（NAS）[14, 22, 34, 39, 24, 43]和神经进化（NE）[36, 5]方法来自动化ANN设计过程。最近，自然启发的神经架构搜索（NI-NAS）算法显示出越来越大的潜力，包括人工蜂群（ABC）[19]、蝙蝠[41]、萤火虫[40]和布谷鸟搜索[21]算法。

蚁群优化（ACO）——最初作为一种图优化方法被提出[10]——已被证明是一种成功的自然启发神经架构搜索（NI-NAS）策略。ACO作为一种强可行的NAS方法的根源在于其作为图优化方法的应用概念，提供了令人印象深刻的结果[26, 3, 9, 25, 10, 7, 8, 33]。由于神经网络结构本质上是有向图，这使得ACO非常适合解决NAS问题。最初，ACO在NAS中的应用仅限于小的Jordan和Elman RNN神经网络结构[6]，或用于选择网络输入[27]。ACO还被用于优化RNN记忆单元结构内的突触连接（权重）[11]，随后扩展到在一种称为基于蚁群的神经拓扑搜索（ANTS）的算法框架内优化整个RNN架构[13]。

ANTS利用一个大规模连接的神经网络结构作为离散的结构搜索空间。尽管该方法已显示出成功，但对该策略的主要批评在于搜索空间的离散性限制。其他NAS方法大多基于进化；它们不是在固定范围内操作，而是在进化过程中不断添加和删除节点/边[37, 28, 31]。尽管这些构造性NAS方法不像ANTS那样受到离散搜索空间的限制，但它们仍然更容易陷入（早期/较差）局部最小值，或消耗大量时间来进化结构。

本研究引入了一种新颖的蚁群启发算法——**无反向传播的连续基于蚁群的神经拓扑搜索（BP-Free CANTS）**，它利用连续搜索域灵活地设计任意大小的人工神经网络（ANNs），以解决上述挑战。合成的连续蚂蚁（cant）代理在搜索空间中漫游，利用信息素信号的密度和分布进行探索，模拟现实世界中蚂蚁的群体行为。代理探索产生的路径用于构建RNN架构的节点和边。BP-Free CANTS（以及原始的CANTS算法[12]，在本文中为了清晰起见，我们称之为BP-CANTS）是一种分布式、异步算法，它促进了高性能计算（HPC）资源的可扩展使用，并利用集体智慧减少候选进化网络所需的训练量。

本研究将BP-Free CANTS与应用于RNN时间序列数据预测的最先进基准NAS设计策略进行了比较：ANTS[13]和BP-CANTS[12]。除了放宽对预定义架构边界的要求外，BP-Free CANTS还显示出在显著降低计算成本的情况下，其结果优于ANTS和BP-CANTS。BP-Free CANTS算法还为NI-NAS领域提供了一项进展，即它能够高效地选择高性能架构，同时在不使用反向传播的情况下找到表现良好的权重。尽管ACO之前已被应用于连续域问题[35, 20, 38, 18, 4]，但据作者所知，BP-Free CANTS是首批模拟并应用蚂蚁在无界四维连续空间中移动以搜索最优神经参数和架构的算法之一。BP-Free CANTS能够在不应用耗时的反向传播和梯度下降过程的情况下优化神经拓扑和神经突触参数，这进一步减少了所需的计算能力和时间消耗。BP-Free CANTS还为其cant代理提供了在优化过程中进化的手段，从而增加了达到更好性能模型的机会，同时减少了与cant行为相关的超参数。

2 方法论

图1展示了**BP-Free CANTS算法**的抽象工作原理。该算法采用了一种异步、分布式的“工作窃取”策略（见算法1中的伪代码），以便在高性能计算（HPC）集群上实现可扩展性。当接收到来自工作进程（assignee）的请求时，管理进程（assignor）会生成新的架构。在请求新架构时，工作进程会报告其训练和评估的架构的适应度。管理进程维护一个固定数量的由工作进程发现的最佳RNN架构。管理进程还会通过在连续搜索空间中释放信息素来奖励蚂蚁代理生成RNN架构所走的路径。这种计算设计使得工作进程能够一次评估并报告单个生成架构的性能，而无需阻塞等待其他工作进程的结果，从而提供了一种自然负载均衡的算法。此外，这使得BP-Free CANTS比同步并行进化策略具有更高的可扩展性，因为它可以支持的工作进程数量大于种群大小。管理进程管理的种群保存了由工作进程报告的已发现RNN的最佳适应度（验证数据的均方误差）。该种群保持固定大小，并像稳态进化算法一样更新，即移除种群中最差的成员，并用任何新发现的性能更好的RNN替换。

候选神经架构从由堆叠的2D连续平面组成的搜索空间中采样，其中每个2D平面代表特定的时间步长t（见图3a），而在BP-Free CANTS中，搜索空间中给定点的第四维度代表该点的权重值。每个时间步长的输入特征（表示为输入节点）均匀分布在搜索空间某一轴的零点。合成的连续蚂蚁代理（cant）离散地选择一个输入节点位置作为其路径的起点，通向输出节点。然后，cant根据当前信息素痕迹的密度和分布在其路径上通过连续空间移动。在搜索空间中的给定平面（滞后层级）上，cant只能向前移动到输出侧，或向上跳转到任何更高的滞后层级，但不允许移动到堆栈中更低的滞后层级，或在同一滞后层级上向后移动。由于向上移动的路径（循环连接）表示将信息从先前时间步的神经元传递到未来时间步的神经元，反向移动则意味着将不可用的未来信息传递到RNN的先前时间步，这是不可能的。尽管cant在给定平面上只能向前移动，但当它们跳转到更高的滞后层级时，允许向后移动，因为循环连接可以将信息从架构的某一层级传递到具有更高滞后层级的更低层级。这种在平面上（通过层级）向前移动和在堆栈上（通过滞后层级）向上移动的强制要求确保了cant向输出的连续进展，并减少了搜索空间中的循环。

图3展示了cant从输入到输出在搜索空间中移动的场景。图中所示的移动展示了cant在搜索空间中探索新区域、利用先前搜索过的区域（被之前的信息素沉积吸引），以及如何将cant路径转化为最终的候选架构（更多细节请参考[12]）。

Cant代理的输入节点和层级选择

Cant代理的移动cant在搜索空间中的移动是**利用**和**探索**之间的平衡，这种平衡通过模仿现实世界中蚂蚁的行为来实现，蚂蚁通过线索传递目标信息。当cant移动一步时，它首先决定是否要爬升到平面堆栈中的更高滞后层级，这一过程与选择初始滞后层级类似，但层级选项仅限于堆栈中更高的平面。当cant确定下一步是爬升还是水平移动后，它会决定该步是探索还是利用。移动类型（探索或利用）由cant根据其探索/利用参数决定，该参数最初通过均匀随机分布生成，随后在生成神经架构的过程中作为代理行为之一进行进化（见下文“Cant进化”部分）。

在**利用移动**中，即跟随信息素痕迹/线索，cant会首先感知其感知半径内的信息素痕迹。如果决定在同一滞后层级上移动，cant会忽略其后方先前沉积的信息素；否则，cant会考虑感知半径内的整个信息素分布以确定其路径中的下一个位置。cant计算感知半径内信息素分布的质心，并将其作为路径中下一步的位置。如果生成的RNN成功进入最佳发现RNN的种群，cant的路径点将由该候选RNN保存，以便后续信息素沉积，用于与其他cant的通信。通过将质心应用于cant的下一步移动选择，与空间中某个区域的信息素浓度相比，单个点上的信息素沉积在cant间通信中成为一个外围有效因素，这类似于自然界中蚂蚁的觅食行为。

Cant的进化每个CANTS代理（cant）在初始化时会被赋予均匀分布的随机探索/利用系数感知范围系数。此外，还引入了两个额外的参数，通过以下二次多项式公式控制感知半径的大小，从而调节cant移动（一步）的速度：

参数控制单个cant的感知范围大小，基于cant与输入节点之间的距离（即与输入节点的y空间距离）。感知范围越大，cant在概念上能够一次性移动的步长越长；感知范围越小，cant的步长越小。然而，感知范围的最小值被设置为0.1，以确保代理不会完全失去对信息素的感知并停止移动。所使用的二次多项式公式最终控制cant移动速度的模式：

a) **初始较慢，接近输出时加快**，或

b) **初始较慢，中间加快，接近输出时再次减慢**。

图4展示了这些模式。

尽管这些Cants参数是为各个Cant单独生成的，但它们会在CANTS迭代之间通过遗传算法进行演化。该算法基于表现最佳生成的神经网络（NN），通过变异和交叉操作来调整这些参数（参见算法1中的cant.Evolve()）。

通过引入上述行为特征，优化代理本身具备了更大的灵活性。设计这种演化机制使得这些参数在进化过程中能够自我调整，而不是被视为额外的超参数。

将Cant路径压缩为RNN节点：不同Cant路径上的点可能在空间上接近，这种接近性也可以映射到神经网络的邻近性，从而表现出一种冗余。为了避免在神经空间中存在多余的神经元，使用DBSCAN算法对Cant路径上的点进行聚类，并将生成的聚类压缩为质心。随后，给定聚类内的邻近点由该聚类的质心表示，而质心则被转换为生成的神经架构中的一个神经元（见图3g和3h）。节点类型通过基于信息素的离散局部搜索来选择，类似于离散空间中的ANTS算法。每个选定点上的节点类型都有其自身的信息素值，这些值驱动了概率选择。

共享权重策略：为了避免从头开始重新训练新生成的RNN的神经参数，BP-Cants采用了一种共享权重策略，利用之前训练过的RNN的参数值为新生成的RNN提供一个高级的起点（详见[12]）。在BP-Free CANTS中，生成的RNN仅进行测试而不进行BP训练，因此共享权重在整个优化过程中持续进行，无需从生成的RNN中获取任何更新。

信息素沉积：当一个候选RNN在种群中赢得一席之地时，管理进程会将该架构对应空间质心的信息素值增加一个固定值作为奖励。由于这些质心通过其信息素值参与了质心的创建，因此靠近质心的点（即用于生成质心的点簇）也会根据它们与质心的距离，按比例增加其信息素水平。空间点的信息素值设有一个最大阈值，以避免某些点对Cant产生过强的吸引力，导致优化过程过早结束。

信息素挥发：无论工作者报告的RNN表现如何，信息素在每次迭代过程中都会定期衰减。衰减按固定值进行，当信息素值低于预定的最小阈值时，该点将从搜索空间中消失。清除信息素痕迹微弱的点有助于搜索空间摆脱可能阻碍Cant间通信以及拖慢整体优化过程的微小残留信息素。这种信息素衰减机制还防止算法过早陷入局部最小值。

算法的时间复杂度：尽管各种ANTS算法的时间复杂度很重要，但需要注意的是，使用这些算法生成递归神经网络（RNN）所花费的时间远远少于评估生成的神经网络适应度所需的时间（对于ANTS和BP-CANTS，这需要训练和验证；而对于BP-Free CANTS，仅需验证）。这一点在图7中得到了突出体现。

对于ANTS和BP-CANTS，每个生成的递归神经网络（可能包含数万个可训练参数）都需要通过时间反向传播进行多轮训练。由于所有ANTS算法都采用异步分布式/并行执行策略，训练可能同时在分布式计算节点上运行数百个RNN，而生成新RNN的主进程大部分时间都在等待工作者发出更多工作请求（生成一个网络可能只需几分之一秒，但训练它们并在验证数据集上评估它们可能需要数分钟，即使只进行少量轮次的训练）。对于BP-Free CANTS，网络在验证数据上的前向传播（无需反向传播）仍然比算法生成网络的时间快几个数量级。

BP-Free CANTS的时间复杂度为O(P log P)，其中P是搜索空间中信息素点的数量。这是因为复杂度受限于搜索空间中信息素的DBSCAN操作（所有其他操作，例如网络构建，都是基于DBSCAN生成的聚类线性进行的）。每当Cant代理在搜索空间中移动时，都会添加新的信息素值。这些信息素值会随时间衰减，并在低于给定阈值时被移除。遗憾的是，由于算法的随机性，无法计算可能的最大信息素数量的上限。尽管如此，根据我们在图7中展示并在第3.2.2节中讨论的实验结果，RNN生成时间在我们的实验中并未表现出无限制增长的趋势。如果这被证明是一个计算瓶颈，未来的一个潜在研究方向可能是通过移除最旧的信息素或合并聚类信息素痕迹，严格限制搜索空间中任意时刻可能存在的信息素数量。

3 结果

本研究将BP-Free CANTS与之前最先进的ANTS和BP-CANTS算法在三个与电力系统相关的真实数据集上进行了比较。所有三种方法均用于对某一参数进行时间序列数据预测，这些参数在之前的工作中已被用作基准。对于燃煤电厂数据，使用的是电厂锅炉的净厂热耗率。此外，还进行了实验以研究Cant代理数量的影响。

**计算环境**：ANTS、BP-CANTS和BP-Free CANTS的实验结果是在罗切斯特理工学院的高性能计算集群上调度完成的。该集群配备64个Intel® Xeon® Gold 6150 CPU，每个CPU有36个核心和375 GB内存（总计2304个核心和24 TB内存）。实验使用了3个节点（108个核心），并花费了大约4周时间完成。

**数据集**：使用的数据集来自燃煤电厂传感器读数，已在EXAMM仓库中公开，以鼓励在时间序列数据预测和可重复性方面的进一步研究。该数据集来自燃煤电厂12个燃烧器的测量数据。数据集是多变量且非季节性的，包含12个输入变量（可能存在依赖性）。这些时间序列非常长，燃烧器数据被分为7000个时间步长的片段。数据集被采样并分为1875个时间步长的训练集和625个时间步长的测试集（每分钟记录一次）。

3.1 Cant代理数量的影响

为了确定Cant代理数量对BP-Free CANTS算法性能的影响，进行了一项实验。实验聚焦于燃煤电厂锅炉数据集中的净厂热耗率特征。模拟和评估的Cant数量分别为5、10、15、25、35和50。

3.2 算法基准比较

为了比较三种不同的神经网络架构搜索（NAS）策略，每个实验重复了10次（试验）以进行统计比较。算法的计算处理设置如下：

- **ANTS和BP-CANTS**（遗传算法）：模拟1000个总步骤，每个候选RNN应用30轮局部反向传播（用于微调）。

- **BP-Free CANTS**（非遗传算法）：模拟3000个步骤，不进行任何反向传播。

BP-Free CANTS被赋予更多的优化迭代次数，因为它完成得更快（将在后文讨论），而BP-CANTS和ANTS由于每轮优化过程中执行反向传播轮次而消耗更多时间。

对于BP-CANTS和BP-Free CANTS，Cant代理的感知半径和探索本能值在创建/初始化时通过均匀分布∼ U(0.01, 0.98)生成，初始信息素值设置为1，最大值为10，信息素衰减率为0.05。对于DBSCAN模块，聚类距离设置为0.05，最小点数为2。使用的种群大小为10。ANTS、BP-CANTS和BP-Free CANTS的最大递归深度为5，预测时间跨度为1。生成的RNN在遗传算法ANTS和BP-CANTS中允许进行30轮反向传播以进行局部搜索/微调。ANTS使用了之前报道的最佳结果的超参数[31, 13]。

3.2.1 性能基准测试

图5展示了BP-Free CANTS、BP-CANTS和ANTS在实验设置下的性能比较结果，测量了每种算法找到的最佳RNN的均方误差（MSE）范围。图中使用箱线图展示了实验不同试验的最小值、最大值、中位数（四分位距内的线）和平均值（星号标记），未显示异常值。阴影形状界定了不同试验中适应度的最大值和最小值之间的区域（包含异常值）。表1展示了三种方法的平均MSE，表明BP-Free CANTS在绝大多数实验中处于领先地位。

令人满意的是，BP-CANTS和提出的BP-Free CANTS在所有实验试验中均优于ANTS。ANTS结果的平均值和中位数在5到15个代理时持续改善，但在使用25个代理时出现了一些准确性较低的结果。然而，随着代理数量增加到35和50，ANTS结果继续改善。总体而言，ANTS算法的性能随着代理数量的增加而表现出更低的MSE。

虽然BP-CANTS在5个Cant时略微优于BP-Free CANTS，但后者在所有其他代理数量下均表现出比前者更稳定的性能。CANTS性能曲线随Cant数量的饱和表明，对于所使用的数据集，最佳优化代理数量为最少的5个Cant，但BP-Free CANTS在35和50个Cant时仍能找到相对最佳的网络。需要注意的是，BP-Free CANTS在更高的优化迭代次数下获得了这些高质量的结果（在适应度/损失方面），但关键的是其计算时间成本显著更低（见下一节）。

3.2.2 时间基准测试

图6展示了每种优化方法（ANTS、BP-CANTS、BP-Free CANTS）在实验不同试验中消耗的平均CPU时间。从图中可以看出，BP-Free CANTS与ANTS和BP-CANTS之间在时间消耗上存在显著差距。不仅BP-Free CANTS在大多数代理数量下的性能显著优于CANTS，而且即使BP-CANTS在模拟优化迭代过程中进行了更多的演化操作，BP-Free CANTS仍然比ANTS和BP-CANTS快几个数量级，因为它在迭代过程中无需应用反向传播（BP）。CANTS（带BP）和ANTS的总操作时间非常相似，但这是可以预期的，因为两者被允许执行相同数量的优化迭代和BP轮次。

图7展示了BP-Free CANTS与BP-CANTS在时间消耗上的差异。两种方法被允许使用8个CPU和35个代理生成200个神经网络结构。图中显示了生成神经网络结构所消耗的时间，两种方法的时间非常接近，但由于BP-Free CANTS引入了额外的第四维度，其处理时间略长。

可以明显观察到，BP-CANTS的评估时间比BP-Free CANTS高出一个数量级，因为前者使用了反向传播（BP），而后者则没有。图中还展示了随着迭代的进行，两种方法在神经网络结构生成和RNN评估上的累积时间。BP-CANTS与BP-Free CANTS在累积时间上的巨大差异主要源于BP所消耗的时间。

在早期迭代中，累积时间的斜率较高，这是因为迭代开始时搜索空间相对空旷（没有信息素沉积），但随着迭代次数的增加，搜索空间逐渐被填充，导致代理创建更多的神经元，从而增加了评估时间。随后，曲线趋于饱和，这是由于信息素蒸发效应，使得信息素痕迹保持在一个相对恒定的水平。

4 讨论与未来工作

本研究提出了无反向传播的连续蚁群神经网络拓扑搜索（BP-Free CANTS），这是一种新颖的、受自然启发的非遗传优化方法，采用四维连续空间进行无界神经网络架构搜索（NAS）。CANTS提供了一种独特的策略，克服了构造性神经进化策略（通常过早陷入局部最小值）以及其他受搜索空间限制的NAS策略的关键局限性。此外，BP-Free CANTS通过将演化神经网络的突触权重搜索空间映射为四维空间中的第四维度，扩展了之前以蚁群优化（ACO）为核心的方法，统一了对最优神经网络结构和突触权重值的搜索。

实验评估验证了BP-Free CANTS在电力系统领域的真实数据集上自动设计用于时间序列预测的递归神经网络（RNNs）的性能。我们将该方法与最先进的元启发式优化方法ANTS（一种离散空间蚁群NAS算法）以及强大的遗传/反向传播核心算法CANTS（BP-CANTS）进行了比较。结果表明，BP-Free CANTS在性能上优于ANTS和BP-CANTS，同时运行速度显著更快。

本研究在将蚁群优化算法推广到复杂的连续搜索空间（特别是针对无界图优化问题，以NAS为关键应用）方面迈出了重要一步，为未来工作开辟了许多有前景的方向。特别是对于BP-Free CANTS，虽然搜索空间在时间堆栈的每个二维平面（或时间步长）上是连续的，但用户仍需指定（最大）离散层数。因此，一个潜在的扩展方向是使搜索空间在所有三个维度上完全连续，彻底消除这一参数，让信息素沉积指导递归连接的深度。这可能对离散事件、连续时间RNN模型[30]产生影响，这些模型试图解决更广泛、更复杂的序列建模问题。

此外，BP-Free CANTS可以为具有无法计算导数的激活函数或其他组件的网络（例如具有采样活动的模型，如伯努利分布，甚至是离散的脉冲神经网络）的设计和训练提供高性能的解决方案。BP-Free CANTS的一个潜在缺点是，如果有足够的计算资源为基于BP的NAS方法提供大量训练轮次（无需担心成本或排放），则生成模型的准确性将高于BP-Free CANTS。然而，BP的计算成本始终是NAS方法的负担，这也是寻找更快替代方案的重要原因[29, 42, 32, 44]。

最后，可能最有趣的是，包括本工作设计的算法在内的ACO算法通常只关注利用单一蚁群。根据蚁学家5的观点，将合成蚁群视为具有蚂蚁作为其“细胞”的活体生物[17]，可能会为模拟蚂蚁代理如何完成与整体生存相关的更复杂任务提供一个灵活、可扩展的仿真框架（即蚁群的蚁群）。将该算法扩展到其他领域，例如自动设计卷积神经网络（用于计算机视觉）或其他类型的递归时间网络（如用于自然语言处理的网络），将进一步证明这种受自然启发的方法的广泛适用性。

原文链接：https://arxiv.org/pdf/2305.06715