适应度共享（FS）

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

适应度共享（FS）

名称

适应度共享（Fitness Sharing）、共享适应度（Shared Fitness）、适应度共享机制（Fitness Sharing Scheme）

分类

查看分类思维导图

适应度共享是一种应用于进化算法（Evolutionary Algorithms）中的小生境技术，而进化算法属于计算智能（Computational Intelligence）与生物启发计算（Biologically Inspired Computation）的一个分支。它与拥挤法（Crowding）、物种形成（Speciation）等其他小生境方法密切相关。适应度共享所属的层次结构如下：

计算智能
- 生物启发计算
  - 进化计算
    - 进化算法
      - 遗传算法
        小生境方法
        适应度共享

策略

适应度共享是一种旨在维持种群多样性并防止遗传算法过早收敛的技术。其基本思想是降低彼此相似个体的适应度，从而促使种群分散开来，探索搜索空间中的不同区域。

适应度共享的核心思想在于：种群中的个体需要竞争有限资源。若多个个体占据同一小生境（即彼此相似），则它们必须共享该小生境中的可用资源。该资源共享机制通过如下方式加以模拟：将个体的原始适应度除以一个反映与其相似个体数量的度量值。

相似性度量

为了判定个体之间的相似性，需要定义某种距离度量。该距离度量可以基于基因型相似性（例如二进制表示中的汉明距离，Hamming Distance），也可以基于表现型相似性（例如解空间中的欧氏距离，Euclidean Distance）。一个称为共享半径（sharing radius）的阈值用于判断两个个体是否足够相似，以至于需要共享适应度。

共享适应度

在确定个体之间的相似性之后，需要计算每个个体的共享适应度。其方法是：将个体的原始适应度除以共享因子（sharing factor）。所谓共享因子，是指该个体与种群中所有落入共享半径范围内个体之间相似性值之和。

通过降低相似个体的适应度，适应度共享能够促使种群保持多样性，并探索搜索空间中的不同区域。这有助于防止种群过早收敛于次优解，并提高算法在多峰优化问题中定位多个最优解的能力。

过程

初始化种群
1. 生成由多个个体构成的种群
2. 评估每个个体的适应度
当终止条件未满足时：
1. 对于种群中的每个个体 $i$ $i$ ：
  1. 计算共享因子：
    1. 令 sharing_factor = 0
    2. 对于种群中的每个个体 $j$ $j$ （ $j \ne i$ $j \neq = i$ ）：
      1. 计算个体 $i$ 与个体 $j$ 之间的距离 $d$
      2. 若 $d < sharing\_radius$ ：
        计算共享函数值： $sh = 1 - (d / sharing\_radius)^\alpha$
        sharing_factor += sh
  2. 计算个体 $i$ 的共享适应度：shared_fitness[i] = raw_fitness[i] / sharing_factor
2. 基于共享适应度值执行选择操作
3. 应用遗传算子（交叉与变异）生成新种群
4. 评估新种群中每个个体的适应度
返回找到的最优解

数据结构：

种群（Population）：由多个个体构成的数组
个体（Individual）：表示候选解，通常编码为字符串（例如二进制串、实值串）或更复杂的数据结构
适应度（Fitness）：表示个体质量的数值

典型参数：

种群规模（Population Size）：种群中的个体数量
共享半径（Sharing Radius）：用于判定个体是否共享适应度的距离阈值
$\alpha$ ：共享函数的缩放因子（通常取 1）
选择方法（Selection Method）：用于选择个体进行繁殖的方法（如锦标赛选择、轮盘赌选择）
交叉概率（Crossover Rate）：应用交叉算子的概率
变异概率（Mutation Rate）：应用变异算子的概率

注意事项

优点：

能够促进种群多样性，从而避免过早收敛
能够在多峰优化问题中发现并维持多个最优解
易于集成到现有遗传算法实现中

缺点：

由于需要计算个体间的成对距离，因此会增加计算复杂度
需要定义合适的距离度量与共享半径，而这通常依赖于具体问题
在某些情况下，可能会减缓收敛速度，因为该方法会抑制种群过快集中到最有前景的区域

启发式建议

共享半径的选择

共享半径应足够大，以鼓励多样性；但又不能过大，以至于妨碍收敛。
一种较好的初始设置方式是，将共享半径设为个体间最大可能距离的一定比例（例如 10%）。
可通过实验尝试不同取值，并根据具体问题以及对探索与开发平衡的需求进行调整。

共享半径的自适应调整

可考虑随进化过程逐步减小共享半径，以便在后期实现更聚焦的搜索。
也可以根据种群多样性指标（如平均成对距离）动态调整共享半径，以维持期望的多样性水平。

与其他技术结合

适应度共享可以与其他多样性保持技术结合使用，例如拥挤法（Crowding）或物种形成（Speciation），以进一步提升性能。
还可引入局部搜索方法（如爬山算法，hill climbing），对遗传算法结合适应度共享所发现的解进行精细化改进。

计算复杂度的处理

为降低成对距离计算带来的额外开销，可考虑采用 KD 树等数据结构，或使用聚类技术对相似个体进行分组。
还可以将距离计算与适应度共享过程并行化，从而利用多核处理器或分布式计算资源。

参数调节

可尝试不同的种群规模、交叉概率和变异概率，以寻求探索与开发之间的合理平衡。
可采用参数调优技术，例如网格搜索（grid search）或进化式参数优化，以自动寻找特定问题下更有效的参数配置。

监测与分析

可在进化过程中跟踪种群多样性指标（如平均成对距离、不同解的数量），以评估适应度共享的效果。
可对种群在搜索空间中的分布进行可视化，从而更直观地分析算法的探索与收敛行为。
可将适应度共享与其他多样性保持技术以及标准遗传算法进行性能对比，以评估其在具体问题中的实际作用。