带局部竞争的新颖性搜索（NSLC）

名称

带局部竞争的新颖性搜索（Novelty Search with Local Competition, NS-LC）

分类

查看分类思维导图

带局部竞争的新颖性搜索是在新颖性搜索算法基础上发展而来的一种扩展方法，它通过引入局部竞争机制，在进化算法中平衡探索与开发。该方法属于进化计算、随机优化和生物启发计算领域中的一种技术。:contentReference[oaicite:0]

• 计算智能
  • 生物启发计算
    • 进化计算
      • 进化算法
        • 遗传算法
          • 新颖性搜索
            • 带局部竞争的新颖性搜索

策略

带局部竞争的新颖性搜索建立在新颖性搜索的核心思想之上。新颖性搜索通过奖励表现出新颖行为的个体，而不是直接优化适应度函数，从而促进搜索过程对未知区域的探索。在新颖性搜索中，个体的新颖性由其行为与以往已出现行为档案之间的差异来决定，行为越新颖的个体，在繁殖过程中获得越高优先级。

NS-LC 在新颖性的基础上进一步引入了局部竞争的概念，同时考虑个体在其行为邻域中的新颖性与局部质量。个体的局部质量是由其相对于行为空间中邻近个体的性能表现来确定的。通过引入这一局部竞争机制，NS-LC 能够在探索行为空间中新区域与开发这些区域内的高质量解之间取得平衡。

该算法在整个进化过程中维护一个由新颖个体及其行为构成的档案。在每一代中，个体均根据其新颖性得分和局部质量得分进行评估。其中，新颖性得分通过测量个体与档案中最近邻个体之间的行为距离来计算，而局部质量得分则通过比较当前种群中个体与其最近邻个体之间的适应度来确定。

NS-LC 中的选择与繁殖基于新颖性得分和局部质量得分的组合，高得分个体更有可能被选为下一代的父代。这样的选择机制保证了种群既能够探索行为空间中的新区域，又能够在这些区域内部持续改进高质量解。

过程

数据结构

• 种群（Population）：由若干个体组成的集合，用于表示问题的潜在解。
• 档案集（Archive）：在进化过程中遇到的新颖个体及其行为构成的档案集合。
• 行为表征（Behavior Characterization）：一种将个体行为编码为紧凑表示的方法，例如实数向量。
• 行为距离度量（Behavioral Distance Metric）：用于度量两个行为表征之间差异程度的函数。

参数

• 种群规模（Population Size）：进化算法每一代中的个体数量。
• 新颖性阈值（Novelty Threshold）：个体被视为新颖并加入档案所需满足的最小行为距离阈值。
• 最近邻数量（Nearest Neighbors，$k$）：在计算新颖性得分和局部质量得分时所考虑的最近邻数量。
• 繁殖算子（Reproduction Operators）：用于生成新个体的遗传算子，例如变异和交叉。

伪代码

1. 随机初始化种群。
2. 初始化一个空档案。
3. 当终止条件尚未满足时：
   1. 对种群中的每个个体进行评估：
      1. 计算该个体的行为表征。
      2. 计算该个体的新颖性得分：
         1. 基于行为距离度量，在档案中寻找该个体的 $k$ 个最近邻。
         2. 计算该个体与这 $k$ 个最近邻之间的平均行为距离。
      3. 计算该个体的局部质量得分：
         1. 基于行为距离度量，在当前种群中寻找该个体的 $k$ 个最近邻。
         2. 计算该个体相对于这 $k$ 个最近邻的相对适应度。
   2. 更新档案：
      1. 对种群中的每个个体：
         1. 若该个体的新颖性得分超过新颖性阈值，则将其加入档案。
   3. 基于新颖性得分和局部质量得分的组合选择父代个体。
   4. 对选出的父代施加繁殖算子，生成下一代。
4. 返回在整个进化过程中找到的最优个体。

注意事项

优点

• 能够促进对新颖解的探索，避免搜索过程过早收敛到次优区域。
• 通过同时考虑新颖性与局部质量，在探索与开发之间实现平衡。
• 有助于在复杂搜索空间中发现兼具多样性与高质量的解。

缺点

• 需要定义合适的行为表征方式和距离度量，而这往往依赖具体问题，设计难度较高。
• 随着算法运行，档案规模可能不断扩大，从而增加新颖性得分计算的开销。
• 算法性能对参数选择较为敏感，例如新颖性阈值以及最近邻数量的设定都会显著影响结果。

启发式建议

行为表征

• 应选择能够刻画问题领域中个体关键行为特征的行为表征方式。
• 行为表征应尽量紧凑，并具有较高的计算效率。
• 可结合领域知识，或采用自动特征提取技术，构造信息量更丰富的行为表征。

距离度量

• 应选择能够准确衡量行为表征差异性的距离度量方式。
• 常见选择包括欧几里得距离、曼哈顿距离和余弦距离，具体应依据行为空间的性质而定。
• 可尝试多种距离度量，并分析其对算法性能的影响。

新颖性阈值

• 新颖性阈值的设定应兼顾探索能力与档案规模控制。
• 较高的新颖性阈值可能导致档案规模较小、探索不足；较低的阈值则可能增大档案规模，并带来更高的计算开销。
• 可根据进化过程的进展情况或问题特性，对新颖性阈值进行动态调整。

最近邻数量 ($k$)

• 应选择能够合理表征行为空间局部邻域结构的 $k$ 值。
• 较小的 $k$ 值可能导致新颖性和局部质量估计噪声较大；较大的 $k$ 值则可能弱化局部竞争的效果，使邻域刻画过于粗糙。
• 可通过实验比较不同 $k$ 值对算法性能的影响。

繁殖算子

• 应选择适合具体问题领域及个体表示方式的繁殖算子。
• 常见做法包括采用引入小幅扰动的变异算子，以及结合双亲遗传信息的交叉算子。
• 可根据需要对繁殖算子进行调整，以维持种群多样性，并促进产生新颖且高质量的后代。