预测每次运行中连续优化算法性能的提升情况

《Swarm and Evolutionary Computation》：Forecasting continuous optimization algorithm performance improvement within each run

　　彼得·科罗谢克
计算机系统系，约瑟夫·斯特凡研究所，雅莫瓦街39号，卢布尔雅那，1000，斯洛文尼亚

**摘要**
本研究引入了预测模型，以预测连续优化算法在运行过程中的性能提升，这些模型不同于传统方法，后者仅关注最终性能结果。这些模型利用了顺序的、按迭代规模缩放的数据，包括算法执行过程中观察到的解决方案位置及其对应的目标值。通过这些信息，模型旨在预测未来迭代中的性能提升，并在预定的时间范围内进行评估。这种实时预测能力可以用于算法配置场景，提供额外的洞察，从而进一步提高黑盒连续优化问题的性能。我们评估了几种长短期记忆网络，选择它们是因为它们在处理顺序数据方面的有效性，并在两种场景下进行了测试：一是使用特定算法实例在单个问题实例上的运行数据来开发个性化模型；二是使用该算法实例在多种优化问题实例上的运行数据来开发模型。通过使用CEC2014基准测试套件（包含10维无约束问题实例）和不同的差分进化算法配置，我们的方法展示了优于基线预测模型的结果。

**1. 引言**
连续优化算法是解决工程、金融和机器学习等不同领域中各种复杂问题的基本工具。这些算法旨在在连续搜索空间中找到最优解，这些空间通常受到各种约束。为了提高它们的效率和适应性，许多研究引入了基于搜索过程反馈的自动参数控制机制。例如，[1]在L-SHADE框架内提出了一种集合正弦适应策略，实现了算法参数的动态调整；[2]则采用了强化学习来增强基于梯度的参数调整。[3]提供了关于此类自适应和自我调整策略的更广泛概述，[4]强调了将参数控制整合到元启发式算法自动化设计中的重要性。虽然这些方法旨在改进算法的执行行为，但一个新兴的补充方向是预测优化算法的未来性能。根据内部算法动态和种群行为来预测进展，可以为参数控制提供主动信息，指导策略性重启，并优化资源使用。这种预测建模可以与自适应方法相结合，为更智能、数据驱动的元启发式算法铺平道路。准确的预测在优化的多个方面都起着关键作用：它可以改进参数调整和算法选择，支持更高效的计算预算制定，并为新优化策略的设计提供依据。此外，它还有助于更深入地理解影响算法性能的潜在因素。

性能预测通常涉及分析多个因素，包括问题特征（如维度和景观特征）、算法属性、计算预算以及选定的性能指标。传统的性能预测模型依赖于问题的静态表示，这些表示通常来自探索性景观分析（ELA）[5]。ELA从采样候选解中计算统计特征，通常使用拉丁超立方或Sobol采样等预定义的采样策略[6]。这些特征一旦计算出来就固定不变，常用于训练监督机器学习（ML）回归模型，以估计算法的最终性能[7]。基于问题实例的景观特征训练的模型，用于预测在该实例上实现的算法性能，被称为实例级算法性能预测模型。现有实例级性能预测模型的一个关键局限性是它们专注于固定预算或固定目标的预测，而忽略了算法进展的动态性。一种缓解这一局限性的方法是分别为不同的预算或性能目标训练单独的回归模型。然而，这种策略依赖于静态的问题表示，无法适应不断演变的优化过程的动态性，因此会忽略优化轨迹中潜在的宝贵信息。

最近的研究探索了运行级算法性能预测模型，这些模型利用了算法执行过程中收集的数据[8][9]。这些模型利用从候选解轨迹中提取的景观特征，并在选定的预算下预测算法的最终结果，从而提供了更动态的算法性能估计视角。尽管取得了有希望的结果，现有的运行级模型往往忽略了观察到的候选解序列中的时间依赖性。

未来的一个关键挑战是开发能够充分利用优化数据时间结构的模型，以实现更准确和自适应的性能估计。通过整合先进的ML技术、时间感知建模方法和概率推理，未来的研究可以显著提高算法性能预测，从而制定出更明智的优化策略。

为了应对这一挑战，我们研究了优化过程的顺序迭代是否包含足够的信息来支持准确的性能预测。具体来说，我们关注运行过程中生成的解决方案种群，并评估它们预测未来迭代（如10步或40步之后）性能提升的潜力。通过捕捉迭代过程中种群动态的趋势，我们旨在确定这种在线信息是否足以预测性能提升。

这项工作的主要目的是增强对种群演化与算法性能之间关系的理解。所获得的见解在自动化优化策略中具有潜在应用价值。例如，它们可以用于触发算法超参数的调整，或在达到预定义的停止标准之前提前终止优化过程，从而减少计算时间和能耗。

**我们的贡献**：一个关键的创新是开发了运行级模型，这些模型可以在特定问题实例上预测算法性能的提升，同时明确考虑了观察到的候选解的顺序性质。我们提出的方法利用了顺序信息，特别是迭代种群中的解决方案位置及其对应的目标值。这些数据经过完全缩放，以消除对绝对值的依赖，并确保对搜索空间的简单变换具有不变性。利用这种表示方法，该方法旨在预测后续迭代中的性能提升，具体由预测范围定义。

