噪声优化中任意时间算法性能评估的标准化报告框架研究

《Mathematics》：On the Performance Evaluation of Anytime Algorithms in Noisy Optimization

　　

在当前的基准测试框架中，缺乏一种标准化、详尽且论证充分的性能指标，用于对噪声优化问题中的任意时间算法（Anytime Algorithms, AAs）进行基准测试。本研究旨在遵循设计科学研究（Design Science Research, DSR）方法论，开发这样一项指标作为研究产物。研究人员回顾了现有的噪声处理实践和基准测试指南，并开展了基准测试实验，实验包含包含13个人工测试函数的测试套件，使用两种最先进的算法来评估该性能指标。基于实验结果和现有文献，本研究得出结论：算法性能不应依赖单一量化数值进行评估，而应通过一份全面的性能报告进行评估，该报告包含数值损失值（loss value）、函数评估次数（number of function evaluations）、墙钟运行时间（wall-clock runtime）以及展示损失值随时间变化轨迹的性能剖面图（performance profile）。该方法旨在最大限度地提高性能评估的可靠性、表达力和信息价值。

论文解读文章

一、研究背景与问题提出

许多现实世界的优化问题具有高度复杂性、不确定性和有限的计算资源等特征。受达尔文选择、重组和变异原理启发的进化计算（Evolutionary Computation, EC）自二十世纪中叶兴起以来，进化算法（Evolutionary Algorithms, EAs）及相关元启发式算法已广泛应用于工程和科学领域的各类挑战性优化问题。然而，无免费午餐定理（No Free Lunch Theorem, NFLT）表明，没有任何优化算法能在所有问题类别上表现最佳，这凸显了基准测试对于识别适用于特定应用的算法的重要性。

基准测试在优化研究中发挥着至关重要的作用，能够实现算法性能的系统性比较。然而，由于方法论要求、标准化流程的需求以及适当性能指标的选择，设计有意义的基准测试研究仍面临挑战。尽管已有若干基准测试框架被提出以改善可比性和可复现性，但随着优化方法和应用领域的不断演进，仍需持续改进。

噪声优化问题中面临一个特殊挑战：目标函数评估受到不确定性影响，如测量误差、随机模拟或环境变化。这类问题在规划、调度和路径规划等实际工程应用中十分常见。进化算法通常被认为适合这些场景，因其基于种群的搜索和迭代改进过程提供了一定程度的噪声鲁棒性。此外，它们可被视为任意时间算法（Anytime Algorithms, AAs），即随着可用计算资源的增加能够逐步产生更优解。

尽管在基准测试和噪声优化方面均取得了显著进展，但在单目标噪声优化中，尚缺乏一个被广泛接受、能够同时捕捉解质量和计算开销的性能指标。现有基准测试研究采用多种性能指标和停止准则，限制了研究间的可比性并降低了实验结果的可解释性。性能剖面图虽能提供有价值的算法行为视觉洞察，但并未提供标准化的总体性能量化度量。

该指标的开发还面临三个挑战：第一，基准测试研究在实验设计和报告标准上往往存在显著差异，使得得出一般性结论变得困难；第二，对任意时间行为和停止准则的不同理解阻碍了通用性能度量的定义；第三，噪声优化研究遵循两种不同的范式：一种侧重于重采样和种群控制等算法机制以减轻噪声，另一种则强调停止准则和对接近最优解的置信度。调和这些视角对于建立普遍适用的基准测试指标至关重要。

二、研究内容与主要结论

本研究针对上述研究空白，通过设计科学研究方法论，开发了一种用于单目标噪声优化中任意时间算法基准测试的总体性能指标。研究人员回顾了噪声优化、任意时间算法和基准测试的理论背景，描述了实验方法和基准测试设置，并基于实验结果评估了所提出的性能指标。

