约束新颖性搜索（CNS）

名称

约束新颖性搜索（Constrained Novelty Search, CNS）

分类

查看分类思维导图

约束新颖性搜索是一种属于进化计算领域的技术，更具体地说，属于多样性维持方法方向。它与新颖性搜索（Novelty Search）以及可行-不可行双种群（Feasible-Infeasible Two-Population, FI-2Pop）遗传算法密切相关。:contentReference[oaicite:0]

• 计算智能
  • 生物启发计算
    • 进化计算
      • 进化算法
        • 遗传算法
          • 多样性维持方法
            • 约束新颖性搜索

策略

约束新颖性搜索建立在新颖性搜索的基本思想之上。新颖性搜索通过奖励表现出新颖行为的解，而非针对某一特定目标进行优化，从而促进对搜索空间的探索。CNS 在此基础上进一步引入了必须满足的约束条件，同时仍然鼓励新颖性。

新颖性与可行性的平衡

CNS 维护两个相互独立的种群：可行种群和不可行种群。可行种群由满足全部约束的解构成，而不可行种群则包含至少违反一个约束的解。该算法促进两个种群同时演化，在探索新颖解与满足约束要求之间实现平衡。

新颖性的度量

新颖性通过将某个解的行为与其在行为空间中最近邻解的行为进行比较来度量。行为空间通常由一组行为表征函数定义，用以刻画解在性能上的相关特征。若某个解的行为与其邻域内其他解显著不同，则该解被认为具有较高的新颖性，并被赋予更高的新颖性得分。

约束处理

CNS 通过约束违反函数来处理约束，该函数用于量化某个解违反约束的程度。约束违反值较低的解优于约束违反值较高的解。不可行种群使算法能够探索搜索空间中那些虽尚未满足约束、但可能接近可行解的潜在有前景区域。

过程

数据结构

• 可行种群（FeasiblePopulation）：满足全部约束条件的解种群。
• 不可行种群（InfeasiblePopulation）：违反一个或多个约束条件的解种群。
• 行为空间（BehaviorSpace）：由行为表征函数定义的空间，用于刻画解性能的相关特征。
• 新颖性档案库（NoveltyArchive）：用于存储先前发现的新颖解的档案库。

参数

• 种群规模（PopulationSize）：可行种群与不可行种群的规模。
• 新颖性阈值（NoveltyThreshold）：判定某个解是否具有新颖性的阈值。
• 约束容忍度（ConstraintTolerance）：约束违反的容忍水平。
• 最大代数（MaxGenerations）：终止前允许的最大代数。

步骤

1. 随机初始化 FeasiblePopulation 和 InfeasiblePopulation。
2. 评估两个种群中每个解的约束违反情况及其行为特征。
3. 当终止条件尚未满足时，重复步骤 4-10。
4. 根据每个解在 BehaviorSpace 中的行为及其最近邻行为，计算两个种群中各解的新颖性得分。
5. 基于新颖性得分，从 FeasiblePopulation 中选择父代个体。
6. 对选出的父代施加遗传操作（如交叉与变异）以生成子代。
7. 评估子代的约束违反情况及其行为特征。
8. 将满足全部约束的子代加入 FeasiblePopulation，将违反任一约束的子代加入 InfeasiblePopulation。
9. 将来自两个种群中的新颖解更新到 NoveltyArchive 中。
10. 若 FeasiblePopulation 达到目标规模，则移除新颖性最低的解；若 InfeasiblePopulation 达到目标规模，则移除约束违反程度最高的解。
11. 返回 FeasiblePopulation 中找到的最优解。

注意事项

优点

• 通过鼓励新颖性促进搜索空间探索。
• 在约束优化问题中，有助于发现那些采用基于目标优化方法较难找到的解。
• 保持种群多样性，降低过早收敛的风险。

缺点

• CNS 的有效性在很大程度上依赖于行为表征函数的选择以及行为空间的定义。
• 新颖性度量未必总与解的质量一致，因此可能导致算法探索搜索空间中缺乏效率的区域。
• 计算新颖性得分以及维护新颖性档案库会带来较高的计算开销。

启发式建议

行为空间的定义

• 选择能够刻画问题领域相关特征及目标解特性的行为表征函数。
• 确保行为空间具有足够的表达能力，以区分不同解；但也不宜过于复杂，以免妨碍新颖行为的识别。

新颖性阈值的设定

• 在搜索初期可采用相对较高的新颖性阈值，以增强探索能力。
• 随着搜索推进，逐步降低新颖性阈值，从而将搜索重心转向对潜在优良解的细化。

新颖性档案库的管理

• 限制新颖性档案库的规模，以防其过度膨胀并拖慢搜索过程。
• 定期更新新颖性档案库，纳入新发现的新颖解，并移除过时或相关性较弱的解。

可行与不可行种群的平衡

• 在可行种群与不可行种群规模之间保持平衡，以确保新颖性探索与约束满足均得到足够关注。
• 可根据搜索进展及约束满足难度，动态调整两个种群的规模。

约束违反的处理

• 采用适当的约束处理技术，例如罚函数或修复机制，以引导搜索向可行区域推进。
• 根据问题特性以及对探索与开发权衡的需求，自适应调整约束容忍水平。