Page 157 - 《软件学报》2024年第4期

钱鸿 等: 基于动态批量评估的绿色无梯度优化方法 1735

均值来降低噪声影响 [41] 、通过阈值选择来处理噪声 [32] 、通过值抑制方法(如 SSRACOS 算法 [42] )控制受噪声影
响的评估值等. 这些方法均可用来处理使用训练子集评估造成的不精确问题, 例如, 可以采用多次评估取平
均值的降噪方法, 即在多个不同的训练子集上评估后, 将其评估的平均值作为评估值, 这样可减少不同训练
子集之间的差异性对优化性能的影响, 降低了评估的不确定性. 但此类方法也面临在优化过程中难以动态自
适应调节用于当前解评估的训练子集大小的问题.
• 梯度优化中的批量策略
随着 SGD [28] 和 MBGD 算法的问世, 诸多高效的基于样本子集的梯度优化算法被提出 [29,40,43,44] , 这些工作
往往将全量数据集划分为若干个小的批量, 并在批量上进行代价较低的批量梯度优化, 通过设计批量策略实
现高效优化. 例如: 随机平均梯度下降(SAG)算法 [40] 在训练期间记录每个批量上的梯度信息, 进而估计完整
批量的平均梯度, 实现高效梯度优化; 随机方差缩减梯度下降(SVRG) [43] 不需要长期存储每个批量梯度信息,
而是通过方差缩减技巧提高梯度估计质量以加速收敛, 达到更好的优化性能; SAGA 算法 [44] 在借鉴了 SAG 算
法中梯度估计方法的同时, 消除了 SVRG 算法的复杂步骤, 兼具了两者的优势. 尽管基于小批量样本子集进
行优化会在一定程度上带来解的收敛性问题, 但随着梯度优化方法的不断发展, 基于批量的梯度优化方法愈
加完善, 目前已经能够准确高效地处理梯度优化问题. 与梯度优化方法形成对比的是, 无梯度优化中聚焦批
量策略的工作匮乏, 当前鲜有针对批量优化的算法.
2 基础知识

d
对于变量θ∈Θ⊆ , 寻找黑盒函数 f(θ)的最优值(最大值或最小值)的问题称为无梯度优化问题. 本文以最
小化为例, 无梯度优化问题可被抽象为
θ * = argmin d f ( ),θ
Θ
θ ∈⊆
其中, f(θ)是黑盒目标函数, d 维变量θ∈Θ称为解, Θ称为解空间.
无梯度优化(又称黑盒优化、零阶优化) [22−24] 是通过对解空间进行采样并评估解的质量(即目标函数的值)
来完成优化任务的. 大多数无梯度优化方法的算法具有类似的框架, 如图 1 所示. 首先, 随机在解空间中采样
解来初始化解集. 在评估样本解的目标函数值后, 无梯度优化方法显式或隐式地建立关于潜在目标函数的模
型. 然后, 根据特定机制从模型中采样出待评估的新解. 最后, 将这些完成评估的解用于更新模型. 无梯度优
化方法迭代进行采样与模型更新过程, 不断提高解的质量, 直到算法满足终止条件, 以期找到最优解.

图 1 无梯度优化框架图
无梯 度优化的代 表性方法包 括演化策略 (evolutionary strategy, ES) [45−47] 、贝叶斯 优化 (Bayesian
optimization, BO) [48,49] 、基于分支定界法的乐观优化(optimistic optimization) [50−53] 、交叉熵方法(cross-entropy
method) [54] 等. 其中, 演化策略隶属于演化算法(evolutionary algorithm, EA), 是一种基于种群的优化方法, 无
需目标函数的梯度信息即可搜索解空间进行寻优 [46,55,56] . 在演化策略中, 搜索过程始于由一组候选解组成的
初始种群. 种群中的每个解都沿着特定的轨迹探索解空间, 每次迭代称为种群的一次演化, 由此产生的解集
称为种群的一代, 迭代过程中的种群会权衡探索与利用并趋于最优解. 演化策略具有在解空间中寻找全局最
优解的潜力.
在演化策略过程中, 构成解集的个体解将经历算子操作, 例如变异、杂交和选择, 这些操作产生新的解进