SDDObench：面向带有概念漂移的流式数据驱动优化问题的测试基准

《SDDObench: A Benchmark for Streaming Data-Driven Optimization with Concept Drift》

作者：Yuan-Ting Zhong, Xin-Can Wang, Yu-Hong Sun, Yue-Jiao Gong*
会议：GECCO 2024

文章指路：SDDObench

辅助材料–SDDObench_supply.pdf

开源代码库：LabGong/SDDObench

动机

数据驱动的优化限制在静态环境下，针对动态变化环境下的相关算法研究却寥寥无几
当前缺乏统一的测试基准和比较指标来对不同的算法做比较。

创新点

本文提出了一个统一的测试基准来针对动态环境下的数据流驱动优化问题的算法进行评估
该测试基准由两类不同的目标函数和五类不同的概念漂移函数通过设计的变换函数组合而成，最终得到一个适用于测试动态数据流环境下的优化算法测试基准。
本文提出的测试基准参数允许用户自定义进行调节，具有高度自定义化。

测试基准实例速览

在SDDObench中，一个优化问题定义如下：

$F=f(g(\phi,\delta(t))) \tag{1}$

其中， $F$ 就是最终需要优化的目标函数，而 $\phi$ 则是相应的自变量，t表示时间。这个复合形式的函数中， $f$ ， $g$ 和 $\delta$ 这三个函数就是本方法中所提出的三个子函数部分，共同构成了具有动态特征的问题本身，通过选取不同的漂移函数和目标函数相结合，可以得到多种的，具有不同特性的动态优化问题：

图1 SDDObench的问题实例概览

上表中的三个部分分别是目标函数（ $f$ ），变换函数（ $g$ ）以及漂移函数（ $\delta$ ）。其中控制各部分变化的相关参数都可以由用户自定义调节。

SDDObench定义细节

1、目标函数（ $f$ ）

目标函数选取了在DDEA（Data-driven Evolutionary Algorithm）评估中被广泛使用的几个函数（ $f_{DCF}$ ）以及在动态优化中最常用的移动多峰函数（ $f_{MPF}$ ）。

$f_{DCF}$ 选取的函数如下表所示：

图2 $f_{DCF}$的问题实例概览

其中初始时刻的问题适应度地形和对应的等高线图如下所示：

$f_{MPF}$ 的选取则考虑了易用性和可控性，因此选择了比较简单的形式：

$f_{MPF}(x)=\min _{i \in\{1, \ldots, m\}} \frac{h_i}{1+w_i\left\|x-c_i\right\|^2}$

其中， $m$ 代表峰的个数而 $d$ 则是问题的维度， $h_i$ ， $w_i$ 和 $c_i$ 分别表示第 $i$ 个峰在适应度地形上的的高度、宽度和位置。

2. 漂移函数（ $\delta$ ）

针对现实环境下的数据流特征，存在的概念漂移可以分为如下几类：1）突变型：变化程度较大的；2）渐变型：变化程度较低；3）周期性的：概念漂移存在周期出现的特性；

基于上述的原因，本文提出了五类漂移函数，囊括了上面所提到的漂移类别。

$D_1$ : No drift

$\delta(t)=0$

$D_2$ : Sudden drift

$\begin{aligned} & \delta(t)=\begin{cases} & rand(-1,1), \rm{if} \;t \in \varLambda \\ & \delta(t-1), \rm{otherwise} \end{cases} \end{aligned}$

其中， $\varLambda=\left\{t_1, t_2, \cdots, t_{|\Lambda|}\right\}$ 中的每个 $t_i \in rand(1, T)$ 表示对全部时间点进行随机采样的一批时间点。

$D_3$ : Recurrent Sudden drift

$\begin{aligned} & \delta(t)=\begin{cases} & -0.5, \; {\rm if} \; t \,\text{mod}\, P < 0.5P \\ & 0.5, \; {\rm otherwise} \end{cases} \end{aligned}$

其中， $P$ 表示循环的周期。

$D_4$ : Recurrent Incremental drift

