概率拥挤法（PC）

名称

概率拥挤法（Probabilistic Crowding，PC）

分类

查看分类思维导图

概率拥挤法是一种隶属于进化计算（Evolutionary Computation）领域的小生境技术，而进化计算又是计算智能（Computational Intelligence）的一个分支。它与确定性拥挤法（Deterministic Crowding）和受限锦标赛选择（Restricted Tournament Selection）等其他小生境方法密切相关。

• 计算智能
  • 进化计算
    • 进化算法
      • 遗传算法
        • 小生境方法
          • 概率拥挤法

策略

概率拥挤法是一种用于在遗传算法中维持种群多样性的小生境技术。其目标是防止过早收敛，并促进围绕多个最优解形成稳定的子种群。

概率拥挤法的核心思想是根据个体之间的相似性对种群中的个体进行配对，然后在每一对个体内部施加选择压力。这种机制鼓励相似个体之间相互竞争，从而使不同小生境能够相对独立地演化。

配对机制

在概率拥挤法中，种群中的每个个体都会依据其基因型相似性或表现型相似性，与另一个个体进行配对。相似性度量可以采用多种方式，例如针对二进制表示的汉明距离（Hamming Distance），或针对实值表示的欧氏距离（Euclidean Distance）。

该配对过程具有概率性，即相似度越高的个体，被配对在一起的概率越大。这使得配对过程在促进小生境形成的同时，仍保留一定的随机性。

选择与替换

当个体完成配对后，需要在每一对个体内部执行选择机制。通常采用锦标赛选择，即比较两个个体的适应度值，并将适应度较高者选为胜者。

锦标赛中的胜者将替换败者在种群中的位置。该替换策略保证了种群规模保持不变，同时使适应度更高的个体得以存活并传播其遗传信息。

通过在每对个体内部施加选择压力，概率拥挤法能够促进围绕不同最优点形成稳定子种群。它使不同小生境中的个体能够相对独立地演化，从而保持种群多样性并防止过早收敛。

过程

1. 初始化一个固定规模为 $N$ 的种群。
2. 当终止条件未满足时，重复执行步骤 3–7。
3. 对于种群中的每个个体 $i$，执行：
   1. 根据与个体 $i$ 的相似性，从种群中选择另一个个体 $j$。
   2. 对个体 $i$ 和 $j$ 应用遗传算子（交叉与变异），生成一个后代个体 $o$。
   3. 评估后代个体 $o$ 的适应度。
   4. 在个体 $i$ 与后代个体 $o$ 之间进行一次锦标赛：
      1. 若 $o$ 的适应度优于 $i$ 的适应度，则用 $o$ 替换种群中的 $i$。
      2. 否则，丢弃 $o$。
4. 重复步骤 3，直到种群中的所有个体都被处理完毕。
5. 若满足终止条件，则停止算法并返回最终种群。
6. 否则，返回步骤 3，进入下一代。

数据结构

• 种群（Population）：表示当前种群的个体数组或列表。
• 个体（Individual）：表示搜索空间中的一个候选解。根据具体问题，可采用二进制串、实值向量或排列等不同表示方式进行编码。
• 适应度函数（Fitness Function）：用于评价个体质量或优劣程度的函数。它根据个体在给定问题上的表现，为每个个体赋予一个适应度值。

参数

• 种群规模（Population Size, $N$）：种群中的个体数量。该参数决定了遗传多样性水平，以及探索与开发之间的权衡关系。
• 相似性度量（Similarity Measure）：用于计算个体之间相似程度的度量方式。常见选择包括用于二进制表示的汉明距离，以及用于实值表示的欧氏距离。
• 交叉概率（Crossover Probability）：施加交叉算子以生成后代的概率。该参数控制对优良遗传信息的利用程度。
• 变异概率（Mutation Probability）：对后代施加变异算子的概率。该参数用于维持多样性，并支持对搜索空间新区域的探索。

注意事项

优点

• 维持种群多样性：概率拥挤法能够促进围绕多个最优点形成稳定子种群，从而防止过早收敛，并支持对搜索空间不同区域的探索。
• 保留小生境信息：通过基于相似性进行配对并在配对内部施加选择压力，概率拥挤法能够保留特定小生境中的信息，并使不同小生境相对独立地演化。
• 增强全局优化能力：概率拥挤法有助于在多峰优化问题中找到多个最优解。当目标是获得一组具有多样性的高质量解时，该方法尤为有效。

缺点

• 计算复杂度增加：概率拥挤法中的配对过程需要计算个体之间的相似性，尤其在种群规模较大和搜索空间维数较高时，这会带来较高的计算开销。
• 对相似性度量敏感：概率拥挤法的性能在很大程度上依赖于相似性度量的选取。为了有效实现小生境划分，需要选择能够准确刻画问题领域关键特征的相似性度量。
• 参数敏感性：概率拥挤法的效果可能对其参数取值较为敏感，例如种群规模和相似性阈值。因此，需要对这些参数进行合理调节，以获得较优性能。

启发式建议

种群规模

• 应将种群规模设置得足够大，以维持充分的遗传多样性，并支持形成多个小生境。
• 在确定种群规模时，应综合考虑问题复杂度以及期望获得的最优解数量。
• 较大的种群规模有助于探索更广范围的解空间，但同时也会提高计算成本。

相似性度量

• 应选择与问题表示方式相匹配、且能够刻画搜索空间关键特征的相似性度量。
• 对于二进制表示，通常采用汉明距离，以衡量两个个体之间不同位的数量。
• 对于实值表示，通常采用欧氏距离，以计算搜索空间中两点之间的直线距离。
• 可考虑对相似性度量进行归一化处理，以保证个体之间的比较更加公平。

遗传算子

• 应采用与问题表示方式相适应的交叉与变异算子。
• 对于二进制表示，常用算子包括位翻转变异（bit-flip mutation）以及单点交叉或多点交叉。
• 对于实值表示，高斯变异（Gaussian mutation）和算术交叉（arithmetic crossover）是较常见的选择。
• 应根据问题特征以及期望的探索—开发平衡，对交叉概率和变异概率进行调整。

终止条件

• 应根据问题需求和可用计算资源设定合适的终止条件。
• 常见终止条件包括达到最大迭代代数、达到期望适应度水平，或观察到种群已基本收敛。
• 可考虑加入停滞检测机制，当在一定代数内未观察到显著改进时触发算法终止。

小生境半径

• 小生境半径决定了每个小生境的作用范围，并影响子种群的形成方式。
• 应根据问题领域特征以及期望的多样性水平来设置小生境半径。
• 较小的小生境半径会形成更集中、更局部化的小生境，而较大的半径则会形成范围更广、重叠更多的小生境。
• 可通过实验比较不同小生境半径取值，以在保持多样性与允许小生境内部竞争之间取得平衡。