扩展紧凑遗传算法（ECGA）

名称

扩展紧凑遗传算法（Extended Compact Genetic Algorithm, eCGA）

分类

查看分类思维导图

扩展紧凑遗传算法是一种基于概率模型构建的遗传算法，属于进化计算（Evolutionary Computation）领域，而进化计算又是计算智能（Computational Intelligence）的重要分支。它与紧凑遗传算法（cGA）和贝叶斯优化算法（BOA）关系密切。

• 计算智能
  • 进化计算
    • 进化算法
      • 遗传算法
        • 概率模型构建遗传算法
          • 扩展紧凑遗传算法（eCGA）

策略

扩展紧凑遗传算法是一种通过识别并利用问题结构来高效求解优化问题的概率模型构建遗传算法。该算法维护一个关于优良解的概率模型，并利用该模型生成新的候选解。

概率建模

eCGA 将种群表示为搜索空间上的一个概率分布。该概率模型能够刻画问题变量之间的依赖关系，从而使算法可以利用问题的内在结构，生成高质量解。

模型构建与采样

在每一代中，eCGA 基于一组被选出的优良解构建概率模型。该模型通常采用边缘乘积分布模型（marginal product model），即假设问题变量可以划分为若干子集，而每个子集服从各自独立的概率分布。随后，算法根据该模型采样生成新的候选解。

选择与模型更新

在对采样得到的候选解完成适应度评估后，eCGA 根据适应度值选择其中最有前景的个体。再利用这些被选中的个体更新概率模型，以进一步修正下一代的搜索方向。

流程

数据结构：

• 概率模型：用于表示搜索空间上概率分布的数据结构，通常采用边缘乘积分布模型。
• 种群：候选解的集合。

参数：

• 种群规模：每一代中维护的候选解数量。
• 选择压力：用于模型构建与更新的被选个体占种群的比例。
• 学习率：概率模型根据所选个体进行更新时的调整速率。

1. 初始化概率模型
   1.1 为每个问题变量设置初始概率
2. 从概率模型中采样生成初始种群
3. 计算种群中每个候选解的适应度值
4. 当终止条件未满足时，重复以下过程：
   4.1 根据适应度值从种群中选择一组有前景的个体
   4.2 基于被选个体构建新的概率模型
   4.3 从更新后的概率模型中采样生成新种群
   4.4 计算新种群中每个候选解的适应度值
   4.5 用新种群替换旧种群
5. 返回搜索过程中找到的最优解

注意事项

优点：

• 能够通过刻画变量之间的依赖关系来利用问题结构
• 相较于传统遗传算法，通常需要更少的函数评估次数
• 适用于搜索空间较大且变量交互关系复杂的问题

缺点：

• 算法性能依赖于概率模型的选择
• 构建概率模型可能带来较高的计算开销
• 若模型表达能力不足，可能会过早收敛到次优解

启发式建议

种群规模

• 初始种群规模可设置为不少于问题规模（变量个数）的 10 倍
• 对于变量交互复杂或搜索空间较大的问题，可适当增大种群规模

选择压力

• 可采用中等强度的选择压力（如选择 50% 的种群）以平衡探索与开发
• 较高的选择压力有助于加快收敛，但也可能增加早熟收敛到次优解的风险

学习率

• 学习率宜设为较小值（如 0.1），以避免概率模型发生过于剧烈的变化
• 可随着迭代进行逐步提高学习率，以更精细地调整搜索方向

概率模型

• 默认可采用边缘乘积分布模型作为概率模型
• 对于变量交互关系更复杂的问题，可考虑采用表达能力更强的模型，如贝叶斯网络
• 应根据问题规模及可用计算资源自适应调整模型复杂度

终止条件

• 可依据可用计算预算设置最大迭代代数或最大适应度评估次数
• 当最优解的适应度在连续若干代内不再提升时，可终止算法
• 也可结合具体问题设置专门的终止条件，例如达到目标适应度值或满足预期解质量