$\delta(t)=cos(\frac{2\pi t}{P}+\frac{\pi}{2})$

$D_5$ : Recurrent Incremental drift with Noise

$\delta(t)=(1-\epsilon)\cdot cos(\frac{2\pi t}{P}+\frac{\pi}{2})+\epsilon \cdot rand(-1,1)$

其中 $\epsilon$ 代表一个小程度的随机噪声， $P$ 的定义和Eq. (5)中相同。

不同的漂移具有不同的特性，更直观的展示不同漂移函数之间的区别，如下图所示：

图4 五种不同的漂移函数变化图示

3. 变换函数（ $g$ ）

变换函数的作用是将动态的漂移性质通过平移、旋转变换作用到自变量上，从而使静态的基础目标函数具有动态变化的特性。变换函数的定义如下：

$g(\phi,\delta(t))=(\phi+\lambda \delta(t))\cdot \mathbf{R}^{(t)}$

其中， $\phi$ 表示被变换的相关变量，而 $\lambda$ 则表示缩放系数，定义如下：

$\lambda=\mathcal{I}_{\phi}\cdot(\phi_{max}-\phi_{min}) %\nonumber$

其中， $\phi_{\text{max}}$ 和 $\phi_{\text{min}}$ 分别表示变量 $\phi$ 的最大值和最小值，而 $\mathcal{I}_{\phi}$ 则表示待变换变量 $\phi$ 的变化剧烈程度。旋转矩阵 $\mathbf{R}^{(t)}$ 定义如下：

$\mathbf{R}_{l,l+1}=\begin{pmatrix} cos\theta^{(t)}&-sin\theta^{(t)}\\ sin\theta^{(t)}&cos\theta^{(t)}\\ \end{pmatrix} %\nonumber$

其中， $\theta^{(t)}=4\cdot arcsin(\delta(t)^2)$ .

总结来说，变换过程是先将相关变量通过 $\lambda \delta(t)$ 进行平移，接着再使用旋转矩阵 $\mathbf{R}^{(t)}$ 右乘从而得到随时间变化后的变量。

实验

评价指标

面对有多个环境的动态优化问题，在SDDObench中使用了常见的评价指标：

在线错误（ $E_{\rm{online}}$ ）：该指标计算当前时间点下的算法优化误差。

$\begin{equation} E_{\rm{online}}^{(t)}=f(x^{*(i,t)})-f(x^{\star(t)}) \end{equation}$

其中， $x^{*(i,t)}$ 表示在第t个时间点下算法所找到的最优解， $x^{\star(t)}$ 则表示t时间点下的全局最优解。

离线错误（ $E_{\rm{offline}}$ ）：该指标计算所有时间点以及进化的每一代的算法优化误差之和。

$\begin{equation} E_{\rm{offline}}=\frac{1}{TI}\sum_{t=1}^{T}\sum_{i=1}^{I}\left[f(x^{*((t-1)I+i)})-f(x^{\star(t)})\right] \end{equation}$

其中， $T$ 表示总的时间点数目，而 $x^{*((t-1)I+i)}$ 则表示在第t个环境的第i次优化迭代之后算法找到的最优解。

实验结果

使用了四个对比算法，如下所示：

部分实验结果如下所示：

总结

从实验结果来看，当前提出的针对动态环境下的数据驱动优化算法在SDDObench上的表现仍然存在局限性，针对这些局限性，我们对未来发展方向提出了几点建议：

有效的变化检测手段：当前提出的有关动态变化的算法并未能对未知变化的数据流进行检测，都是默认可以获得当前环境的所有数据，这个先验假设是不符合现实优化限制的。
合理的数据管理机制：对于源源不断到达的数据流，由于内存的限制和概念漂移现象的存在，需要对过时的旧数据进行抛弃，但同时需要保留关键的旧数据和新数据一起来辅助当前环境的优化。
新环境的热启动优化：对于一个新的环境，需要根据新旧环境之间的关联，来对新环境的优化进行热启动，从而能更加高效的解决当前环境的优化。