自适应进化策略（SA-ES）

名称

自适应进化策略（Self-Adaptive Evolution Strategy, SA-ES），也可简称为进化策略（Evolution Strategy, ES）。

分类

查看分类思维导图

自适应进化策略是一种受生物进化启发的优化算法，属于进化计算（Evolutionary Computation）领域，而进化计算又是计算智能（Computational Intelligence）的一个子领域。它与其他进化策略和进化算法密切相关，例如 $(\mu/\rho +, \lambda)$-ES、CMA-ES 以及进化规划（Evolutionary Programming）。

• 计算智能
  • 生物启发计算
    • 进化计算
      • 进化算法
        • 进化策略
          • 自适应进化策略

策略

自适应进化策略运用生物进化的基本原理，对给定优化问题中的候选解种群进行迭代改进。算法维持一个由多个个体构成的种群，其中每个个体代表问题的一个潜在解。这些个体通常编码为实值向量，常被称为基因型（genotype）或染色体（chromosome）。

变异与重组

在算法的每一次迭代（世代）中，个体通过变异与重组操作产生子代。变异通过对个体的遗传信息施加随机扰动来实现，从而增强对搜索空间的探索能力；而重组则通过整合多个父代的遗传信息来生成新的子代，以促进对潜在优良解区域的开发。

策略参数的自适应

自适应进化策略的一个关键特征在于策略参数（如变异步长）的自适应机制。每个个体不仅携带目标变量（即问题解的编码），同时也携带相应的策略参数。这些策略参数与目标变量一起参与变异和重组，使算法能够在优化过程中动态调整自身的搜索行为。

选择与替换

在子代生成之后，算法通过选择机制决定哪些个体能够存活到下一代。自适应进化策略通常采用 $(\mu, \lambda)$ 或 $(\mu + \lambda)$ 选择方案，其中 $\mu$ 表示父代数量，$\lambda$ 表示子代数量。在 $(\mu, \lambda)$ 方案中，由表现最优的 $\mu$ 个子代替换父代；而在 $(\mu + \lambda)$ 方案中，则从父代与子代构成的联合种群中选出最优的 $\mu$ 个个体进入下一代。

终止

变异、重组与选择过程不断迭代进行，直至满足某一终止准则。常见的终止条件包括达到最大代数、获得满意的适应度水平，或观察到种群已表现出收敛特征。

过程

1. 初始化种群
   1. 设定种群规模 $\mu$ 与子代数量 $\lambda$
   2. 随机初始化 $\mu$ 个个体，每个个体同时包含目标变量和策略参数
2. 当未满足终止准则时，重复执行：
   1. 重组
      1. 从种群中选择 $\rho$ 个父代
      2. 对所选父代的目标变量和策略参数执行重组，生成 $\lambda$ 个子代
   2. 变异
      1. 对每个子代的策略参数进行变异
      2. 利用变异后的策略参数对每个子代的目标变量进行变异
   3. 评估
      1. 计算每个子代的适应度
   4. 选择
      1. 从子代中选出最优的 $\mu$ 个个体（对应 $(\mu, \lambda)$ 选择），或从父代与子代的联合种群中选出最优的 $\mu$ 个个体（对应 $(\mu + \lambda)$ 选择）
      2. 用选出的个体替换父代种群
3. 返回搜索过程中找到的最优个体

数据结构

• 个体：表示一个候选解，由目标变量和策略参数构成
• 种群：由多个个体组成的集合

参数

• $\mu$：种群中父代个体的数量
• $\lambda$：每一代生成的子代数量
• $\rho$：参与重组的父代数量
• 变异强度：控制施加于目标变量和策略参数上的变异幅度
• 重组类型：定义父代个体重组方式的方法（如离散重组、中间重组）

注意事项

优点

• 策略参数的自适应机制使算法能够在优化过程中自动调整搜索行为
• 在求解连续优化问题时表现有效
• 对局部最优具有一定鲁棒性，能够跳出次优搜索区域

缺点

• 算法性能可能对初始策略参数的选择较为敏感
• 与某些其他优化方法相比，通常需要较多的适应度评估次数
• 自适应机制会增加算法结构与实现上的复杂性

启发式建议

种群规模

• 种群规模 $\mu$ 应足够大，以维持多样性，但也不宜过大，以免影响收敛速度
• 一个常见经验是令 $\mu$ 与问题维度成比例，例如 $\mu = 4 + \lfloor 3\ln(n) \rfloor$，其中 $n$ 表示目标变量的个数

子代规模

• 子代数量 $\lambda$ 通常设置为大于种群规模 $\mu$
• 一个常见建议是取 $\lambda = 7\mu$

选择方案

• $(\mu, \lambda)$ 选择方案通常更适用于追求较快收敛的情形
• 对于适应度景观动态变化的问题，或希望增强探索能力的场景，可采用 $(\mu + \lambda)$ 选择方案

变异强度

• 初始变异强度应依据目标变量的预期取值范围进行设置
• 可将变异强度初始化为搜索空间范围的一定比例，例如变量取值范围的 $1/10$
• 在优化过程中，应允许变异强度随搜索进展进行自适应调整

重组

• 对目标变量和策略参数，通常都可采用中间重组
• 参与重组的父代数量 $\rho$ 通常设置为 2

终止准则

• 可根据可用计算预算设定最大代数
• 可监测最优适应度值的变化，若在预设代数内未观察到显著改进，则停止算法
• 还可通过衡量个体多样性来判断种群是否收敛，例如利用适应度值的标准差作为判据