\chisao{}：一种基于GPU的原生并行优化器，通过收敛-反收敛振荡实现多模态黑盒函数优化

# 一种用于多模态黑箱函数的GPU原生并行优化器：基于收敛-反收敛振荡机制

来源：https://arxiv.org/html/2606.26164  
Ira Wolfson  
电子与电气工程系  
布劳德工程学院，卡米尔，以色列  
wolfsoni@braude\.ac\.il  

###### 摘要

寻找多模态黑箱函数的所有模式是优化、贝叶斯推理和科学计算中的一项基础挑战。现有方法——盆地跳跃、CMA-ES、多起点梯度下降——均以顺序方式运行，无法利用现代GPU硬件的巨大并行性。我们提出 **ChiSao**（收敛-暂停-反转-粘附-振荡），这是一种GPU原生的种群优化器，它同时运行整个样本批次，并利用有意的收敛-反收敛振荡周期来逃离局部陷阱，同时冻结已确认的模式。其结构性举措是非对称的：达到真正峰值的样本被冻结（“粘附”）并保留，而其余样本则通过基于动量的反收敛和随机平滑梯度继续探索。通过两种互补策略（“赶猴”和“金鸡”）进行自适应重播种，以维持整个过程中的种群多样性。在西蒙弗雷泽大学优化基准套件的全部42个函数上，涵盖维度d ∈ {2, 4, 8, 16, 32, 64}，ChiSao 在所有CPU基线方法在最难的多模态函数上于d≥8时均失效的情况下，实现了100%的模式恢复；在所有人方法都成功的函数上（Michalewicz函数d=64），加速比高达34倍；在单模态函数上（旋转超椭球d=64，纯GPU红利），加速比高达39倍。所有基准测试仅通过函数值评估目标——梯度通过有限差分计算——因此报告的加速比是在无导数的最坏情况下的测试结果。在相当大的似然噪声下（σ_noise 高达1.0），模式检测仍保持100%可靠。该算法以独立开源Python包的形式在PyPI上提供。

**关键词：** 多模态优化，GPU计算，黑箱优化，种群方法，模式发现，并行优化

## 1 引言

多模态优化——寻找仅能通过黑箱评估访问的函数 f: R^d → R 的所有显著最大值——在科学计算、概率推理和机器学习中广泛出现。挑战不仅在于找到全局最优，而在于 **列举所有模式**，因为下游任务（贝叶斯模型平均、多起点细化、混合模型拟合）需要完整的模式结构知识。

经典方法分为两类。**顺序** 方法，如盆地跳跃 [27] 和模拟退火 [10]，通过扰动单个解并随机接受或拒绝移动；它们一次只探索一条轨迹，本质上是顺序的。**种群** 方法，如CMA-ES [6] 和粒子群优化 [9]，维护一组候选解，但通常会将整个种群收敛到单个盆地，从而失去模式多样性。多起点梯度下降运行多个独立的优化轨迹，但这些仅在平凡意义上是尴尬并行的——每个轨迹独立且最多发现一个模式。这些方法都不是为现代GPU架构设计的：数千个算术单元同时对不同数据执行相同指令。在拥有 P > 10^4 个并行核心的GPU上，一个大小为 N ≤ P 的梯度评估批次与单次评估完成于相同的挂钟时间。顺序方法完全浪费了这种能力；种群方法仅在一次生成步骤内使用它。

