随机启发式搜索

前置知识

漂移指的是随机过程中的期望变化率。漂移分析是一种用于分析随机算法性能的工具，特别是在优化算法中。它通过研究算法在每一步的期望变化来推断算法的收敛速度和性能。

加性漂移指的是在每一步中，我们都有

\mathbb{E}(X_{t+1} - X_t| T > t) \geq \delta

其中 $X_t$ 表示算法在第 $t$ 步的状态， $T$ 是算法达到目标状态的时间， $\delta>0$ 是一个常数。

加性漂移有一个性质：

\mathbb{E}(T|X_0) \leq \frac{X_0}{\delta}

乘性漂移指的是在每一步中，我们都有

\mathbb{E}(X_{t+1} - X_t | X_t) \geq \delta X_t

其中 $\delta>0$ 是一个常数。

乘性漂移有一个性质：

\mathbb{E}(T|X_0) \leq \frac{1}{\delta} \left(1 + \ln \left( \frac{X_0}{x_{\min}} \right)\right)

乘性漂移的好处在于我们可以更加自然地使用势能函数。我们在分析一个优化算法的过程中，尤其是离散进化算法，我们通常会定义一个势能函数来衡量当前解与最优解之间的距离。乘性漂移允许我们直接分析这个势能函数的期望变化，从而推断算法的收敛速度。