博客
DREAM 算法的候选点生成与接受机制

DREAM 算法的候选点生成与接受机制

June 13, 2019

DREAM 算法巧妙地融合了进化计算中的差分进化策略和 MCMC 方法的理论基础，形成了一个强大而灵活的采样框架。我们将从四个方面详细分析这些机制：差分进化策略在候选点生成中的应用、Metropolis 接受准则的使用、候选点生成的数学描述，以及接受机制如何在探索和利用之间取得平衡。通过这些分析，我们将揭示 DREAM 算法如何在保持理论正确性的同时，显著提高了采样效率和适应性。

候选点生成

DREAM 算法的候选点生成过程是其核心创新之一，融合了差分进化、子空间采样和随机扰动等多个元素。这个过程不仅提高了采样效率，还增强了算法对复杂参数空间的适应能力。

差分进化的应用

差分进化策略是DREAM算法候选点生成过程中的关键组成部分。这一策略源自于进化算法领域，但在DREAM中被巧妙地应用于概率分布采样。差分进化的核心思想是利用种群中个体之间的差异来指导搜索，这在DREAM算法中表现为利用多条马尔可夫链之间的信息差异来生成新的候选点。

具体来说，DREAM 算法在每次生成新候选点时，会随机选择几对不同的链，计算它们之间的差值。这个过程可以表示为：

$$\Delta x = \sum_{j=1}^{\delta} (x_{r1(j)}^t - x_{r2(j)}^t)$$

其中，$\delta$ 通常为 $2$ 或 $3$，$r1(j)$ 和 $r2(j)$ 是随机选择的链索引。

这种差分操作的重要性在于它能够自适应地捕捉参数空间的局部结构和参数间的相关性。在参数空间的不同区域，链之间的差异会反映出该区域的特征尺度和主要变化方向。例如，在参数空间的平坦区域，链之间的差异可能较小，生成的候选点会倾向于进行小幅探索；而在参数空间的陡峭区域，链之间的差异可能较大，从而允许算法进行更大范围的搜索。

这种自适应性是 DREAM 算法强大功能的关键所在。它使得算法能够在不同的参数空间区域自动调整其行为，既能在复杂的多模态分布中进行全局探索，又能在高概率密度区域进行精细搜索。

子空间采样与随机扰动

在差分进化的基础上，DREAM 算法引入了子空间采样和随机扰动，进一步增强了其在高维空间中的性能。

子空间采样的核心思想是在每次迭代中只更新参数向量的一个子集，而不是所有维度。这可以通过一个二元向量 $z \in {0, 1}^d$ 来实现，其中每个元素以概率 $CR$（交叉概率）为 $1$，以概率 $1-CR$ 为 $0$。数学上，这个过程可以表示为：

$$x_i^* = x_i^t + z \odot (\Delta x’ + \epsilon)$$

其中 $\odot$ 表示元素 wise 乘法，$\Delta x’$ 是经过缩放和扰动的差分向量，$\epsilon$ 是一个小的高斯噪声向量，用于增加探索能力。这样，当 $z$ 为 $1$ 时，该维度的值更新；反之，该维度的值保持不变。

子空间采样策略的引入有几个重要的意义：

  1. 提高高维问题的采样效率：在高维空间中，全维度更新往往会导致低接受率，而子空间采样允许算法在保持较高接受率的同时进行有效探索。

  2. 增加算法的灵活性：通过调整交叉概率 $CR$，可以控制每次更新的维度数量，从而在全局探索和局部精细化之间取得平衡。

  3. 处理参数间的条件依赖：在某些问题中，参数之间可能存在复杂的条件依赖关系。子空间采样允许算法在固定某些参数的情况下探索其他参数，有助于捕捉这些复杂的依赖结构。

随机扰动的引入则进一步增强了算法的鲁棒性和探索能力。这包括对差分向量的小幅随机调整和添加高斯噪声。这些扰动机制有助于算法跳出局部最优，探索更广阔的参数空间。

