稳态遗传算法（SSGA）

名称

稳态遗传算法（Steady-State Genetic Algorithm, SSGA）

分类

查看分类思维导图

稳态遗传算法是标准遗传算法的一种变体，隶属于演化计算领域，而演化计算又是计算智能的一个分支。

• 计算智能
  • 演化计算
    • 演化算法
      • 遗传算法
        • 稳态遗传算法

策略

稳态遗传算法与标准遗传算法的主要区别在于其种群管理策略。标准遗传算法通常在每一代中整体更新种群，而 SSGA 在每次迭代中仅选择少量个体（通常为 1 个或 2 个）进行替换。

选择与替换

SSGA 通常采用锦标赛选择方法来选取用于繁殖的父代个体。在通过交叉和变异生成子代之后，算法再从当前种群中选出少量个体，由新生成的子代进行替换。替换策略可以基于适应度、年龄或其他准则进行设计。

遗传多样性的保持

由于每一代仅替换少量个体，SSGA 相比标准遗传算法能够维持更为稳定的种群结构，而后者通常是在每一代中整体替换整个种群。这种渐进式更新方式有助于保持遗传多样性，并能够在一定程度上降低算法过早收敛到次优解的风险。

稳态演化

SSGA 的增量式替换策略模拟了自然界中的稳态演化过程，即种群随时间逐步演化，而非突变式整体更新。这种方式使得优化过程具有更强的连续性，因为种群始终在通过新子代不断进行局部更新。

过程

数据结构：

• 种群：由若干个体构成的列表，每个个体表示问题的一个潜在候选解。
• 个体：一个单独的解，通常编码为位串、整数串或其他表示形式。

参数：

• 种群规模：种群中的个体数量。
• 替换率：每一代中需要被替换的个体数量。
• 交叉率：对选中父代施加交叉操作的概率。
• 变异率：对子代施加变异操作的概率。

1. 随机生成个体，初始化种群。
2. 评估种群中每个个体的适应度。
3. 重复以下过程，直到满足终止准则（如达到最大迭代代数或达到足够高的适应度水平）：
   1. 采用锦标赛选择方法选择父代个体进行繁殖。
   2. 以交叉率为概率，对选中的父代施加交叉操作以生成子代。
   3. 以变异率为概率，对子代施加变异操作。
   4. 评估新生成子代的适应度。
   5. 根据替换策略（如最低适应度替换或最老个体替换）从当前种群中选出待替换个体。
   6. 用新生成的子代替换所选个体。
4. 返回优化过程中找到的最优个体。

注意事项

优点：

• 能够较好地维持遗传多样性，从而降低早熟收敛风险。
• 种群持续被局部更新，因此优化过程更具连续性。
• 在达到满意解所需的适应度评估次数方面，可能比标准遗传算法更高效。

缺点：

• 相比标准遗传算法，增量式替换策略可能导致收敛速度较慢。
• 算法性能对替换策略及替换率的设定较为敏感。
• 为获得较优性能，相比标准遗传算法可能需要更加细致的参数调节。

启发式建议

种群规模

• 应选择能够在多样性保持与计算效率之间取得平衡的种群规模。
• 较大的种群有助于探索更广泛的搜索空间，但通常需要更多适应度评估。
• 较小的种群虽然可能收敛更快，但也更容易陷入次优解。

替换率

• 较低的替换率（如每代替换 1 个或 2 个个体）有助于维持种群稳定性和多样性。
• 较高的替换率可能加快收敛，但也可能削弱多样性并增加早熟收敛风险。

选择方法

• 锦标赛选择因其实现简单且效果稳定，在 SSGA 中被广泛采用。
• 锦标赛规模应合理设定，以在选择压力与多样性保持之间取得平衡。

交叉率与变异率

• 交叉率通常应设置得较高（如 0.8 至 0.95），以促进父代之间的遗传信息交换。
• 变异率通常应保持较低（如 0.01 至 0.1），以在不显著破坏优良解的前提下引入小幅扰动。
• 应结合具体问题及解的表示方式，通过实验比较不同参数组合，以获得更合适的设置。

替换策略

• 基于适应度的替换策略，即优先替换适应度最低的个体，有助于推动种群向更优解方向演化。
• 基于年龄的替换策略，即优先替换存在时间最长的个体，有助于移除停滞解并维持种群多样性。
• 将适应度与年龄相结合的替换策略，通常能够在开发与探索之间取得较好的平衡。