随机启发式搜索

前置知识

漂移分析（Drift Analysis）

定义

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

加性漂移

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

\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)

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

随机搜索启发式概述

随机搜索启发式（Randomised Search Heuristics, RSH）是一类不依赖问题具体结构的通用优化算法。它们通过随机操作在搜索空间中进行迭代探索，并利用适应度函数（fitness function）来引导搜索方向。典型的 RSH 包括：

进化算法（Evolutionary Algorithms, EA）
遗传规划（Genetic Programming, GP）
模拟退火（Simulated Annealing）
蚁群优化（Ant Colony Optimization）
估计分布算法（Estimation of Distribution Algorithms）

这些算法的共同特征是：

把候选解编码为某种数据结构（如二进制串、排列、语法树等）。
通过随机变异（mutation）、重组（crossover）等算子产生新解。
根据适应度进行选择，保留较优解。
重复上述过程直到满足终止条件。

RSH 常用于黑箱优化、组合优化以及理论计算机科学中的运行时间分析。

EA算法

(1+1) EA 的基本框架

最简单的进化算法之一是 (1+1) EA，它只维护一个父代个体，并通过逐代变异来寻找更优解。以二进制优化问题为例：

算法 1: (1+1) EA

随机初始化 $x \in \{0,1\}^n$ 。
重复以下步骤：
- 生成子代 $y$ ：对 $x$ 的每一位，以概率 $1/n$ 独立翻转。
- 若 $f(y) \geq f(x)$ ，则令 $x \leftarrow y$ 。
直到达到停止条件。

这里使用的变异算子称为 标准位变异（standard bit mutation）。每一位被翻转的期望次数为 1，因此子代与父代的平均汉明距离约为 1。这种“小步长”的变异方式保证了局部开发与全局探索之间的平衡。

常见的选择机制

在更复杂的 EA 中，通常会维护一个种群（population），并采用不同的选择策略：

$(\mu+\lambda)$ 选择：从 $\mu$ 个父代和 $\lambda$ 个子代中选出最好的 $\mu$ 个个体。
$(\mu,\lambda)$ 选择：只从 $\lambda$ 个子代中选出最好的 $\mu$ 个个体。
锦标赛选择（Tournament Selection）：随机抽取若干个体，取其中最优者。

经典测试问题

ONEMAX

ONEMAX 函数计算二进制串中 1 的个数：

\text{ONEMAX}(x) = \sum_{i=1}^{n} x_i

对于 (1+1) EA，使用乘性漂移可以证明其期望优化时间为 $O(n \log n)$ 。直观上，当前串中 0 的个数每步以与自身成比例的概率减少，因此越接近最优解，收敛越慢，最终得到对数因子。

LEADINGONES

LEADINGONES 函数计算二进制串前导 1 的个数：

\text{LEADINGONES}(x) = \max\{k \mid x_1 = x_2 = \cdots = x_k = 1\}

(1+1) EA 在 LEADINGONES 上的期望运行时间为 $\Theta(n^2)$ 。原因在于一旦前导 1 的个数增加，就必须保持前面的位不变，而翻转第 $k+1$ 位的概率约为 $1/n$ 。

运行时间分析示例

下面用乘性漂移定理给出 (1+1) EA 在 ONEMAX 上的上界。

设势函数 $X_t$ 为第 $t$ 步时当前解中 0 的个数。若 $X_t = k > 0$ ，则下一步至少减少一个 0 的概率至少为

\frac{k}{n}\left(1 - \frac{1}{n}\right)^{n-1} \approx \frac{k}{en}

因此

\mathbb{E}[X_t - X_{t+1} \mid X_t = k] \geq \frac{k}{en}

由乘性漂移定理，取 $\delta = 1/(en)$ ，得到

\mathbb{E}[T] \leq en(1 + \ln n) = O(n \log n)

GP算法

遗传规划（Genetic Programming, GP）是一种让计算机自动生成程序或数学表达式的进化算法。与传统的 EA 把解编码为固定长度的二进制串不同，GP 通常把个体编码为语法树（syntax tree），其中内部节点是函数（如 $+, -, \times, \div, \sin$ ），叶节点是变量或常量。

基本流程

初始化：随机生成一组语法树，常用方法包括 grow、full 和 ramped half-and-half。
评估：根据适应度函数评估每棵树的性能。
选择：选择适应度较高的个体作为父代。
遗传操作：
- 交叉（Crossover）：随机选择两个父代的子树并交换。
- 变异（Mutation）：随机替换某个子树为一棵新生成的小树。
替换：用新生成的个体更新种群。
重复 2–5 步直到满足终止条件。

交叉示例

设父代 $A$ 的表达式为 $(x + y) \times z$ ，父代 $B$ 为 $x - (y \times z)$ 。若随机选中 $A$ 的子树 $(x + y)$ 和 $B$ 的子树 $(y \times z)$ ，交换后得到：

子代 $A'$ ： $(y \times z) \times z$
子代 $B'$ ： $x - (x + y)$

这种基于树的表示使 GP 能够处理变长、结构复杂的解。

膨胀问题（Bloat）

在实践中，GP 经常会出现膨胀现象：个体的语法树变得越来越庞大，但适应度并没有明显提升。这会导致搜索效率下降、过拟合以及解释性变差。常见的控制方法包括：

树深度限制：限制个体的最大深度。
** parsimony pressure**：在适应度中惩罚树的复杂度。
子树删除变异：随机删除子树以简化个体。

理论研究方向

GP 的理论分析相对困难，近年来主要关注：

运行时间分析：利用漂移定理分析 GP 在简单问题上的收敛速度。
泛化界：研究训练集上表现良好的 GP 个体在未知数据上的泛化能力。
语义遗传规划：通过考虑子树的语义信息来设计更有效的交叉和变异算子。

漂移分析的进一步工具

除了前面提到的加性漂移和乘性漂移，还有更一般的工具：

可变漂移（Variable Drift）

设势函数 $X_t > 0$ ，若存在单调递增函数 $h: \mathbb{R}^+ \to \mathbb{R}^+$ ，使得

\mathbb{E}[X_t - X_{t+1} \mid X_t] \geq h(X_t)

则期望 hitting time 满足

\mathbb{E}[T] \leq \frac{1}{h(1)} + \int_{1}^{X_0} \frac{1}{h(x)} \, dx

可变漂移统一了加性漂移和乘性漂移，是分析复杂 RSH 的有力工具。

负漂移（Negative Drift）

当算法远离最优解时，如果势函数期望变化为正（即倾向于远离），则称发生负漂移。负漂移定理可用于证明某些问题难以在多项式时间内被简单 EA 优化。

总结

随机搜索启发式为黑箱优化提供了一套通用且强大的框架。理解它们的关键在于：

选择合适的问题编码和遗传算子。
利用漂移分析等工具对期望运行时间进行理论刻画。
在实践中注意种群多样性与选择压力之间的平衡，以及 GP 中的膨胀问题。

对于进一步的学习，推荐阅读 Jansen 的 Analysing Evolutionary Algorithms 以及 Oliveto、Witt 等关于 EA/GP 运行时间分析的经典论文。