受限锦标赛选择拥挤法（RTS）

Goat_Yang2026/3/21约 1753 字大约 6 分钟

受限锦标赛选择拥挤法（RTS）

名称

受限锦标赛选择拥挤法（Crowding with Restricted Tournament Selection，RTS）

受限锦标赛选择拥挤法是一种属于进化计算（Evolutionary Computation）的小生境技术，而进化计算是计算智能（Computational Intelligence）和生物启发计算（Biologically Inspired Computation）的一个分支。它与适应度共享（Fitness Sharing）、清除法（Clearing）以及确定性拥挤法（Deterministic Crowding）等其他多样性保持技术密切相关。

计算智能
- 生物启发计算
  - 进化计算
    - 进化算法
      - 遗传算法
        小生境方法
        拥挤法
        受限锦标赛选择拥挤法

策略

受限锦标赛选择拥挤法旨在通过促进相似个体之间的竞争，维持遗传算法中的种群多样性并防止过早收敛。其实现方式是对选择过程进行改造，将锦标赛选择限制在基于基因型相似性或表现型相似性构建的种群局部子集中进行。

RTS 的核心思想是：为种群中的每个个体构造一个由其最相似成员组成的局部邻域，然后仅在这些局部邻域内施加选择压力。这样可以鼓励搜索过程中不同小生境的形成与保持。

相似性度量

为了确定每个个体的局部邻域，需要采用某种相似性度量。该度量用于量化个体之间在基因型或表现型上的距离，从而识别种群中与当前个体最相近的成员。常见的相似性度量包括欧氏距离（Euclidean Distance）、汉明距离（Hamming Distance），以及针对具体问题设计的领域特定度量。

受限锦标赛选择

当局部邻域构建完成后，选择过程通过一系列受限锦标赛进行。对于种群中的每个个体，从其最近邻中随机抽取一个较小子集参与锦标赛。局部锦标赛的获胜者通常是适应度最高的个体，并被选中用于繁殖。

通过将竞争限制在相似个体之间，RTS 能够促进搜索空间中多样化解的保持。这种局部化选择压力使不同小生境能够相对独立地演化，从而防止某一个小生境主导整个种群并导致过早收敛。

过程

随机生成初始种群。
评估种群中每个个体的适应度。
对于每一代，执行以下过程：
1. 创建一个空的子代种群。
2. 对当前种群中的每个个体：
  1. 使用选定的相似性度量，计算该个体与种群中所有其他个体之间的相似性。
  2. 选取与该个体最相似的 $K$ 个个体，构成局部邻域。
  3. 从局部邻域中随机选取 $N$ 个个体，参与一次受限锦标赛。
  4. 选择锦标赛中适应度最高的个体作为获胜者。
  5. 对获胜者施加遗传算子（交叉与变异），生成一个子代个体。
  6. 将该子代加入新种群。
3. 用子代种群替换当前种群。
4. 评估新种群中每个个体的适应度。
重复步骤 3，直到满足终止条件（如达到最大迭代代数或达到满意的适应度水平）。

参数

种群规模（Population Size）：种群中的个体数量。
$K$ ：每个个体局部邻域的规模。
$N$ ：每次受限锦标赛中参与竞争的个体数量。
交叉概率（Crossover Rate）：对选中个体施加交叉算子的概率。
变异概率（Mutation Rate）：对子代个体施加变异算子的概率。

注意事项

优点

能够促进并维持种群多样性，防止过早收敛。
有利于不同小生境的形成与保持，从而能够同时探索多个最优解。
在多峰搜索空间中，提高了发现全局最优解的可能性。

缺点

由于需要计算个体之间的相似性，计算复杂度较高。
算法性能依赖于相似性度量的合理选择，而这通常需要领域知识或实验调参。
局部邻域规模 $K$ 和受限锦标赛规模 $N$ 需要仔细设定，才能获得较优效果。

启发式建议

相似性度量的选择

应选择能够反映问题领域关键特征的相似性度量。
对于基因型相似性，可考虑采用二进制表示下的汉明距离，或实值表示下的欧氏距离。
对于表现型相似性，可采用能够度量个体行为或功能相似性的领域特定指标。

参数调节

种群规模（Population Size）：
- 应选择能够在多样性与计算效率之间取得平衡的种群规模。
- 较大的种群可以维持更强的多样性，但也需要更多计算资源。
局部邻域规模（Local Neighborhood Size, $K$ $K$ ）：
- 应将 $K$ 设置为能够反映搜索空间局部结构的取值。
- 较大的 $K$ 会形成更具多样性的邻域，但可能削弱选择压力。
受限锦标赛规模（Restricted Tournament Size, $N$ $N$ ）：
- 应使 $N$ 小于 $K$ ，以保证竞争保持局部化。
- 较大的 $N$ 会增强每个邻域内部的选择压力。
交叉概率与变异概率（Crossover and Mutation Rates）：
- 应根据问题特征以及对探索与开发平衡的需求，对交叉概率和变异概率进行调整。
- 较高的交叉概率有助于促进个体间遗传信息交换，而较高的变异概率则有助于引入新的遗传变异。

探索与开发的平衡

种群多样性的监测：
- 应定期利用基因型距离或表现型距离等指标评估种群多样性。
- 若多样性低于某一阈值，可考虑增大变异概率或调整局部邻域规模，以增强探索能力。
自适应参数控制：
- 可引入自适应机制，根据搜索进展动态调整变异概率或局部邻域规模等参数。
- 当种群过于同质化或适应度提升停滞时，可适当增强探索。

混合化与扩展

可将 RTS 与其他多样性保持技术结合使用，例如适应度共享（fitness sharing）或清除法（clearing），以进一步提升种群多样性。
可结合局部搜索或模因算法（memetic algorithms），对各个小生境中的解进行精细化改进。
可将 RTS 扩展到多目标优化问题中，在目标空间中结合 Pareto 支配与小生境机制进行处理。