强度 Pareto 演化算法（SPEA）

名称

强度 Pareto 演化算法（Strength Pareto Evolution Algorithm, SPEA）

分类

查看分类思维导图

SPEA 是一种用于多目标优化的演化算法，隶属于演化计算领域，而演化计算又是计算智能的一个分支。该算法与其他多目标演化算法密切相关，例如非支配排序遗传算法（NSGA）和 Pareto 存档进化策略（PAES）。

• 计算智能
  • 演化计算
    • 演化算法
      • 多目标优化
        • 强度 Pareto 演化算法（SPEA）

策略

SPEA 维持两个种群：主种群和外部档案集。外部档案集用于存储当前已找到的非支配解。主种群中个体的适应度根据档案集中支配该个体的解的数量来计算。这种机制能够推动主种群逐步向 Pareto 前沿演化。

档案集的容量是固定的。当非支配解的数量超过档案容量时，算法会采用聚类技术对档案集进行压缩，同时尽可能保持解集的多样性。这使得档案集能够形成对 Pareto 前沿分布较均匀的近似表示。

在每一代中，主种群通过选择、交叉和变异产生子代。随后，将子代与档案集合并，并从合并后的种群中提取非支配解作为新的档案集。下一代主种群则通过二元锦标赛选择，从新的档案集中选取个体进行填充。

过程

数据结构：

• 种群（Population）：个体构成的主种群
• 档案集（Archive）：存储非支配解的外部档案集
• 个体（Individual）：表示一个解，包含决策变量和目标函数值

参数：

• 主种群规模（popSize）：主种群规模
• 档案规模（archiveSize）：档案集的最大容量
• 最大代数（maxGenerations）：最大迭代代数
• 交叉率（crossoverRate）：交叉操作的执行概率
• 变异率（mutationRate）：变异操作的执行概率

步骤：

1. 随机生成 popSize 个个体，初始化 Population
2. 评估 Population 中每个个体的目标函数值
3. 初始化一个空的 Archive
4. 对 Population 中的每个 Individual：

• 若 Individual 不被 Archive 中任何成员支配，则将其加入 Archive
• 删除 Archive 中所有被 Individual 支配的成员

5. 若 Archive 的大小超过 archiveSize，则使用聚类方法对 Archive 进行压缩
6. 根据 Archive 中支配每个个体的成员数量，为 Population 中每个 Individual 赋予适应度
7. 当终止条件未满足时（例如未达到 maxGenerations）：
   1. 使用二元锦标赛选择从 Population 中选取父代
   2. 以 crossoverRate 的概率对所选父代执行交叉，生成子代
   3. 以 mutationRate 的概率对子代执行变异
   4. 评估子代的目标函数值
   5. 将子代与 Archive 合并
   6. 通过删除被支配解并在必要时使用聚类压缩档案集，更新 Archive
   7. 使用二元锦标赛选择从 Archive 中选取 popSize 个个体，构成下一代 Population
8. 返回 Archive 作为 Pareto 前沿的近似解集

注意事项

优点：

• 通过外部档案集与聚类机制维持 Pareto 前沿近似解集的多样性
• 通过基于支配关系的适应度赋值机制推动种群向 Pareto 前沿收敛
• 能够处理具有多个目标和多个决策变量的复杂多目标优化问题

缺点：

• 用于压缩档案集的聚类技术计算代价较高，尤其是在高维目标空间中更为明显
• SPEA 的性能对参数选择较为敏感，例如种群规模、档案规模以及聚类相关参数
• 与其他演化算法类似，SPEA 往往需要较多次函数评估，才能收敛到较好的 Pareto 前沿近似

启发式建议

种群规模与档案规模

• 种群规模应足够大，以维持多样性，但又不宜过大，以免计算效率显著下降。常见取值范围为 50–200 个个体。
• 档案规模应在 Pareto 前沿近似质量与计算复杂度之间取得平衡。常用经验做法是将档案规模设为与种群规模相同。

交叉与变异

• 交叉率应足够高，以促进对搜索空间的探索，但也不宜过高，以免频繁破坏优良解。常见取值范围为 0.7–0.9。
• 变异率应足够低，以支持算法收敛；同时又应足够高，以维持多样性并避免早熟收敛。常见取值范围为 $1/n$ 到 $1/(2n)$，其中 $n$ 为决策变量个数。

聚类参数

• 用于压缩档案集的聚类方法应根据具体问题特性进行选择，例如目标数量和 Pareto 前沿形状。
• 聚类簇数应在多样性保持与聚类计算复杂度之间取得平衡。常见经验做法是将簇数设置为档案规模的十分之一。

终止准则

• 最大迭代代数应设置得足够大，以支持算法收敛，但又不宜过大，以免浪费计算资源。常见范围为 100–1000 代。
• 还可引入附加终止准则，例如 Pareto 前沿近似的改进速率；当算法已基本收敛时，可据此提前停止。