DE/rand/1/bin

名称

DE/rand/1/bin，也称为：差分进化 rand/1/bin 变体。

分类

查看分类思维导图

差分进化（Differential Evolution, DE）是一种随机优化算法，属于进化计算领域，而进化计算又是计算智能的一个分支。它与其他基于种群的元启发式算法，如遗传算法和进化策略，具有密切关联。

• 计算智能
  • 仿生计算
    • 进化计算
      • 进化算法
        • 遗传算法
        • 进化规划
        • 进化策略
        • 差分进化
          • DE/rand/1/bin

策略

差分进化是一种基于种群的优化方法，其通过对一组候选解（称为个体）进行迭代更新，不断改进解的质量。算法维护一个由多个个体组成的种群，每个个体表示问题的一个潜在解。在每一代中，DE 通过差分变异算子和交叉算子对现有个体进行组合，从而产生新的个体。变异算子从种群中随机选取三个互不相同的个体，将其中两个个体的差分向量按比例缩放后加到第三个个体上，生成变异向量。随后，交叉算子将变异向量与对应的目标向量进行组合，得到试验向量。最后，试验向量与目标向量进行竞争，较优者进入下一代。

差分变异

差分变异算子是 DE 的核心组成部分。对于种群中的每个目标向量，算法随机选取另外三个互不相同的个体，并通过将其中两个个体的差分按比例缩放后加到第三个个体上，构造出一个变异向量。缩放因子记为 $F$，用于控制差分扰动的放大程度。

交叉

在完成变异后，DE 通过交叉算子进一步增强种群多样性。最常用的交叉策略是二项式交叉，即 DE/rand/1/bin。在该策略下，试验向量中的每个分量都依据交叉概率 $CR$，从变异向量或目标向量中继承对应元素。该算子通过在保留目标向量部分特征的同时引入新信息，实现探索与开发之间的平衡。

选择

DE 中的选择算子是一种简单的一对一竞争机制，即试验向量与对应的目标向量直接比较。若试验向量的目标函数值优于或不劣于目标向量，则试验向量替换目标向量进入下一代；否则保留目标向量。该贪婪选择策略保证了种群质量不会随迭代过程下降。

过程

数据结构：

• 种群：由若干候选解构成的集合，其中每个候选解均表示为一个 $D$ 维实值向量。
• 变异向量：由差分变异算子生成的向量。
• 试验向量：由交叉算子生成的向量，其由变异向量与目标向量的分量组合而成。

参数：

• 种群规模（NP）：种群中个体的数量。
• 交叉概率（CR）：在交叉过程中从变异向量继承分量的概率。
• 缩放因子（F）：用于控制差分变异幅度的参数。

过程：

1. 初始化：
   1. 设置 NP、CR 和 F 的取值。
   2. 在搜索空间边界内随机初始化包含 NP 个个体的种群。
2. 当终止准则未满足时，执行：
   1. 对种群中的每个目标向量，执行：
      1. 变异：
         1. 从种群中随机选取三个与目标向量不同的互异个体。
         2. 将其中两个个体的差分向量按比例缩放后加到第三个个体上，生成变异向量。
      2. 交叉：
         1. 根据交叉概率 CR，将变异向量与目标向量的分量进行组合，生成试验向量。
         2. 对于试验向量的每个维度，执行：
            1. 生成一个 0 到 1 之间的随机数。
            2. 若该随机数小于等于 CR，或当前维度为预先随机指定的某一维度，则该维度从变异向量继承；否则从目标向量继承。
      3. 选择：
         1. 计算试验向量的目标函数值。
         2. 若试验向量的目标函数值优于或不劣于目标向量，则用试验向量替换目标向量；否则保留目标向量。
3. 返回种群中找到的最优解。

注意事项

优点：

• 结构简单，易于实现，控制参数较少。
• 能够有效求解多种优化问题，包括不可导、非线性及多峰函数优化问题。
• 具有较好的收敛性能，对问题特定参数调节的依赖较小。

缺点：

• 在高维搜索空间中，随着问题景观复杂度上升，其性能可能下降。
• 收敛速度可能较慢，尤其是在存在大量局部最优的复杂问题中。
• 缺乏显式的多样性保持机制，在某些情况下可能导致早熟收敛。

启发式建议

种群规模（NP）

• 一般可将 NP 设置为问题维数的 5 到 10 倍。
• 较大的种群有助于增强探索能力并避免早熟收敛，但会增加计算成本。
• 较小的种群虽然收敛较快，但更容易陷入次优解。

交叉概率（CR）

• CR 用于平衡探索与开发。较大的取值更有利于探索，较小的取值更偏向开发。
• 常用的初始设置是 $CR = 0.5$，即对变异向量和目标向量给予大致相同的重要性。
• 应根据问题特性调整 CR。对于可分问题，较小的 CR 值（如 0.1 到 0.2）往往更有效；对于不可分问题，较大的 CR 值（如 0.9 到 1.0）通常表现更好。

缩放因子（F）

• F 控制差分扰动的幅度。较大的 F 会增大搜索步长，较小的 F 则使搜索更为保守。
• F 通常设置在 0.4 到 1.0 之间，一个较常见的初始值约为 0.5。
• 较小的 F 适用于单峰问题，或种群已经接近最优解时；较大的 F 则有助于在多峰问题中跳出局部最优。

终止准则

• 可根据可用计算预算设定最大迭代代数或最大函数评估次数。
• 可监测最优解在若干代内的改进情况，若长期无显著提升，则考虑提前终止。
• 也可结合具体问题知识，如可接受的解质量或收敛阈值，设定更有针对性的停止条件。

约束处理

• 对于约束优化问题，可在选择阶段同时考虑约束违反程度与目标函数值。
• 可通过罚函数对不可行解进行惩罚，从而引导搜索朝向可行域。
• 也可采用修复机制或专门的约束处理算子，以维持种群可行性。