研究得出核心结论：不应依赖单一量化数值来评估算法性能，而应通过一份综合性能报告进行评估。该报告包含四个量化组成部分：最佳损失值、函数评估次数、墙钟运行时间和损失值与解候选之间的相关性。同时辅以性能剖面图作为视觉补充，以展示损失值随时间变化的轨迹。这一方法旨在最大化性能评估的可靠性、表达力和信息价值，为噪声优化领域更可靠、可解释和标准化的基准测试实践做出贡献。

三、关键技术方法概述

研究人员主要采用了以下关键技术方法：基于设计科学研究（DSR）方法论的指标开发流程；利用Nevergrad平台（版本1.0.1）构建包含13个人工测试函数的基准测试套件，涵盖可扩展维度、可分离与不可分离函数、偏置、多模态、病态条件数和欺骗性函数等特征；采用高斯噪声（Gaussian noise）作为加性扰动项并设置噪声水平（1和10）；选取两种具有噪声处理特性的任意时间算法——基于种群规模自适应的进化策略TBPSA和基于多臂老虎机（Multi-Armed Bandit）框架的NoisyBandit算法；采用固定预算（fixed-budget）方法评估损失值；通过50次独立重复实验获取统计样本，并运用Shapiro–Wilk检验、Kolmogorov–Smirnov检验、单样本T检验、Wilcoxon检验、Welch T检验、Wilcoxon秩和检验及Cliff's delta效应量进行统计推断；采用自适应局部线性相关分析检验损失值与解候选之间的非线性关系。

四、研究结果

4.1 描述性结果与算法比较

实验结果表明，NoisyBandit在大多数人工测试函数上通常评估初始解后即停滞，特别是在噪声水平1下，其损失值普遍高于TBPSA。主要例外是Ackley函数实例以及条件数为10,000和1,000,000的Bentcigar函数在噪声水平10、五维情况下的实例。在Genzcornerpeak和Deceptive Path函数上，NoisyBandit产生了无穷损失值，被视为在所测试配置下未能获得有限损失值的失败。TBPSA的性能随维度、噪声水平和函数难度而变化，在大多数评估案例中其平均损失未达到最优值，但在噪声水平1的两个实例上达到了目标精度阈值ε = 10^?1。总体而言，描述性结果在大多数评估实例上倾向于TBPSA，但并非在所有函数和噪声条件下均一致。

4.2 算法性能统计分析

研究人员对三种假设进行了统计检验：H1（TBPSA的损失值与各函数最优损失值显著不同）、H2（NoisyBandit的损失值与最优损失值显著不同）和H3（两种算法的损失值彼此显著不同）。H1在除Styblinski–Tang在噪声水平10、五维情况外的所有函数及其实例上均得到确认。H2在所有评估案例中均表明NoisyBandit的损失值与已知最优值显著不同。H3在大多数可评估配置中显示算法比较具有统计显著性，但两个Bentcigar案例（噪声水平10、五维）为例外，差异不显著或效应较弱。

4.3 性能指标讨论

研究人员从八个有效性标准维度讨论了损失值和函数评估次数作为性能指标的适用性。损失值虽是量化的但并非固有比率尺度；函数评估次数提供更清晰和更具表达力的比较度量。在目标逼近方面，所有实验中全局最优均未达到，但达到的平均损失与最优损失之间的差异可指示算法接近目标的程度。非单调性是固定目标方法面临的问题，而固定预算方法依赖单调性假设。停滞情况下固定目标方法失效，固定预算方法更优。可复现性和可比性方面，函数评估次数受机器计算速度影响，需以秒为单位报告墙钟时间以确保公平比较。损失值的可比性要求算法共享相同起始条件，且不同函数间绝对损失差异不一定可比，因此采用函数特定的排名而非跨套件聚合原始损失差异进行比较。

4.4 质量指标检验