鉴于数据的时间序列性质，我们使用长短期记忆（LSTM）网络作为预测模型。我们的目标不是确定最佳的时间序列预测方法，而是证明优化轨迹数据包含足够的信息来进行准确的性能预测。LSTM作为一种广泛用于建模顺序依赖性的架构，使我们能够在不需要比较多种预测技术的情况下捕捉算法行为趋势。

传统方法，如性能曲线拟合和生存分析[10]，可以为算法行为提供有价值的见解。然而，我们的方法直接从优化轨迹中提取预测信号。在这种情况下，种群数据经过缩放，以消除绝对值和简单变换的影响。为了评估我们的方法，我们在两种场景下测试了LSTM模型：
1. 仅使用单个算法实例在单个问题实例上的运行数据训练的个性化预测模型；
2. 使用单个算法实例在多个不同优化问题的实例上的运行数据训练的通用预测模型。

我们使用CEC2014基准测试套件[11]，在具有不同差分进化（DE）配置的10维问题实例上进行了实验。我们的结果表明，所提出的方法有效捕捉了优化动态，始终优于基线预测模型。

**论文结构**：
本文的其余部分组织如下：第2节概述了相关工作；第3节介绍了用于预测算法轨迹运行期间性能的基于LSTM的预测流程的所有步骤；第4节介绍了本研究涉及的数据以及评估所提出方法的两个场景；第5节展示了结果和讨论；第6节提出了结论。

**可重复性**：为了确保本文中介绍的工作具有可重复性，作者可以应要求提供所有相关数据、代码和结果。

**2. 相关工作**
大多数关于单目标优化自动算法性能预测的研究都集中在实例级模型上，这些模型预测算法在给定问题实例上的最终性能[12][13]。这些研究的一个共同趋势是将ELA特征作为输入到ML模型中进行性能预测。这些模型已应用于单目标（预测一个算法的性能）[7]和多目标（预测多个算法的性能）[14]回归设置。此外，还有一些研究采用了可解释的机器学习技术进行自动算法性能预测，如[14][15][16][17]所示。这些研究旨在通过SHAP可解释方法[18]进行景观特征分析，以阐明算法性能。

另一种替代静态ELA的方法是自适应景观分析，该方法使用算法在运行过程中访问的候选解来计算特征[19]。这种方法已应用于固定预算的运行级性能预测[8]，用于协方差矩阵适应进化策略（CMA-ES）[20]，其中从观察到的候选解中提取的特征可以预测超出给定预算的未来性能。这些方法依赖于在固定预算内从观察到的解决方案中计算的ELA特征，通常与从内部算法参数中提取的时间序列特征（tsfresh [21]）结合使用。然后，随机森林（RF）模型根据这些提取的特征预测未来性能[9]。然而，这些方法忽略了候选解生成的时间方面，将观察结果视为独立的而非顺序的。

其他研究探索了基于轨迹的表示方法，如DynamoRep[22]，它使用统计度量（平均值、标准差、最小值和最大值）来总结优化运行。这些特征可以视为ELA的一个子集，因为它们包含在ELA中，并有效地捕捉了优化算法针对的问题类的特征。当与RF模型结合使用时，这种方法的表现与标准ELA基方法相当。

除了基于特征的方法外，机器学习中还探索了基于数据的替代模型，这些模型不仅预测最终性能，还预测中间进展。学习曲线外推[23]和基于性能趋势的提前停止技术为预测模型行为提供了额外的见解。最近，我们引入了Opt2Vec[24]，这是一种连续优化问题表示方法，它消除了手动计算特征的需要。Opt2Vec直接从观察到的候选解中学习表示，使用在每次迭代中分别缩放的种群（即所有值都在0到1之间）进行训练。实验表明，这种表示仅通过优化轨迹的一次迭代就能准确分类问题类型，表明其在性能预测方面的潜力。这一见解直接启发了我们的研究，即研究动态的、缩放的、无特征的表示是否可以有效预测未来的性能提升。我们强调的不是实际性能值，而是给定算法配置在当前优化阶段预期的性能提升。

在基于轨迹的分析基础上，我们引入了一种预测单个算法运行中性能提升的方法。与依赖于预定义预算和手动提取特征的方法不同，我们的方法使用原始候选解数据作为输入到基于LSTM的预测模型中。通过滑动窗口方法，我们捕获了一定数量的过去迭代，以确定这些历史信息是否可以预测指定数量未来迭代中的最佳解决方案的提升。此外，我们还评估了输入序列长度对LSTM模型性能的影响，探索了短期、中期和长期的预测能力。

**3. LSTM预测流程**
为了描述我们的方法，我们首先解释了训练和评估它所需的训练数据，然后解释了LSTM预测模型作为回归任务来预测算法性能提升的方式。

**3.1. 训练数据**
为了生成训练数据，我们遵循了[24]中概述的协议，其中提供了详细的描述。本质上，我们的目标是在优化算法轨迹的任何点进行预测。每次优化运行包含多次迭代，直到满足预定义的停止条件。在运行过程中生成的种群被存储下来，捕捉算法种群随时间的变化情况。

