动态小生境聚类（DNC）

名称

动态小生境聚类（Dynamic Niche Clustering，DNC）

分类

查看分类思维导图

动态小生境聚类是一种隶属于计算智能（Computational Intelligence）领域的技术，更具体地说，属于进化算法（Evolutionary Algorithms）与小生境方法（Niching Methods）方向。它与适应度共享（Fitness Sharing）、拥挤法（Crowding）以及受限锦标赛选择（Restricted Tournament Selection）等其他小生境技术密切相关。

• 计算智能
  • 进化算法
    • 小生境方法
      • 适应度共享
      • 拥挤法
      • 受限锦标赛选择
      • 动态小生境聚类

策略

动态小生境聚类是一种旨在维持种群多样性并促进搜索空间中稳定子种群（即小生境）形成的小生境技术。其基本思想是动态识别并保留搜索空间中的潜在优良区域，从而使算法能够同时搜索多个最优解。

DNC 的核心思想是在基因型空间或表现型空间中，根据个体之间的相似性对其进行聚类。通过形成多个聚类，算法能够在进化过程中识别并维持多个小生境。每个聚类对应搜索空间中的一个特定区域，并被视为一个独立的子种群。

聚类过程会在进化算法运行期间以固定间隔动态执行。聚类频率由一个称为聚类间隔（clustering interval）的参数控制。在每一次聚类步骤中，个体依据某种相似性度量被划分为不同聚类；该相似性度量通常根据问题表示方式选取，例如欧氏距离（Euclidean distance）或汉明距离（Hamming distance）。

当聚类形成后，算法会在每个聚类内部施加小生境压力（niching pressure），以促进多样性并防止过早收敛。这通常通过修改选择算子与繁殖算子来实现，使其优先保留相对于各自聚类内部其他个体更不相似的个体。

这种小生境压力有助于在搜索空间中不同最优区域周围形成稳定子种群。每个聚类可以独立进化，从而使算法能够同时对多个潜在优良区域进行探索与开发。由此，算法既能保持种群多样性，又能降低陷入局部最优的风险。

过程

数据结构

• 种群（Population）：由若干个体构成的数组或列表，表示潜在解集合。
• 聚类（Clusters）：由多个聚类组成的列表，其中每个聚类是种群中一部分个体构成的子集。

参数

• 种群规模（Population Size）：种群中的个体数量。
• 聚类间隔（Clustering Interval）：两次聚类操作之间所间隔的代数。
• 相似性阈值（Similarity Threshold）：用于判定个体是否属于同一聚类的最大距离或相似性阈值。
• 小生境压力（Niching Pressure）：在每个聚类内部施加的小生境压力强度。

步骤

1. 随机初始化种群。
2. 评估种群中每个个体的适应度。
3. 按照给定代数重复以下过程，直到满足终止条件：
   1. 若当前代数是聚类间隔的整数倍：
      1. 对种群执行聚类：
         1. 计算个体之间的两两距离或相似度。
         2. 根据相似性阈值将个体划分为若干聚类。
   2. 对每个聚类分别执行：
      1. 在聚类内部施加小生境压力：
         1. 修改选择算子，使其优先选择与该聚类内部其他个体差异较大的个体。
         2. 执行繁殖操作（交叉与变异）以生成后代。
      2. 评估后代个体的适应度。
      3. 通过以后代替换适应度较低的个体来更新该聚类。
   3. 将更新后的各聚类重新合并为主种群。
4. 返回找到的最优解（或最优解集）。

注意事项

优点：

• 能够维持种群多样性并促进稳定小生境的形成。
• 使算法能够同时对搜索空间中的多个潜在优良区域进行探索与开发。
• 降低过早收敛和陷入局部最优的风险。

缺点：

• 引入了额外参数，如聚类间隔和相似性阈值，需要进行调节。
• 聚类过程可能具有较高计算代价，尤其是在大规模种群和高维搜索空间中。
• 算法效果较大程度上依赖于相似性度量与问题表示方式的选择。

启发式建议

参数设置

• 应根据问题复杂度和可用计算资源设置种群规模。较大的种群规模有助于增强探索能力，但会增加计算开销。
• 应根据算法收敛速度选择聚类间隔。较小的聚类间隔意味着更频繁的聚类，但会增加额外计算负担；较大的聚类间隔则允许每个聚类内部有更多代数进行独立演化。
• 应根据问题领域特征及期望的小生境形成程度设定相似性阈值。较小阈值会形成更集中的小生境，而较大阈值则允许每个小生境内部保留更多多样性。
• 应调节小生境压力，以平衡每个聚类内部的探索与开发。较高的小生境压力有助于维持多样性，但可能减缓收敛；较低的小生境压力则有利于更快收敛，但可能导致过早收敛。

相似性度量

• 应选择与问题表示方式相适应的相似性度量。对于实值表示，通常采用欧氏距离；对于二进制表示，通常采用汉明距离。
• 可考虑对距离或相似度进行归一化处理，以保证不同尺度或取值范围下个体之间的比较具有公平性。
• 可尝试不同的相似性度量，并观察其对小生境形成与稳定性的影响。

小生境压力

• 可通过修改每个聚类内部的选择算子来实现小生境压力。常见方法包括适应度共享（fitness sharing）、拥挤法（crowding）和受限锦标赛选择（restricted tournament selection）。
• 适应度共享通过根据个体间相似性分配共享适应度值，从而促进每个聚类内部差异较大的个体被选择。
• 拥挤法通过将后代与聚类中的部分个体进行比较，并在后代更优时替换其中最相似个体。
• 受限锦标赛选择则在聚类内部的局部邻域中执行锦标赛选择，从而优先保留差异较大的个体。

聚类管理

• 应在整个进化过程中定期监测各聚类的规模与多样性。若某些聚类规模过小或过早收敛，可考虑将其与其他聚类合并，或引入新的随机个体。
• 可尝试不同的聚类合并策略，例如依据聚类中心之间的距离，或依据各聚类最优个体的适应度进行合并。
• 可考虑加入停滞聚类或已收敛聚类的检测与移除机制，从而释放计算资源，用于探索搜索空间中的其他区域。

混合化策略

• 可将动态小生境聚类与其他进化算法或局部搜索技术结合，以提升整体优化性能与效率。
• 可在每个聚类内部引入局部搜索，以细化候选解并加速向最优解收敛。
• 可融入特定领域知识或启发式信息，以指导聚类过程及各小生境内部的演化。