确定性拥挤法（DC）

名称

确定性拥挤法（Deterministic Crowding，DC）

分类

查看分类思维导图

确定性拥挤法是一种用于遗传算法中的小生境技术，而遗传算法隶属于进化计算（Evolutionary Computation）领域，进化计算则是计算智能（Computational Intelligence）的一个分支。

• 计算智能
  • 进化计算
    • 进化算法
      • 遗传算法
        • 小生境技术
          • 确定性拥挤法

策略

确定性拥挤法旨在通过促进种群中相似个体之间的竞争来维持种群多样性，并防止过早收敛。其核心在于采用一种特殊的替换策略，使后代个体直接与其最相似的父代个体竞争生存机会。

相似性度量

为了判定个体之间的相似性，需要引入某种距离度量。常见选择包括用于连续值问题的欧氏距离（Euclidean distance），以及用于离散值问题的汉明距离（Hamming distance）。该距离度量基于个体的基因型或表现型特征，对个体间的不相似程度进行量化。

替换策略

在替换阶段，每个后代个体都与其最相似的父代个体竞争进入下一代的资格。这种父代与子代之间的直接竞争，有助于种群内部小生境的形成与维持。由于后代只能替换与自身最相似的父代个体，确定性拥挤法能够在保持多样性的同时，避免某一个优势解主导整个种群。

过程

1. 初始化包含 $N$ 个个体的种群
2. 当未满足终止条件时，重复以下过程：
   1. 使用某种选择方法（如锦标赛选择）从种群中选取 $N/2$ 对父代个体
   2. 对每一对父代个体：
      1. 应用遗传算子（交叉和/或变异）生成两个后代个体
      2. 使用距离度量计算每个后代个体与每个父代个体之间的相似性
      3. 将每个后代分配给与其最相似的父代进行竞争
      4. 对每一组父代-后代配对：
         1. 若后代个体的适应度优于父代个体，则在下一代中以后代替换父代
         2. 否则，在下一代中保留父代个体
3. 返回找到的最优解

数据结构

• 种群（Population）：由个体构成的数组或列表，表示问题的候选解集合
• 个体（Individual）：表示单个解，通常编码为比特串、整数串或实数向量
• 适应度函数（Fitness Function）：用于评估个体解质量或适应度的函数

参数

• 种群规模（Population Size, $N$）：种群中的个体数量
• 交叉概率（Crossover Rate）：对父代个体对应用交叉算子的概率
• 变异概率（Mutation Rate）：对个体应用变异算子的概率
• 距离度量（Distance Metric）：用于计算个体间相似性的函数，例如欧氏距离或汉明距离

注意事项

优点

• 通过促进小生境的形成与维持来保持种群多样性
• 通过防止单一优势解占据整个种群来降低过早收敛的风险
• 允许同时探索搜索空间中的多个潜在优良区域，从而增强全局搜索能力

缺点

• 由于需要计算个体之间的相似性，会增加计算复杂度
• 算法性能可能对距离度量的选择较为敏感
• 可能需要额外机制，以确保在每个小生境内部对有前景解进行充分开发

启发式建议

种群规模

• 选择能够在探索与开发之间取得平衡的种群规模
• 较大的种群有助于保持多样性，但也会消耗更多计算资源
• 较小的种群可能收敛更快，但也更容易陷入次优解

遗传算子

• 应使用与问题表示方式相适应的遗传算子，例如适用于二进制编码问题的比特串交叉算子，或适用于连续优化问题的实值交叉算子
• 应根据问题复杂度以及对探索与开发平衡的需求调整交叉概率和变异概率
• 较高的交叉概率有助于促进个体间遗传信息交换，而较高的变异概率则有助于引入新的遗传多样性

距离度量

• 应选择能够在具体问题背景下准确反映个体相似性的距离度量
• 对于连续值问题，欧氏距离是一种常用选择
• 对于离散值问题，可采用汉明距离来衡量对应分量之间的差异数量
• 可考虑对距离度量进行归一化处理，以确保不同尺度或取值范围下的个体之间能够进行公平比较

终止准则

• 应根据期望达到的解质量水平或可用计算资源来设定终止条件
• 常见终止条件包括达到最大迭代代数、找到满足要求适应度水平的解，或观察到种群已基本收敛
• 应在给予算法足够搜索时间与避免在收益递减阶段进行过度计算之间取得平衡