ChiSao 是一种GPU原生的种群优化器，具有三种先验方法未曾结合的结构性举措。第一种是 **冻结与探索的非对称性**。达到真正峰值的样本（通过梯度范数和似然质量测试）从探索阶段中被冻结，但继续参与梯度上升以细化峰值。其余种群继续移动。标准种群方法要么推进所有粒子，要么一个也不推进；ChiSao 只推进那些仍有工作要做的粒子。第二种是 **有意的反收敛阶段**。在每个批处理L-BFGS传递之后，未冻结样本采取基于动量的梯度 **下降** 步骤。这既不是噪声注入（模拟退火），也不是随机扰动（盆地跳跃）；这是定向运动，动量项携带样本穿过山谷进入新盆地。第三种是 **随机平滑**，应用为“云手”阶段，其中未冻结样本在 ∇f 的高斯平滑估计上上升。在尺度 σ 下的平滑会抹去亚σ尺度的纹理，并暴露全局盆地几何形状。HLC和反收敛是互补而非冗余的：HLC在平滑景观上将样本引向有希望的区域；反收敛随后在原始景观上将其分散。两种重播种策略——“赶猴”（当许多样本仍未被冻结时使用）和“金鸡”（当大多数样本已被冻结时使用）——关闭了循环。该算法仅需要批处理函数和梯度评估，直接映射到GPU执行，并可作为一个即插即用的探索模块用于任何提供初始种群的优化器。

##### 贡献。
本文贡献有四个方面：将振荡周期作为多模态优化的一种策略，并形式化了冻结-探索的非对称性（第3节）；针对对数凹目标给出收敛保证，并为多模态情况提供覆盖分析（第4节）；在d ∈ {2, 4, 8, 16, 32, 64}的所有42个SFU函数上，与差分进化、盆地跳跃和CMA-ES进行基准测试（第5节）；以及噪声鲁棒性结果，显示在σ_noise = 1.0（即信号尺度本身）下仍能100%检测模式（第5.7节）。

## 2 相关工作

##### 盆地跳跃。
Wales和Doye [27] 提出盆地跳跃，交替进行随机扰动和局部最小化，通过Metropolis准则接受移动。该方法在低维有效，并已广泛应用于计算化学 [28]。其根本局限性在于顺序执行：每一步一个扰动、一个局部最小化、一个接受/拒绝决策。GPU并行化仅限于局部最小化子问题，而非搜索策略本身。

##### 模拟退火。
Kirkpatrick等人 [10] 引入基于温度的随机接受，在缓慢冷却下提供理论收敛保证 [5]，但在实践中需要指数级缓慢的调度以避免过早收敛。并行实现 [21] 分布独立链但不共享信息，失去了种群多样性的优势。

##### 进化与种群方法。
CMA-ES [6] 根据种群几何自适应调整全协方差矩阵，在单模态和轻度多模态问题上达到最优性能。小生境扩展 [20] 试图维持多样性但增加了显著复杂性。粒子群优化 [9] 使用对种群最优解的社交吸引力，除非修改加入排斥项 [3]，否则在多模态设置中会将种群聚集于一个盆地。差分进化 [25] 通过组合种群成员生成候选解，但与CMA-ES一样具有模式崩溃的倾向。

##### 多起点方法。
从随机初始点运行多个独立的基于梯度的优化器是实践中最常见的方法 [13]。它易于并行化，但有两个弱点：收敛到相同模式的起点浪费计算，且在收敛开始后缺乏维持种群多样性的机制。ChiSao 的去重和重播种直接解决了这两点。

##### 贝叶斯优化。
高斯过程代理方法 [24] 从串行角度针对相同的黑箱设置：每次采集步骤根据所有先前的评估重新拟合代理，然后优化采集函数。其设计目标是定位单一最佳点且在最小评估预算下，而非列举模式，且每步代理成本随种群大小增长而表现不佳。

##### GPU并行优化。
GPU加速优化主要集中在深度学习中的随机梯度下降 [4]，其目标函数是单模态的，瓶颈在于数据吞吐量而非探索。对于黑箱多模态优化，GPU加速在很大程度上尚未被探索，Salimans等人 [23] 是一个主要例外——为强化学习大规模并行化的进化策略，但采用单目标设计，不列举模式。Albert [1] 在GPU上并行化嵌套抽样（JAXNS），但嵌套抽样的顺序压缩结构限制了GPU在迭代间批处理中的利用率。ChiSao 似乎是首个在搜索策略本身实现完全GPU利用率的黑箱多模态优化器，而不仅仅在单次迭代内部。