研究人员应用了文献中提出的质量指标公式，选取Styblinski–Tang和Ellipsoid函数的三种不同优化状态进行分析。分析结果不具决定性：极端波动状态下，选择序列中最差1%的值会导致异常值被用作质量指标；收敛状态下损失和解候选值几乎相同，指标选择的相关性降低；中等波动状态下，选择最差1%往往产生边缘候选值，不能代表算法状态。研究提出使用序列中位数可能更准确地反映算法状态，但需进一步实证检验。

4.5 最佳损失值作为质量指标的可靠性

研究人员在三个难度不同的函数上检验了损失值与解候选之间的相关性：Styblinski–Tang（简单）、Discus100（中等）和Bentcigar条件数1,000,000（困难）。对于TBPSA，所有数据均非正态分布且无线性相关。通过自适应局部线性相关分析，Styblinski–Tang和Discus100呈现抛物线形状，表明损失随解偏离最优而增加；Bentcigar上TBPSA对许多不同解候选返回零损失值，非线性相关仅为1.3%。仅评估三个函数不足以得出确定性结论，但表明损失作为质量指标的可靠性取决于算法和函数的特征，这与无免费午餐定理一致。

4.6 对现有知识库的贡献

研究提出了一种标准化性能报告框架，包含四个量化输入：运行的最佳损失值、函数评估次数、以秒为单位的墙钟时间以及损失与解候选之间的相关性。这些值分别报告而非通过效用函数组合，共同作为解释算法在噪声优化问题上性能的基础。性能剖面图作为视觉补充纳入报告，以识别非单调行为和停滞。该框架的新颖性在于提出了一种标准化报告机制，呈现解释算法性能所需的信息，并支持同一问题上算法间的比较。

五、讨论与结论总结

讨论部分总结

研究讨论了性能指标在噪声优化中的多重挑战。损失值作为质量指标在噪声条件下可靠性不确定，需通过相关性分析加以评估。函数评估次数作为运行成本指标可解释，但依赖于达到目标的噪声损失值，且受函数评估计算成本和机器性能影响，必须以秒为单位报告墙钟时间。损失值和运行时间具有互补性，结合两者可提供更全面的性能度量。报告所有四个量化值虽降低了简洁性，但这是噪声优化固有复杂性和不确定性所必需的。研究承认其局限性：仅分析了高斯噪声分布、实验限于三个维度和两个噪声水平、预算受硬件限制为256,000次评估、仅使用13个测试函数、相关性计算仅针对三个函数且限于一维、质量指标公式仅在两个函数上测试、相关性和质量指标公式未在NoisyBandit上测试。尽管存在局限，研究工作仍实现了研究目标：开发了用于单目标噪声优化中任意时间算法基准测试的总体性能指标，并得到了理论论证和实证实验的支持。

研究结论翻译

本研究的实验表明，仅有一个函数实例达到了全局最优，凸显了对逼近度量（approximation measure）的需求。损失值在已知最优值的情况下可用于逼近最优，而运行时间在未知最优值时无法进行逼近。非单调性是另一个问题：固定目标方法仅关注达到目标，而固定预算方法依赖单调性。若在预算内未达到目标，可分配更多运行时间，尤其在过程停滞的情况下。此时固定目标方法失效。损失值和运行时间的比率陈述可用于比较算法性能，但损失受噪声影响，其作为质量指标的可靠性不确定。相比之下，运行时间可解释为优化成本，但依赖于达到目标的噪声损失。因此，考虑损失与解候选之间的相关性对于评估损失作为质量指标至关重要。损失函数针对每个优化问题定制，最优损失值各异，增加了可比性难度。运行时间也受函数评估计算成本和机器性能影响，必须以秒为单位报告以进行比较。损失和运行时间互补，结合两者可提供更全面的性能指标。报告墙钟时间补充了函数评估的成本信息，损失与解候选之间的相关性则反映了损失的可靠性。虽然报告所有四个值降低了简洁性，但这是噪声优化固有复杂性和不确定性所必需的。尽管噪声处理和质量指标方面取得了进展，噪声仍是持续挑战，需要进一步研究。