复合差分进化（CoDE）

名称

复合差分进化（Composite Differential Evolution, CoDE）

分类

查看分类思维导图

复合差分进化是一种基于种群的随机优化算法，属于进化计算领域，而进化计算又是计算智能的一个分支。它是在经典差分进化（Differential Evolution, DE）算法基础上的一种扩展。

• 计算智能
  • 仿生计算
    • 进化计算
      • 进化算法
        • 差分进化（DE）
          • 复合差分进化（CoDE）

策略

复合差分进化将经典差分进化算法中的三种试验向量生成策略与三组控制参数设置相结合。对于种群中的每个个体，算法随机选择三种试验向量生成方法中的一种，以及三组控制参数中的一组，用以生成新的试验向量。该机制使算法能够根据待求解问题的特性进行适应，因为在优化过程的不同阶段，不同的策略与参数设置可能具有不同的效果。

CoDE 中采用的三种试验向量生成策略如下：

1. DE/rand/1/bin：通过将两个随机选取个体的加权差分向量加到第三个随机选取个体上，生成试验向量；随后再采用二项式交叉算子，将该试验向量与目标向量进行组合。
2. DE/rand/2/bin：与 DE/rand/1/bin 类似，但其试验向量是通过两对随机选取个体的加权差分之和来构造的。
3. DE/current-to-rand/1：通过将一个随机选取个体与目标向量之间的加权差分加到另一个随机选取个体上，生成试验向量；随后再采用二进制交叉算子，将该试验向量与目标向量进行组合。

CoDE 中采用的三组控制参数设置如下：

1. $F = 1.0,\ Cr = 0.1$
2. $F = 1.0,\ Cr = 0.9$
3. $F = 0.8,\ Cr = 0.2$

其中，$F$ 表示缩放因子，$Cr$ 表示交叉概率。

过程

数据结构

• 种群：由候选解构成的数组，其中每个候选解均表示为一个实数向量。
• 试验向量：通过对种群中个体应用试验向量生成策略及控制参数设置而得到的新候选解。
• 目标向量：当前与试验向量进行比较的候选解。
• 最优解：在优化过程中迄今为止找到的、具有最佳适应度值的候选解。

参数

• 种群规模（NP）：种群中候选解的数量。
• 缩放因子（F）：控制差分变异算子幅值的参数。
• 交叉概率（Cr）：决定试验向量各分量从变异向量继承的概率。
• 最大迭代代数：算法终止前允许运行的最大迭代次数。

伪代码

1. 初始化包含 NP 个候选解的种群。
2. 评估种群中每个候选解的适应度。
3. 当未满足终止条件时（例如达到最大迭代代数之前）：
   1. 对种群中的每个候选解（目标向量）：
      1. 选择一种试验向量生成策略和一组控制参数设置。
      2. 利用所选策略和参数生成变异向量。
      3. 通过对变异向量和目标向量施加二项式交叉算子，生成试验向量。
      4. 评估试验向量的适应度。
      5. 若试验向量的适应度优于目标向量，则用试验向量替换目标向量。
   2. 更新当前找到的最优解。
4. 返回找到的最优解。

注意事项

优点

• 适应性强：CoDE 通过采用不同的试验向量生成策略和控制参数设置，能够适应待求解问题的不同特性。
• 鲁棒性较好：多种策略与参数组合使 CoDE 相较于经典 DE 对控制参数的选择不那么敏感。
• 效率较高：由于能够较快识别并利用搜索空间中的潜在优良区域，CoDE 往往能在较少迭代次数内找到更优解。

缺点

• 复杂度增加：相比经典 DE，引入多种试验向量生成策略和控制参数设置后，CoDE 的实现与理解都更为复杂。
• 单次迭代计算成本更高：由于需要为每个目标向量生成并评估多个试验向量，CoDE 每次迭代的计算量更大。
• 参数敏感性仍然存在：尽管 CoDE 比经典 DE 对参数设置更鲁棒，但算法性能仍可能受到种群规模、缩放因子和交叉概率选择的影响。

启发式建议

种群规模

• 种群规模应足够大，以维持种群多样性并避免早熟收敛；但也不宜过大，否则计算成本会显著增加。
• 一个常见的经验设置是将种群规模设为问题维数的 10 倍，但具体数值仍需根据问题复杂度进行调整。

缩放因子

• 缩放因子控制差分变异算子的作用幅度，应根据问题特性进行设置。
• 对于搜索空间较大或适应度景观较复杂的问题，较大的缩放因子（如 $F = 0.8$ 或 $1.0$）通常更有效。
• 对于搜索空间较小或适应度景观较简单的问题，较小的缩放因子（如 $F = 0.5$）可能已经足够。

交叉概率

• 交叉概率决定试验向量各分量从变异向量继承的概率，应根据探索与开发之间的平衡需求进行设置。
• 较高的交叉概率（如 $Cr = 0.9$）更偏向于利用当前较优解，较低的交叉概率（如 $Cr = 0.1$）则更有利于探索新的搜索区域。
• 一种常见经验是将交叉概率设置在 $0.1$ 到 $0.9$ 之间，具体取值应结合问题特性确定。

终止准则

• 最大迭代代数应依据可用计算资源以及期望的解质量来设定。
• 对于已知最优解的问题，当当前最优解与理论最优解之间的误差低于某个容差阈值时，可终止算法。
• 对于未知最优解的问题，当最优解在连续若干代中的改进幅度低于预设阈值时，可终止算法。