兼顾质量的新颖性搜索（NSQ）

名称

兼顾质量的新颖性搜索（Novelty Search with Quality, NS-Q）

分类

查看分类思维导图

兼顾质量的新颖性搜索是在新颖性搜索基础上发展而来的一种扩展算法，它通过引入质量度量，在随机优化过程中平衡探索与开发。该方法与新颖性搜索以及质量多样性算法密切相关。:contentReference[oaicite:0]

• 计算智能
  • 随机优化
    • 生物启发计算
      • 进化计算
        • 新颖性搜索
          • 兼顾质量的新颖性搜索

策略

兼顾质量的新颖性搜索将新颖性搜索的探索能力与质量度量相结合，以确保所发现的解不仅具有新颖性，同时也具备较高质量。该算法维护一个由先前发现的解构成的档案，用于计算新解的新颖性。新颖性度量鼓励算法探索搜索空间中尚未充分开发的区域，而质量度量则保证所找到的解具有实际应用价值。

算法首先随机初始化一个解种群，并评估各个解的新颖性与质量。在每一轮迭代中，根据新颖性得分和质量得分，从种群中选择一部分解。随后，利用变异和交叉等遗传算子，由这些被选中的解生成新的后代。接着对后代的新颖性与质量进行评估，并在满足特定条件时将其加入种群。

一个解的新颖性由其与档案中最近邻解之间的距离决定。与最近邻距离较远的解被视为更具新颖性。解的质量则通过面向具体问题的适应度函数来衡量，该函数用于评估解在给定问题上的性能表现。

该算法通过在搜索过程中动态调整新颖性与质量的相对重要性，来维持探索与开发之间的平衡。这通常通过一种动态加权机制实现，使其能够根据搜索进展自适应地改变权重分配。

过程

数据结构：

• 种群（Population）：候选解集合
• 档案集（Archive）：先前发现的解集合

参数：

• 种群规模（Population Size）：种群中候选解的数量
• 新颖性阈值（Novelty Threshold）：解被加入档案所需满足的最小新颖性阈值
• 质量阈值（Quality Threshold）：解被视为有效解所需满足的最小质量阈值
• 新颖性-质量平衡（Novelty-Quality Balance）：在选择过程中，新颖性与质量的相对重要性

1. 随机初始化种群
2. 评估种群中每个解的新颖性与质量
3. 将同时满足新颖性阈值和质量阈值的解加入档案
4. 当终止条件尚未满足时：
   1. 根据新颖性得分和质量得分，从种群中选择一部分解
   2. 对所选解施加遗传算子，生成后代
   3. 评估后代的新颖性与质量
   4. 将满足新颖性阈值和质量阈值的后代加入档案
   5. 用新生成的后代替换种群中新颖性较低或质量较低的解，从而更新种群
   6. 根据搜索进展调整新颖性与质量之间的平衡
5. 返回找到的最优解

注意事项

优点：

• 有助于发现兼具多样性与高质量的解
• 在搜索过程中兼顾探索与开发
• 可通过引入面向具体问题的质量度量，适应不同问题领域

缺点：

• 需要设计合适的新颖性度量，对于某些问题而言这一点可能较为困难
• 算法性能对参数选择较为敏感，例如新颖性阈值和质量阈值的设定
• 由于增加了新颖性计算的复杂性，相较于传统优化算法，可能需要更大的计算预算

启发式建议

参数选择：

• 种群规模应足够大，以维持种群多样性；但也不宜过大，以免拖慢搜索过程
• 新颖性阈值应设定得足够高，以促进探索；但也不宜过高，以免阻碍有效解的发现
• 质量阈值应根据具体问题所期望达到的性能水平进行设定
• 新颖性与质量之间的权衡应根据搜索进展动态调整，通常在搜索早期更强调新颖性，在后期更强调质量

新颖性度量：

• 新颖性度量应能够刻画问题领域中的关键特征
• 可考虑结合行为距离与基因型距离共同评估新颖性
• 应对新颖性得分进行归一化处理，以保证不同解之间比较的公平性

质量度量：

• 质量度量应能够有效表征解在给定问题上的性能
• 可考虑结合多个目标或约束共同定义质量
• 应确保质量度量的计算过程具有较高效率

遗传算子：

• 应采用能够引入足够变异的变异算子，以有效探索搜索空间
• 可考虑采用能够保留父代重要特征的交叉算子
• 可根据种群多样性和搜索进展，自适应调整变异率与交叉率

种群管理：

• 应在种群中保持高新颖性解与高质量解之间的合理平衡
• 可考虑引入多样性维持机制，例如拥挤机制或小生境机制，以防止过早收敛
• 应及时从种群中移除新颖性较低或质量较低的解，为新后代腾出空间