需要强调的是，缩放收集到的种群数据对于确保不同优化轨迹之间的一致性至关重要，因为每个轨迹对应于不同的问题景观。由于绝对解决方案值可能会有所变化，但仍能传达有关算法行为的有意义信息，因此需要进行归一化。我们将最小-最大缩放应用于将各个种群标准化到[0,1]范围内。每个收集到的种群表示为一个矩阵，记为A，其维度为m×(n+1)，其中m是种群大小，n+1是解决方案的长度，包括n个决策变量和目标值。矩阵中的每一行对应一个解决方案，由目标值y和决策变量xj（其中j=1,…,n）组成。对决策变量和目标值分别进行缩放。对于决策变量，计算该种群中所有m个解决方案及其n个决策变量的最小值和最大值，以确保保持种群内解决方案之间的关系。同样，对于目标值，在缩放之前也从m个目标值中计算最小值和最大值。这样就得到了一个缩放后的矩阵A?，优化轨迹的每次迭代都由一个标准化的种群矩阵表示。这个过程生成了多个缩放后的矩阵，有效地捕捉了算法与问题实例之间的相互作用。

3.2. LSTM模型
长短期记忆（LSTM）[25]是一种循环神经网络（RNN）架构[26]，旨在解决传统RNN中的梯度消失问题，从而允许更有效地学习和保留序列数据中的长期依赖性。在这项工作中，我们采用了一个基于LSTM的预测流程，其高级可视化如图1所示。为了表示连续迭代中观察到的候选解决方案，我们评估了两种不同的输入特征向量：无特征和迭代ELA。
下载：下载高分辨率图片（233KB）
下载：下载全尺寸图片
图1. LSTM预测流程的流程图。

3.2.1. 无特征表示
我们将这种方法称为无特征表示，因为它不涉及特征提取的学习。相反，每次迭代的表示是通过将所有观察到的候选解决方案及其对应的解决方案值使用该迭代的缩放矩阵（A?）连接成一个单一向量来构建的。因此，每次迭代表示为一个m?(n+1)×1向量：[y1?x11?…x1n?y2?x21?…x2n??ym?xm1?…xmn?]?，其中m表示候选解决方案的数量，每个解决方案由一个缩放后的目标值y?和n个决策变量x?表示。在本文中，标有星号（?）的变量表示缩放后的值，而未标记的变量对应于原始的未缩放值。这些值的连接有两种方式：
1. 无特征（FF）：保持获得候选解决方案的顺序。
2. 无特征排序（FFS）：在连接之前根据它们的缩放后目标值对解决方案进行降序排序。
值得注意的是，对于总共记录了r次迭代的优化运行，我们会生成r个这样的向量。

3.2.2. 迭代ELA表示
我们选择了ELA表示方法，因为它是一种用于连续优化问题中特征计算的先进方法。如相关工作部分所述，大多数现有研究使用在y值上计算的ELA特征子集来预测算法性能。为了确保实验的公平性，我们采用了迭代ELA（iELA）计算程序[24]。在这种方法中，每次迭代都使用缩放矩阵A?来计算ELA特征。该矩阵包含一组缩放后的候选解决方案及其对应的目标值。
重要的是要区分基于轨迹的ELA计算[8]和iELA。基于轨迹的方法汇总了直到预定义预算的所有迭代的候选解决方案来计算ELA特征，捕捉优化运行的完整历史背景。相比之下，iELA仅从给定迭代中的当前种群中的候选解决方案派生ELA特征。这使得iELA能够捕捉轨迹中的动态变化，非常适合训练LSTM模型，因为LSTM可以从序列数据中受益。
虽然已知ELA特征对样本大小敏感[27]，但我们使用等于优化算法种群的样本大小来计算迭代特征，确保它们在我们的学习框架中的相关性。传统方法通常将ELA特征与静态随机森林模型配对，以预测固定次数迭代后的性能。相比之下，iELA特征是为每次新迭代计算的，为LSTM模型提供一系列输入。这种序列学习框架允许LSTM整合过去的信息并识别随时间变化的性能趋势。

