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

1738 软件学报 2024 年第 35 卷第 4 期

1
}
11: 将{y , t i i∈ {i i i } 记录动态评估表 R 中, 并计算出 y = ∑ i∈ {ii i } y ;
t
, t i
t
1 2 , ,..., t n
1 2 , ,..., t n
n
12:  t+1 = t ∪{θ t ,y t };
13: t←t+1;
14: end while
*
15: θ ←Optimizer( t+1 );
*
输出: 算法找到的最优解θ .

图 3 基于动态批量评估的绿色无梯度优化方法框架(GRACE)

从图 3 可以看出, 算法的结构分为两个部分. 在图 3 中, 右侧的红色顺时针循环代表了无梯度优化的通用
框架, 可以带入多种无梯度优化算法(如演化策略、贝叶斯优化等)进行实践. 左侧的蓝色逆时针循环表示算法
评估期间更新批量相似树(通过批量相似树来表示不同批量之间的相似度关系)并确定评估使用的批量的过程.
黑盒 API(即优化任务的目标函数)评估后得到的解会保存在最右边的动态评估表 R 中, 并将不同批量下评估
结果的均值反馈给无梯度优化算法, 进而完成优化器的一次无梯度优化迭代.
在图 3 右侧的红色顺时针循环表示的无梯度优化过程中, 由黑盒优化器(即对应的无梯度优化方法)提供
待评估的解, 通过调用黑盒 API 得到解在各个批量下的评估值, 将其记录在动态评估表 R 中并进行相关处理,
完成黑盒优化过程. 在图 3 左侧的蓝色逆时针循环表示的更新批量相似树过程中, 其核心是使用动态评估表 R
构建批量之间的相似度关系, 进而指导批量样本的选择与样本子集的构建. 在这个过程中, 算法会定期根据
动态评估表的内容构建一棵名为批量相似树的二叉树, 通过批量相似树来表征各批量之间的相似程度. 具体
而言, 批量相似树的每个叶节点均对应一个批量, 评估值高度相似的批量叶节点会被放置在同一父节点下,
表示批量内部样本的高度相似, 每一个非叶节点中存储着其子节点的相似度信息. 在每次优化之前, 会基于
当前的批量相似树, 使用批量索引选择策略选择多个批量参与到本次优化的过程(图 3 中蓝色字体确定批量的
过程). 通过图 3 左侧的蓝色循环过程, 动态选择出差异尽可能大的批量进行评估, 以较小成本获得更准确的
评估值, 从而使算法能够绿色高效地完成优化任务.
算法 1 展示了 GRACE 的完整过程. 算法每消耗 M 预算时更新一次批量相似树的结构, 并添加一个新的
批量进行评估. 在每次优化迭代时, 算法都会基于当前批量相似树的结构选择要使用的批量, 并将其与黑盒
优化器提供的待评估解拼接后调用黑盒评估 API, 以返回每个批量在当前参数组合下的评估值. 随后, 评估值
会被记录在动态评估表 R 中, 并根据动态评估表的记录向优化器返回最终评估值. 通过不断循环上述过程,
直到消耗完昂贵优化的预算, 由黑盒优化器返回最终的评估值作为优化结果, 完成整个优化过程. 这里黑盒
优化器可以是一般的无梯度优化方法, 在本文实验中, 选择了优化效果较为稳定的 CMA-ES [45] 算法.
4.2 批量相似树构造算法
在本节中将介绍批量相似树的构造算法, 算法首先评估不同批量之间的相似度, 然后根据相似度信息建
立批量之间相似关系的二叉树结构.
首先讨论动态评估表 R 的构建与动态更新的过程. 如前文所述, 动态评估表 R 是用来记录解在不同批量