##### 平滑与延拓方法。
将目标函数的高斯平滑作为逃离局部最优的启发式方法，已作为“扩散”或“渐近非凸性”被研究 [2, 14]。Nesterov和Spokoiny [16] 分析了凸优化中的高斯平滑。ChiSao 的“云手”阶段将平滑作为一个结构化振荡周期中的一环，而非全局预处理步骤或退火调度。

##### 与先前工作的对比。
ChiSao 在任何结构化轴上都与上述所有方法不同：方向性反收敛而非随机扰动；周期内的随机平滑而非全局退火调度；冻结-探索非对称性而非均匀种群移动；全批次GPU执行而非步内并行。带重启的盆地跳跃 [27] 是最接近的邻居；它在上述四个轴上都不同。

## 3 算法

### 3.1 问题陈述

设 f: Θ → R 是定义在有界域 Θ ⊂ R^d 上的黑箱函数，可通过评估 f(θ) 访问；算法使用的梯度 ∇f(θ) 通过有限差分计算，或在可用时通过解析方式提供。我们寻找所有 **显著模式** 的集合：

M* = {θ* ∈ Θ : ∇f(θ*) = 0, ∇²f(θ*) ≺ 0, f(θ*) ≥ f_max + log δ}   (1)

其中 f_max = max_θ f(θ) 且 δ ∈ (0,1) 是质量阈值（默认 δ=0.1，即全局最大值的十分之一范围内的模式）。目标不仅是找到全局最大值，而是识别 M* 中的所有成员。

ChiSao 接收一个初始候选点种群 {x_i}_{i=1}^N ⊂ Θ（任意；由调用者提供），并返回估计的集合 M̂* ⊆ {x_i}。

### 3.2 振荡周期

ChiSao 运行 n_osc 个振荡周期（默认为3）。每个周期由六个阶段组成，按固定顺序执行。该顺序是精心设计的，其理由在第3.3节中给出。

#### 3.2.1 阶段1：收敛
所有冻结掩码被释放（每个样本暂时解冻），整个种群经历 n_conv 步批处理L-BFGS [12,17] 朝着 f 的局部最大值。所有 N 个样本在单个GPU批次中同时优化：

x_i ← L-BFGS(x_i, n_conv)   ∀i=1,...,N   (GPU并行)   (2)

L-BFGS 的记忆参数默认 m=10。迭代次数根据维度自适应：n_conv = max(10, 3 log₂ d)。

#### 3.2.2 阶段2：粘附检测
收敛后，已达到真正局部最大值的样本被标记为 **粘附**：

stuck_i ← (‖∇f(x_i)‖_∞ < ε_grad) ∧ (f(x_i) ≥ f_max + log δ)   (3)

梯度阈值 ε_grad（默认10^{-6}）确保样本已达到驻点。似然阈值 log δ（默认 log 0.1）防止在 M* 之外的低质量局部最大值处粘附。粘附样本被排除在探索阶段之外，但继续参与梯度上升以细化峰值。

#### 3.2.3 阶段3：去重
使用 L_∞ 度量（见附录A）对粘附样本进行去重：如果存在 x_i ≠ x_j 使得 ‖x_i - x_j‖_∞ < ε_dup 且 f(x_i) ≥ f(x_j)，则移除 x_j。函数值较高的样本存活；其逆Hessian估计将保留用于宽度估计。记录移除的重复数量 K_lost。

#### 3.2.4 阶段4：重播种（赶猴 / 金鸡）
如果 K_lost > 0 且这不是最后一个振荡，则通过重播种将种群维持为大小 N。根据消耗状态使用两种策略。

##### 赶猴。
当剩余 ≥5 个未冻结样本时，新的样本通过从未冻结样本沿随机方向发射射线生成，沿这些射线在 Θ 内均匀采样。这使新候选解远离已知峰值。

##### 金鸡。
当剩余 <5 个未冻结样本时（接近耗尽），新样本从已确认峰值使用通过随机矩阵QR分解获得的正交射线方向生成。这利用GPU的并行能力系统地探测已知峰值的正交方向。