3.2.3. 预测模型
LSTM预测模型的流程图如图1所示。我们将优化轨迹结构化为一系列迭代，将每次迭代视为一个时间步长。预定义的窗口大小（w）决定了用于预测的迭代次数。目标是在指定数量的未来迭代（f）后使用这些连续迭代来预测性能改进。每个输入数据实例由w个大小为m?(n+1)×1的序列向量（迭代）组成，所有这些向量都来自同一轮运行。给定一个记录了r次迭代的优化运行，最多可以生成r?w个训练数据实例，因为无法从最后w次迭代中形成一个完整长度的窗口。这可以解释为在运行内的连续迭代中逐个移动窗口。
无论使用FF/FFS还是iELA表示，每个迭代向量都会附加一个额外的特征：连续迭代之间最佳解决方案的对数改进。计算公式为：log(max(yi?1best?yibest,0)+1)，其中yibest表示第i次迭代中最佳解决方案的未缩放目标值。如果当前迭代中的最佳解决方案比前一次更差（即“负”改进），我们将计算出的改进值设置为0，视为没有改进。添加1确保所有计算出的值保持非负。这个特征捕捉了连续迭代与目标预测之间的关系。
然后将每个训练数据实例与一个目标值关联起来，该目标值代表f次迭代后算法的性能改进。改进定义为第i次迭代中最佳解决方案的目标值（即窗口大小w中的最后一次迭代）与第i+f次迭代中最佳解决方案的目标值之间的差异。为了考虑可能的较大改进，特别是在探索阶段，应用了对数转换：log(max(yibest?yi+fbest,0)+1）。
考虑到预测范围（f）和可用的数据实例（r?w），每次运行的最终训练实例数量为r?w?f，因为只有这些实例才能计算f次迭代后的改进。每次运行生成的训练实例数量取决于r、w和f，不同的设置会产生不同数量的可用训练数据。
使用两种数据实例表示（FF/FFS和iELA），在两种情况下训练每次运行的LSTM模型：
- **针对单个问题实例的个性化**：在这种情况下，使用特定算法实例在特定问题实例上获得的运行结果。该算法实例在该特定问题实例上进行了多次运行。之后，将总运行次数分为训练集、验证集和测试集，分布分别为70%、20%和10%。这确保了来自单次运行的数据实例（即迭代）仅分配给训练集、验证集或测试集，因为分割是在运行级别进行的。这个过程已经针对10个不同的算法实例重复进行了10次，具体细节在实验设计中有所说明。为每对算法实例和问题实例分别训练了一个模型。
- **针对多样化问题实例的模型**：在这种情况下，使用特定算法实例在整个问题实例集上获得的运行结果，将它们随机分配到训练集、验证集和测试集中，比例分别为70%、20%和10%。应该注意的是，由于这种随机分割，不能保证每个问题实例在训练数据中至少有一次运行。与之前的场景类似，从单次运行中收集的数据实例仅分配给训练集、验证集或测试集，因为分割是在运行级别进行的。为10个不同的算法实例（即算法配置）分别训练了一个模型。

4. 实验设计
4.1. 基准问题集
为了说明我们的方法，我们从CEC 2014竞赛[28]中选择了测试问题。在实验中使用了所有30个测试问题，并且固定维度D=10。我们选择这个维度是因为它在基准研究中被广泛使用，代表了典型的现实世界优化场景，并且无需在多个维度上进行广泛的实验就能提供全面的见解。

4.2. 优化算法
我们选择了一个基本的差分进化（DE）算法[29]作为优化方法，因为它简单且具有强大的启发式性能，旨在评估我们提出方法的潜力。原则上，任何优化算法的轨迹数据都可以用来测试这种方法。
在我们的实验中，我们通过在以下范围内变化超参数来随机选择十个不同的算法实例：变异策略DE/(Rand/1/Bin, Rand/1/Exp, Rand/2/Bin, Rand/2/Exp, Best/1/Bin, Best/1/Exp, Best/2/Bin, Best/3/Bin, RandToBest/1/Bin, RandToBest/1/Exp, Rand/Rand/Bin)，缩放因子F∈(0,1)，以及交叉概率Cr∈(0,1)。这些策略使用标准符号DE/x/y/z表示，其中x表示基础向量选择方法，y表示差分向量的数量，z指定交叉类型。这些策略的详细描述可以在[29]、[30]中找到，DE/Rand/Rand/Bin除外，它有点异常，但也是原始DE作者实现的。就标准DE符号而言，它最接近的类似物是DE/Rand/1/Bin。尽管如此，它在几个关键方面有所不同：(i) 它引入了两个级别的随机性，因为基础向量和缩放因子在每次变异时都是随机化的；(ii) 它不是使用固定的或均匀分布的缩放因子F，而是使用高斯分布的F，产生的步长从非常小到偶尔很大，从而可能增强探索；(iii) 它仍然使用单个差分向量（标准符号中的y=1），保持了经典DE/rand/1方案的结构简洁性，同时改变了其搜索动态。变异可以表示为xi+F(xj?xk)，F～N(0,1)，其中xi,xj,xk∈{x1,x2,…,xm}表示当前种群中的三个不同解决方案向量（i≠j,j≠k,i≠k）。
在下文中，“/”从符号中省略，以匹配类名。为了避免任何偏见（无论是有意识的还是无意识的），超参数的选择完全是随机的。为十个DE实例选择的配置列在表1中。
每个问题实例都使用相同的十个随机选择的配置进行评估，代表不同的算法超参数设置。对于每个配置，每个问题实例进行了30次独立运行。种群大小设置为问题维度，虽然这不是为了获得最佳性能而优化的，但为了本研究的目的，它在探索和利用之间提供了一个合理的平衡。

表1. 随机选择的DE配置。
策略 FCr DEBest2Bin 0.024 139 98
DEBest3Bin 0.533 438 0.809 657
DEBest2Bin 0.862 978 320 0.993 288
DERandToBest1Exp 0.138 804 610 0.516 620
DEBest2Exp 0.625 808 960 0.996 116
DEBest1Bin 0.617 255 170 0.514 743
DERandRandBin 0.516 212 630 0.686 841
DERand2Exp 0.330 060 380 0.028 075 69
DERand2Bin 0.133 79 181 0.364 538
DEBest1Bin 0.451 446 890 0.173 182 33

虽然选择特定的超参数值总是有争议的，但我们的目标是展示所提出方法的潜力，而不是微调DE以获得最佳性能。未来的研究需要进行多方面的全面敏感性分析，但这超出了本文的范围。

4.3. 迭代ELA特征
在每次迭代中，我们计算了所有来自disp、basic、ela_meta和ela_level类别的ELA特征，如[31]中所定义的。由于某些计算产生了NA值，我们只保留了在给定问题实例的所有迭代中都有有效值的特征。因此，使用的ELA特征数量在31到59之间变化，取决于实验配置，包括问题维度和算法实例的行为。

4.4. 基于LSTM的预测架构
在这里，我们提供了使用Python库TensorFlow[32]实现所提出方法的详细信息。我们实验中使用的基于LSTM的预测模型包括以下层：一个自定义的洗牌层、一个LSTM层、一个丢弃层和两个全连接层。迭代次数设置为4000，批量大小设置为512，学习率设置为0.001，选择Adamax作为优化器。
洗牌层仅在FF表示中应用，它在每次迭代中随机重新排序解决方案。这是必要的，因为种群本身并不决定解决方案的顺序，这意味着它们的位置可以是任意的。为了防止这种随机性影响模型，洗牌层确保每次执行都保持随机顺序。然而，对于FFS和iELA表示，不使用这个层，因为值的顺序已经预先定义。
对于LSTM层，隐藏单元的数量由以下公式确定：?23×(input_vector_size+target_size)?，其中input_vector_size表示单个输入向量的维度。在FF或FFS的情况下，这对应于人口规模与解决方案长度的乘积，并增加了一个维度来表示对数改进。对于iELA，inputvectorsize被定义为ELA特征的数量，同样增加了一个维度来考虑对数改进。在我们的案例中，target_size的值始终为一，因为我们只预测一个数字。这个方程遵循了一个常用的启发式方法来选择LSTM单元的数量，将其定位在输入和目标大小之间作为一个合理的起点。激活函数被设置为双曲正切。正则化参数被设置为l1=5×10^-6和l2=10^-6。由于正则化值高度依赖于数据，我们在一个小数据集上进行了初步运行以确定适当的值，从集合{10^-4, 5×10^-4, 5×10^-5, 10^-5, 5×10^-6, 10^-6}中选择。加入了dropout层以减少过拟合并增强模型在训练期间的鲁棒性。我们使用标准的dropout率为0.2，意味着20%的LSTM输出在后续层中被随机忽略。在最后阶段，添加了两个全连接的隐藏层来计算预测结果。这些层的宽度是根据LSTM输出大小和输出层大小（在我们的案例中为1）之间的几何级数来确定的。本研究的主要目标是评估所提出的方法是否产生有希望的结果，而不是优化模型架构本身，后者是一个复杂的任务。在未来的工作中，我们计划应用神经架构搜索（NAS）[33]技术来识别最佳的LSTM架构和超参数。此外，我们旨在进行全面的敏感性分析，以评估我们的方法对各种LSTM参数选择的鲁棒性。实验使用了所有10种DE配置和30个问题实例中的个别运行。针对每种DE配置，分别使用每个问题实例的运行来训练个性化模型。此外，还集体使用所有30个问题实例的运行来训练LSTM模型。性能在不同的窗口大小（w∈{1,10,20, 30}和预测范围（f∈{10,20,30,40}）上进行了评估。选择这些值是为了检查短窗口大小和长窗口大小，以及短预测范围和长预测范围。每个实验都包括了FF、FFS和iELA表示方法，总共训练了14,880个模型。鉴于这项研究需要大量的模型，实施了提前停止策略以减少计算复杂性。如果在20%的所有周期内没有观察到改进，则停止训练，这有助于在保持模型性能的同时优化资源使用。4.5. 评估结合了三种表示方法（FF、FFS、iELA）的LSTM预测流程使用平均绝对误差（MAE）在测试集上进行了评估。结果按DE配置组织，窗口大小（w）和预测范围（f）固定。这种设置每种配置产生了93个模型，来自3种表示方法×31个模型（30个个性化模型加上一个跨所有问题实例训练的模型）。在分析结果之前，我们首先建立了一个基线模型，作为评估所提出方法有效性的参考。4.5.1. 基线模型选择了四种不同的基线模型进行评估。1. 第一个基线（B1）遵循标准的机器学习方法进行回归任务，其中训练实例中观察到的平均改进被用作所有测试实例的预测值。然而，由于这种方法没有考虑到数据的时间序列特性，即改进取决于轨迹的阶段（例如，在早期探索期间有较大的增益，而在后期增益较小），我们引入了三个来自时间序列领域的额外基线。2. 第二个基线（B2）通过使用窗口大小内最后观察到的改进来预测性能改进，假设后续迭代中趋势相似。3. 第三个基线（B3）计算窗口大小内所有迭代的平均改进，根据该窗口内的过去趋势估计未来的改进。4. 第四个基线（B4）通过将平均改进乘以预测迭代次数来扩展B3，有效地假设在预测范围内改进呈线性增长。在基线评估之后，预测结果进行了统计和实证分析。4.5.2. 统计分析对于每个元组（DE配置、w和f），我们进行了统计分析，以确定使用FF、FFS和iELA表示方法训练的LSTM模型与选定的基线模型之间的预测性能是否存在显著差异。我们统计比较了四种基线模型并选择了表现最好的一个。然后使用这个选定的基线作为评估我们LSTM模型的参考。在一个30×4的矩阵上进行了Friedman测试[34]，其中每一行代表一个不同的评估场景，列对应于FF、FFS、iELA和基线模型。每个30个场景都被视为一个独立的实例，因为训练数据仅来自个别问题实例的个性化模型。然而，我们排除了跨所有问题实例的运行训练的模型，因为将其包括在内将违反统计测试所需的独立性假设。最后，为了识别模型对之间的统计显著差异，我们应用了Bergman和Hommel的程序[35]进行全对全的事后测试方法。4.5.3. 实证分析为了评估三种LSTM模型和选定的基线模型之间的实际预测性能差异，我们进行了实证分析。使用公式sMAE(i)=MAEi?MAEmin/MAEmax?MAEmin对每个元组（DE配置、w和f）内的31个评估场景（30个个性化模型和一个跨多个问题实例训练的模型）的平均绝对误差（MAE）进行了缩放。这种转换将MAE值规范化到0到1的范围内，其中0代表最低的MAE，1代表最高的MAE，所有其他值按比例缩放。这确保了绝对误差幅度不会影响比较，允许对具有相似MAE的模型进行更细致的评估。通过对31个评估场景的平均sMAE进行平均，为每个模型提供了总体性能指标。使用这些聚合值，计算了每个DE配置在固定w和f下的模型之间的成对差异，提供了它们相对预测成功的见解。下载：下载高分辨率图像（739KB）下载：下载全尺寸图像图2. 使用FF方法和DE配置（strategy=DEBest1Bin, F=0.45144689, Cr=0.17318233）在测试数据实例上比较真实（蓝线）与预测（粉线）改进的情况。5. 结果和讨论为了说明性能改进预测与实际改进的比较，我们在图2中展示了四个示例，展示了单个算法配置实例在四种场景下的结果。蓝线代表随时间（即迭代次数）的实际改进，而粉线表示基于特定DE配置（strategy=DEBest1Bin, F=0.45144689, Cr=0.17318233）应用的FF方法的预测改进。子图2(a)显示了所有问题的聚合结果，窗口大小w=10，预测范围f=40，其中预测的改进通常与真实趋势一致。子图2(b)–2(d)分别展示了在不同w和f配置下的个别问题（18、30和21）的结果。在每种情况下，预测曲线相对紧密地跟随真实改进轨迹，有效地捕捉到了急剧下降、平稳期和周期性行为，尽管峰值幅度和时间有些变化。聚合和个别案例之间的一致性展示了模型在不同问题上的泛化能力，并能够准确预测未见测试实例上的优化性能。下载：下载高分辨率图像（625KB）下载：下载全尺寸图像图3. 使用FF方法和DE配置（strategy=DEBest1Bin, F=0.45144689, Cr=0.17318233）的训练（蓝曲线）和验证（橙曲线）数据实例的MSE损失曲线。在图3中，我们还展示了与图2中相同的四种场景的MSE损失曲线。子图3(a)汇总了窗口大小w=10和特征大小f=40的所有问题实例的训练和验证损失，显示训练损失迅速减少，而验证损失相对稳定。子图3(b)–3(d)提供了特定问题的结果，在所有情况下，训练损失如预期般持续减少，而验证损失稳定在较高水平，表明泛化差距因问题和配置而异。这些曲线突出了训练过程的收敛行为，并展示了所显示配置下的预测性能趋势。损失曲线还揭示了几个配置中的轻微过拟合程度，这通过训练和验证MSE之间的差距得到证明。虽然模型在训练过程中一致收敛，但更高且更稳定的验证损失表明泛化可以进一步改进。我们计划结合更多的正则化策略，并根据最低的验证MSE应用模型检查点，以确保最终模型参数对应于未见数据上的最佳性能状态。所有实例和场景的完整结果可向作者索取。在以下部分，我们将通过统计和实证分析呈现整个研究结果。5.1. 基线比较对每个DE配置在固定w和f值的情况下进行了统计分析。如果在事后测试中一对基线之间发现了0.05显著性水平的统计显著差异，则结果记录为零；否则，分配一个值为一。结果表明，在大多数测试配置（DE配置,w,f）中大多数基线之间存在显著差异，如图4所示，所有单元格都非常浅蓝色。图中的每个单元格代表在160个配置中没有检测到统计显著差异的配置数量。深蓝色表示显著差异的数量较多，而浅蓝色表示统计显著差异较少的情况。图中观察到的模式在所有测试的窗口大小和预测范围内保持一致。下载：下载高分辨率图像（149KB）下载：下载全尺寸图像图4. 在所有160个元组（DE配置，w，f）上，基线模型之间的统计分析结果。为了确定最合适的基线，我们对所有四个基线模型进行了实证分析（见图5）。子图5(a)–5(c)中的箱形图分别展示了基线模型B2、B3和B4与B1相比的相对预测性能改进，考虑了不同的窗口大小、预测范围及其组合。在每个子图中，预测的相对改进计算为sMAE(B1)?sMAE(Bi)/sMAE(B1)，其中i∈{2,3,4}，使用第4.5.3节中描述的聚合sMAE。正值表示预测性能有所改进（即Bi的MAE小于B1的MAE），而负值表示预测准确性下降。结果表明B2和B3的性能相似，都优于B1。然而，B4的表现始终不如所有其他基线。基于此分析，我们选择了B3作为最终基线模型（B），因为它在实证评估中表现略优于B2。下载：下载高分辨率图像（558KB）下载：下载全尺寸图像图5. 基线模型预测性能的实证比较。下载：下载高分辨率图像（339KB）下载：下载全尺寸图像图6. 关于窗口大小（w）的LSTM模型与选定基线之间的统计分析结果。5.2. 统计分析（LSTM vs 基线）图6展示了四种不同f值和10个DE配置的合并统计结果，共分析了40个模型以寻找显著差异。子图中的每个单元格代表在40个案例中没有发现统计显著差异的案例数量。在窗口大小w=1时，使用FF和FFS表示方法的LSTM模型之间几乎没有统计显著的性能差距，两者与使用iELA的LSTM表现相似。当w=10或20时，FFS和iELA之间没有观察到显著的性能差异，两者都与FF紧密对齐。在w=30时，所有三个模型的表现相当，(FF, LSTM-FFS)和(FFS, iELA)对之间的差异最小。然而，在所有情况下，基线模型的表现都显著低于任何LSTM模型，无论使用哪种表示方法。在单独分析预测范围时（见图7），我们发现预测范围大小对三个LSTM模型的性能没有统计显著影响。再次，基线模型在所有情况下的预测性能与任何LSTM模型相比都表现出显著差异。在接下来的部分中，我们将通过实证分析进一步探讨LSTM模型与选定基线之间的差异。下载：下载高分辨率图像（339KB）下载：下载全尺寸图像图7. 关于预测范围的LSTM模型与选定基线之间的统计分析结果。下载：下载高分辨率图像（607KB）下载：下载全尺寸图像图8. LSTM模型与基线预测性能的实证比较。表2. 每个问题的MAE值，分别针对三种LSTM模型（FF、FFS、iELA）和基线模型（B）进行报告。每个MAE值是在16种模型变体（w和f的组合）上平均得出的，并在10种DE配置上再次平均。每个问题的最佳结果以粗体显示。5.3. 实证分析（LSTM vs 基线）为了提供一个关于预测性能的总体概述，我们汇总了所有比较方法的MAE值（FF、FFS、iELA和B）。具体来说，我们通过在不同w和f的组合下计算16种不同配置的平均MAE值，然后在10种DE配置上再次平均。这种汇总是针对每个问题场景以及包含所有问题实例运行的场景分别进行的。这种汇总提供了所有训练模型结果的高层次总结。表2中的结果显示，FF方法在31个案例中有17个案例表现最佳，iELA在8个案例中表现最佳，而基线模型B始终表现最差。乍一看，这些结果表明使用FF表示法训练的LSTM模型整体表现最好。然而，当考虑包含所有问题实例运行的训练场景时，FFS方法的表现最佳。尽管基于LSTM的方法之间的差异不大，尤其是与基线模型相比，但结果突显了表示选择对预测准确性的影响。为了获得更深入的见解，我们使用固定w和f的每种DE配置的聚合sMAE来分析模型之间的成对差异。结果在图8中可视化。与图5类似，子图8(a)–8(c)中的箱形图展示了每个LSTM模型相对于基线的预测性能的相对改进。在所有情况下，LSTM模型总体上始终优于基线模型，尽管有些个别情况下（由低于0.0的须状线表示）基线模型的表现更好。在这些模型中，使用FF表示法训练的模型取得了最佳的预测性能。下载：下载高分辨率图像（584KB）下载：下载全尺寸图像图9. LSTM模型预测性能的实证比较。5.4. 实证分析（LSTM模型）鉴于LSTM模型之间的性能相似，我们进行了更详细的实证分析，专门针对这些模型并排除了基线模型。图9中的结果表明，当窗口大小大于一时，使用FF表示法训练的LSTM模型在所有预测范围内都取得了最佳性能。此外，当窗口大小为30时，使用FFS表示法训练的LSTM模型在预测性能上优于使用iELA表示法训练的LSTM模型，无论预测范围如何。这表明，在输入更多历史信息时，无特征方法可能更有效。虽然使用无特征表示法（FF和FFS）的LSTM模型与使用iELA的LSTM模型在性能上没有统计学上的显著差异，但后者计算成本更高。这主要是由于每次迭代都需要在无特征表示的基础上计算ELA特征。此外，迭代次数因运行而异，因为不同的算法实例和配置不一定遵循严格的探索-利用模式。这种变异性可能导致优化阶段延长或缩短。5.5. 在更高维度下的性能洞察在实验中，由于评估的复杂性和耗时性，我们将维度限制为10。为了了解该方法在更高维度下的潜力，我们在图2中展示的单一问题实例上进行了相同的实验，但维度设置为30。DE算法使用与D=10实验相同的超参数设置执行，只是将种群大小增加到30以匹配问题维度。此外，由于D的增加，评估预算增加到D×10,000=300,000次函数评估。LSTM模型架构的构建保持不变。确定LSTM单元数量、输出宽度和整体结构的程序与原始实验相同。唯一的修改是输入大小，从D=10的10×(10+1)增加到D=30的30×(30+1)，同样是由于D的增加。这种输入维度的变化自然影响了相应的层，但底层模型设计和配置保持一致。实验设置没有其他修改。因此，总体运行时间显著增加，模型通常需要更多的训练周期，这也可以从所检查的实验实例结果中观察到。图10、图11和表3中的相应结果表明，即使在维度增加的情况下，相对性能仍然相当，表明所提出的方法也可以有效地应用于更高维度的问题。考虑到更高的维度，图10和图11显示的行为与D=10时的观察结果一致。表3中报告的MAE值略有差异，其中iELA的表现略优于FF。尽管如此，所有基于LSTM的方法仍然显著优于基线模型。表3. 问题18、21和30的MAE值，分别针对三种LSTM模型（FF、FFS、iELA）和基线模型（B）进行报告。每个MAE值是在16种模型变体（w和f的组合）上平均得出的，并在维度为30的10种DE配置上再次平均。下载：下载高分辨率图像（497KB）下载：下载全尺寸图像图10. 使用FF方法和DE配置（strategy=DEBest1Bin, F=0.45144689, Cr=0.17318233）在维度为30的测试数据实例上，真实值（蓝线）与预测值（粉线）的比较。下载：下载高分辨率图像（495KB）下载：下载全尺寸图像图11. 使用FF方法和DE配置（strategy=DEBest1Bin, F=0.45144689, Cr=0.17318233）在维度为30的训练（蓝曲线）和验证（橙曲线）数据实例上的MSE损失曲线。6. 结论本研究引入了旨在通过利用序列迭代数据来提高实时算法性能预测的预测模型。与仅关注最终性能结果的传统方法不同，我们的模型预测了预定义迭代次数内的改进，提供了有价值的预测范围。利用适合处理序列数据的LSTM网络，我们在单实例运行和多样化的问题实例集上进行了实验。模型使用CEC2014基准套件进行评估，该套件包含10维问题实例和各种DE配置。我们的结果表明，LSTM模型始终优于基线预测模型，突显了它们的有效性。此外，我们比较了无特征表示和迭代ELA表示作为模型输入的效果。研究发现，当候选解决方案未按目标值排序时，无特征方法的表现优于迭代ELA表示。这突显了使用无特征方法进行预测的优势。在基于种群的算法中，可扩展性是一个关键因素，特别是随着种群规模和问题维度的增加。较大的种群通常有助于保持多样性并避免过早收敛。这种效应在高级差分进化变体（如L-SHADE [1]）中尤为明显。然而，大型种群也会给基于学习的组件带来挑战，包括增加的内存需求、降低的计算效率和建模稳定性。此外，由于问题复杂性的增加或混合或自适应算法中模块组件的激活/性能，维度的增加进一步加剧了准确预测改进轨迹的难度。解决这一挑战的一个潜在途径是降维技术。通过将种群成员的高维表示压缩到更紧凑的潜在空间中，诸如自动编码器 [24] 等技术可以帮助保持固定大小的学习输入，同时保留种群动态的关键特征。这不仅减少了计算负担，还可以通过过滤掉噪声和冗余信息来稳定学习过程。对于未来的研究，我们计划：•扩展LSTM模型以进行多点预测，以捕捉比独立预测每个范围更丰富的时间模式。•通过集成学习来提高模型性能，结合多个无特征和迭代ELA模型来改进我们的预测方法。•探索先进的时间序列建模技术，特别是基于Transformer的架构 [36]。•研究不同算法和问题集之间的泛化能力，将我们的分析扩展到目前测试的算法和问题实例之外。•研究迁移学习，即在一个特定问题实例上针对不同配置训练的LSTM模型在同一实例的不同配置上进行测试。•还将进行全面的敏感性分析，以评估各种参数如何影响预测性能。•研究强化学习（RL）在动态性能预测中的应用，其中基于RL的模型可以根据观察到的优化进度来调整预测。•研究降维技术，以提供有关在大型或高维设置中平衡种群多样性和学习效率的宝贵见解。通过解决这些方向，我们旨在进一步提高预测能力并改进优化算法中的实时决策。我们相信这项工作为未来在算法选择和配置方面的进展奠定了坚实的基础，提供了比静态方法更动态的替代方案。