DREAM 算法的候选点生成过程融合了差分进化、子空间采样和随机扰动等多个创新元素。这个过程可以分为以下几个关键步骤：

  1. 差分进化操作： 算法维护多条并行的马尔可夫链，每次生成新候选点时，会随机选择几对不同的链，计算它们之间的差值。这个步骤的目的是捕捉参数空间中的分布特征和参数间的相关性。通过利用多条链之间的信息，算法能够更好地适应目标分布的形状和尺度。

  2. 缩放和扰动： 计算得到的差分向量会被进行缩放和扰动。缩放因子的选择基于理论分析，旨在达到最优的接受率。同时，引入小的随机扰动，增加了算法的探索能力。这个步骤使得算法能够自适应地调整提议步长，在不同的参数空间区域采用不同的搜索策略。

  3. 子空间采样： DREAM 算法引入了子空间采样策略，即每次迭代只更新部分维度的参数。这个机制通过一个随机生成的二元向量来实现，该向量决定了哪些维度会被更新。子空间采样大大提高了算法在高维空间中的效率，因为它允许算法在保持高接受率的同时，进行更大幅度的参数调整。

  4. 候选点生成： 最后，通过将差分向量、扰动和子空间采样的结果结合，生成新的候选点。这个过程还包括添加一个小的高斯噪声，进一步增强算法的探索能力。

这种候选点生成机制的设计旨在平衡全局探索和局部精细化。差分进化操作提供了自适应的步长调整，子空间采样提高了在高维空间中的效率，而随机扰动和噪声则增强了算法的鲁棒性和探索能力。

数学描述

为了更深入地理解 DREAM 算法中候选点生成的过程，我们需要对其进行详细的数学描述。这个过程综合了差分进化、子空间采样和随机扰动等多个元素，形成了一个独特而高效的采样机制。

设 $X^t = {x_1^t, x_2^t, …, x_N^t}$ 表示在第 $t$ 次迭代中 $N$ 条马尔可夫链的状态集合，其中每个 $x_i^t$ 是一个 $d$ 维向量。对于第 $i$ 条链，新的候选点 $x_i^*$ 的生成过程可以分为以下几个步骤：

  1. 差分进化操作： 首先，随机选择 $\delta$ 对不同的链（通常 $\delta = 2$ 或 $3$），计算它们之间的差值： $$\Delta x = \sum_{j=1}^{\delta} (x_{r1(j)}^t - x_{r2(j)}^t)$$ 其中 $r1(j)$ 和 $r2(j)$ 是除 $i$ 之外随机选择的链索引。

  2. 缩放和扰动： 对差分向量进行缩放和扰动： $$\Delta x’ = (1_d + e) \gamma(\delta, d) \Delta x$$ 其中 $\gamma(\delta, d) = 2.38 / \sqrt{2\delta d}$ 是缩放因子，$e$ 是一个小的随机扰动向量，其元素服从均匀分布 $U(-b, b)$，$b$ 通常很小（如0.0001）。

  3. 子空间采样： 引入一个二元向量 $z \in {0, 1}^d$，其中每个元素以概率 $CR$（交叉概率）为 $1$，以概率 $1-CR$ 为 $0$。同时，为确保至少一个维度被更新，随机选择一个维度 $j$ 并将 $z_j$ 设为 $1$。

  4. 候选点生成： 最后，候选点 $x_i^*$ 通过以下方式生成： $$x_i^* = x_i^t + z \odot (\Delta x’ + \epsilon)$$ 其中 $\odot$ 表示元素 wise 乘法，$\epsilon$ 是一个小的高斯噪声向量，用于增加探索能力。

这个数学描述展示了 DREAM 算法如何综合利用多个创新元素来生成候选点。差分进化操作捕捉了参数间的相关性和尺度信息，缩放因子 $\gamma$ 根据问题维度自动调整步长，子空间采样策略允许算法在不同维度上采用不同的更新策略，而随机扰动和噪声则增加了算法的鲁棒性和探索能力。

接受机制如何平衡探索和利用

DREAM算法的接受机制，基于Metropolis准则，在算法的探索（exploration）和利用（exploitation）之间扮演着关键的平衡角色。这种平衡对于算法在复杂的参数空间中有效搜索至关重要。

  1. 自适应步长调整：DREAM的候选点生成机制中，步长（通过差分向量的缩放）是自适应的。在参数空间的平坦区域，大的步长促进了广泛探索；而在高概率密度区域，小的步长则有利于精细搜索。Metropolis准则通过接受或拒绝这些不同尺度的移动，实现了探索和利用之间的自动平衡。

  2. 概率性接受：Metropolis 准则的一个关键特性是它允许接受一些导致目标函数值降低的移动。这种"向下"移动的可能性使得算法能够跳出局部最优，探索更广阔的参数空间。同时，由于接受概率与目标函数值的比值成正比，算法仍然倾向于移向更高概率的区域，从而实现了探索和利用之间的平衡。

  3. 多链协同：DREAM 算法维护多条并行的马尔可夫链，这不仅提高了采样效率，也为探索和利用的平衡提供了新的维度。不同的链可能处于参数空间的不同区域，通过差分进化操作，信息可以在链之间传播。这种机制使得算法能够同时在多个区域进行探索和精细化搜索。

  4. 子空间更新的影响：子空间采样策略允许算法在每次迭代中只更新部分维度。这种方法在保持高接受率的同时，也为算法提供了在不同尺度上探索参数空间的能力。大范围的更新有利于探索，而小范围的更新则有利于局部精细化。

