动态小生境共享（DNS）

名称

动态小生境共享（Dynamic Niche Sharing，DNS）

分类

查看分类思维导图

动态小生境共享是一种隶属于进化计算（Evolutionary Computation）领域的技术，而进化计算又是计算智能（Computational Intelligence）的一个分支。该方法与适应度共享（Fitness Sharing）和拥挤法（Crowding）等技术密切相关。

• 计算智能
  • 进化计算
    • 遗传算法
      • 小生境算法
        • 动态小生境共享

策略

动态小生境共享是一种用于保持种群多样性的技术，旨在维持遗传算法种群中的稳定子种群（即小生境）。该方法致力于防止过早收敛，并促进在多峰优化问题中对多个最优解的探索。

动态小生境共享的核心思想是根据个体与种群中其他个体之间的相似性，对个体适应度进行调整。具体而言，通过定义一个共享函数来度量搜索空间中个体之间的距离。彼此距离较近的个体（即更相似的个体）被视为属于同一小生境，因此需要共享其适应度。

共享函数通常包含一个共享半径参数，用于确定每个小生境的范围。处于彼此共享半径之内的个体，其适应度会按照共享该小生境的个体数量按比例降低。这种机制有助于促进不同小生境的形成与维持，因为位于搜索空间中较稀疏区域的个体将具有相对更高的适应度。

共享半径的动态调整

动态小生境共享的一个关键特征是在进化过程中对共享半径进行动态调整。初始阶段，共享半径通常设置得较大，以便形成范围较宽的小生境。随着种群不断进化并逐渐趋于收敛，共享半径会逐步减小，从而在已发现的最优解附近形成更局部化的小生境。

这种对共享半径的动态调整，使算法能够适应适应度景观的结构，并在探索（exploration）与开发（exploitation）之间维持平衡。在进化早期，较大的共享半径通过防止种群过快收敛来促进探索；而随着搜索的推进，逐渐减小的共享半径则有助于对潜在优良区域进行更精细的搜索，并维持围绕已发现最优解所形成的稳定小生境。

与遗传算法的集成

动态小生境共享通常被集成到遗传算法的选择过程中。在施加共享函数并得到调整后的适应度值后，这些适应度将用于指导个体的繁殖选择。这能够保证来自不同小生境的个体都拥有较为公平的被选中机会，从而维持种群多样性，并防止某一个小生境主导整个种群。

动态共享半径通常按照固定时间间隔进行更新，这一更新往往与代数计数或预设调度方案相关。共享半径的具体更新策略及其缩减速率，可以根据问题特征以及对探索与开发平衡的需求进行调整。

过程

1. 初始化种群：
   1. 随机生成初始种群中的各个个体。
   2. 评估每个个体的适应度。
2. 设置初始共享半径：

• 根据问题特征和期望的小生境规模确定初始共享半径。

3. 当终止条件未满足时，重复以下步骤：
4. 应用共享函数：
   1. 对于种群中的每个个体：
      1. 计算该个体与种群中其他所有个体之间的距离。
      2. 确定当前共享半径范围内的个体数量。
      3. 根据共享该小生境的个体数量调整该个体的适应度。
5. 执行选择：

• 根据调整后的适应度值选择用于繁殖的个体。

6. 应用遗传算子：
   1. 对选中的个体执行交叉操作以生成后代。
   2. 对后代执行变异操作。
7. 评估新生成个体的适应度。
8. 更新种群：

• 用新个体替换种群中的一部分个体。

9. 更新共享半径：

• 按照预设调度方案或给定准则调整共享半径。

10. 检查终止条件：

• 若满足终止条件，则停止算法并返回找到的最优解（或最优解集）。
• 否则，返回步骤 4。

参数

• 种群规模（Population Size）：种群中的个体数量。
• 共享半径（Sharing Radius）：共享半径的初始取值及其缩减调度方案。
• 交叉概率（Crossover Rate）：对选中个体施加交叉操作的概率。
• 变异概率（Mutation Rate）：对后代施加变异操作的概率。
• 替换策略（Replacement Strategy）：用新后代替换种群中个体的方法（例如精英保留、稳态替换）。

注意事项

优点

• 保持多样性：动态小生境共享能够有效保持种群多样性，防止种群过早收敛到次优解。
• 适应适应度景观：通过动态调整共享半径，算法能够适应适应度景观的结构，在早期促进探索、后期强化开发。
• 发现多个最优解：通过维持稳定小生境，动态小生境共享能够在多峰优化问题中发现并保留多个最优解。

缺点

• 参数敏感：动态小生境共享的性能对初始共享半径及其缩减调度较为敏感。不恰当的设置可能导致小生境形成效果不佳，或多样性保持不足。
• 计算复杂度增加：应用共享函数需要计算个体之间的距离，尤其在大规模种群或高维搜索空间中，这会带来较高的计算代价。
• 共享半径设置困难：合适的初始共享半径及其缩减策略较难确定，因为它们依赖于具体问题的特征，通常需要问题相关知识或实验调参。

启发式建议

初始共享半径的设置

• 设置初始共享半径时，应考虑搜索空间的规模及其维数。
• 较大的初始共享半径有助于更广泛的探索，而较小的半径则更有利于局部化搜索。
• 若已有关于问题的先验知识，可利用其指导初始共享半径的设定。
• 可通过实验比较不同初始取值对算法性能的影响。

共享半径缩减调度的调整

• 共享半径的缩减调度应在整个进化过程中平衡探索与开发。
• 渐进式缩减有助于实现从全局探索向局部开发的平滑过渡。
• 在确定缩减速率时，应结合算法的收敛行为进行分析。
• 缩减过快可能导致过早收敛，而缩减过慢则可能使搜索过程不必要地延长。

高维搜索空间的处理

• 在高维搜索空间中，由于维数灾难（curse of dimensionality），动态小生境共享的效果可能受到限制。
• 可考虑采用降维技术或结合问题相关知识，将搜索聚焦于更关键的维度。
• 应结合高维空间中搜索点更加稀疏的特点，对共享半径及其缩减调度进行相应调整。

种群规模与小生境规模的平衡

• 种群规模应足够大，以维持足够数量的小生境并避免多样性损失。
• 但种群规模过大也会减慢收敛速度，并增加计算开销。
• 在参数配置时，应综合考虑种群规模与小生境规模之间的权衡关系。
• 当种群规模受限时，可能需要采用较小的初始共享半径，以保证不同小生境能够形成清晰区分。

与其他多样性保持技术的结合

• 动态小生境共享可与其他多样性保持技术结合使用，例如拥挤法（crowding）或物种划分（speciation）。
• 组合多种技术能够进一步提升算法维持多样性及有效探索搜索空间的能力。
• 可尝试不同技术组合及参数配置，以寻找更适合具体问题的方案。