DE/best/1/z

名称

DE/best/1/z，带可选外部档案的差分进化“best/1”变体。

分类

查看分类思维导图

DE/best/1/z 是差分进化（Differential Evolution, DE）算法的一种变体。差分进化属于进化计算领域，而进化计算又是计算智能的一个分支。DE 与其他进化算法（如遗传算法和进化策略）具有密切关联。

• 计算智能
  • 仿生计算
    • 进化计算
      • 进化算法
        • 差分进化（DE）
          • DE/best/1/z

策略

DE/best/1/z 遵循差分进化的一般思想，即通过维护一个候选解种群，并借助变异、交叉和选择过程不断推进种群演化。其关键特征在于变异策略采用当前种群中的最优个体作为基向量。

变异

在变异步骤中，DE/best/1/z 通过将当前种群最优个体与两个随机选取个体之间的加权差分相加，生成变异向量。这种机制能够引导搜索朝向搜索空间中更具潜力的区域。

交叉

在变异之后，算法对变异向量与种群中的对应目标向量执行交叉操作。该过程有助于引入多样性，并促进不同解之间的信息交换。DE/best/1/z 采用二项式交叉，即子代向量的每一个维度都依据交叉概率，从变异向量或目标向量中继承对应分量。

选择

选择步骤用于决定新生成的子代向量是否替换种群中的目标向量。DE/best/1/z 采用贪婪选择策略，即仅当子代向量的适应度优于目标向量时，才进行替换。

外部档案（z）

DE/best/1/z 引入了一个可选外部档案，“z”即表示这一机制。该档案用于存储搜索过程中发现的优良解。这些档案解可用于辅助变异过程，从而增强算法的开发能力，使搜索更加偏向于利用已有优良区域。

过程

数据结构

• 种群：由候选解构成的数组，其中每个解均表示为一个实值参数向量。
• 档案（可选）：用于存储搜索过程中已发现优良解的独立数组。

参数

• 种群规模（NP）：种群中候选解的数量。
• 交叉概率（CR）：交叉过程中子代从变异向量继承某一维度的概率。
• 缩放因子（F）：作用于差分向量的权重系数。
• 最大迭代代数（G_max）：算法终止前允许执行的最大代数。

伪代码

1. 随机生成 NP 个候选解，初始化种群。
2. 计算种群中每个候选解的适应度值。
3. 当未满足终止条件时（如未达到最大迭代代数）：
   1. 对种群中的每个候选解（目标向量）：
      1. 选择当前种群中的最优个体作为基向量。
      2. 从种群中随机选取两个互不相同的个体。
      3. 将这两个个体的差分向量乘以缩放因子后加到基向量上，生成变异向量。
      4. 对变异向量与目标向量执行二项式交叉，生成子代向量。
      5. 计算子代向量的适应度值。
      6. 若子代向量的适应度优于目标向量，则用子代向量替换目标向量。
      7. （可选）若使用外部档案，则用当前已发现的优良解更新档案。
   2. 迭代代数加 1。
4. 返回种群或档案中的最优解。

注意事项

优点

• 强化优良解利用：以最优个体作为变异基向量，使 DE/best/1/z 能够围绕潜在优良区域进行更有针对性的搜索。
• 兼顾探索与开发：外部档案的引入增强了开发能力，同时变异与交叉操作仍能维持一定种群多样性。
• 结构简单、易于实现：与其他 DE 变体相比，DE/best/1/z 结构清晰，实现难度较低，参数调节需求也相对较少。

缺点

• 易早熟收敛：对最优解的强调可能导致算法在多峰优化问题中过早收敛到局部最优。
• 种群多样性受限：随着搜索推进，种群可能逐渐丧失多样性，从而削弱跳出局部最优的能力。
• 对种群规模较敏感：DE/best/1/z 的性能可能显著受到种群规模设置的影响，因此需要针对具体问题仔细调参。

启发式建议

种群规模（NP）

• 一般可将 NP 设置为问题维数的 5 到 10 倍。
• 对于复杂多峰问题，可适当增大 NP 以维持种群多样性。
• 若种群规模过小，算法可能早熟收敛，或难以找到高质量解。

交叉概率（CR）

• 常见的初始设置是 $CR = 0.9$，这有助于在解之间实现较强的信息交换。
• 当种群多样性较低时，可适当减小 CR，以增强探索能力。
• 对于变量间相关性较强的问题，较大的 CR 通常有助于保持优良解结构。

缩放因子（F）

• F 的常用取值范围为 0.5 到 1.0。
• 较小的 F 值（约 0.5）更偏向开发，较大的 F 值（约 1.0）更偏向探索。
• 可在搜索过程中自适应调整 F，例如前期采用较大值以增强探索，后期逐渐减小以提升开发能力。

外部档案

• 外部档案的规模可设置为种群规模的一定比例，例如 NP 的 25%。
• 应定期将当前发现的优良解更新至档案中。
• 可结合聚类、拥挤距离等策略维护档案多样性，以避免档案中过度集中于局部区域。