通过这些机制，DREAM 算法能够在全局探索和局部精细化之间取得平衡，既能有效地搜索整个参数空间，又能在高概率区域进行深入探索。这种平衡是算法在处理复杂、高维问题时表现出色的关键所在。

结论

DREAM 算法通过巧妙地融合差分进化策略和 MCMC 方法，在候选点生成和接受机制上实现了创新。这些创新不仅提高了算法在复杂参数空间中的采样效率，还增强了其适应不同问题特征的能力。差分进化策略的引入使得算法能够自适应地调整采样行为，而 Metropolis 准则的使用则确保了算法的理论正确性。候选点生成过程的精心设计和接受机制的巧妙平衡，使 DREAM 算法成为处理高维、复杂概率分布的强大工具。

参考文献

  1. Vrugt, J. A., Ter Braak, C. J. F., Diks, C. G. H., Robinson, B. A., Hyman, J. M., & Higdon, D. (2009). Accelerating Markov chain Monte Carlo simulation by differential evolution with self-adaptive randomized subspace sampling. International Journal of Nonlinear Sciences and Numerical Simulation, 10(3), 273-290.

  2. Storn, R., & Price, K. (1997). Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), 341-359.

  3. Roberts, G. O., Gelman, A., & Gilks, W. R. (1997). Weak convergence and optimal scaling of random walk Metropolis algorithms. The Annals of Applied Probability, 7(1), 110-120.

  4. Ter Braak, C. J. F., & Vrugt, J. A. (2008). Differential Evolution Markov Chain with snooker updater and fewer chains. Statistics and Computing, 18(4), 435-446.

  5. Laloy, E., & Vrugt, J. A. (2012). High‐dimensional posterior exploration of hydrologic models using multiple‐try DREAM(ZS) and high‐performance computing. Water Resources Research, 48(1).

  6. Vrugt, J. A. (2016). Markov chain Monte Carlo simulation using the DREAM software package: Theory, concepts, and MATLAB implementation. Environmental Modelling & Software, 75, 273-316.

  7. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6), 1087-1092.

  8. Andrieu, C., & Thoms, J. (2008). A tutorial on adaptive MCMC. Statistics and Computing, 18(4), 343-373.

  9. Gelman, A., & Rubin, D. B. (1992). Inference from iterative simulation using multiple sequences. Statistical Science, 7(4), 457-472.

  10. Haario, H., Saksman, E., & Tamminen, J. (2001). An adaptive Metropolis algorithm. Bernoulli, 7(2), 223-242.

  11. Brooks, S. P., & Gelman, A. (1998). General methods for monitoring convergence of iterative simulations. Journal of Computational and Graphical Statistics, 7(4), 434-455.

  12. Vrugt, J. A., & Ter Braak, C. J. F. (2011). DREAM(D): an adaptive Markov Chain Monte Carlo simulation algorithm to solve discrete, noncontinuous, and combinatorial posterior parameter estimation problems. Hydrology and Earth System Sciences, 15(12), 3701-3713.

  13. Sadegh, M., & Vrugt, J. A. (2014). Bridging the gap between GLUE and formal statistical approaches: approximate Bayesian computation. Hydrology and Earth System Sciences, 18(12), 4239-4264.

  14. Roberts, G. O., & Rosenthal, J. S. (2001). Optimal scaling for various Metropolis-Hastings algorithms. Statistical Science, 16(4), 351-367.

  15. Ter Braak, C. J. F. (2006). A Markov Chain Monte Carlo version of the genetic algorithm Differential Evolution: easy Bayesian computing for real parameter spaces. Statistics and Computing, 16(3), 239-249.

DREAM 算法的核心组件：子空间采样与交叉概率DREAM 算法的自适应机制：CR 概率更新与离群链校正